第一题0.9未通过所有用例：判断 ‘-1 0 1’，其中0可以表示任意数，能够构成等差为1的等差数列
import sys
while sys.stdin.readline().strip():
line = sys.stdin.readline().strip()
values = list(map(int,line.split()))
values.sort()
l,r = len(values),-1
for i in range(len(values)):
if values[i] == 0:
l = min(l,i)
r = max(r,i)
if r > -1:
res = r - l + 1
values = values[:l] + values[r+1:]
flag_print = 0
for i,v in enumerate(values):
if i == 0:
continue
if i > 0 and values[i-1] == values[i]:
flag_print = 1
print('Invalid')
break
if values[i] - values[i-1] == 1:
continue
res -= (values[i]-values[i-1] - 1)
if res < 0:
flag_print = 1
print ('Invalid')
break
if flag_print == 0:
print('Valid')
第二题0.6超时：给一个矩阵M*N，怎么样通过第一行到最后一行代价最小
import sys
line = sys.stdin.readline().strip()
values = list(map(int,line.split()))
M,N = values
a = []
for _ in range(M):
line = sys.stdin.readline().strip()
values = list(map(int, line.split()))
a.append(values)
# print(M)
# print(N)
# print(a)
dp = [[float('inf')] * N for _ in range(M)]
dp[-1] = a[-1]
for i in range(M-2,-1,-1):
for j in range(N):
dp[i][j] = min(dp[i][j],dp[i+1][j] + a[i][j])
tmp = a[i][j]
for k in range(j-1,-1,-1):
tmp += a[i][k]
dp[i][j] = min(dp[i][j],dp[i+1][k]+tmp)
tmp = a[i][j]
for k in range(j+1,N):
tmp += a[i][k]
dp[i][j] = min(dp[i][j],dp[i+1][k]+tmp)
print(min(dp[0]))
第三题0.3超时，且忘了取余：s='FRF'表示不等关系，N=len(s)，把{0,1,2,...,N}填入，有多少种情况
import sys def helper(pre, tmp, line): if not tmp: global res res += 1 return for i, t in enumerate(tmp): if line[0] == 'R': if pre < t: helper(t, tmp[:i] + tmp[i + 1:], line[1:]) else: continue if line[0] == 'F': if pre > t: helper(t, tmp[:i] + tmp[i + 1:], line[1:]) else: continue while True: line = sys.stdin.readline().strip() if not line: break l = len(line) tmp = list(range(0, l + 1)) res = 0 for i in range(len(tmp)): helper(tmp[i], tmp[:i] + tmp[i + 1:], line) print(res)
全部评论
(0) 回帖