第十四届蓝桥杯大赛软件赛国赛Python大学B组题解

弹珠堆放

递推式$a_i=a_{i-1}+i$，$n=20230610$非常小，直接模拟

答案等于$494$

划分

• 因为总和为$1e6$，因此可以dp，就是一个存在性01背包问题
• 答案为$12873625444$

偶串

• 直接一个桶记录就好
• 才发现，蓝桥杯oj使用exit(0)会段错误得使用sys.exit(0)

import sys
from collections import defaultdict
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())d=defaultdict(int)
s=input()
for c in s:d[c]+=1for x,y in d.items():if y%2==1:print('NO')sys.exit(0)print('YES')

交易账本

恶心的模拟题

import sys
from collections import defaultdict
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())def solve():n,m=read()acc=[[] for _ in range(m)]vis=[[] for _ in range(m)]ok=Truefor _ in range(m):s=list(read())idx=0x=s[idx]idx+=1all=0f=Falsewhile x:x-=1id,c=s[idx],s[idx+1]idx+=2if id==-1 and c==-1:f=Truecontinueif c>=len(acc[id]):ok=Falsecontinueif vis[id][c]:ok=Falsecontinuevis[id][c]=Trueall+=acc[id][c]x=s[idx]idx+=1while x:x-=1id,c=s[idx],s[idx+1]idx+=2all-=cacc[_].append(c)vis[_].append(False)if not f and all!=0:ok=Falseprint('YES' if ok else 'NO')
T=1
T=int(input())
for _ in range(T):solve()

背包问题

• 看数据应该是枚举其中一种cnt，vp过了赛后交一发t了，神奇的oj
• 首先枚举前面两个桶装A的数量，然后前两个桶贪心地装B
• 那么剩下一个桶呢？肯定是先贪心放体积更小的
• 复杂度$O(cn{t}^2)$

import sys
from collections import defaultdict
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())def solve():B=list(read())cnta,cntb=read()va,vb=read()ans=0for i in range(min(cnta,B[0]//va)+1):for j in range(min(cnta-i,B[1]//va)+1):ra=cnta-i-jA=[B[0]-i*va,B[1]-j*va,B[2]]res=i+jt=min(A[0]//vb+A[1]//vb,cntb)rb=cntb-tres+=tif va<vb:tmp=min(A[2]//va,ra)A[2]-=tmp*vares+=tmp+min(A[2]//vb,rb)else:tmp=min(A[2]//vb,rb)A[2]-=tmp*vbres+=tmp+min(A[2]//va,ra)ans=max(ans,res)print(ans)T=1+0
T=int(input())
for _ in range(T):solve()

翻转

• 很典的线性dp，$d{p}_{i,0/1}$表示当前是否翻转即可
• 复杂度$O(n)$

import sys
from collections import defaultdict
from math import inf
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())def solve():n=int(input())dp=[[inf]*2 for _ in range(n+1)]s=[0]*(n+1)for i in range(1,n+1):s[i]=input()dp[1][0]=dp[1][1]=2for i in range(2,n+1):for x in range(2):for y in range(2):dp[i][y]=min(dp[i][y],dp[i-1][x]+2-(s[i][y]==s[i-1][x^1]))print(min(dp[n][0],dp[n][1]))T=1
# T=int(input())
for _ in range(T):solve()

最大阶梯

• 全场第二恶心的题
• vp没想好居然旋转了45度再dp
• 实际上直接dp四次就行
• 复杂度$O(n^2)$

import sys
from collections import defaultdict
from math import inf
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())def solve():n=int(input())a=[[inf]*(n+2)]for _ in range(n):a.append([inf]+list(read())+[inf])a.append([inf]*(n+2))ans=0dp=[[0]*(n+10) for _ in range(n+10)]for i in range(1,n+1):for j in range(1,n+1):if a[i][j]==a[i-1][j]==a[i][j-1]:dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1else:dp[i][j]=1ans=max(ans,dp[i][j])dp=[[0]*(n+10) for _ in range(n+10)]for i in range(n,0,-1):for j in range(1,n+1):if a[i][j]==a[i+1][j]==a[i][j-1]:dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1else:dp[i][j]=1ans=max(ans,dp[i][j])dp=[[0]*(n+10) for _ in range(n+10)]for i in range(1,n+1):for j in range(n,0,-1):if a[i][j]==a[i-1][j]==a[i][j+1]:dp[i][j]=min(dp[i-1][j],dp[i][j+1])+1else:dp[i][j]=1ans=max(ans,dp[i][j])dp=[[0]*(n+10) for _ in range(n+10)]for i in range(n,0,-1):for j in range(n,0,-1):if a[i][j]==a[i+1][j]==a[i][j+1]:dp[i][j]=min(dp[i+1][j],dp[i][j+1])+1else:dp[i][j]=1ans=max(ans,dp[i][j])print(ans)T=1
# T=int(input())
for _ in range(T):solve()

最长回文前后缀

• 也是很典的manacher问题
• 注意：前缀和后缀其中一个可以为0(这点题没表述清wa了一个点)，其次数据太水，为什么$n^2$只是t一个点
• 首先最小答案为1
• 如果原本就是回文串，那么输出$2n$
• 如果前后缀都选的话，那么假设前缀为$A$，后缀为$B$，且$|A|\ge |B|$,那么$|A|=B_{rev}S$，因此最后的拼接字符串必定是$BS{B}_{rev}$这种形式
• 用manacher预处理出$L_i$表示以$i$为左端点的最长回文串，$R_i$表示以$i$为右端点的最长回文串
• 那么我们枚举前后缀的合法长度，假设$S[1:i]=S[n-i+1:n]$,然后我们看中间部分是属于前缀还是后缀即可
• 复杂度$O(n)$

