杂题乱做1

没写过几道题也来写sol的cyb就是屑

CF1305G Kuroni and Antihype

一操作等同于和一个年龄为0的人进行二操作。考虑在按位与为0的两人之间连边，边权为年龄和，题意即为求最大生成树减去点权和。注意到按位与为0，因此从大到小枚举年龄和，再枚举子集表示一个人的年龄，然后跑最小生成树。实现时将相同年龄的一起处理，$cnt_i$ 表示年龄为 $i$ 的有多少连通块，经过一次合并后变成一个连通块。

$\texttt{code}$

CF1019C Sergey’s problem

神秘构造。对每个点打 $used$ 和 $up$ 标记。首先 $1\to n$ 乱选，对一个没打过 $used$ 的点同时打上 $used$ 和 $up$，并将他能到的点都打上 $used$，使得打了 $up$ 标记的点到任意一个点距离不超过 $1$ 。注意到后标记 $up$ 的点可能可以到达先打上的点，因此再倒着做一次，对一个 $up$ 的点，将其能到的点 $up$ 标记全部打成 $false$。由于一个点被删除当且仅当存在一个 $up$ 的点到它距离为 $1$，因此继续保证 $up$ 点集到任何一个点距离都不超过 $2$。

$\texttt{code}$

CF842D Vitya and Strange Lesson

感觉是一道比较套路的题目。
使用 $01-trie$ 不但可以动态支持 $O(\log n)$ 复杂度查询 $mex$ ，还支持全局 $xor$。

$\texttt{code}$

CF1553H XOR and Distance

又双叒叕被wsy爆了
使用 $01-trie$。$xor\ x$ 相当于若 $x$ 第 $i$ 位为 $1$，则交换第 $i$ 层所有结点的左右子。
可以从上一个结果继承，只要交换两者 $xor$ 和的二进制 $1$ 的位结果就行。
直接做还是会 $T$，然而可以交换求值顺序，使较低位少交换。具体的，将二进制位反转进行操作。

$\texttt{code}$ 和 相同套路

CF512E Fox And Polygon

首先可以把多边形都变成以1号点为根的菊花，然后拼接上步骤。
然后发现可以分治，具体的若1号点有边则任选一条劈开分治，否则l,r节点之间必有连边，将其操作后再劈开。
实现过程中，对l,r之间边的操作使用了set。

$\texttt{code}$

P4632 [APIO2018] 新家

对时间扫描线，存储每个商店上一家同种类的位置 $pre$，线段树维护区间最小 $pre$。
二分答案，注意到若区间 $[p-r,p+r]$ 未出现一个种类，则 $[p+r+1,inf]$ 的 $pre$ 最小值必然小于 $p-r$，因此直接查询即可。也可以线段树上二分，将复杂度优化到单 $\log$ 但我懒得写了。

$\texttt{code}$

CF1553G Common Divisor Graph

注意到就算 $a_s$ 和 $a_t$ 都是奇数，将两点都操作后也联通了，因此答案不超过2。
接下来分开考虑。答案为 $0$，可以将质因子看作点，对每个 $a_i$ 分解质因数后使用并查集将这些质因子合并，询问时查询 $a_s$ 和 $a_t$ 的任一质因子是否连通。
此时再看可以发现，一次操作相当于将 $a_i\times (a_i+1)$ 的所有质因子合并，即 $a_i$ 和 $a_i+1$ 的质因子的并集里两两合并，注意不是合并 $a_i$ 质因子和 $a_i+1$ 质因子。。。开个unordered_map存一下就做完了。

$\texttt{code}$

CF547D Mike and Fish

同一行/列的选一半的两两匹配，由于是网格图，一个点列上/行上度都至多为1，故有环时环上必然是列边和行边交替，必然没有奇环，因此直接染色就好了。。。神秘。

$\texttt{code}$

P8991 [北大集训 2021] 出题高手

还是不是很懂。由于数据随机，前缀和的期望单调栈长度不会太长，而最终答案选择的区间必然是一个极小值和一个极大值，即在单调队列上，因此扫描线后动态加入点，枚举他往前跳单调队列跳到的位置，将这些区间的贡献用数据结构维护，实测树状数组和分块差别不大。。。总之做完了。

