格式有点问题，可以到 https://blog.hydd.cf/p/group/ 去看，但是加载比较慢。

群论

群的定义

定义：给定集合 $G$ 和集合 $G$ 上的二元运算 $\cdot$，满足以下条件称为群：

1、封闭性（Closure）：若 $a,b\in G$，则 $\exists c\in G$，使得 $a\cdot b=c$。

2、结合律（Associativity）：对 $\forall a,b,c\in G$，有 $(a\cdot b)\cdot c=a\cdot(b\cdot c)$。由于结合律成立，可记作 $a\cdot b\cdot c$。

3、有单位元（Identity）：$\exists e\in G$，满足对 $\forall a\in G$，有 $a\cdot e=e\cdot a=a$。

4、有逆元（Inverse）：$\forall a\in G$，满足 $\exists b\in G$，使得 $a\cdot b=b\cdot a=e$，记作 $b=a^{-1}$。

一些概念

群元素的个数是有限的，是有限群；群元素的个数是无限的，是无限群。

有限群 $G$ 的元素个数叫做群的阶，记做 $|G|$。

设 $G$ 是群，$G'$ 是 $G$ 的子集，若在 $G'$ 原有的运算之下也是一个群，则称为 $G$ 的一个子群。

若群 $G$ 的任意两元素 $a,b$ 恒满足 $a\cdot b=b\cdot a$。则称 $G$ 为交换群，又称 Abel 群。

一些性质

单位元唯一：$e_1e_2=e_2=e_1$

左右逆元相等：$ab=e,ca=e\rightarrow b=c$

证明：$cab=(ca)b=eb=b, cab=c(ab)=ce=c \Rightarrow b=c$

消去律成立：$ab=ac\rightarrow b=c$

证明：$ab=ac \Rightarrow a^{-1}ab=a^{-1}ac\Rightarrow b=c$

每个元的逆元唯一：$ab=ba=e,ac=ca=e \rightarrow b=c$

证明：$e=ab=ac\Rightarrow b=c$

多个数乘积的逆元：$(ab\cdots c)^{-1}=c^{-1}\cdots b^{-1}a^{-1}$

证明：$(c^{-1}\cdots b^{-1}a^{-1})(ab\cdots c)=c^{-1}\cdots b^{-1}(a^{-1}a)b\cdots c=\cdots=e$

对于有限群，逆元存在于消去律存在等价。

证明：上面已经证明逆元存在则消去律存在，接下来证明消去律存在则逆元存在。

$ab=ac\rightarrow b=c$，则令 $G'=\{ax|x\in G\}$，根据消去律 $ax$ 两两不同，则 $|G|=|G'|$，而根据封闭性，$G'\subseteq G$，（对有限群）故 $G=G'$，则必然存在 $e\in G'$，即 $\exists x\in G,ax=e$。

对于有限群，若 $a\in G$，则存在最小正整数 $r$，使得 $a^r=e$，且 $a^{-1}=a^{r-1}$。

证明：设 $g=|G|$，则 $a,a^2,\cdots,a^g,a^{g+1}\in G$ 中必有相同项（鸽巢原理）。

设 $a^j=a^k(1\leq j\lt k\leq g+1)$，则 $e=a^{k-j}$（消去律）。令 $r=k-j$，则 $a^r=a^{r-1}a=e$，即 $a^{-1}=a^{r-1}$。

既然存在正整数 $r$ 使得 $a^r=e$，其中必有最小者，不妨仍设为 $r$。

$r$ 称为 $a$ 的阶（和群的阶不同，这是一个元的阶），容易证明 $H=\{a,a^2,\cdots,a^r=e\}$ 在原有运算意义下也是一个群。

置换群

置换

置换：$[1,n]$ 到自身的一一映射称为 $n$ 阶置换，共有 $n!$ 个。$S_n$ 为所有 $n$ 阶置换组成的置换群。

置换群的运算：双射的复合（不满足交换律）。

循环

循环：$p=(a_1,a_2,\cdots,a_n)$ 称为 $n$ 阶循环，$a_1\rightarrow a_2\rightarrow a_3,\cdots\rightarrow a_n\rightarrow a_1$。$p^n=(1)(2)\cdots (n)=e$。

若两个循环无共同文字，称为不相交的，不相交的循环相乘可交换。任一置换可表示成若干不相交循环的乘积。

共轭类

$P=(a_1a_2\cdots a_{k_1})(b_1b_2\cdots b_{k_2})\cdots(h_1h_2\cdots h_{k_l})$，其中 $a,b,\cdots,h$ 都是不相交循环，$k_1+k_2\cdots k_l=n$。设 $k_i=j$ 的出现次数为 $c_j$，用 $(j)^{c_j}$ 表示，$\sum_{j=1}^njc_j=n$ 则它的格式为 $(1)^{c_1}(2)^{c_2}\cdots (n)^{c_n}$。

共轭类：$S_n$ 中所有相同格式的置换全体构成一个共轭类。

对换

任意循环都可以表示为对换的积：$(1\ 2\cdots n)=(1\ 2)(1\ 3)\cdots (1\ n)$。

每个置换的分解方式不是唯一的，但是表示成对换的个数的奇偶性是唯一的。

陪集

