感觉难度还是有点高，先写了部分简单的，如有不对还请大佬指点指点
测试地址：蓝桥杯ACM训练系统-C语言网
不知道什么原因，有些题python过不了，用cursor转成c++却可以过…

第十四届蓝桥杯 python c组

• A: 求和 （填空）
• B: 分糖果 （填空）
• C:三国游戏
• D: 平均
• E: 填充
• F: 棋盘
• G: 翻转
• H: 异或和之差

A: 求和 （填空）

题意概括：
求 1 （含）至 20230408 （含）中每个数的和。

思路：
没啥好说的，送分题直接暴力

print(sum(range(20230409))) # 204634714038436

B: 分糖果 （填空）

题意概括：
两种糖果分别有 9 个和 16 个，要全部分给 7 个小朋友，每个小朋友得到的糖果总数最少为 2 个最多为 5 个，问有多少种不同的分法。
只要有其中一个小朋友在两种方案中分到的糖果不完全相同，这两种方案就算作不同的方案。

思路：
dfs暴搜每个孩子拿到每种组合的糖果的方案数

res = 0# 第i个孩子，第一种糖果和第二种糖果剩余的数量def dfs(i, t1, t2):global resif i == 6: # 最后一个孩子if 2 <= t1 + t2 <= 5: # 剩余的糖果res += 1# print(res)return# 分两个for j in range(3):if t1 - j >= 0 and t2 - 2 + j >= 0:dfs(i + 1, t1 - j, t2 - 2 + j)# 分三个for j in range(4):if t1 - j >= 0 and t2 - 3 + j >= 0:dfs(i + 1, t1 - j, t2 - 3 + j)# 分四个for j in range(5):if t1 - j >= 0 and t2 - 4 + j >= 0:dfs(i + 1, t1 - j, t2 - 4 + j)# 分五个for j in range(6):if t1 - j >= 0 and t2 - 5 + j >= 0:dfs(i + 1, t1 - j, t2 - 5 + j)dfs(0, 9, 16)print(res)# 5067671

C:三国游戏

题目：
小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵X; Y; Z (一开始可以认为都为 0 )。游戏有 n 个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i 个事件发生时会分别让 X; Y; Z 增加Ai; Bi; Ci 。
当游戏结束时 (所有事件的发生与否已经确定)，如果 X; Y; Z 的其中一个大于另外两个之和，我们认为其获胜。例如，当 X > Y + Z 时，我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?
如果不存在任何能让某国获胜的情况，请输出 −1。

思路
贪心，分别考虑三个国家获胜的情况，因为每个事件相互独立，那么不管发生顺序，先按照该次事件该国增加士兵减去其余两个国家增加士兵的数量倒序排序三元组，然后依次累加士兵数量，直到当前该国士兵小于等于其他两国之和。

n = int(input())A = list(map(int, input().split()))B = list(map(int, input().split()))C = list(map(int, input().split()))AL = list(zip(A, B, C))def get_ans(i):AL.sort(key=lambda f: 2*f[i]-sum(f), reverse=True)res = -1cur = [0, 0, 0]for k, (a, b, c) in enumerate(AL, 1):cur[0] += acur[1] += bcur[2] += cif cur[i] <= sum(cur) - cur[i]:return resres = kreturn resres = max(get_ans(0), get_ans(1), get_ans(2))print(res)

D: 平均

题目：
有一个长度为 n 的数组（n 是 10 的倍数），每个数 ai 都是区间 [0; 9] 中的整数。小明发现数组里每种数出现的次数不太平均，而更改第 i 个数的代价为bi，他想更改若干个数的值使得这 10 种数出现的次数相等（都等于 10 n ），请问代价和最少为多少。

思路：
贪心+哈希表，因为每个数字出现的次数是确定好的，只需要统计大于应该出现次数的数字，对于每个大于应该出现次数的数字，取代价最小的几个转换。

from collections import defaultdictn = int(input())mp = defaultdict(list)for _ in range(n):a, b = list(map(int, input().split()))mp[a].append(b)x = n // 10# 每个数字应该出现多少次res = 0for k, v in mp.items():if len(v) <= x: continue# 出现次数小于等于应该出现的次数,不用转换v.sort()# 换代价最小的res += sum(v[:len(v) - x])print(res)

E: 填充

题目：
有一个长度为 n 的 01 串，其中有一些位置标记为 ?，这些位置上可以任意填充 0 或者 1，请问如何填充这些位置使得这个 01 串中出现互不重叠的 00 和11 子串最多，输出子串个数。

思路：
动态规划

dp数组定义：
$dp[i][0]$ 表示以 $i$ 作为对子后面一个数时的最大对数
$dp[i][1]$ 表示不以 $i$ 作为对子后面一个数时的最大对数

状态转移：
以 $i$ 作为对子后面一个数，则前一个数作为对子第一个数，那么当前位置从 $i-2$ 的两个状态和 $i-1$ 作为对子的第一个数的状态转移过来，取两者最大值，前提是当前位置能和上一个位置构成对子

$dp[i][0]=max(dp[i-2][0],dp[i-2][1],dp[i-1][1])+1$

不以 $i$ 作为对子后面一个数，直接从 $i-1$ 的两种状态转移过来：

$dp[i][1]=max(dp[i-1][0],dp[i-1][1])$

code:

s = input()n = len(s)f = [[0, 0] for _ in range(n)]f[1][0] = 1 if s[0] == '?' or s[1] == '?' or s[0] == s[1] else 0 # 初始化，判断前两个数是否能构成对子for i in range(2, n):if s[i] == s[i - 1] or s[i] == '?' or s[i - 1] == '?':f[i][0] = max(f[i - 2][0], f[i - 2][1], f[i - 1][1]) + 1f[i][1] = max(f[i - 1][0], f[i - 1][1])print(max(f[-1]))

