杂题乱做2

没写几题就换2的cyb就是屑

CF1765G Guess the String

注意到查询次数大于 $\frac{n}{2}$ 小于 $n$，因此尽量每次查出两个位置。具体的，先查出第二个位置，然后每次往后跳两个位置，随一种查询，能确定一到二个位置，确定不了两个就再查一次。

$\texttt{code}$

P7830 [CCO2021] Through Another Maze Darkly

计一号点走一圈为一次，则一共会走至多 $n$ 次就循环了。注意到每次走的都是一个欧拉序状物，我不会高妙做法，因此考虑直接维护欧拉序，要支持插入叶子，就用了 splay。注意，新插入的点一开始在最后出现的 $fa$ 之后，后来要在第一个 $fa$ 之后，然后是在上一个靠前面的之后。之后将询问离线下来排序，然后查询是简单的。

$\texttt{code}$

P6822 [PA2012] Tax

拆无向边为有向，然后以边为点，在相反两边之间连边权为原边权值的边，超级源向1的出边连其边权的边，n的入边向超级汇连其边权的边。然后将一个点所有出边排序，边记为 $l_i$，边权 $w_i$，则每个 $l_i$ 向 $l_{i+1}$ 连边权为 $w_{i+1}-w_i$ 的边， $l_{i+1}$ 向 $l_i$ 连边权为0的边，然后跑最短路即可。

$\texttt{code}$

P3587 [POI2015] POD

zes：好题！好题！好题！
来自[CSP-S 2022] 星战的经验告诉我们，当你没啥好做法的时候，就该想想哈希。。。
于是乎，我们希望能够当 $a_{l-1}\oplus a_r=0$ 时，区间 $[l,r]$ 合法。因此给每个点附随机权值，给上个位置 $xor$ 相同的值，再做个前缀，然后使用unordered_map套vector维护值相同的位置，lower_bound取出差最小的值，就做完了。

$\texttt{code}$

CF1753F Minecraft Series

好家伙。直接枚举对角线并扫描线，观察到一个点最多被扫到 $O(\min(n,m))=O(\sqrt{nm})$ 次，因此要进行 $O(nm\sqrt{nm})$ 次修改，$O(nm)$ 次查询 $mex$，使用分块 $O(1)$ 修改，$O(\sqrt{n})$ 次查询即可。

$\texttt{code}$

CF1878G wxhtzdy ORO Tree

经典套路，如果是区间问题，则对于询问的区间，or和不同的前缀只有log个，因此记录这些位置，求区间or即可。树上的话，可以树剖解决，也可以跟我一样倍增。

$\texttt{code}$

CF1844G Tree Weights

cxy:这题IQ test别做。然而上半年就做了，现在一看不太会，还是来补个sol好了。
注意到两点距离即为两点到根距离减lca到根距离的两倍，因此可以轻松求出每个点到根距离二进制下的第一位。然后发现这个东西可以推广，可以用第 $i$ 位推出 $i+1$ 位。做完了。

$\texttt{code}$

CF1610G AmShZ Wins a Bet

考虑删除一对括号时，若删除的右括号的左边是个右括号，则删除这个肯定最优；否则，删除左边那个右括号一定不劣于删除这个。由此，我们证明了每次删除的是连在一起的左右括号；进一步，我们发现删除的是一些合法括号子串。
然后考虑dp，$f_i$ 表示以 $i$ 为开头的后缀的字典序最小字符串，首先 $f_i=s_i+f_{i+1}$，+ 表示字符串拼接；其次，若存在以 $i$ 开头的合法括号子串，设其结尾的下一位为 $nxt_i$，则 $f_i=\min(f_i,f_{nxt_i})$。发现因为是加入字符，所以容易倒着用 $trie$ 维护，判断两字符串大小可以在 $trie$ 上倍增并处理到根的 $hash$ 值。

$\texttt{code}$

