总结

• 好难啊。
• T1 数学
• T2 二维差分模板
• T3 贪心+树状数组上二分
• T4 差分模拟
• T5 贪心+前后缀分解

新一与基德的身高大战

链接: 新一与基德的身高大战

1. 题目描述

2. 思路分析

• 奇数+偶数会造成损失，那么优先把奇数和奇数互相配对即可。

3. 代码实现

def solve():n, = RI()a = sorted(RILST(), key=lambda x: x & 1)b = sorted(RILST(), key=lambda x: x & 1)print(sum((x + y) // 2 for x, y in zip(a, b)))

肖恩的投球游戏加强版

链接: 肖恩的投球游戏加强版

1. 题目描述

2. 思路分析

• 直接贴模板，二维树状数组或者二维差分即可。

3. 代码实现

class BinTree2DIUPQ:"""二维树状数组"""def __init__(self, m, n):self.n = nself.m = mself.tree = [[0] * (n + 1) for _ in range(m + 1)]def lowbit(self, x):return x & (-x)def _update_point(self, x, y, val):m, n, tree = self.m, self.n, self.treewhile x <= m:y1 = ywhile y1 <= n:tree[x][y1] += valy1 += y1 & -y1x += x & -xdef _sum_prefix(self, x, y):res = 0tree = self.treewhile x > 0:y1 = ywhile y1 > 0:res += tree[x][y1]y1 &= y1 - 1x &= x - 1return resdef add_interval(self, x1, y1, x2, y2, v):self._update_point(x1, y1, v)self._update_point(x2 + 1, y1, -v)self._update_point(x1, y2 + 1, -v)self._update_point(x2 + 1, y2 + 1, v)def query_point(self, x, y):return self._sum_prefix(x, y)#       ms
def solve():n, m, q = RI()tree = BinTree2DIUPQ(n, m)for i in range(1, n + 1):row = RILST()for j, v in enumerate(row, start=1):tree.add_interval(i, j, i, j, v)for _ in range(q):x1, y1, x2, y2, c = RI()tree.add_interval(x1, y1, x2, y2, c)for i in range(1, n + 1):ans = []for j in range(1, m + 1):ans.append(tree.query_point(i, j))print(*ans)

体育健将

链接: 体育健将

1. 题目描述

2. 思路分析

• 首先想背包，发现值域1e8，放弃。那肯定是贪心了。
• 题目特殊点肯定是最后一个比赛可以无视休息，那么考虑枚举每一个比赛作为只取a的那场，看剩余k-ai的时间，能取多少场比赛。
• 那么按a+b排序，然后在树状数组上二分即可，对于每个i，看前缀<=k-ai能到哪。

3. 代码实现

def lower_bound(lo: int, hi: int, key):"""由于3.10才能用key参数，因此自己实现一个。:param lo: 二分的左边界(闭区间):param hi: 二分的右边界(闭区间):param key: key(mid)判断当前枚举的mid是否应该划分到右半部分。:return: 右半部分第一个位置。若不存在True则返回hi+1。虽然实现是开区间写法，但为了思考简单，接口以[左闭,右闭]方式放出。"""lo -= 1  # 开区间(lo,hi)hi += 1while lo + 1 < hi:  # 区间不为空mid = (lo + hi) >> 1  # py不担心溢出，实测py自己不会优化除2，手动写右移if key(mid):  # is_right则右边界向里移动，目标区间剩余(lo,mid)hi = midelse:  # is_left则左边界向里移动，剩余(mid,hi)lo = midreturn hiclass BinIndexTree:"""    PURQ的最经典树状数组，每个基础操作的复杂度都是logn；如果需要查询每个位置的元素，可以打开self.a    """def __init__(self, size_or_nums):  # 树状数组，下标需要从1开始# 如果size 是数字，那就设置size和空数据；如果size是数组，那就是aif isinstance(size_or_nums, int):self.size = size_or_numsself.c = [0 for _ in range(self.size + 5)]# self.a = [0 for _ in range(self.size + 5)]else:self.size = len(size_or_nums)# self.a = [0 for _ in range(self.size + 5)]self.c = [0 for _ in range(self.size + 5)]for i, v in enumerate(size_or_nums):self.add_point(i + 1, v)def add_point(self, i, v):  # 单点增加,下标从1开始# self.a[i] += vwhile i <= self.size:self.c[i] += vi += i & -idef sum_prefix(self, i):  # 前缀求和，下标从1开始s = 0while i >= 1:s += self.c[i]# i -= i&-ii &= i - 1return sdef lowbit(self, x):return x & -x#       ms
def solve():n, k = RI()a = RILST()b = RILST()ans = 0s = BinIndexTree(n)ab = sorted(zip(a, b), key=lambda x: x[0] + x[1])for i, (x, y) in enumerate(ab, start=1):s.add_point(i, x + y)for i, (x, y) in enumerate(ab, start=1):s.add_point(i, -(x + y))p = lower_bound(1, n, lambda y:s.sum_prefix(y) > k-x) - 1ans = max(ans, 1 + p - int(p >= i))s.add_point(i, x + y)print(ans)

小桥的奇异旋律

链接: 小桥的奇异旋律

1. 题目描述

2. 思路分析

• 由于是交替，可以考虑枚举正负正负…和负正负正…两种情况。
• 由于求的是前缀和，但修改的是原数组，因此考虑枚举前缀和，从前向后处理，做差分即可。
• 对于每个位置，如果它正负性不满足，则调整到1或-1。

3. 代码实现

def solve():n, = RI()a = RILST()p = list(accumulate(a))ans = 0def get(z):d =ans= 0for i,v in enumerate(p):v += dif i %2==z:  # 需求正数if v <= 0:x = 1 - vans += xd += xelse:  # 需求负数if v >= 0:x = v+1ans += xd -= xreturn ansprint(min(get(1),get(0)))

区间or划分

链接: 区间or划分

1. 题目描述

2. 思路分析

赛中看错题了，以为是异或，其实是或，那就好想一点。

• 由于a|b<a+b，那么最小的或和，一定是整个数组或起来的值。
• 那么每一位上的1一定要在同一组，否则会进位。
• 考虑能分多少组：发现两组的分界点一定等价于前缀或&后缀或==0。

3. 代码实现

def solve():n, = RI()a = RILST()m = reduce(ior,a)p = [0]+list(accumulate(a,ior))s = 0ans =  0for i in range(n-1,-1,-1):s |= a[i]if s & p[i] == 0:ans += 1print(m,ans)

六、参考链接

• 无