仅供复习使用

很多都是看能不能有思路，然后动态规划要重点学习理解，加强异或、字符串前后缀等知识点的学习。

一、思维题

第一题

找规律，但一定要注意验证，可以每次循环print弹珠数，层数少循环很快，还没想明白为什么会多一个（来不及思考了，但一定要记得验证！！！！多print多看！！！

n = 1
ans = 1
t = 3
k =3
while n < 20230610:
    n += t
    t += k
    k += 1
    ans += 1
##    print(n) 发现最后一行超过20230610了再手动减一
print(ans)

第五题

物品类型和背包数量少，可以枚举。通过交换确保A的体积小，用贪心思维确定A的分配，剩余空间尽可能多放B。

T = int(input())

def solve():
    B1,B2,B3 = map(int,input().split())
    cnta,cntb = map(int,input().split())
    va,vb = map(int,input().split())
    if va>vb:
        va,vb = vb,va
        cnta,cntb = cntb,cnta
    ans = 0
    for a1 in range(min(B1//va,cnta)+1):
        for a2 in range(min(B2//va,cnta-a1)+1):
            a3 = min(B3//va,cnta-a1-a2)
            b1 = min((B1-a1*va)//vb,cntb)
            b2 = min((B2-a2*va)//vb,cntb-b1)
            b3 = min((B3-a3*va)//vb,cntb-b1-b2)
            tot = a1+a2+a3+b1+b2+b3
            ans = max(ans,tot)
    return ans

for _ in range(T):
    print(solve())

二、动态规划类（01背包，二维dp选不选问题

第二题

题目：给定 4040 个数，请将其任意划分成两组，每组至少一个元素。每组的权值为组内所有元素的和。划分的权值为两组权值的乘积。请问对于以下 4040 个数，划分的权值最大为多少。

问题转化：想到正方形面积最大，所以两个组的和应尽可能相等。设总和为T，在不超过T/2的前提下，找最大的子集和。每个数选或不选问题，目标是在总容量为T/2的背包中，装入总和最大的数字 ----> 01背包

代码分析：

1、遍历范围

• i 的范围：0 到 40（0 表示一个数都不选）

• j 的范围：0 到 t（t = sum(nums)//2，是总容量的一半）

2、为什么 max(dp[40]) 就是我们想要的结果

因为 dp[40][j] 是关于 j 的 非递减函数（容量越大，能装下的最大和不会变小）。
所以当 j 从 0 增加到 bag 时，dp[40][j] 只会增加或不变，最大值一定在 j = bag 处取得。
因此：max(dp[40]) = dp[40][bag]

也可以写dp[40][t]，但这样更保险

a = [5160, 9191, 6410, 4657, 7492, 1531, 8854, 1253, 4520, 9231,
    1266, 4801, 3484, 4323, 5070, 1789, 2744, 5959, 9426, 4433,
    4404, 5291, 2470, 8533, 7608, 2935, 8922, 5273, 8364, 8819,
    7374, 8077, 5336, 8495, 5602, 6553, 3548, 5267, 9150, 3309]
##转化为总质量不超过一半总和的最大和
t = sum(a)//2
n = 40

#dp[i][j]表示考虑前i个数，在容量j内能得到的最大和
dp = [[0]*(t+1) for _ in range(n+1)] #注意行是n+1是数，列是容量
for i in range(1,n+1): #注意遍历范围是谁
    cur = a[i-1]
    for j in range(1,t+1):
        if j >= cur:
            dp[i][j] = max(dp[i-1][j-cur]+cur,dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
a1 = max(dp[40]) #dp[40][t]
a2 = sum(a)-a1
print(a1*a2)

第六题

题目分析：

• 每个工件的状态只有两种（翻转/不翻转），且当前拼接的节省只依赖于前一个工件的尾字符和当前工件的头字符是否相等。这满足最优子结构：前 i 个工件的最优方案，一定由前 i-1 个工件的最优方案加上第 i 个工件得到，且只需要知道前一个工件最终的头/尾字符（由是否翻转决定）

n = int(input())
s = []
for _ in range(n):
    s.append(input())

##dp[i][0]表示处理完前i-1个工件，当前工件不反转的最小长度
dp = [[0]*2 for _ in range(n)]
dp[0][0],dp[0][1] = 2,2#设定初始条件 第一个工件，无论是否翻转，长度都是2
##遍历i，j的所有可能取值
for i in range(1,n):# 从第二个工件开始遍历
    for j in range(2):# j=0表示当前工件不翻转，j=1表示翻转
        l0,l1 = 0,0
        if s[i-1][1] == s[i][j]: #注意是s[i][j],用j涵盖所有可能
            l0 = 1
        if s[i-1][0] == s[i][j]:
            l1 = 1
        dp[i][j] = min(dp[i-1][0]-l0,dp[i-1][1]-l1)+2
print(min(dp[n-1])) #遍历完所有工件找到其中最小的

第九题

因为每件商品利润独立，且体积相同，如果混合，总利润等于各部分利润之和，而每部分利润不会超过最优单件利润，所以全部买最优的那种商品即可。因此问题退化为背包容量为1的情形。找到一种最优的单件商品买卖策略（即只考虑一件商品的买进卖出，获得最大利润），那么因为容量为 k，你可以重复这个策略 k 次，总利润就是单件利润 × k。

n,m,k = map(int,input().split())
p = [0]*(n+1)
for i in range(1,n+1):
    p[i] = [0]+list(map(int,input().split()))

##dp[i][j]表示到第i个地点背包中装有第j种商品时的最大收益
dp = [[-10**18]*(m+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
    for j in range(0,m+1): #从0开始遍历，0表示没有买商品
        dp[i][j] = dp[i-1][j]
##    全部卖出时的最大收益
    for j in range(1,m+1):
        if p[i][j] != -1:
            dp[i][0] = max(dp[i][j]+p[i][j],dp[i][0])
    for j in range(1,m+1):
        if p[i][j] != -1:
            dp[i][j] = max(dp[i][0]-p[i][j],dp[i][j])
print(dp[n][0]*k)

三、异或

第三题

异或性质总结

• 异或自己的结果为0：a ^ a = 0；
• 异或0的结果还是自己本身：a ^ 0 = a；
• 异或-1的结果为自身的值按位取反值：a ^ -1 = ~a
• 两个数异或的结果去异或其中一个数，其结果一定是另一个数

s = input()
t = 0
for i in s:
    t ^= ord(i)
##    print(t)
if t != 0:
    print("NO")
else:
    print("YES")

四、回文串前后缀

第八题

先分别从前和从后看字符串的对称的部分，然后看中间部分的最长回文前缀是多少。

定义fun函数用于求最长回文前缀，即比较前半部分与后半部分的反序是否相同。

s = input()

##求一个字符串的最长回文前缀长度
def fun(s):
    for i in range(len(s),-1,-1):
        if s[0:i//2] == s[i-1:(i-1)//2:-1]:
            return i

ss = s[::-1]
i = 0
while i<len(s) and s[i]==ss[i]:
    i += 1
print(2*i+max(fun(s[i:]),fun(ss[i:])))