a2oj ladders 泛做

题解

某@EHK老司机向我安利了一下他前同事搞的一个工具，基本上就是每个分段抓取了100题（如果做完就能上分？

https://a2oj.com/ladders

这里主要是我觉得一些有价值的题目的题解

450E 很妙的一道构造。首先把不可能在答案中的数排除，即$1$和大于$\frac{n}{2}$的素数。然后对于每个大于$2$的素数$p$，我们考虑当前还没有用过的$p$的倍数,$p,2p,3p,4p,5p\cdots$,如果一共有偶数个，那么我们两两配对，否则把$2p$拿出来，然后再两两配对。可以发现，最后留下的数都是偶数，所以他们也可以两两配对。当最后剩下的偶数的个数是偶数的时候，显然所有数都被用上了，如果是奇数，说明原本有用的数就只有奇数个，而我们只浪费了一个数，所以也是最优的。

351E 很妙的一道题。贪心，对于每组绝对值不同的数对，是否是逆序对只由绝对值较大的那个数的符号决定。具体分析见 http://codeforces.com/blog/entry/9070?#comment-149927

463D 五维偏序，$O(n^2)$水过

343D 裸树剖染色。

246E dfs序+数颜色

338D 很强大的一道数论题，感谢vfk的题解。注意到如果存在解，那么$x$坐标为所有数的$lcm$, 而$y$坐标用$excrt$算一算就行了，最后check一波答案即可。确实是很好的一道题，让我重新学习了一下excrt233。

208E 大数据结构之术！树剖水过

469D 杜教的一道好题，注意如果$x$和$x-a(b)$都存在，那么他们肯定在一个集合，并查集维护即可

282D 暴力dp

600E dfs+启发式合并

446B 好题，注意任意一对行列之间的拿顺序不影响答案s，所以我们可以枚举拿的行数以及拿的列数，优先队列维护一下即可。

459E 边按照权值排序，dp

459C 很妙的一道题，虽然是2C，每个人的坐车安排我们都可以看成$k$进制下的一个长度为$n$数，那么显然只要两两数不同那么问题有解。显然可行安排一共有$k^d$种，判一判就好了。

280C 期望线性性，$ans = \sum_{i = 1}^{n} \frac {1}{depth[i]}$

734E 缩点，然后求直径即可

734F 学习到了一个很妙的性质$a \& b + a | b = a + b$,然后设$d_i = b_i + c_i$,接下来就是把弄一下和式，最后check一下答案是否合法即可

594D 离线BIT+筛法

455D 分块暴力（替罪羊写了一年，以后还是让萌萌哒zxy写吧= =

555C 对于横和竖分别维护一棵树表示对应坐标能延伸过去的最小值，可以选择动态线段树或者离散化（动态线段树需要卡卡空间

406D 倒着做一遍凸包找到每个点的父亲，然后跑lca就好了

433C 枚举被改的数，通过排序找到最优目标值

276D 显然我们要从高位到低位枚举每一位是不是能异或出1，假设当前这一位l和r不同那么我们不用动直接加到贡献里，如果l是0，r是0，那么我们看一下把l的这一位变成1，后面全都变成0会不会小于等于r（因为要尽可能使变化小），l和r都为1的时候同理搞一下r。（注意l和r都是1的时候是不能把l的那一位变成0的：因为使l变成0而且增大l的话，会使得高位的贡献被取消）

319B并查集维护每个数最右边第一个没有被删除的节点，运用类似于spfa优化bellman-ford的思想，维护一个queue，里面存的是有可能能删除下一个点的节点

286B 相当巧妙的一道题，注意到每一块相当于只有一个数在动，而且这个数移动到的位置可以发现是下一个动的数的位置。

369E 补集转化，离线BIT即可

375D 对询问离线，维护权值线段树以及用map维护出现次数即可。

451D 注意到任意一对相同字母之间的字符串都是“回文串”然后扫一遍就行了

359D 官方题解是二分长度，我的做法是枚举起点，因为每个起点只可能有$\log$种$\gcd$，再套个st表加点常数优化就可以低空飞过去了（可见我智商还是很低的（连二分答案都没想到

346D 岛娘出的题，注意到答案是不下降的，扫一遍即可。（证明大概是依赖每个模数把区间搞成了一堆长度为$x_i$的等价类

375B 维护一下每个点向右边最多有多少连续个1，枚举起点+排序即可

388B 我是用二进制分解做的，常数太大导致需要常数优化，某@萌萌哒zxy用了一种方法只需要94个点就可以AC了，%%%

492E 因为$\gcd(dx,n)$所以每个点都能走到x坐标是0的点，我们同时也可以得到$\forall C\not\equiv 0 \pmod{n} \ \ C*dx \not\equiv 0 \pmod{n}$，我们可以知道找的的坐标是唯一的，所以每个坐标找到对应x坐标为0的点就可以了。

242E 拆位搞32个线段树就行了。

438D 线段树维护$\max$暴力$mod$就行了，注意一个数最多只会有$\log$次有效$mod$运算，感谢某萌萌哒的zxy

301D 注意两两不同的条件，$O(n\log(n))$枚举倍数就行了，离线树状数组。

463E 我是枚举素数建虚树做的，事实上由于时限是10s所以直接暴力也能过。（窝跑的还没暴力快好心酸QAQ

498C 枚举素数跑二分图匹配（dinic居然15ms就飞过去了

383C dfs然后线段树就好了

145E 线段树维护区间最长不降和最长不增

486E 首先判一个数能不能再LIS里面，分辨2，3的话就看一下前面有没有比他大于等于的但是也可以在LIS里面的，或者是后面的比他小于等于的可以在LIS里面的数。如果有的话答案为2，否则为3。

650D 和上面差不多，离线两边跑一下就行了

425D 注意任意时刻都会有某条竖线或者横线上的点数是$O(\sqrt{n})$的。证明：不失一般性，假设不存在，我们取任意一条点数超过$O(\sqrt{n})$的横线，因为这条横线对应了超过$O(\sqrt{n})$条竖线，所以不可能每条竖线上的点数都超过$O(\sqrt{n})$

439E 基础反演题，预处理一下阶乘及其逆元，然后线性筛一波就可以单次$O(log(n))$了。

342E 对询问分块，复杂度$O(n\sqrt{n})$