P7482 不条理狂诗曲

当你想到分治，就做完了。

$\texttt{code}$

P4340 [SHOI2016] 随机序列

注意到对于一个位置 $i$，若前面不添加乘号，则加减均可添加，贡献为 $0$。
由于第一个前面无符号，则有贡献的是一个前缀，因此答案为：

$$\sum\limits_{i=1}^{n-1} 2\times3^{n-i-1}\times\prod\limits_{j=1}^i a_j+\prod\limits_{i=1}^n a_i$$

对于修改，我们动态维护 $b_i=2\times3^{n-i-1}\times\prod\limits_{j=1}^i a_j$（特判最后一个），则修改相当于在 $b$ 数组上后缀乘，查询就是求 $b$ 数组全局和，线段树维护即可。

$\texttt{code}$

[ARC144D] AND OR Equation

注意到 $2^n$ 非常非常大，因此考虑拆位。取假设 $a_{2^i}=h_i+a_0(1\le i\le n)$，取 $i\neq j(1\le i,j\le n)$，则有 $a_{2^i|2_j}+a_0=a_{2^i}+a_{2^j}=h_i+h_j+a_0\times 2$，即 $a_{2^i|2^j}=h_i+h_j+a_0$。
推广后得到 $a_i=a_0+\sum\limits_{(i>>x)\& 1}h_x$。
注意：$h_i$ 可以为负。
因此合法序列满足：

• $a_0+\sum\limits_{i=1}^n \max(h_i,0)\le K$
• $a_0+\sum\limits_{i=1}^n \min(h_i,0)\ge 0$

然后考虑若已确定 $h$ 数组，则满足条件的 $a_0$ 数量为：

$$K-\sum\limits_{i=1}^n \max(h_i,0)-\sum\limits_{i=1}^n \max(-h_i,0)+1=K-\sum\limits_{i=1}^n|h_i|+1$$

然后枚举非零的 $h_i$ 数量，推个组合数状物，每个注意要乘 $2^{\text{非零}h_i\text{数}}$。做完了。

$\texttt{code}$

[ABC301Ex] Difference of Distance

哥我尝试阅读了一下你们的题解，真的好抽象，完全看不懂，，，我还是去写不高明的线段树分治了。。。

$\texttt{code}$

CF1693C Keshi in Search of AmShZ

shaojia：蓝题过分了嗷。
随机走=最坏情况，，，考虑若已求出一个点能到的所有点的最短路，则将这些点按最短路排序，答案必然是封掉一个后缀后走最后一个没被封的，因此进行类似 dijkstra 的扩展。

$\texttt{code}$

P2446 [SDOI2010] 大陆争霸

还是类 dijkstra 的算法。从每个结界向它保护的点连边，当保护一个点的所有结界都被破坏时再将其加入优先队列。

$\texttt{code}$

CF1882E2 Two Permutations (Hard Version)

神仙题，但是鸽了好久。在序列开头添加字符 $x$，则修改为 $xAcB\to xBcA$，相当于 $xAcB\to cAxB$，即交换 $x$ 与任意一个元素的位置。考虑从一种状态变到另一种状态，最小步数为 $x$ 不在的大小不为 1 的环的大小 +1 之和，再加上 $x$ 所在环大小 -1。由于目标状态 $x$ 不一定在开头，需要试 $n+1$ 种目标序列，并且为了步数最小，奇偶分开考虑，最后再合并两个序列，方法同 easy version。

$\texttt{code}$

P4042 [AHOI2014/JSOI2014] 骑士游戏

一个怪物如果不用法术直接杀死，必须普攻后变成的怪物杀死的代价之和小于法术杀死消耗的体力，必然变成的每个都比他小，因此类似 dijkstra 地转移即可。

$\texttt{code}$

CF1386A Colors

感觉比较神秘。首先考虑二分，然后发现很容易超出序列长度，因此先构造出二分最坏情况下的询问序列，倒着将指针移动到正确位置，然后直接二分即可。