$\texttt{code}$

P4631 [APIO2018] 选圆圈

取目前最大半径 $R$，以 $2R$ 为边长将网格图划分成正方形，则与一个圆相交的圆必然在与其八连通的正方形内（包括自己这个），暴力枚举内部的圆即可。为防止复杂度退化，当最大半径减半时重新取最大半径 $R$ 并重构正方形，可以证明每个正方形被访问的次数是常数级别。
手写两int合并成一个long long的hash函数一定要注意符号，不要正数按位或负数！！！！！！

$\texttt{code}$

P6619 [省选联考 2020 A/B 卷] 冰火战士

感觉是一道比较套路的题目线段树二分板子。

$\texttt{code}$

P4585 [FJOI2015] 火星商店问题

题面稀烂！诋毁！诋毁！
二维问题，但是要 $01-trie$，没啥想法，就用线段树套 $01-trie$ 带 $n\log^2n$ 空间艹过去了。。。

$\texttt{code}$

CF576E Painting Edges

wsy：3300莎蔽题
线段树分治，每次修改前先判断是否可以染色，如果不能则相当于染上之前就染着的颜色。

$\texttt{code}$

CF1198F GCD Groups 2

cxy有高妙的确定性做法，但我看不懂。。。于是我使用shuffle通过了这题。具体的，卡时shuffle，然后贪心取出 $\gcd=1$ 的最小前缀，判后缀 $\gcd$ 是否为 $1$。注意到很多数相同的情况下效果很差，但很多相同的数相当于两个集合各放一个，因此相当于两个，处理掉就过了。

$\texttt{code}$

P2605 [ZJOI2010] 基站选址

正解出人意料地简单。
考虑 dp，$f_{i,j}$ 表示前 $i$ 个点中第 $i$ 个点放基站共放了 $j$ 个的最小代价，则 $f_{i,j}=\min\limits_{k=1}^{i-1}f_{k,j-1}+cost(k,i)$，随后发现在右侧加入一个 $i$ 只会影响刚好能覆盖到 $i-1$ 的端点，线段树维护贡献即可。统计答案时，枚举最右侧的基站 $i$ ，类似先前地处理刚好覆盖到 $i+1$ 的断点，加上贡献即可。

$\texttt{code}$

P5381 [THUPC2019] 不等式

一发过，开心(●’◡’●)
经典问题，使用 FHQ-treap 动态维护区间 $a$ 的和以及与 $y=0$ 的交点乘 $a$ 的和，然后类似线段树上二分地split，利用维护的值计算答案即可。

$\texttt{code}$

CF482C Game with Strings

状压dp，$f_i$ 表示达成 $i$ 状态的概率， $sm_i$ 表示达成 $i$ 状态时所有还没被确定的字符串，状压求，易得。
则对朋友选每个字符串的期望步数之和为 $\sum\limits_{i=0}^{2^{len}-1}f_i\times\text{popcount}(sm_i)$。由于求的是平均值，要 $\div n$

$\texttt{code}$

P6344 [CCO2017] Vera 与现代艺术

比较巧妙。操作不好处理，但观察到将高低位颠倒之后变成了二位数点，然后就扫描线+ds维护就好了。

$\texttt{code}$

P5631 最小mex生成树

本来以为有高论的，结果就是 2log。相当于小到大枚举mex，对于每条边在边权不是mex的地方都 加边，加边，加边然后并查集，然后线段树分治一下。并查集随机权值被卡常了，，，不得不使用维护size。。。

$\texttt{code}$

CF1059E Split the Tree

想了半天有没有高妙做法，然后一个一个叉掉了。。。
倍增处理每个点向上最高到多少，然后 n~1 简单 dp 即可。

$\texttt{code}$

P5504 [JSOI2011] 柠檬

