上海网站公司哪家好,学网站开发需要会什么,上海网页制作步骤,公司网站制作哪家公司好[蓝桥复盘] 算法赛内测赛2 20230831 总结新一与基德的身高大战1. 题目描述2. 思路分析3. 代码实现 肖恩的投球游戏加强版1. 题目描述2. 思路分析3. 代码实现 体育健将1. 题目描述2. 思路分析3. 代码实现 小桥的奇异旋律1. 题目描述2. 思路分析3. 代码实现 区间or划分1. 题目描… [蓝桥复盘] 算法赛内测赛2 20230831 总结新一与基德的身高大战1. 题目描述2. 思路分析3. 代码实现 肖恩的投球游戏加强版1. 题目描述2. 思路分析3. 代码实现 体育健将1. 题目描述2. 思路分析3. 代码实现 小桥的奇异旋律1. 题目描述2. 思路分析3. 代码实现 区间or划分1. 题目描述2. 思路分析3. 代码实现 六、参考链接 总结
好难啊。T1 数学T2 二维差分模板T3 贪心树状数组上二分T4 差分模拟T5 贪心前后缀分解 新一与基德的身高大战
链接: 新一与基德的身高大战
1. 题目描述 2. 思路分析
奇数偶数会造成损失那么优先把奇数和奇数互相配对即可。
3. 代码实现 def solve():n, RI()a sorted(RILST(), keylambda x: x 1)b sorted(RILST(), keylambda 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, start1):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的时间能取多少场比赛。那么按ab排序然后在树状数组上二分即可对于每个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则返回hi1。虽然实现是开区间写法但为了思考简单接口以[左闭,右闭]方式放出。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), keylambda x: x[0] x[1])for i, (x, y) in enumerate(ab, start1):s.add_point(i, x y)for i, (x, y) in enumerate(ab, start1):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 %2z: # 需求正数if v 0:x 1 - vans xd xelse: # 需求负数if v 0:x v1ans xd - xreturn ansprint(min(get(1),get(0)))区间or划分
链接: 区间or划分
1. 题目描述 2. 思路分析
赛中看错题了以为是异或其实是或那就好想一点。由于a|bab那么最小的或和一定是整个数组或起来的值。那么每一位上的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)六、参考链接
无