$\texttt{code}$ 和 双倍经验（记得删多测。）

P4211 [LNOI2014] LCA

好题。注意到 $dep[\text{LCA}(x,y)]$ 正好为 $x$ 到根链 +1，$y$ 查询到根链求和。然后扫描线，树剖+线段树/树状数组均可。

$\texttt{code}$

SP10707 COT2 - Count on a tree II

树上莫队板子题。但是由于第一次写，为了处理链上情况口胡了一个欧拉括号序状物，实测非常正确，就是常数有点大，，，但是只要像普通莫队一样写就行，无需任何特判，还比树分块简单（至少我觉得吧。。。）

$\texttt{code}$

CF1270G Subset with Zero Sum

从 $i$ 向 $i-a_i$ 连边，变成了有向基环森林，找环即可。

$\texttt{code}$

[AGC003E] Sequential operations on Sequence

首先，一次操作长度比上次短的话，上次操作是无效的。由此我们将操作序列变得递增了。
然后，我们考虑每个序列由几段其他序列拼成，于是在操作序列上二分出比他小的最大值，并对其取模，再继续求出下一段。由于一次取模长度至少减半，新的序列至多由 $\log_2n$ 段其他序列拼成。序列最后剩下的部分相当于前缀加，于是我们求出每一段的前缀加用了多少次，然后直接在差分数组上改即可。（然而我脑抽写了树状数组。。。。。。随便吧反正复杂度瓶颈不在这。）

$\texttt{code}$

CF1622F Quadratic Set

不会做。打开sol。发现第一篇是 shaojia 两年前写的。。。
首先答案不小于 n-3，构造详见 shaojia 的 sol。
然后考虑判掉答案是否是 n，n-1，n-2，这玩意可以随机+抑或哈希。

$\texttt{code}$

CF472G Design Tutorial: Increase the Constraints

非常困难，是分块+fft状物，大概就是把一串反过来，变成了和为固定值的位的xor和之和，之类的东西吧。
于是就用__uint128_t压128位艹了。你问我为啥不写bitset？因为没卡过去。

$\texttt{code}$

CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

把22个char压成一个int，处理出每个点到根的xor和 $a$，则一个路径 $(x,y)$ 合法当且仅当 $\text{popcount}(a_x\oplus a_y)\le 1$。启发式合并不知道为啥被卡常了，改成 $0-1trie$ 合并就过了。

$\texttt{code}$

P6819 [PA2012] Binary Dodgeball

首先，移不移出事等价的。然后，$i$ 位置石头的 $sg$ 值为 $\lfloor\log_2(\frac{n}{i})\rfloor$。考虑算贡献，则 $\lfloor\frac{\log_2(n)}{x}\rfloor$ 作为 $sg$ 值的贡献数量是 $\lfloor\frac{n}{2^{x}}\rfloor-\lfloor\frac{n}{2^{x+1}}\rfloor$。由于最后 $x$ 要 xor 在一起，答案只与数量奇偶性有关，即 n 二进制下第 x 位和 x+1 位是否一样。因此可以二分答案，然后数位dp即可。

$\texttt{code}$

CF1534E Lost Array

构造题，考虑得到的结果一定是一些查询 xor 在一起，因此求的就是一种每步将 k 个位置取反，最后使得 n 个位置都是 1 的方案。观察到构造过程中是那些位置并不重要，重要的是有多少个 1，因此可以直接以 1 的个数为状态 bfs，转移是简单的，从长度构造出方案也是。

$\texttt{code}$

CF741C Arpa’s overnight party and Mehrdad’s silent entering

类似 Mike and Fish，在 $2i-1$ 和 $2i$ 之间连边，情侣之间也连，则若成环必然一条情侣边一条相邻边地走，则没有奇环，直接二分图染色即可。

$\texttt{code}$