点击“原题链接”可看到历年真题。
A 卡片
a=[int(input())]*10
cnt=1
try:
while 1:
for i in str(cnt):
i=int(i)
if a[i]==0:
raise go_out()
a[i]-=1
cnt+=1
except:
print(cnt-1)
答案:3181
B 直线
数据小,纯暴力。
from fractions import*
x,y=map(int,input().split())
lines=set()
for x1 in range(x):
for y1 in range(y):
for x2 in range(x):
for y2 in range(y):
if x1-x2:
k=Fraction(y1-y2,x1-x2)
b=k*x1-y1
lines.add((k,b))
elif y1-y2:
k=float('inf')
b=x1
lines.add((k,b))
print(len(lines))
答案:40257
C 货物摆放
这题数据已经达到了16位,纯暴力肯定是跑不出来的。
可以先找出所有因数,然后在这些因数里找出符合条件的排列。
from math import*
n=int(input())
ans=0
x=2
r=set([1,n])
for i in range(2,int(sqrt(n))+1):
if n%i==0:
r.add(i)
r.add(n//i)
r=sorted(r)
for i in r:
for j in r:
if j>n//i:
break
for k in r:
if k>n//(i*j):
break
if i*j*k==n:
ans+=1
print(ans)
稍微等几秒就可以得到答案。
答案:2430
D 路径
无向图最短路径。
跑一遍Dijkstra即可。
from math import lcm
n=int(input())
g=[[float('inf')for _ in range(n+1)]for _ in range(n+1)]
st=[False]*(n+1)
dist=[float('inf')]*(n+1)
for a in range(1,n):
for b in range(a+1,a+22):
if b>n:break
c=lcm(a,b)
g[a][b]=g[b][a]=min(g[a][b],c)
dist[1]=0
for _ in range(n):
t=-1
for i in range(1,n+1):
if not st[i] and (t==-1 or dist[t]>dist[i]):
t=i
for i in range(1,n+1):
dist[i]=min(dist[i],dist[t]+g[t][i])
st[t]=True
print(dist[n])
答案:10266837
E 回路计数
状压DP
from math import *
n=int(input())
t=1<<n
dp=[[0 for _ in range(n+1)]for _ in range(t+1)]
g=[[0 for _ in range(n+1)]for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,n+1):
if gcd(i,j)==1:
g[i-1][j-1]=g[j-1][i-1]=1
dp[1][0]=1
for i in range(1,t):
for j in range(n):
if i>>j&1==0:
continue
for k in range(n):
if g[j][k]==0 or i>>k&1:
continue
dp[i+(1<<k)][k]+=dp[i][j]
print(sum([dp[t-1][i]for i in range(n)]))
要跑个一两分钟吧…
答案:881012367360