Educational Codeforces Round 75 题解
Broken Keyboard如果某一段相同的字符长度为奇数，那么这个字符一定是正常的。代码Binary Palindromes一个长度为偶数的回文串一定有偶数个 $1$，一个长度为奇数的回文串可以有任意个 $1$。检查 $1$ 的奇偶性，如果为偶数则答案为 $n$；否则，如果有长度为奇数的回文串则答案为 $n$，否则答案为 $n-1$。代码Minimize The Integer注意到奇偶...
标签 堆 下的文章
- 首页
- 堆
CF1249D Too Many Segments
CodeforcesLuogu分析我们从左往右扫，并保证扫过的位置不是 bad point。假设当前点是一个被覆盖了 $k+\Delta$ 次的 bad point，那么我们一定会删掉覆盖了它的 $\Delta$ 条线段。那么删哪 $\Delta$ 条线段最优呢？贪心地考虑，我们会删掉右端点最靠右的 $\Delta$ 条（因为左边都已经不是 bad point 了，而右端点越靠右显然会越优）...
洛谷3620 [APIO/CTSC2007]数据备份
Luogu分析一个显然的想法是我们每次选能选的最短的一根。但是这样会有一些问题，就是选了最短的之后两边的就不能选了，然后答案会偏大。这个其实比较好解决。假设当前最短的长度为 $l_u$，左右两边的长度分别为 $l_L$ 和 $l_R$，那么我们在选 $u$ 之后加一个长度为 $l_L+l_R-l_u$ 的候选项，表示删掉 $u$ 而选左右两个。这样子就是对的了。用堆维护以上过程，双向链表维...
CF720A Closing ceremony
CodeforcesLuogu分析好像以前看到过...于是切了考虑先给从 $(0,0)$ 进来的人安排座位。贪心地想，我们会把每个人安排到能坐的离 $(0,m+1)$ 最远的位置。那么用堆维护一下能坐的位置就好了。然后会剩下一些没有人坐的座位，这些座位应该分给从 $(0,m+1)$ 进来的人，而且耐力大的人的座位离 $(0,m+1)$ 会远。不可行的话就很容易判断了，如果一个人没有座位或者座...
CF332C Students' Revenge
CodeforcesLuogu分析贪心地想可以知道，主席一定优先做 $b$ 最大的，如果 $b$ 相同会做 $a$ 最小的。那么我们把所有任务排序，使得优先级越高的越靠后。现在假设我们选了 $p$ 个任务出来，那么一定存在一条分界线，使得线前的主席都不做，线后的主席都做。于是我们可以枚举分界线的位置，然后选出线前 $b$ 最大的 $p-k$ 个和线后 $a$ 最大的 $k$ 个，这就是这条线...
洛谷2056 [ZJOI2007]捉迷藏
Luogu分析首先吐槽一句...当初写《幻想乡战略游戏》的时候抄了个错的 ST 表求 LCA 的板子，那题竟然还过了...然后我蒯过来出现各种问题，害我调了好久 QAQ看到这个毒瘤的时限以及修改操作可以想到动态点分治。对于每个节点 $u$ 维护两个堆：一个堆维护点分子树中所有关灯的点到 $u$ 在点分树上父亲的距离，一个维护所有儿子的前一个堆的堆顶。这样子就很好计算每个点的答案了。再维护一个...
Codeforces Global Round 2 题解
orz GM Itst比赛地址Ilya and a Colorful Walk显然最优解要么是从 $1$ 走到某个地方，要么是从 $n$ 走到某个地方。直接 $O(n)$ 扫一遍即可。代码Alyona and a Narrow Fridge枚举答案 $x$ ，然后判断。判断的话，把前 $x$ 个瓶子按高度从大到小排序，然后每两个分成一组，再判断是否超出限制即可。代码Ramesses and ...
AGC010E Rearranging
AtCoderLuogu分析好神啊...先考虑如果先手已经给出了序列，后手怎么做才能让字典序最大。容易发现，两个不互质的数的相对位置一定不会改变。对于每个数，向后面的与它不互质的数连边，然后在做一遍字典序最大的拓扑排序即可。考虑先手怎么做。我们把不互质的数间连双向边，那么先手的任务就相当于给每条边定向。手玩一下发现，先手从每个连通块中最小的点出发给所有边定向即可。正确性证明不会，感性理解一下...
洛谷5283 [十二省联考2019]异或粽子
LuoguBZOJLOJ分析我们先来看一道比这题难的题目：NOI2010 超级钢琴。如果不会做这题，下面是题解链接：然后发现这题跟超级钢琴相比，就只是限定 $L=1,R=n$ ，然后把和换成了异或和。那么相应的把主席树换成可持久化 Trie 树就行了，其它地方不怎么需要改。具体实现及细节见代码。顺手跑进 BZOJ 第一版代码// ===============================...
洛谷2048 [NOI2010]超级钢琴
LuoguBZOJ分析堆+主席树。考虑对于每个左端点 $l$ ，先找到一个 $r$ 使得 $\sum\limits_{i=l}^ra[i]$ 最大。设 $s[i]=\sum\limits_{j=1}^i a[i]$ ，也就是说要找到一个 $r$ 使得 $sum[r]-sum[l-1]$ 最大。显然只要在 $r$ 的范围内找区间最大值就行了，因为 $sum[l-1]$ 是定值。这样子就找到了一...