陪集：对于 $G$ 的一个子群 $G'$，它关于 $a\in G$ 的右陪集为 $G'_a=\{x\cdot a|x\in G'\}$，左陪集为 $_aG'=\{a\cdot x|x\in G'\}$。

根据消去律，陪集的元素两两不同，故 $G'$ 每一个陪集的大小都和 $G$ 相等。

方便起见，以下均以右陪集为例，左陪集同理。

一个性质：对于 $a,b\in G$，若 $G'_a \cap G'_b\neq \varnothing$，则 $G'_a=G'_b$。

证明：因为 $G'_a \cap G'_b\neq \varnothing$，所以 $\exists x,y\in G',x\cdot a=y\cdot b$，$y^{-1}\cdot x\cdot a=b$。

对 $\forall z\in G'_b$，设 $z=tb(t\in G')$，则 $z=tb=t\cdot y^{-1}\cdot x\cdot a=(t\cdot y^{-1}\cdot x)\cdot a$，而 $t\cdot y^{-1}\cdot x\in G'$，故 $z\in G'_a$，即 $G'_b\subseteq G'_a$。同理可以证明 $G'_a\subseteq G'_b$，故 $G'_a=G'_b$。

拉格朗日定理

拉格朗日定理（Lagrange's theorem）：对任意 $G$ 的一个子群 $G'$，$|G'||G':G|=|G|$（$|G':G|$ 表示 $G'$ 在 $G$ 中的陪集个数）。

证明：上面说明了 $G'$ 的陪集的大小都是 $|G'|$，而且任意两个相等或不交。

又因为 $e\in G'\Rightarrow x\in G'_x \Rightarrow \bigcup_{x\in G} G'_x=G $，所以共有 $|G':G|=\frac{|G|}{|G'|}$ 个不同的陪集。

这个定理说明了一个群的子群大小是整除该群大小的。

不动点、轨道和稳定化子

很多概念在中文翻译的描述上有差异，我们主要用不动点/轨道/稳定化子来描述。

设群 $G$ 作用在集合 $X$ 上。对于 $X$ 中的一个元素 $x$，每个 $G$ 中元素 $g$ 都把 $x$ 映射到某个 $g(x)\in X$ 上。

注意，$g(x)$ 表示将 $g$ 作用在 $x$ 上得到的结果。

不动点（fixed point）：对于 $X$ 中的一个元素 $x$，如果 $x\in X$ 在任意 $g\in G$ 的作用下都不变，即 $g\cdot x=x$，那么称 $x$ 为该群作用的一个不动点。不动点集 $X^g=\{x\in X\mid g(x)=x, \forall g\in G\}$。

轨道（orbit）：对于 $X$ 中的一个元素 $x$，所有能被映射到的元素 $g(x)$ 构成了 $X$ 的一个子集，称为元素 $x$ 的轨道。$\mathrm{orbit}(x)=\{g(x)\mid g\in G\}$。轨道集合 $X/G$ 为所有不同轨道的集合。

（另外的一种描述，等价类。）

稳定化子（stablizer）：对于 $X$ 中的一个元素 $x$，所有满足 $g(x)=x$ 的 $g$ 构成了 $G$ 的一个子群，称为元素 $x$ 的稳定化子。$\mathrm{stab}(x)=\{g\in G\mid g(x)=x\}$。

（另外的一种描述，$k$ 不动置换类：设 $G$ 是 $S_n$ 的一个子群。对于 $k\in [1,n]$，$G$ 中使得 $k$ 元素保持不变的置换全体，称为 $k$ 不动置换类，记作 $Z_k$。）

轨道-稳定化子定理

轨道-稳定化子定理（Orbit-stabilizer theorem）：对 $\forall x\in X$，有 $|\mathrm{stab}(x)||\mathrm{orbit}(x)|=|G|$。

证明：首先我们有对于 $\forall x\in X$，满足 $\forall g,h\in G,g(x)=h(x) \Longleftrightarrow g$ 和 $h$ 在稳定化子的同一个左陪集上，证明如下 $g(x)=h(x)\Leftrightarrow (g^{-1}\cdot h)(x)=x\Leftrightarrow g^{-1}\cdot h\in \mathrm{orbit}(x)\Leftrightarrow h\in \ _g\mathrm{orbit}(x)$。

故轨道数量 $|\mathrm{orbit}(x)|$ 就是稳定化子的陪集数量 $|\mathrm{stab(x)}:G|$，根据拉格朗日定理，可以得到 $|\mathrm{stab}(x)||\mathrm{orbit}(x)|=|G|$。

Burnside 引理

伯恩赛德引理（Burnside's lemma）：$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|$。轨道数（等价类）数量为所有置换下不动点数量的平均值。

证明：$|X/G|=\sum_{x\in X}\frac{1}{|\mathrm{orbit}(x)|}=\frac{\sum_{x\in X} |\mathrm{stab}(x)|}{|G|}=\frac{\sum_{g\in G} |X^g|}{|G|}$。

解释：第一个等号是，每个 $x$ 出现在大小为 $|\mathrm{orbit}(x)|$ 的轨道，而每个轨道应该被计算恰好一次，相当于其中每个元素贡献 $\frac{1}{|\mathrm{orbit}(x)|}$；第二个等号是轨道-稳定化子定理；第三个等号是两个分子都等于 $x\in X,g\in G,g(x)=x$ 的数量。

Pólya 定理

波利亚计数定理（Pólya enumeration theorem）：对于 $n$ 阶置换群 $G$，用 $t$ 种颜色给 $n$ 个位置着色的不同方案数为 $|X/G|=\frac{1}{|G|}\sum_{g\in G}t^{c(g)}$，其中 $c(g)$ 表示置换 $g$ 拆出的不相交循环个数。

证明：只需证明 $|X^g|=t^{c(g)}$。$X^g$ 中的元素在 $g$ 作用下不变，等价于同一个循环上的颜色都相同，而不同循环间独立，故 $|X^g|=t^{c(g)}$。

https://blog.hydd.cf/p/ioi2022/

Day2 T3 Thousands Islands 待填。

Catfish Farm

第 $i$ 列哪些鱼被抓住，只和第 $i$ 列堤的高度，以及 $i-1/i+1$ 列中较高堤的高度有关。

容易想到按列 dp，这样第 $i$ 列就有两种情况，较高的列是 $i-1/i+1$。

这个较高没有必要，仅仅多加了限制，所以可以每个 $i$ 自由选择 $i-1/i+1$，这样如果选的不是较高的答案只会更小。

我开始想的是，对于选择 $i-1$ 的，记录第 $i$ 列的高度；对于选择 $i+1$ 的，记录这列抓的鱼最高的高度。这样状态就表示算完了前 $i$ 列的答案，当前是选择 $i-1/i+1$。

其实不用这样，题目要求我们每一列选择一个堤的高度，就按照题目来，状态改为表示固定完了前 $i$ 列堤的高度，当前是选择 $i-1/i+1$。选择 $i+1$ 的答案在 $i+1$ 时再计算。

具体来说，记 $dp(i,j,0/1)$ 表示前 $i$ 列，堤恰好不覆盖这一列从下往上第 $j$ 条鱼，当前选择 $i+1/i-1$（当前列贡献 未计算/已计算）。对于前一列选当前列/这一列选前一列的，要算上增加的贡献。

https://qoj.ac/submission/44615

Prisoner Challenge

比较大小，容易想到在二进制下按位比较。$x$ 需要记录当前存的是第几位，当前位为 $\varnothing/A$ 的当前位的值是多少。

每次，如果当前记录的是 $A$，就拿 $B$ 这一位比较，如果相同跳到下一位，否则返回；记录的是 $\varnothing$，就把 $A$ 这一位记录进去。

这样次数太多（大概是 $3\log n$），但是用 $B$ 比较完相同后，你其实可以知道 $B$ 下一位的信息，把 $B$ 下一位信息存进去。可以发现，比较是按照位数 $B,A,B,A$ 交替，不需要记录里面存的是 $A/B$，现在只需要记录位数和当前位的值，大概是 $2\log n$。

一种思路是换进制，$k$ 进制应该是 $k\lceil\log_k n\rceil$，但还是不能通过。

二分和从高到低贪心填是几乎等价的。按照同样思路，可以改为每次把值域范围分成 $k$ 份，看是否在同一个值域区间，次数是 $f(n)=f(\lceil \frac n k\rceil)+k$，没区别。

题目保证了两个数不同，故如果当前数为 $1$ 或 $n$ 就直接返回，把剩下的范围再分成 $k$ 份，也就是 $f(n)=f(\lceil \frac {n-2} k\rceil)+k$。

把这个式子拿去 $dp$，对于不同的 $n$，$k$ 不固定，$f(n)=\min_k f(\lceil \frac {n-2} k\rceil)+k$，这样算出来 $f(5000)$ 恰好为 $20$。就按照 dp 出的方案选 $k$ 即可。

https://qoj.ac/submission/45397

Radio Towers

先考虑固定 $D$，对于选择的两个信号塔 $i,j$，中间要存在一个塔 $k$，$H_k\geq \max(H_i,H_j)+D$。

可以发现只有相邻的两个选择的信号塔才需要判断。

对每个 $i$，找到左右第一个 $k$，满足 $H_k\geq H_i+D$，分别记作 $L_i,R_i$。

$i,j$ 之间要有满足条件的塔，就要求 $R_i\leq L_j$（$i,j$ 中较大的对应的位置一定满足 $k$ 的条件），也就是区间 $[L_i,R_i)$ 两两不交。

同理易证区间只会有包含和不交两种情况（$D\geq 0$），对于两个位置 $i,j$，不妨假设 $H_i\geq H_j$，若 $R_i>L_j$，则区间 $[L_j,R_j)$ 都不满足条件，即 $R_i\geq R_j$。

不考虑询问的区间限制，$D$ 增加时，$L$ 只可能减小，$R$ 只可能增大，且根据证明，只有 $H$ 大的包含 $H$ 小的，故只会一些不是包含关系的区间变成了包含关系。

按照 $D$ 从小到大，每次把所有包含其它区间的区间全部删去（维护 $i$ 对应区间包含相邻某个的最小时刻），剩下的区间个数就是当前 $D$ 能选的数量。

有询问给定的区间限制 $l,r$ 时，把当前 $D$ 所有剩下的 $i$ 在 $[l,r]$ 内的个数求出来，但这样可能两边各少 $0/1$ 个区间（一个 $i$ 在 $[l,r]$ 内的，包含了一个在 $[l,r]$ 外的被删除了，实际上这个 $i$ 可以选）。

如果求出来的个数不为 $0$，看其中最小的 $L$ 和最大的 $R$，看 $[l,L),(R,r]$ 内是否还能选。要求区间内 $x\lt y,H_x-H_y$（或 $H_y-H_x$）的最大值，类似于 $ST$ 表的方法预处理即可。

https://qoj.ac/submission/45344

Digital Circuit

必须有一个叶子节点到根一路都是黑色，但是直接计数会算重。

要每一种方案对应唯一的叶子节点（相当于添加了限制条件）。

树的形态固定，由于根节点为黑色，说明儿子里至少有 $p$（参数）个是黑色，那么选择其中的第 $p$ 个黑色儿子，往下走。

最终会走到一个叶子节点，则设这种方案对应这个叶子节点。

现在考虑每个叶子节点 $x$，算对应到它的方案的数量。首先它到根的都必须是黑色，此外其它点的参数毫无关系，因为固定其它点的参数后其它点的颜色固定后，要求对应到的是 $x$，则 $x$ 到根路径的所有的参数是唯一确定的。

对每个叶子节点预处理出到根路径外的点的参数选择的方案数。线段树支持区间取反操作，维护所有黑色叶子节点的方案数之和即可。

https://qoj.ac/submission/45436

Rarest Insects

把不同的数放在不同的列，这个东西很像一个柱形图（？）

一种思路是每次删掉一行（删掉所有出现过的数各一次，需保证数量始终为 $1$），次数是行数（最多数出现次数）$\times n$。

另一种思路是每次删掉一列（删掉某种数的所有出现，需保证数量每次必须加 $1$），次数是列数（数字种数）$\times n$。

两种各做 $\sqrt n$ 次后一定能删完（数字总数为 $n$）。这样是 $O(n\sqrt n)$ 次。没什么优化空间。

第一种思路其实可以扩展成每次删掉 $r$ 行，需保证数量始终不超过 $r$ 即可。

求出数字种类数 $c$。考虑二分答案（上界 $\frac nc$），用第一种思路来 check 当前答案 $mid$，是 $O(n\log n)$ 次。

这个可以继续优化，如果 check 成功了（加入了 $mid\times c$ 个数），已经加入的数之后就不需要加了；如果 check 失败了，未加入的数之后也不可能加。

这样每次数量接近减半（有个上取整），次数共 $2n$ 左右。再加上外面求种类数的 $n$，总次数 $3n$ 左右。

这样一交得了 99.89 分，再加点优化，比如已经达到 $mid\times c$ 之后的就不需要尝试加入了，再 shuffle 一下序列防止被卡，就通过了。

不知道有没有不用随机化严格在 $3n$ 内的做法？

https://qoj.ac/submission/45454

566E

• 对于一对相邻的点 $(x,y)$，它们其它的相邻点之间的交集就是 $\{x,y\}$。且如果有两个相邻点交集的大小为 2 也一定是两个相邻的（出现的点如果不相邻那么它们路径上的也应该在交集中）。
• 这样可以求出所有非叶子节点之间的连边，剩下的都是叶子节点。叶子节点的连边就看是哪个点和它相邻的所有点都包含了它。
• 这样非叶子节点数量 $\leq 2$。如果没有非叶子节点则 $n=2$，特判；如果只有一个非叶节点，那么所有集合都是 $\{1,2,\cdots,n\}$；如果只有两个可以先用上面的方法找出两个非叶节点，但是不能用上面的方法判，叶子节点只会有两种不同的集合，一种接到一个点即可。
• 用 bitset 优化，时间复杂度 $O(\frac{n^3}w)$。

1637G

• 倒过来考虑，要把两个数 $x,y$ 变为 $\frac{x+y}2,\frac{x-y}2$。可以发现如果它们都是奇质数 $p$ 的倍数变化后还是 $p$ 的倍数，就不可能还原成 $1,2,\cdots,n$ 了。
• 说明最后的结果一定是 $2$ 的幂，则最小的是满足 $2^k\geq n$ 的最小整数。通过构造证明可以取到。
• 可以先把所有数都变成 $2^x(x\leq k)$ 的形式，再造出一个 0 然后再处理（$(0,x)\rightarrow (x,x)\rightarrow (0,2x)$）。
• 先找到 $2^t\lt n$ 最大的 $t$，对于 $[2^t+1,n]$ 的数和它们关于 $2^k$ 对称的位置先做一次操作，会变成一大堆 $2^k$ 和 $2,4,6,8,\cdots$，也可以看作是一个前缀，递归下去两个剩下的前缀即可，次数是一个 log 级别的。

1530G

• 先找不变量，发现 1 的个数不变，且操作可逆。
• 设 1 的个数为 $t$，$k=0,k=t,k>t$ 先特判。
• 下面讨论 $0\lt k\lt t$，由于可逆所以可以把 $s,t$ 变成相同的字符串。
• 看相邻两个 1 之间 0 的个数 $d_i$，如果 reverse 的两端都是 1 那么就是把中间的 $d$ 翻过来。
• 对于一般的 reverse，不仅把中间的翻过来，且对于左右两边，可以给 $d_i+=x,d_{i+k}-=x$，$x\in [-d_i,d_{i+k}]$，就是带上若干个 0。对每个 $i$ 取 $j=d_{i+k}$ 把 $d_{k+1},d_{k+2},\cdots,d_t$ 归零。
• 对于 $k$ 是奇数，剩下的可以一直交替做 $i=0,j=d_k$ 和 $i=1,j=d_{k+1}$。这样会隔一个清一个，而由于 $k$ 是奇数最后会把所有都清了，只剩下第一个位置，次数是 $2k+(m-k)\lt 2n$。
• 对于 $k$ 是偶数，无论怎样翻转奇数位还在奇数位置上，偶数同理，所以可以再判断 $s,t$ 奇数位之和是否相同。剩下的可以一直交替做 $i=0,j=d_k$ 和 $i=1,j=-d_1$。这样清的位置是一个前缀或后缀，且会不停地翻，只剩下第一个和最后一个位置，次数是 $k+(m-k)\lt 2n$。且两个位置奇偶性不同，故只要满足之前的条件就一定可以。

804E

• 有一个经典结论，排列交换相邻两个位置逆序对恰好变化 1，而交换距离为 $d$ 的可以等价于交换相邻的 $d+(d-1)$ 次，所以逆序对奇偶性一定会改变，故交换次数是奇数时一定不会和原序列相同。
• $n\bmod 4=2,n\bmod 4=3$ 时交换次数为奇数，故无解。
• $n\bmod 4=0$，可以 4 个分一组，然后就是组内要两两交换一次，两个组间要两两交换一次。最好的情况是组内和组间的做完都不变。组内的交换一种方案为 $(1,2),(3,4),(1,3),(2,4),(1,4),(2,3)$。两组之间，考虑把每组再分成两部分，两组的一部分之间容易构造出两边都翻转的方案 $(1_a,1_b),(2_a,2_b),(1_a,2_b),(2_a,1_b)$，那么两组每一部分都做一次就可以归位。
• $n\bmod 4=1$，此时多了一个数，考虑在 $(2i,2i+1)$ 交换的时候多加入和 $n$ 的交换，以 $(1,2)$ 为例，把原先的 $(1,2)$ 改成 $(1,n),(1,2),(2,n)$，就可以了。

923F

• 发现某棵树是菊花图一定无解，中心没法分配标号。此外 $n\leq 5$ 的都有解，可以暴力求出，其它的递归考虑。
• 如果当前某棵树有点删掉后就会使得树变成菊花图，设这个点为 $u$，它父亲是 $v$，它父亲的父亲（菊花中心）为 $w$。为了使得另一棵树不能有其它点和 $w$ 连边，就从另一棵树选个叶子节点 $w'$ 与 $w$ 对应，$w'$ 父亲 $u'$ 就与 $u$ 对应。那么 $v'$ 就不能和 $u'$ 相邻，由于不是菊花图，所以一定存在 $v'$。而菊花图的限制只是除了 $u$ 的所有点都不能和 $w$ 相邻，$u$ 和 $v$ 不能相邻，所以剩下的可以随意分配。
• 否则，两棵树都删除两个距离 >2 的叶子使得不是菊花图，递归即可。

833E

• 先离散化然后讨论。
• 如果一个位置覆盖了超过两个，这个位置就一定不会被照到。
• 如果一个位置覆盖了正好两个，想要照到就必须让两个都消失。
• 如果一个位置覆盖了恰好一个，若相交的有覆盖恰好两个的那么之前一定算到了，如果没有则说明相交部分没有贡献，可以都当作没有相交的来算，数据结构维护即可。

1060H

• 它没有两个未知数的乘法操作，只有加法操作。
• 可以想到能表示成 $((x+y)^2-x^2-y^2)/2$。
• $/2$ 可以表示成 $\times 2^{-1}$，求逆元可以在外面求，而乘法可以用龟速乘。$-x$ 可以表示成 $(p-1)\times x$，也用龟速乘。
• 现在问题在于平方，它只有 $d$ 次方，能否通过 $d$ 次方的值求出平方？给 $x,x+1,x+2,\cdots,x+d$ 前带个系数，让它们凑出 $x^2$。用高斯消元消一下，发现是可行的。每个都用龟速乘把系数带上求和即可求出平方后的值。

317E

• 牛逼题。如果你走不到影子那里，又因为两人都不能穿墙，就永远不可能抓到影子。
• 否则，你先走到当前影子的位置，然后看它现在在哪里，再继续走过去。如果你走出了这个 100*100，就可以再通过原来障碍的四个角，把影子靠上去再往它的方向走，就可以移动到一起。
• 每一步走了后长度要么减少要么不变，且如果你出不去的话那么每一次走到影子要么距离减小（影子被挡了一下），要么两个的增量相同，而不可能一直增量相同，那么你就走出去了，所以一定会求出解。

1292E

• 直接问 C,H 各一次剩下的都是 O，这样代价为 $2$。
• 考虑优化，问一下 CC,CH,CO 就可以求出 C 的位置，再求出 H 的位置可以用 OH,HH，剩下的都是 O（第一个位置可能是 H,O，最后一个位置可能是 C,O），这总共问了 $5$ 次长度为 $2$。

• 确定第一个和最后一个位置可以问 $3$ 次长度为 $n$，如果都不是就是剩下的一种。这样的代价总共是 $\frac 54+\frac 3{n^2}$，当 $n>4$ 时不超过 $1.4$。

• 题目的限制是 $n\geq 4$，所以要特判 $n=4$。

• 还是先问 CC,CH,CO,OH，如果问出了结果就至少确定了两个数，剩下的数还是用问 $3$ 次的方法解决，代价不超过 $\frac 44+\frac 3{16}$。但是接下来不能和之前一样了，否则代价就超了。
• 如果问 HH 出了结果，就有几种情况：HHHH,HHH*,HH**。有些不可能（*HHH,*HH*,**HH）的原因是 CH,OH,HH 都问过了，不可能存在某个 H 前一个位置没问出来。而 HHHH 不用考虑；HHH* 最后一个只有可能是 C,O；HH** 倒数第二个只可能是 O（CC,CH,CO 都问过了），最后一个只有可能是 C,O。由于只有最后一个有两种不确定，所以可以直接问 $1$ 次长度为 $4$ 的，代价为 $\frac 54+\frac 1{16}$。
• 如果问 HH 还不出结果，那么说明除了开头结尾一定是 O，且开头不是 C 结尾不是 H，如果其中有 O 就一定可以一次 OOO 问出来，否则就是另一个，代价为 $\frac 54+\frac 19$。

1267H

• 显然的一点是在任何一步不能有两个相同的数字相邻。
• 假设本身某个区间是合法的，往其中加入一些没有出现过的数，还是合法的。
• 考虑每次拿出一些不相邻的位置，然后变成一个子问题。
• 从后往前拆，倒着过来把每个能加入使得不会有数字相邻的选出，把它们分配一个新的权值，剩下的递归。
• 这样能选出 $\frac{n}{3}$ 个数（近似），即每次 $n$ 变为原来的 $\frac 23 n$（近似），那么需要的颜色数为 $\log_{\frac 32} n$（近似）。

1526F

• 考虑倒着推过来，假设知道了 $1,2$ 的位置或 $n-1,n-2$ 的位置，通过 $n-2$ 次询问就可以得到其它所有的（这个比较常见，求出某个特殊的可以推出全部）。
• 如果你求出了两个差比较小的 $a,b$，如果两个数的距离不超过 $\frac {n-4}3$，用它们两个询问出的距离最大次大分别是 $1,2$ 或 $n,n-1$。
• 那么假设你询问出的结果 $\leq \frac{n-4}6$，则任意两个距离都不超过 $\frac {n-4}3$。其实可以大力随机找，找不到的概率很小。不过也可以证明 13 个数中的所有三元组必定有符合条件的。其实也容易证明，考虑按照顺序两两之间的距离（共 12 个），现在相当于问是否有相邻两个都 $\leq \frac{n-4}6$。这个可以用鸽巢原理，总和不超过 $n-1$，则一定只有最多 5 个 $\geq \frac {n-4}6+1$，那么剩下的 7 个必定有两个相邻，它们就满足条件。

$x=0,y=0$ 答案显然为 $0$。

先把括号序列建树。和WC那题区别在于，那题建的是二叉树，这题建的是普通的多叉树（二叉树其实就是普通多叉转二叉得到的）。

左括号的权值即要求边上带权。操作1就是把相邻的两个子树，右边的并到左边，中间加一条新的边，权值为右边子树原先和父亲连边的权值。

操作2就是交换相邻两个子树的顺序。

最终要求没有一个点有两个儿子，也就是结果形如一条链，对应括号序列 ((((...))))。

如果括号序列本身就不需要操作，直接特判，答案为 $0$。

容易发现最优策略是按照深度从小到大依次合并，因为两个子树并起来后再做会比两个子树先分别做再并会更优。

做完前 $i-1$ 层会变成一条链，第 $i$ 层的点只剩下一个，往下连了原先第 $i$ 层的所有边，且新增了一些边（如上图红色的 $c$ 边）的权值产生影响。故树的形态无关紧要，只需要考虑第 $i$ 层所有往下的边的权值。

现在操作可以简化为，每次在当前层选取任意两条往下一层的边，把其中一条丢到下一层，并计算新增代价，直到只剩下一条。

一方面要这一层新增的代价尽量小，另一方面要往下一层丢的权值尽量小。

丢的权值尽量小，每一层只能留下一条，所以丢下去的尽量小就是把最大值留在当前层。

简单情况

当 $x=0,y=1$ 时，假设保留边 $a$，唯一策略是每次选择 $a$ 边和非 $a$ 边合并保留 $a$ 边。 除了保留的边外其它边恰好贡献了一次，设保留边权值为 $w$，所有边之和为 $s$，代价为 $s-w$。 $s$ 固定，故 $w$ 越大越好，所以把最大的留在当前层，同时满足了丢的权值尽量小的条件。

当 $x=1,y=1$ 时，此时每次合并代价与保留谁无关（都选与最小边合并）。 设边数量为 $t$，保留最小边权值为 $m$，所有边之和为 $s$，代价为 $s+(t-2)m$。 还是可以把最大的留在当前层，也满足了丢的权值尽量小的条件。

重头戏

当 $x=1,y=0$ 时，还是先与最小值合并，保留的不是最小值最后把保留值和最小值合并丢到下一层。 设边数量为 $t$，保留最小边权值为 $m$，代价为 $w+(t-2)m$。 此时这种情况新增代价最小的并不是保留最大值而是保留最小值，两个不一致，不能直接贪心。

仔细研究一下，首先每一层的 $t$ 是无论保留什么都不变的，设前 $i$ 层共有 $s_i$ 个值，那么第 $i$ 层的 $t$ 就是 $s_i-i+1$。而树是不能出现断层的，故在 $i$ 不超过树高之前 $t$ 是不降的，超过树高之后 $t$ 就每次 $-1$。

还是拆成两部分，一部分是每一层的 $m$ 尽量小，另一个是 $w$ 尽量小。

最开头的一段 $t=1$ 的一定没用，每一个被保留的都会算一次代价，所以你要 $w$ 之和尽量小也就是最后的一层（也就是合并结束时的那层 $t=1$）的 $w$ 值尽量大。

倒数第二层（合并结束前的那层 $t=2$）的策略也显然是保留最小值，把较大的 $w$ 扔下去。

当 $t\geq 3$ 开始你就可以每次保留非最小值和最大值的一个值，这样即保证了每次能传下去最小值使得 $m$ 尽量小，又保证了最后保留的 $w$ 能是 $t\geq 3$ 开始的最大值。

关键就在于开头 $t=1$ 后的那段 $t=2$，这一段的代价和保留的值决定了最终的代价。如果这一段保留的值比较小，那么它可以变为后面几层的 $m$；如果保留的值比 $t\geq 3$ 开始的最大值还要大，那么可以变成最后保留的 $w$。如果两个都不是的一定不优。

如果你保留的数不比之后的最大值还要大，那么你可以减小保留的值，从而缩小后面几层的 $m$；如果比最大值还要大，那么你一定不会对后面几层的 $m$ 有影响，这样不如继续加大保留的值使得最后剩下的 $w$ 尽量大。

所以对于开头的这段 $t=2$，你只需要保留最小值/最大值即可。两个都算一下取个 $\min$ 就是答案。

这个两段分开考虑还是不好写，可以直接考虑把策略变成每次保留次大值/次小值，这样就不需要把前面的 $t=2$ 和之后 $t\geq 3$ 的分开写了。最后的一个 $t=2$ 直接手动处理一下，也就是把两个数较小值加进答案即可。

代码（不知道对不对）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,x,y,cnt,v[810000],p[810000];
int num[810000],nxt[810000],z[810000];
string s; multiset<int,greater<int> > q;
vector<int> vec[810000];
void solve(int l,int r,int dep){
    while (l<r){
        vec[dep].push_back(v[p[l]]);
        solve(l+1,nxt[l]-1,dep+1);
        l=nxt[l]+1;
    }
}
void build(){
    int sum=0,tot=0;
    for (int i=1;i<=n+n;i++)
        if (s[i-1]=='(') sum++,num[sum]=i,p[i]=++tot;
        else nxt[num[sum]]=i,sum--;    
    solve(1,n+n,1);
}
ll solve01(int l,int r){
    ll sum=0,ans=0; q.clear();
    for (int i=l;i<=r;i++){
        for (int v:vec[i]) q.insert(v),sum+=v;
        sum-=*q.begin(); q.erase(q.begin()); ans+=sum;
    }
    return ans;
}
ll solve11(int l,int r){
    ll sum=0,ans=0; q.clear();
    for (int i=l;i<=r;i++){
        for (int v:vec[i]) q.insert(v),sum+=v;
        int mn=*q.rbegin();
        ans+=sum; ans+=(q.size()-2)*mn;
        sum-=*q.begin(); q.erase(q.begin());
    }
    return ans; 
}
ll solve10_min(int l,int r){
    ll sum=0,ans=0; q.clear();
    for (int i=l;i<r;i++){
        for (int v:vec[i]) q.insert(v),sum+=v;
        int c=*++q.begin(),mn=*q.rbegin();
        ans+=c; ans+=(q.size()-2)*mn;
        sum-=c; q.erase(q.find(c));
    }
    for (int v:vec[r]) q.insert(v),sum+=v;
    return ans+*q.rbegin();
}
ll solve10_max(int l,int r){
    ll sum=0,ans=0; q.clear();
    for (int i=l;i<r;i++){
        for (int v:vec[i]) q.insert(v),sum+=v;
        int c=*++q.rbegin(),mn=*q.rbegin();
        ans+=c; ans+=(q.size()-2)*mn;
        sum-=c; q.erase(q.find(c));
    }
    for (int v:vec[r]) q.insert(v),sum+=v;
    return ans+*q.rbegin();
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin>>n>>x>>y; cin>>s;
    for (int i=1;i<=n;i++) cin>>v[i];
    build();

    z[1]=vec[1].size(); int pos=0;
    for (int i=2;i<=n+1;i++){
        z[i]=(z[i-1]-1)+vec[i].size();
        if (z[i]==0){ pos=i; break;}
    }
    pos--; assert(z[pos]==1);

    int cur=0;
    for (int i=1;i<pos;i++)
        if (z[i]>1){ cur=i; break;}
    if (!cur){ cout<<"0\n"; return 0;}


    if (x==0&&y==1){ cout<<solve01(cur,pos-1)<<'\n'; return 0;}
    if (x==1&&y==1){ cout<<solve11(cur,pos-1)<<'\n'; return 0;}
    if (x==1&&y==0){ cout<<min(solve10_min(cur,pos-1),solve10_max(cur,pos-1))<<'\n'; return 0;}
    cout<<"0\n";
    return 0;
}

我这写的什么离谱题解。。。

$$ \begin{align*} n\overline{a}&=\sum_{i=1}^na_i\\ \\ n^2D &=n\sum_{i=1}^n(a_i-\overline{a})^2\\ &=n\sum_{i=1}^n a_i^2-2n\overline{a}\sum_{i=1}^n a_i+n^2\overline{a}^2\\ &=n\sum_{i=1}^n a_i^2-2(\sum_{i=1}^n a_i)^2+(\sum_{i=1}^n a_i)^2\\ &=n\sum_{i=1}^n a_i^2-(\sum_{i=1}^n a_i)^2\\ \end{align*} $$

观察题目中的式子，$a'_i\leftarrow a_{i-1}+a_{i+1}-a_i$，根据 CF1110E 的套路，可以差分，令 $d_i=a_{i+1}-a_i(1\leq i\lt n)$，一次操作 $(2\leq i\lt n)$ 即：

$$ d'_{i-1}=a'_{i}-a'_{i-1}=(a_{i-1}+a_{i+1}-a_i)-a_{i-1}=a_{i+1}-a_i=d_i\\ d'_i=a'_{i+1}-a'_{i}=a_{i+1}-(a_{i-1}+a_{i+1}-a_i)=a_i-a_{i-1}=d_{i-1} $$

相当于交换 $d_{i-1},d_i(2\leq i\lt n)$，故 $d$ 可以通过若干次操作，变为任意 $d$ 的排列。

由于 $a_1$ 不变，那么 $a$ 和 $d$ 是一一对应的。现在要求一个 $d$ 的排列使得 $n^2D$ 最小，继续推式子： $$ \begin{align*} n^2D &=n\sum_{i=1}^n a_i^2-(\sum_{i=1}^n a_i)^2\\ &=n\sum_{i=1}^n a_i^2-\sum_{i=1}^n\sum_{j=1}^na_ia_j\\ &=\frac{1}{2}(n\sum_{i=1}^n a_i^2-2\sum_{i=1}^n\sum_{j=1}^na_ia_j+n\sum_{j=1}^n a_j^2)\\ &=\frac{1}{2}(\sum_{i=1}^n\sum_{j=1}^n(a_i-a_j)^2)\\ &=\sum_{i=1}^{n-1}\sum_{j=i}^{n-1}(a_{j+1}-a_i)^2\\ &=\sum_{i=1}^{n-1}\sum_{j=i}^{n-1}(d_i+d_{i+1}+\cdots+d_j)^2\\ \end{align*} $$ $n^2D$ 取最小值时，$d$ 一定是先递减后递增的。

考虑在分界位置（即递减到递增）从小到大往两边加数，由于 $$ \begin{align*} n^2D &=n\sum_{i=1}^n a_i^2-(\sum_{i=1}^n a_i)^2\\ \end{align*} $$ 维护 $dp[k][s]$ 表示当前已经加入了 $k$ 个数，现在的 $a$ 之和为 $s$ 的最小 $\displaystyle \sum_{i=1}^n a_i^2$。

初始 $dp[1][s]=0$。

转移时考虑加到左边还是右边：

• 左边：原来是 $a_1,a_2,\cdots,a_k$，现在变为 $d,a_1+d,a_2+d,\cdots,a_k+d$，新增的贡献为

$$ \begin{align*} \Delta &=d^2+\sum_{i=1}^k (d+a_i)^2-\sum_{i=1}^k a_i^2\\ &=(k+1)d^2+2d\sum_{i=1}^ka_i\\ &=(k+1)d^2+2ds\\ \end{align*} $$

• 右边：原来是 $a_1,a_2,\cdots,a_k$，现在变为 $a_1,a_2,\cdots,a_k,a_k+d$，新增的贡献为 $$ \begin{align*} \Delta &=(a_k+d)^2\\ \end{align*} $$ 其实可以发现 $a_k$ 是固定的，为之前所有的 $d$ 之和，不需要再记录。

答案为 $\displaystyle \min_s\{n\times dp[n][s]-s^2\}$。

分析一下时间复杂度，第一维是 $O(n)$ 的，第二维是 $O(nV)$ 的，转移 $O(1)$。

但是可以发现 $d$ 为 $0$ 的转移可以忽略，第一维是 $O(\min(n,V))$ 的，总复杂度为 $O(nV^2)$，可以通过。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1ll<<60;
int n,a[11000],d[11000]; ll dp[510000];
ll sqr(ll x){ return x*x;}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<n;i++) d[i]=a[i+1]-a[i];
    sort(d+1,d+n);

    for (int i=0;i<=500000;i++) dp[i]=INF;
    dp[0]=0; int lim=0,sum=0;
    for (int i=1;i<n;i++){
        if (!d[i]) continue;
        for (int s=lim;s>=0;s--){
            if (dp[s]==INF) continue;
            dp[s+sum+d[i]]=min(dp[s+sum+d[i]],dp[s]+sqr(sum+d[i]));
            dp[s+i*d[i]]=min(dp[s+i*d[i]],dp[s]+2*s*d[i]+i*sqr(d[i]));
            dp[s]=INF;
        }
        lim+=i*d[i]; sum+=d[i];
    }
    ll ans=INF;
    for (int i=0;i<=lim;i++)
        if (dp[i]!=INF) ans=min(ans,n*dp[i]-1ll*i*i);
    printf("%lld\n",ans);
    return 0;
}