import sys
from collections import defaultdict
from math import inf
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())def manacher(s):n=len(s)s='^#'+'#'.join(s)+'#$'id,mr=0,0p=[0]*(len(s))for i in range(1,2*n+1):if i<mr:p[i]=min(p[2*id-i],mr-i)else:p[i]=1while s[i+p[i]]==s[i-p[i]]:p[i]+=1if i+p[i]>mr:id=imr=i+p[i]return pdef solve():s=input()p=manacher(s)# print(p)n=len(s)L=[0]*(n+1)R=[0]*(n+1)for i in range(1,2*n+1):if p[i]<=1:continuer=(p[i]-1)//2if i%2==0:L[i//2-r]=max(L[i//2-r],p[i]-1)R[i//2+r]=max(R[i//2+r],p[i]-1)else:L[i//2-r+1]=max(L[i//2-r+1],p[i]-1)R[i//2+r]=max(R[i//2+r],p[i]-1)Len=0i,j=0,n-1ok=0while i<=j:if s[i]!=s[j]:Len=iok=1breaki+=1j-=1if not ok:print(2*n)returnif Len==0:print(1)return# for i in range(1,n):print(i,L[i],R[i])ans=0for l in range(1,Len+1):# print(l,2*l+L[l+1],2*l+R[n-l])ans=max(ans,l*2+L[l+1],l*2+R[n-l])print(ans)T=1
# T=int(input())
for _ in range(T):solve()

贸易航线

• 思维题
• 关键点：每次卖出肯定是只卖一种商品更优的
• 因此我们每次看卖哪种商品即可
• 定义$d{p}_i$为在第$i$个点，刚好卖出所有物品的最大收益
• 定义$m{x}_j$表示前面买入了$j$物品后的最大收益
• 那么转移很简单，如果不卖任何商品$d{p}_i=d{p}_{i-1}$
• 卖第$j$个物品，$d{p}_i=m{x}_j+k\cdot P_{i,j}$
• 更新$m{x}_j$，$m{x}_j=max(m{x}_j,d{p}_i-k\cdot P_{i,j})$

import sys
from collections import defaultdict
from math import inf
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())def solve():n,m,k=read()P=[[0]*(n+1)]dp=[-inf]*(n+1)dp[0]=0for i in range(n):P.append([0]+list(read()))mx=[-inf]*(m+1)ans=0for i in range(1,n+1):dp[i]=max(dp[i],dp[i-1])for j in range(1,m+1):if P[i][j]==-1:continuedp[i]=max(dp[i],mx[j]+P[i][j]*k)for j in range(1,m+1):if P[i][j]==-1:continuemx[j]=max(mx[j],dp[i]-P[i][j]*k)ans=max(ans,dp[i])print(ans)
T=1
# T=int(input())
for _ in range(T):solve()

困局

• 暴力，可以拿30%
• 打表发现k为奇数无解

import sys
from collections import defaultdict
from math import inf
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())MOD=998244353
n,k=read()
if k%2==1:print(0)sys.exit(0)
match=[0]*(n+1)
def check():x=0cnt=0vis=[0]*(n+1)while True:x+=1if x>n:breakif match[x] and not vis[x]:vis[x]=1x=match[x]cnt+=1return cnt==2*kans=[0]
def dfs(x,st):if x==k+1:if check():ans[0]+=1# print(match[1:])returnfor i in range(st+1,n+1):if match[i]:continuefor j in range(i+1,n+1):if match[j]:continuematch[i]=jmatch[j]=idfs(x+1,i)match[i]=0match[j]=0dfs(1,0)
print(ans[0]%MOD)

• 发现方案只与这$2k$个位置有关，因此我们先令$n=2k$计算出相对顺序的方案数$ans$
• vp的时候居然没想到如此简单的方法，但是官方正解好像不是这个。。
• 那么计算出相对顺序后，只需要在n个点选2k个即可，答案就是$ans\cdot \left(\genfrac{}{}{0ex}{}{n}{2k}\right)$

import sys
from collections import defaultdict
from math import inf
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())MOD=998244353
n,k=0,0
match=[]
def check():x=0cnt=0vis=[0]*(n+1)while True:x+=1if x>n:breakif match[x] and not vis[x]:vis[x]=1x=match[x]cnt+=1return cnt==2*kans=[0]
def dfs(x,st):if x==k+1:if check():ans[0]+=1# print(match[1:])returnfor i in range(st+1,n+1):if match[i]:continuefor j in range(i+1,n+1):if match[j]:continuematch[i]=jmatch[j]=idfs(x+1,i)match[i]=0match[j]=0
nn,kk=read()
if kk%2:print(0)sys.exit(0)k=kk
n=2*k
match=[0]*(n+1)
dfs(1,0)n=nn
fac=[1]*(n+1)
inv=[0]*(n+1)
for i in range(2,n+1):fac[i]=fac[i-1]*i%MODinv[n]=pow(fac[n],MOD-2,MOD)
for i in range(n-1,-1,-1):inv[i]=inv[i+1]*(i+1)%MODdef C(n,m):if n<m:return 0return fac[n]*inv[m]*inv[n-m]%MODprint(ans[0]*C(n,2*k)%MOD)