F: 棋盘

题目：
小蓝拥有 n × n 大小的棋盘，一开始棋盘上全都是白子。小蓝进行了 m 次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反 (也就是白色棋子变为黑色，黑色棋子变为白色)。请输出所有操作做完后棋盘上每个棋子的颜色。

思路：
二维差分数组模板题，直接套，输出的时候判断奇偶性，如果翻转了奇数次则是黑棋否则是白棋。

n, m = list(map(int, input().split()))D = [[0] * (n + 2) for _ in range(n + 2)]# 差分数组 for _ in range(m):x1, y1, x2, y2 = list(map(int, input().split()))D[x1][y1] += 1D[x2+1][y1] -= 1D[x1][y2+1] -= 1D[x2+1][y2+1] += 1for i in range(1, n+1):for j in range(1, n+1):D[i][j] += D[i-1][j] + D[i][j-1] - D[i-1][j-1]print(D[i][j] % 2, end='')print()

G: 翻转

题目：
小蓝用黑白棋的 n 个棋子排成了一行，他在脑海里想象出了一个长度为 n 的 01 串 T，他发现如果把黑棋当做 1，白棋当做 0，这一行棋子也是一个长度为 n 的 01 串 S。
小蓝决定，如果在 S 中发现一个棋子和它两边的棋子都不一样，就可以将其翻转变成另一个颜色。也就是说，如果 S 中存在子串 101 或者 010，就可以选择将其分别变为 111 和 000，这样的操作可以无限重复。
小蓝想知道最少翻转多少次可以把 S 变成和 T 一模一样。

思路：
直接模拟，首先考虑首尾是否存在不相同的，不同则直接输出负一，然后按照题意判断中间的每个字符串即可。

注：
目前我用python在c语言网上提交过不了，相同的逻辑用c++可以一把过。

code：

n = int(input())for _ in range(n):t, s = list(input()), list(input())if s[0] != t[0] or s[-1] != t[-1]:print(-1)continuecnt = 0flag = Falsefor i in range(1, len(s) - 1):if s[i] == t[i]:continueif s[i] != s[i + 1] and s[i] != s[i - 1]:cnt += 1s[i] = t[i]else:flag = Truebreakif flag:print(-1)else:print(cnt)

H: 异或和之差

题目：
给定一个含有 n 个元素的数组 Ai，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。
2 ≤ n ≤ 2 × 1 05, 0 ≤ Ai≤ 220 2 \le n \le 2 \times 10^5,0 \le A_i \le 2^{20}2≤n≤2×105,0≤Ai​≤220

思路：
对于每个位置 $i$ 记录 $[0,i]$ 的最大和最小异或值以及 $[i,n-1]$ 的最大和最小异或值，直接使用递推处理的化复杂度接近 O ( n2)O(n^2)O(n2)，妥妥超时。
这里用到 01Tire 实现 前缀树 来优化时间复杂度，可以将复杂度降到 $O(n\log A)$ 不会超时。
记录下左右两边的最值之后只需要一次遍历选出左边最大值减右边最小值和右边最大值减左边最小值两者最大的那个即可。

注：
这题目前也是python过不了 c++能过

code:

from math import infclass Tire:def __init__(self):self.next = [None, None]def insert(self, x):"""插入前缀和nums[0..i] = x"""t = self# x <= 2^20, 存21位即可for i in range(21, -1, -1):c = ((x >> i) & 1)if not t.next[c]:t.next[c] = Tire()t = t.next[c]def get_max(self, x):"""获取所有前缀中与x异最大的结果"""res = 0t = selffor i in range(21, -1, -1):c = ((x >> i) & 1)h = c ^ 1# 为了异或最大，优先取相反的p = h if t.next[h] else h ^ 1# 存在则走，否则取反res |= (c ^ p) << it = t.next[p]return resdef get_min(self, x):"""获取所有前缀中与x异最小的结果"""res = 0t = selffor i in range(21, -1, -1):c = ((x >> i) & 1)# 为了异或最小，优先取相同的p = c if t.next[c] else c ^ 1# 存在则走，否则取反res |= (c ^ p) << it = t.next[p]return resdef init_min_max():# 初始化前缀xor_min, xor_max = inf, -infxor_cur = 0tire = Tire()tire.insert(0)for i in range(n):xor_cur ^= nums[i]xor_max = max(xor_max, tire.get_max(xor_cur))xor_min = min(xor_min, tire.get_min(xor_cur))left_max[i] = xor_maxleft_min[i] = xor_mintire.insert(xor_cur)# 将 nums[0..i] 的前缀和添加到前缀树# 初始化后缀xor_min, xor_max = inf, -infxor_cur = 0tire = Tire()tire.insert(0)for i in range(n - 1, -1, -1):xor_cur ^= nums[i]xor_max = max(xor_max, tire.get_max(xor_cur))xor_min = min(xor_min, tire.get_min(xor_cur))right_max[i] = xor_maxright_min[i] = xor_mintire.insert(xor_cur)# 将 nums[i..n-1] 的后缀缀和添加到前缀树def solve():res = 0for i in range(n - 1):res = max(res,abs(left_max[i] - right_min[i + 1]),abs(right_max[i + 1] - left_min[i]),)print(res)if __name__ == '__main__':n = int(input())nums = list(map(int, input().split()))left_max, left_min = [0] * n, [0] * nright_max, right_min = [0] * n, [0] * ninit_min_max()solve()