A 汉字田
简要题意:汉字"田"抽象成九个点,问一共有多少条直线恰好只经过这 99 个点中的任意两个点？
瞪眼法直接算就行了
B 床底取牌
简要题意: 六种字母各有五张,拼成"lanqiao"最少需要取多少张
只需考虑最差情况 l,n,q,i,o都拿齐了,依旧组不成,还需2张a,答案就是27
C 设置密码
简要题意: 按照要求判断是哪一种密码
需要注意的是密码可能包含要求之外的字符,要特判为0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
special="~!@#$%^&*()_"
T=int(input())
for _ in range(T):
s=input()
n=len(s)
f1,f2,f3,f4=0,0,0,0
f5=set()
flag=True
for ch in s:
if ch.isupper():
f1=1
elif ch.islower():
f2=1
elif ch.isdigit():
f3=1
elif ch in special:
f4=1
f5.add(ch)
else:
flag=False
break
if not flag:
print(0)
continue
if n>=12 and ((f1+f2+f3+f4==4)or(len(f5)>=3 and f1+f2+f3+f4==3)):
print(3)
elif n>=8 and(f1+f2+f3+f4>=2):
print(2)
elif n>=6:
print(1)
else:
print(0)
|
D 限流器
简要题意: 长度为N的区间最多让访问M次,求访问成功次数
用桶记录一下时间戳的次数,记录一下前缀和即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
n,m,l=map(int,input().split())
t=[0]*1005
a=list(map(int,input().split()))
for x in a:
t[x+1]+=1
for i in range(1,1002):
t[i]+=t[i-1]
r=n
ans=0
while r<=1001:
tmp=t[r]-t[r-n]
ans+=min(tmp,m)
r+=n
r-=n
if r!=1001:
ans+=min(t[1001]-t[r],m)
print(ans)
|
E 特别的数组
简要题意: 删除中间一段,剩下的要组成特别的数组且长度最长
经典的$O(n^2)$枚举无法通过,可以考虑枚举左,维护右,初始计算左边组成特别数组的$l$,和右边组成特别数组的$r$,在通过扩大$l$的同时维护$r$的位置,可以提前维护每个数最后出现的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
n=int(input())
a=list(map(int,input().split()))
l,r=0,0
mx=max(a)
dp=[0]*(mx+5)
st=set()
for i in range(n-1,-1,-1):
if a[i] in st:
r=i+1
break
st.add(a[i])
st.clear()
for i in range(n):
if a[i] in st:
l=i-1
break
st.add(a[i])
for i in range(n):
dp[a[i]]=i
ans=n-r
for i in range(min(l+1,r)):
r=max(r,dp[a[i]]+1)
ans=max(ans,i+1+n-r)
print(ans)
|
F记事本
牛客的一个原题,使用两个栈(对顶栈)模拟即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
t=int(input())
st1,st2=[],[]
for _ in range(t):
s=input()
if "insert" in s:
ts=s.split(' ',maxsplit=1)[1][1:-1]
for ch in ts:
st1.append(ch)
elif s[0]=='d':
x=int(s[1:-1])
if s[-1]=='h':
for i in range(min(len(st1),x)):
st1.pop()
else:
for i in range(min(len(st2),x)):
st2.pop()
else:
x=int(s[0:-1])
if s[-1]=='h':
while st1 and x:
tmp=st1.pop()
st2.append(tmp)
x-=1
else:
while st2 and x:
tmp=st2.pop()
st1.append(tmp)
x-=1
print(''.join(st1)+''.join(st2)[::-1])
|
G 羊圈
简要题意: 尽量用羊圈圈住羊,是最终跑走羊的数量的期望最少
使用状压dp,f(x,s) 表示从第x头羊开始考虑,羊圈二进制可选状态为s的最大值
最终答案是dp(1,(1«n)-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
n,m=map(int,input().split())
v=list(map(int,input().split()))
a=list(map(float,input().split()))
dp=[[-1]*(1<<n) for _ in range(m+2)]
def f(x,s):
if x==m+1:return 0
if dp[x][s]!=-1:return dp[x][s]
res=f(x+1,s)
for j in range(n):
if(s&(1<<j)):
ns=s^(1<<j)
nx=min(m+1,x+v[j])
res=max(res,f(nx,ns)+pre[nx-1]-pre[x-1])
dp[x][s]=res
return res
pre=[0]*(m+1)
for i in range(1,m+1):
pre[i]=pre[i-1]+a[i-1]
s=(1<<n)-1
print(f"{pre[m]-f(1,s):.2f}")
|
改成递推形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
n, m = map(int, input().split())
v = list(map(int, input().split()))
a =list(map (float, input().split()))
pre = [0.0] * (m + 1)
for i in range(1, m + 1):
pre[i] = pre[i - 1] + a[i - 1]
dp = [[-1.0] * ( 1<<n) for _ in range(m + 5)]
# 初始化
for s in range(1 << n):
dp[m + 1][s] = 0.0
for x in range(m, 0, -1):
for s in range(1 << n):
dp[x][s] = dp[x + 1][s]
for j in range(n):
if (s & (1 << j)):
ns = s ^ (1 << j)
nx = min(m + 1, x + v[j])
dp[x][s] = max(dp[x][s], dp[nx][ns] + (pre[nx - 1] - pre[x - 1]))
s = (1 << n) - 1
print("{:.2f}".format(pre[m] - dp[1][s]))
|
H 排练
待补,官网目前提交会内部错误
I 数字与留言
数位dp,待补,目前只写了个5%的暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
x,y=map(int,input().split())
mod=10**9+7
ans=0
def check(n):
sn=str(n)
if '2' in sn or '4' in sn:
return False
else:
return True
for i in range(1,x):
if not check(i):
continue
for j in range(i+1,x):
if not check(j):
continue
for k in range(j+1,x):
if not check(k):
continue
if (i+j+k)%2024==y:
ans=(ans+1)%mod
print(ans)
|
J 药剂
像是概率dp,待补,写了个30%的暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
import sys
from math import comb
def solve():
N, mo = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
if N == 1:
print(a[0] % mo)
return
total = 0
def dfs(current_a):
nonlocal total
if len(current_a) == 1:
total = (total + current_a[0]) % mo
return
for i in range(len(current_a)):
for j in range(i + 1, len(current_a)):
new_a = current_a.copy()
y = new_a.pop(j)
x = new_a.pop(i)
new_a1 = new_a.copy()
new_a1.append(x + y)
dfs(new_a1)
new_a2 = new_a.copy()
new_a2.append(x * y)
dfs(new_a2)
dfs(a)
print(total)
solve()
|
