彈珠堆放

遞推式$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?P_{i,j}$
• 更新$m{x}_j$，$m{x}_j=max(m{x}_j,d{p}_i?k?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?\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)