2022/8/7 猿辅导笔试
1.给一个字母集合，接下来给若干个单词，求用这些集合里的字母能够组成的最大单词数量
from collections import Counter
m=int(input())
while m:
m-=1
s = input()
cnt = Counter(s)
n=int(input())
now=input().split()
ans=0
for t in now:
cur=Counter(t)
temp=float('inf')
for k in cur.keys():
temp=min(temp,cnt.get(k,0)//cur[k])
ans=max(ans,temp)
print(ans) 2.大模拟跳过，吐槽一下，题面太长了，加上选择总共才一个半小时，哪有那么多时间来做阅读理解啊....
3.首先输入数字序列长度n和可以使用的颜色数量k，接下来输入一个数字序列a，a[i]>0表示第i个位置是颜色为a[i]的左括号，a[i]=0表示这个位置你可以选择设为左括号也可以设为右括号，求最终所有合法的括号序列的数量
我的做法是先用记搜求出所有合法的括号序列数量x，再求出还可以涂色的括号对数量y=n/2-z（z=输入序列中大于0的元素个数），最后的答案就是x*(k^y)
python代码RE了，只过了50%，可能是递归太深了，但是也没时间改成c++了
UPD:经评论区一位大佬提醒可能是我记搜的时候没有取模导致可能算出来个天文数字导致内存超限（本地测了下n=5000的情况，果然还是递归层数太深）
from functools import lru_cache n,k=map(int,input().split()) s=list(map(int,input().split())) @lru_cache(None) def dfs(idx,cnt): if idx==n: if cnt==0: return 1 return 0 if s[idx]>0: return dfs(idx+1,cnt+1) else: ans=dfs(idx+1,cnt+1) if cnt>0: ans+=dfs(idx+1,cnt-1) return ans%10001 ans=dfs(0,0) cur=n//2 for v in s: if v>0: cur-=1 print(ans*pow(k,cur,10001)%10001)
查看10道真题和解析