有意思的题。观察到拆成的段头尾颜色一致且为产生贡献的值，否则把其中一个单独成段肯定更优。分颜色考虑，设 $f_i$ 为前缀 $i$ 的最大值，$c_i$ 为 $s_j=s_i(1\le j\le i)$ 的数量，则 $f_i=\max\limits_{s_j=s_i}f_{j-1}+s_i\times(c_i-c_j+1)^2$，拆了平方之后便可以斜率优化了，使用李超线段树实现。

$\texttt{code}$

CF504E Misha and LCP on Tree

好像有两种单 $\log$ 做法，都要到根做正反两个前缀hash：
一种是重链剖分，取出 $\log$ 段区间，观察到每个区间dfn连续，因此直接枚举在哪个区间，然后 $O(1)$ 判断前缀是否相等，直到不相等再在这个区间二分即可。
一种是直接二分，然后长剖做到 $O(1)$ 求 $k$ 级祖先。
然而我直接二分+重剖艹过去了

$\texttt{code}$

CF1774G Segment Covering

非常好题目！非常好题目！非常好题目！非常好题目！非常好题目！
首先考虑假设A线段包含B线段，若选A则B可选可不选，因此对奇偶答案贡献一样，可以删去A。
然后我们得到了不互相覆盖的线段序列。
接着处理每组询问。左端点为询问的 $l$ 的线段必选，从这个开始标号记为1，观察到若存在 $l_1<l_2<l_3\le r_1$，则选择 1，3 时 2可选可不选，贡献一样，由于1必选，3删去。
最后会形成这个样子：
可以存下每个线段后面的第一个 $l$ 比他的 $r$ 大的线段，然后从 1，2 分别倍增跳即可。观察到中间若存在空则答案为0，而若存在空则 1，2 跳到的一样，因此特判一下就好了。

$\texttt{code}$

P3629 [APIO2010] 巡逻

有点绕的题。选一条边相当于环上的边走一次，其余走两次，因此求个直径就好了。两条边会有两个环，则在一个环上的走一遍，在两个环上和不在环上的走两遍，相当于先求一个直径，再将这个直径上的边权改成-1，再求一遍直径。

$\texttt{code}$

CF1270F Awesome Substrings

假设 $s_i$ 表示前 $i$ 个字符中 1 的个数，则答案为 $\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=0}^{i-1}[i-j=d\times(s_i-s_j)]$。
对 $d$ 根号分治。 $d\le\sqrt{n}$ 时，枚举 $d$，有 $\sum\limits_{i=1}^n\sum\limits_{j=0}^{i-1}[i-j=d\times(s_i-s_j)]=\sum\limits_{i=1}^n\sum\limits_{j=0}^{i-1}[i-d\times s_i=j-d\times s_j]$，因此求出所有 $i-d\times s_i$，开个桶维护。
$d>\sqrt{n}$ 时，则选出 1 的个数不超过 $\sqrt{n}$，因此枚举左端点，再枚举最右边的 1，除一下即可得出方案数，记得对 $\sqrt{n}$ 取 $\max$ （因为前面统计过了。）

$\texttt{code}$

CF1835C Twin Clusters

感觉被随机化乱艹有点可惜虽然本身也不是很难的题。
首先发现区间不交是没用的。接下来做前缀，并存下 $lst_i$ 表示上一个前缀 $xor$ 和前 $k$ 位值为 $i$ 的位置。
每次做的时候，若存在 $lst$ 取出 $[lst_{a_i>>k},i]$ 这个区间的 $xor$ 和，然后查询有没有 $xor$ 和一样的区间。
然后发现这玩意非常巧妙，因为一共有 $2^{k+1}+1$ 个前缀（包含 $0$），而前 $k$ 位只有 $2^k$ 种值，故至少有 $2^k+1$ 个有贡献的区间，而后 $k$ 位也只有 $2^k$ 种值，因此必然有两个区间 $xor$ 和一样。
做完了。顺便证明了必然有解。

$\texttt{code}$

[ABC254Ex] Multiply or Divide by 2

洛谷atcoder的RMJ炸了。
构造。取出 $\max_a,\max_b$，若相等都删掉，若 $a$ 大则 $\div2$，若 $b$ 大则判断是不是偶数再 $\div2$。

$\texttt{code}$