前言：
本次比赛题目比较偏向思维，所用到的算法知识点不会太深。
接下来背下锅，很抱歉有人反映C题被卡常。因为std没有任何优化大概500+MS，内测时大家貌似也没有出现被卡常的现象，所以就觉得应该1s足够。没想到比赛期间因为测评机波动，加上可能确实有些算法常数过高，导致了卡常发生，真是抱歉QAQ。
A-神奇天平
考点：数学对于当前
①若
②若
重复以上过程，最终便可找到重的那件物品，不难发现这个过程本质上就是求
以上是正常的思考过程，实际上打个表找找规律应该就能通过此题(跑
时间复杂度：))
。
B-魔法学院(easy version)
考点：差分、贪心
对于某个字符
，我们可以用差分或者贪心的方法处理出他们在
上的覆盖区间。然后接着从
枚举到
，若下标
处的字符可以修改为，则令)
即可。枚举完
种字符后，再对字符串
统计价值和便可得到最终答案。
时间复杂度：)
。
C-魔法学院(hard version)
考点：并查集、双向链表
我们不妨从高价值字符枚举到低价值字符，那么对于高价值字符覆盖过的区间，低价值字符就没有必要去遍历了。因此遍历时，我们使用并查集或者双向链表对之前覆盖过的区间进行跳跃即可，具体可见代码。
时间复杂度：)
。
D-监狱逃亡
考点：树状数组、线段树
首先预处理出每行的前缀和数组，接着注意到行数只有三，于是我们用表示从第一行下到第二行的下标，用
表示从第二行下到第三行的下标，那么问题可以转化成，求满足)
的)
对数。
我们对上式移项，变为)
。显然可以类比逆序对，对其离散化后利用树状数组或者线段树进行求解。
时间复杂度：))
。
E-游戏人生
考点：二分、优先队列
显然玩家的初始生命值越多，通关的可能性就越大，因此我们对答案进行二分，那么题目转化成给定玩家初始生命值，判断玩家是否能通关。这个可以使用反悔贪心的方法来实现，具体如下：
①使用两个变量
与
记录到当前回合，使用了多少次普通攻击和狂暴攻击。
②使用一个大根堆保存到当前回合，反悔后玩家能回复的生命值。
③每个回合开始时，首先我们默认使用狂暴攻击，对boss造成
点伤害，玩家生命值减
，并令
。
④若玩家的生命值小于等于
了，我们进行反悔操作：
1. 如果和都为，表示已经无法通过反悔来回复生命值了，因此无法通关。
2. 如果为，不为，则只能通过将某次狂暴攻击反悔为普通攻击来回复生命值，因此玩家的生命值加，boss的生命值加
，并令
,
。
3. 如果不为，为，则只能通过将某次普通攻击反悔为防御来回复生命值，因此玩家的生命值加堆顶元素，boss的生命值加，弹出堆顶，并令
。
4. 如果和都不为，则判断与堆顶元素的大小，选择回血量更大的操作进行反悔。
⑤接着判断boss生命值是否小于等于，如果是表示能够通关。
⑥然后boss攻击，玩家生命值减少
，并将这次反悔后能回复的生命值压入堆。
⑦若玩家的生命值小于等于了，我们进行反悔，具体操作同④。
从内测来看，本题还有线段树的单log做法。
时间复杂度：%20%5Ctimes%20log(n)))
。
F-卡牌大师
考点：思维
设
的长度是
，考虑每个长度为的后缀到
，某个
想和某个
相加得到或者
，那一个只有一个对应的，所以每个关系，只取一边即可。具体的，
对应
，
对应
，中点讨论一下，然后算一下到分布在四个块里面的数量，每个互斥的块取其中之一。
时间复杂度：))
。
G-区间加
考点：线段树
不算难的数据结构题，主要难度可能在于编程。
考虑某一个普通的数生命历程的所有状态：原数→一直加
变成只有
个→再一直加直到和
合并→只有个。对于第二个过程，一个数只会最多加
次，对于第三个过程，每个数最多只会合并一次，第四个过程之后就相当于每次给这个数乘了。
因此，我们对每个数，如果
，那么我们另外开一棵线段树维护，在这棵线段树上,操作都相当于区间乘；否则我们把最高位和其它位分开，记为
和
。
对于加操作：等价于给区间的乘。
对于加操作：如果区间
存在
，我们暴力找到这个，给它加上，直到
；否则，操作等价于给区间的乘。
接下来只剩一个问题，就是要把
的数合并，并插入到的线段树中。对于这个问题，我们可以维护区间
的差的最小值
，每次加 ，相当于给区间的加，加相当于给区间的减。如果区间存在一个
，我们就暴力找到这个位置，把和合并，插入到另—棵线段树中，并把赋值为
。
每次询问就是把区间的, ,加起来。
考虑时间复杂度，对于加操作，每个数只会加次，每次需要)
访问到这个数，这部分总复杂度是)
；对于合并 和的操作，每个数只会合并一次，需要访问到这个数，这部分总复杂度是)
；其它部分总时间复杂度均为。因此这题时间复杂度是%20%5Ctimes%20log(V)))
。
考虑时间复杂度，对于加
时间复杂度：。
代码：
京公网安备 11010502036488号