泗县网站建设,郴州信息港最新招聘信息,wordpress分类列表插件,推广普通话心得体会文章目录 弹珠堆放划分偶串交易账本背包问题翻转最大阶梯最长回文前后缀贸易航线困局 弹珠堆放 递推式 a i a i − 1 i a_ia_{i-1}i aiai−1i#xff0c; n 20230610 n20230610 n20230610非常小#xff0c;直接模拟
答案等于 494 494 494
划分 因为总和为 1 e 6 1e6… 文章目录 弹珠堆放划分偶串交易账本背包问题翻转最大阶梯最长回文前后缀贸易航线困局 弹珠堆放 递推式 a i a i − 1 i a_ia_{i-1}i aiai−1i n 20230610 n20230610 n20230610非常小直接模拟
答案等于 494 494 494
划分 因为总和为 1 e 6 1e6 1e6因此可以dp就是一个存在性01背包问题答案为 12873625444 12873625444 12873625444
偶串 直接一个桶记录就好才发现蓝桥杯oj使用exit(0)会段错误得使用sys.exit(0)
import sys
from collections import defaultdict
inputlambda:sys.stdin.readline().strip()
readlambda:map(int,input().split())ddefaultdict(int)
sinput()
for c in s:d[c]1for x,y in d.items():if y%21:print(NO)sys.exit(0)print(YES)交易账本 恶心的模拟题
import sys
from collections import defaultdict
inputlambda:sys.stdin.readline().strip()
readlambda:map(int,input().split())def solve():n,mread()acc[[] for _ in range(m)]vis[[] for _ in range(m)]okTruefor _ in range(m):slist(read())idx0xs[idx]idx1all0fFalsewhile x:x-1id,cs[idx],s[idx1]idx2if id-1 and c-1:fTruecontinueif clen(acc[id]):okFalsecontinueif vis[id][c]:okFalsecontinuevis[id][c]Trueallacc[id][c]xs[idx]idx1while x:x-1id,cs[idx],s[idx1]idx2all-cacc[_].append(c)vis[_].append(False)if not f and all!0:okFalseprint(YES if ok else NO)
T1
Tint(input())
for _ in range(T):solve()
背包问题 看数据应该是枚举其中一种cntvp过了赛后交一发t了神奇的oj首先枚举前面两个桶装A的数量然后前两个桶贪心地装B那么剩下一个桶呢肯定是先贪心放体积更小的复杂度 O ( c n t 2 ) O(cnt^2) O(cnt2)
import sys
from collections import defaultdict
inputlambda:sys.stdin.readline().strip()
readlambda:map(int,input().split())def solve():Blist(read())cnta,cntbread()va,vbread()ans0for i in range(min(cnta,B[0]//va)1):for j in range(min(cnta-i,B[1]//va)1):racnta-i-jA[B[0]-i*va,B[1]-j*va,B[2]]resijtmin(A[0]//vbA[1]//vb,cntb)rbcntb-trestif vavb:tmpmin(A[2]//va,ra)A[2]-tmp*varestmpmin(A[2]//vb,rb)else:tmpmin(A[2]//vb,rb)A[2]-tmp*vbrestmpmin(A[2]//va,ra)ansmax(ans,res)print(ans)T10
Tint(input())
for _ in range(T):solve()翻转 很典的线性dp d p i , 0 / 1 dp_{i,0/1} dpi,0/1表示当前是否翻转即可复杂度 O ( n ) O(n) O(n)
import sys
from collections import defaultdict
from math import inf
inputlambda:sys.stdin.readline().strip()
readlambda:map(int,input().split())def solve():nint(input())dp[[inf]*2 for _ in range(n1)]s[0]*(n1)for i in range(1,n1):s[i]input()dp[1][0]dp[1][1]2for i in range(2,n1):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]))T1
# Tint(input())
for _ in range(T):solve()
最大阶梯 全场第二恶心的题vp没想好居然旋转了45度再dp实际上直接dp四次就行复杂度 O ( n 2 ) O(n^2) O(n2)
import sys
from collections import defaultdict
from math import inf
inputlambda:sys.stdin.readline().strip()
readlambda:map(int,input().split())def solve():nint(input())a[[inf]*(n2)]for _ in range(n):a.append([inf]list(read())[inf])a.append([inf]*(n2))ans0dp[[0]*(n10) for _ in range(n10)]for i in range(1,n1):for j in range(1,n1):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]1ansmax(ans,dp[i][j])dp[[0]*(n10) for _ in range(n10)]for i in range(n,0,-1):for j in range(1,n1):if a[i][j]a[i1][j]a[i][j-1]:dp[i][j]min(dp[i1][j],dp[i][j-1])1else:dp[i][j]1ansmax(ans,dp[i][j])dp[[0]*(n10) for _ in range(n10)]for i in range(1,n1):for j in range(n,0,-1):if a[i][j]a[i-1][j]a[i][j1]:dp[i][j]min(dp[i-1][j],dp[i][j1])1else:dp[i][j]1ansmax(ans,dp[i][j])dp[[0]*(n10) for _ in range(n10)]for i in range(n,0,-1):for j in range(n,0,-1):if a[i][j]a[i1][j]a[i][j1]:dp[i][j]min(dp[i1][j],dp[i][j1])1else:dp[i][j]1ansmax(ans,dp[i][j])print(ans)T1
# Tint(input())
for _ in range(T):solve()
最长回文前后缀 也是很典的manacher问题注意前缀和后缀其中一个可以为0(这点题没表述清wa了一个点)其次数据太水为什么 n 2 n^2 n2只是t一个点首先最小答案为1如果原本就是回文串那么输出 2 n 2n 2n如果前后缀都选的话那么假设前缀为 A A A后缀为 B B B且 ∣ A ∣ ≥ ∣ B ∣ |A| \geq |B| ∣A∣≥∣B∣,那么 ∣ A ∣ B r e v S |A|B_{rev}S ∣A∣BrevS因此最后的拼接字符串必定是 B S B r e v BSB_{rev} BSBrev这种形式用manacher预处理出 L i L_i Li表示以 i i i为左端点的最长回文串 R i R_i Ri表示以 i i i为右端点的最长回文串那么我们枚举前后缀的合法长度假设 S [ 1 : i ] S [ n − i 1 : n ] S[1:i]S[n-i1:n] S[1:i]S[n−i1:n],然后我们看中间部分是属于前缀还是后缀即可复杂度 O ( n ) O(n) O(n)
import sys
from collections import defaultdict
from math import inf
inputlambda:sys.stdin.readline().strip()
readlambda:map(int,input().split())def manacher(s):nlen(s)s^##.join(s)#$id,mr0,0p[0]*(len(s))for i in range(1,2*n1):if imr:p[i]min(p[2*id-i],mr-i)else:p[i]1while s[ip[i]]s[i-p[i]]:p[i]1if ip[i]mr:idimrip[i]return pdef solve():sinput()pmanacher(s)# print(p)nlen(s)L[0]*(n1)R[0]*(n1)for i in range(1,2*n1):if p[i]1:continuer(p[i]-1)//2if i%20:L[i//2-r]max(L[i//2-r],p[i]-1)R[i//2r]max(R[i//2r],p[i]-1)else:L[i//2-r1]max(L[i//2-r1],p[i]-1)R[i//2r]max(R[i//2r],p[i]-1)Len0i,j0,n-1ok0while ij:if s[i]!s[j]:Leniok1breaki1j-1if not ok:print(2*n)returnif Len0:print(1)return# for i in range(1,n):print(i,L[i],R[i])ans0for l in range(1,Len1):# print(l,2*lL[l1],2*lR[n-l])ansmax(ans,l*2L[l1],l*2R[n-l])print(ans)T1
# Tint(input())
for _ in range(T):solve()贸易航线 思维题关键点每次卖出肯定是只卖一种商品更优的因此我们每次看卖哪种商品即可定义 d p i dp_i dpi为在第 i i i个点刚好卖出所有物品的最大收益定义 m x j mx_j mxj表示前面买入了 j j j物品后的最大收益那么转移很简单如果不卖任何商品 d p i d p i − 1 dp_idp_{i-1} dpidpi−1卖第 j j j个物品 d p i m x j k ⋅ P i , j dp_{i}mx_jk\cdot P_{i,j} dpimxjk⋅Pi,j更新 m x j mx_j mxj m x j m a x ( m x j , d p i − k ⋅ P i , j ) mx_jmax(mx_j,dp_i-k \cdot P_{i,j}) mxjmax(mxj,dpi−k⋅Pi,j)
import sys
from collections import defaultdict
from math import inf
inputlambda:sys.stdin.readline().strip()
readlambda:map(int,input().split())def solve():n,m,kread()P[[0]*(n1)]dp[-inf]*(n1)dp[0]0for i in range(n):P.append([0]list(read()))mx[-inf]*(m1)ans0for i in range(1,n1):dp[i]max(dp[i],dp[i-1])for j in range(1,m1):if P[i][j]-1:continuedp[i]max(dp[i],mx[j]P[i][j]*k)for j in range(1,m1):if P[i][j]-1:continuemx[j]max(mx[j],dp[i]-P[i][j]*k)ansmax(ans,dp[i])print(ans)
T1
# Tint(input())
for _ in range(T):solve()困局 暴力可以拿30%打表发现k为奇数无解
import sys
from collections import defaultdict
from math import inf
inputlambda:sys.stdin.readline().strip()
readlambda:map(int,input().split())MOD998244353
n,kread()
if k%21:print(0)sys.exit(0)
match[0]*(n1)
def check():x0cnt0vis[0]*(n1)while True:x1if xn:breakif match[x] and not vis[x]:vis[x]1xmatch[x]cnt1return cnt2*kans[0]
def dfs(x,st):if xk1:if check():ans[0]1# print(match[1:])returnfor i in range(st1,n1):if match[i]:continuefor j in range(i1,n1):if match[j]:continuematch[i]jmatch[j]idfs(x1,i)match[i]0match[j]0dfs(1,0)
print(ans[0]%MOD)发现方案只与这 2 k 2k 2k个位置有关因此我们先令 n 2 k n2k n2k计算出相对顺序的方案数 a n s ans ansvp的时候居然没想到如此简单的方法但是官方正解好像不是这个。。那么计算出相对顺序后只需要在n个点选2k个即可答案就是 a n s ⋅ ( n 2 k ) ans \cdot \binom{n}{2k} ans⋅(2kn)
import sys
from collections import defaultdict
from math import inf
inputlambda:sys.stdin.readline().strip()
readlambda:map(int,input().split())MOD998244353
n,k0,0
match[]
def check():x0cnt0vis[0]*(n1)while True:x1if xn:breakif match[x] and not vis[x]:vis[x]1xmatch[x]cnt1return cnt2*kans[0]
def dfs(x,st):if xk1:if check():ans[0]1# print(match[1:])returnfor i in range(st1,n1):if match[i]:continuefor j in range(i1,n1):if match[j]:continuematch[i]jmatch[j]idfs(x1,i)match[i]0match[j]0
nn,kkread()
if kk%2:print(0)sys.exit(0)kkk
n2*k
match[0]*(n1)
dfs(1,0)nnn
fac[1]*(n1)
inv[0]*(n1)
for i in range(2,n1):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[i1]*(i1)%MODdef C(n,m):if nm:return 0return fac[n]*inv[m]*inv[n-m]%MODprint(ans[0]*C(n,2*k)%MOD)
