3月做题记录

2022-03-31

挑选了一些有价值的题记录。
不能再咕咕咕了。

P6076 [JSOI2015] 染色问题
- 容斥，设 $f_i$ 为至多使用 $i$ 种颜色在行列合法的情况下的答案，最终答案 $s$ 为 $\sum\limits_{i=0}^{c}(-1)^i\dbinom{c}{i}f_{c-i}$
- 计算 $f_i$ 还是容斥，考虑每行每个格子有 $i+1$ 种填法，因为可以留空；最后减去全空的不合法情况。对于列容斥，考虑最多选多少列，可以得到 $f_i=\sum\limits_{j=0}^{m}(-1)^{m-j}\dbinom{m}{j}((i+1)^j-1)^n$
P1848 [USACO12OPEN] Bookshelf G
- 暴力 dp 设 $f_i$ 为放前 $i$ 本书的最低高度，容易得到转移 $f_i=\min(f_j+\max(h_j,h_{j+1},\dots,h_i))(j\ge p_i)$，其中 $p_i$ 表示能让 $p_i+1\sim i$ 宽度合法的最靠左的位置。
- 用单调栈找出每个点左侧第一个 $h_i$ 比它大的点 $l$。新加入一个点 $h_i$ 时，将 $[l+1,i]$ 这段区间赋为 $h_i$。$f$ 的值确定，所以我们线段树上维护 $f$ 和 $f+h$ 的最小值，转移时从合法区间 $[p_i+1,i]$ 转移即可。
CF241B Friends
- 考虑在 01-Trie 上先找到第 $k$ 大的值，设其为 $w$。可以通过二分答案在 $\mathcal O(n\log^2\max a_i)$ 时间内完成。
- 再考虑统计大于 $w$ 的数对的和，可以预处理 $f_{i,j}$ 表示 01-Trie 上以 $i$ 为根节点的子树中，对应到叶子节点的所有数中有多少个在二进制下第 $j$ 位为 $1$。有了 $f$，我们就可以计算一整段区间的数异或上一个特定的数的异或值的和。考虑在 01-Trie 上对于每个数走一遍，遇到可以统计进答案的子树（子树中任意值大于 $w$）就按位考虑统计答案，这一部分的时间复杂度也是 $\mathcal O(n\log^2\max a_i)$。
P2081 [NOI2012] 迷失游乐园
- dp 转移较为容易理解，但转移过程中需要考虑的细节很多。
- 约定：$p_i$ 为 $i$ 点父亲的个数（环上为 $2$，否则为 $1$；树上根节点为 $0$），$s_i$ 为 $i$ 点儿子的个数（环上的点不算做儿子）。基环树环上的点称为“黑点”，其余点称为“白点”。
- Subtask 1：对于树的部分，首先设 $f_i$ 为从 $i$ 点开始，第一步向儿子走的期望步数，$g_i$ 为从 $i$ 点开始，第一步向父亲走的期望步数（其余步的方向不限），答案为 $\dfrac{1}{n}\sum\limits_{i=1}^{n}\dfrac{f_is_i+g_ip_i}{s_i+p_i}$
- 考虑 $f$ 和 $g$ 的转移，设 $u$ 的父亲为 $t$，不难得到 $f_u=\dfrac{1}{s_u}\times\sum\limits_{v\in \operatorname{son}_u}(f_v+w_{u,v})\\ g_u=w_{u,t}+\dfrac{1}{p_t+s_t-1}\times(g_kp_k+f_ks_k-f_u-w_{u,k}) (p_t+s_t-1>0)$
- 当 $p_t+s_t-1=0$ 时，$g_u=w_{u,t}$。
- Subtask 2：首先将基环树看做若干普通树根节点相连成环的结果，则对于所有点 $f$ 的转移不变，对于所有白点 $g$ 的转移不变。问题集中在如何求出黑点 $g$ 的转移。
- 从一个黑点 $u$ 向上走，第一步会走到另一个黑点（环上两个父亲之一），接下来可能走到黑点的子树中，也可能继续在环上走，需要分别考虑。首先钦定走的方向，顺时针逆时针概率均等，因此初始化 $P=0.5$；接下来，按走的顺序枚举环上的 $i$，有以下转移（$nxt_i$ 表示按当前方向环上的下一个点）： $g_u=\sum\limits_{i}P_i\times(w+\dfrac{f_is_i}{s_i+1})\\ P_{nxt_i}=\dfrac{1}{s_i+1}P_i$
- 注意如果走完了整个环，则在环上最后一个点处只能往其子树走，需要特殊考虑。
- 实现时要记录环上都有哪些点，这些点的前驱后继，在环上的编号等方便转移。
P4271 [USACO18FEB] New Barns P
- LCT 一遍写过，记之。
- 并查集维护每个连通块直径的端点，加入新点时用 LCT 更新连通块的形态，同时 split 出新点到原直径两端的距离，考虑是否更新。
P7963 [NOIP2021] 棋局
- 终于补完了 NOIP 的题。
- 自己理解+写完+调完用了大概 8~9h，写了 9kb 的代码。
- 32pts 的暴力还是比较好写的：对于每个新加入的棋子暴力 bfs 即可。
- 正向添加棋子相当于断开棋盘的一些点从而改变棋盘的连通性，不好维护，因此考虑倒序处理询问，改为删除棋子让棋盘连通，则问题变得好处理了许多。
- 连通性问题首先考虑到并查集。一个 naive 的想法是暴力查询 1 类边，用并查集维护 2、3 类边，对于第 2 类边考虑最远能延伸到哪，对于 3 类边维护连通块和连通块边缘可以吃到的棋子。但这样做是错误的：第 2 类边的统计和第 3 类边的统计会发生重复。
- 去重是本题的难点。我们先统计 3 类边，在统计 2 类边时将重复统计的删掉。这时候我们不能只用并查集存 3 类边形成的连通块，因为我们关系重复统计的节点的具体编号。发现 2 类边如果按行或列顺序排序后，编号是一段连续的区间，可以想到用线段树维护统计 3 类边时访问过的点横向和纵向的编号，这样可以通过线段树区间查询快速得到重复点的个数；去除棋子，合并 3 类边的连通块时，用线段树合并即可维护。
- 注意维护完连通块后，还要考虑连通块外可以吃掉的棋子。我们将每个棋子的等级离散化（这样每个棋子等级不同且不影响答案，可以借用上述查连通块编号时使用的线段树），对于在 3 类边连通块的边缘的两种颜色的棋子各开一棵线段树维护棋子的等级，每次查询等级 $\le lv_i$ 的棋子有多少个。对于 2 类边和 1 类边的吃子情况，可以暴力考虑四个方向，但需要注意判断其是否已经在统计 3 类边连通块边缘时被统计到。
- 最后答案减 1，因为不计算棋子自身的位置。
P3674 小清新人渣的本愿
- bitset 练手好题，用 bitset 维护加减法是否存在合法，以减法为例，答案就是 (b & (b >> x)).any()。bitset 的单点修改用莫队。乘法暴力枚举约数。
AGC032C Three Circuits
- 注意三个环覆盖了整个图，所以整个图一定是欧拉回路，每个点的度数一定是偶数。
- 其次，设 $d$ 为最大度数，有以下情况需要讨论：
1. $d\ge 6$ 一定合法，$d=2$ 一定不合法；
2. $d\ge 4$ 且只有一个点度数为 $4$，一定不合法；有三个点以上度数为 $4$，一定合法；
3. 否则讨论是否为两个度数为 $4$ 的点之间有 $4$ 条链连接的情况，若不是则合法。
P4126 [AHOI2009] 最小割
- 最小割必经边和可行边的判断。将残量网络缩点成 DAG，只有这个 DAG 上且满流的边可以被割掉。而这些边如果有直接连通 S 和 T 的则为必经边。
CF622F The Sum of the k-th Powers
- 可以严谨证明原式为 $k+1$ 次多项式。
- 考虑拉格朗日插值，预处理前缀后缀连乘积可以做到 $\mathcal O(k)$。
CF1202F You Are Given Some Letters…
- 设总共循环 $p$ 次，每次循环用到 $c_a$ 个 a，$c_b$ 个 b，那么合法的 $k$ 满足 $k=\lfloor\dfrac{n}{p}\rfloor$ 且 $c_a+c_b=k$。
- 考虑对于一个确定的 $p$ 必须满足的条件，整理可得 $\lceil\dfrac{a}{p+1}\rceil\le c_a\le\lfloor\dfrac{a}{p}\rfloor\\$ $\lceil\dfrac{b}{p+1}\rceil\le c_b\le\lfloor\dfrac{b}{p}\rfloor$
- 可以枚举 $p$，再用整除分块优化一下即可。
P7116 [NOIP2020] 微信步数
- 比 NOIP2021 T4 可做了不少。
- 发现从每个点开始考虑不好实现，可以改成移动整个高维区域，每一步移动后剩下没有出界的格子为这一步的总贡献；如果走一轮回到了起点，且还有格子没有出界，则为 -1（这一步当时考场上就想到了）。
- 设每一步走完后第 $i$ 维剩下的区间为 $[l_i,r_i]$，则 $\prod(r_i-l_i+1)$ 即为这一步产生的贡献。暴力模拟直到所有格子出界，期望得分 45。
- 考虑优化。发现第一轮走过后，剩下的格子每一轮的在每个维度上的偏移量是确定的，即每个维度上还合法的点数与轮数成一次函数关系。设 $w_i$ 为当前第 $i$ 维的贡献，$T$ 为最大轮数，则我们要求的是 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{T}\prod\limits_{k=1}^{m}\max(0,w_k)$。内层的 $\prod$ 可以暴力求系数，展开成一个 $m$ 次多项式 $f(x)$，然后对于每项的 $a_ix^k$ 只需要求出 $\sum\limits_{x=1}^{T}x^k$ 即可。可以按照 CF622F 的做法，但没必要：$\le 3$ 的直接套公式，$>3$ 的可以暴力预处理。总时间复杂度 $\mathcal O(nk^2)$。
P3295 [SCOI2016] 萌萌哒
- 学到了 ST 表的另类应用。
- 可以类似线段树打标记的形式，将每个区间先拆成 $\log n$ 个小区间进行并查集合并，最后一起下传，下传的形式与倍增类似。
2022.3.4 常州集训 T2 algebra
- 题意：给定矩阵 $A$，问是否存在正整数 $p$ 使得对于任意正整数 $k$ 都有 $A^k$ 中任意元素不大于 $p$。
- 将题目中的矩阵视为邻接矩阵，原题要求的就是该图是否有环。拓扑排序即可。
LOJ #6101 「2017 山东二轮集训 Day1」第二题
- 是的，「第二题」就是这个题的题目名称。
- 考虑找出最低点，然后递归考虑两侧，可以建立一棵笛卡尔树。统计答案时先将子节点的贡献统计完毕，再用总的减去子节点的去计算父亲处的贡献。
LOJ #6100 「2017 山东二轮集训 Day1」第一题
- 「第一题」。
- 对于每个位置维护出最远能到的右端点，可以通过维护前缀和 $s_{0/1,i,k}$ 表示前 $i$ 个数的第 $k$ 位存在多少次 $0\rightarrow 1/1\rightarrow 0$ 的情况，二分判断这个区间是否有 $1\rightarrow 0\rightarrow 1$ 或 $0\rightarrow 1\rightarrow 0$ 的情况，如果没有则说明这是一个合法的区间。
- 将所有左右端点维护完毕后，用可持久化线段树维护区间加区间求和，通过标记永久化实现。
P2048 [NOI2010] 超级钢琴
- 异或粽子的主席树版本。
- 主席树查前缀和一段区间的第 $k$ 大，将每个左端点对应的第一大区间扔进堆中，取出堆顶后再放入对应左端点排名下一位的区间。这样贪心地取一定最优。
S2OJ #1328 GCD
- 先考虑如果题目中的 $f$ 是斐波那契数列我们怎么做。首先，$\gcd(af_i+bf_{i+1},cf_i+df_{i+1})$ 可以通过辗转相减变化成 $\gcd(af_i+bf_{i+1},cf_i)$ 的形式。由 $\gcd(f_i,f_{i+1})=1$，我们可以进一步转化为求 $\gcd(af_i+bf_{i+1},cf_i)$。$\gcd(b,f_i)$ 可以矩阵快速幂求出，设为 $g$，则有如下式子： $\begin{aligned} &\gcd(af_i+bf_{i+1},cf_i)\\ =\ &g\cdot\gcd(\dfrac{af_i+bf_{i+1}}{g},\frac{cf_i}{g})\\ =\ &g\cdot\gcd(\dfrac{af_i+bf_{i+1}}{g},c)\\ =\ &g\cdot\gcd(\dfrac{af_i+bf_{i+1}\pmod{g\cdot c}}{g},c) \end{aligned}$
- 本题的递推式为 $f_i=9f_{i-1}+12f_{i-2}$，可以发现 $\gcd(f_i,f_{i-1})=3^{\lfloor\frac{n}{2}\rfloor}$，计算结果的时候乘进去，快速幂求 $f_i$ 的时候等价于成原转移矩阵平方后每项除以 $3$，即 $A=\begin{bmatrix}31 & 36\\3 & 4\end{bmatrix}$。
P2495 [SDOI2011] 消耗战
- 虚树 dp 板子。虚树的思想是每次树上只询问需要用到的点，忽略不需要重复计算的点，可以将复杂度优化到与所有询问的点集大小之和级别。建虚树时用单调栈考虑 dfn 序，将需要维护信息的点与它们所有的 LCA 加入虚树中。
- 转移很简单，考虑是否切断当前点到父亲节点的边在虚树上进行 dp 即可。
CF1110G Tree-Tac-Toe
- 首先发现黑子不可能赢。考虑弱化题目限制，初始所有点均未染色如何做。可以分情况考虑：如果有度数 $\ge 4$ 或度数 $=3$ 但至少两条出边都不是叶子节点的点，则白子必胜。在剩下的情况中，还有一种树的形态白子必胜，如下图：
  A D
  \ /
  C1-C2-...-Cn
  / \
  B E
- 不难发现 $n$ 为奇数时白子可以第一步下 C2 来获得必胜策略。
- 再考虑有白子被涂色的情况。下图说明了将一个位置涂白等价于在该位置下挂一个分叉：
  W -> A
  |
  B
  / \
  C D
- 不难发现，若 ABCD 初始均为空，则白棋下 A 后黑棋必须下 B，此时 A 被涂白且轮到白棋落子。
S2OJ #331 代数几何
- 大型结论+贪心。
- 环上错位 $k$ 相当于形成 $\dfrac{n}{\gcd(n,k)}$ 个置换环，排序后每个环上填原序列的连续一段一定最优，环上要从大往小放，大的放中间。
S2OJ #332 几何考试
- 暴力做法是 $\mathcal O(n^2)$ 枚举每一对，统计贡献。考虑在线段树上完成这个统计贡献的过程，可以先将所有线段按左端点第一关键字、右端点第二关键字排序，然后倒序扫一遍，将左端点相同的一起计算贡献，再一起插入线段树（具体做法见下），统计所有当前线段右侧的线段对当前线段的贡献；同理再正序扫一遍，统计所有当前线段右侧的线段对当前线段的贡献。在这里我们忽略了左端点相同的线段两两间的贡献，最后加上即可。
- 如何用线段树维护呢？具体来说，线段树每个节点存下了该位置上累加的二次函数系数，区间修改时为二次函数的叠加，查询时单点查询当前线段右端点对应的函数，再代入该函数所对应的未知量求出函数值进行贡献。查询时右端点所对应的函数是因为本质上之前加入的每条线段都是对在一个特定区间的右端点进行了函数的叠加贡献。
- 注：以下“线段 $1$”，“线段 $2$”，分别指代区间 $[l_1,r_1],[l_2,r_2]$，$s_1,s_2$ 指在对应区间内均匀随机的一个取值。
- 先考虑倒序，即从右往左插入线段，统计贡献的过程。
- 设线段 $1,2$ 满足 $l_1>l_2$，分相交和包含两种情况考虑：
  - 相交，即 $l_1< r_2< r_1$，此时可以统计 $s_1>s_2$ 的概率，用 $1$ 减去概率则为线段 $2$ 期望增加的排名。不难发现，有 $P=\dfrac{(r_2-l_1)^2}{2(r_1-l_1)(r_2-l_2)}$。$\dfrac{1}{r_2-l_2}$ 我们在询问时可以单独乘上，因此以 $r_2$ 为未知量，令 $x=r_2$，在线段树上 $[l_1,r_1]$ 这段区间加上 $\dfrac{(x-l_1)^2}{2(r_1-l_1)}$ 这个二次函数的系数。
  - 包含，即 $l_1< r_1\le r_2$，还是统计 $s_1>s_2$ 的概率，有 $P=\dfrac{r_1-l_1}{2(r_2-l_2)}+\dfrac{r_2-r_1}{r_2-l_2}$，我们仍然可以提出 $\dfrac{1}{r_2-l_2}$ 并以 $r_2$ 为未知量，在线段树 $[r_1+1,+\infty)$ 上加上 $x-\dfrac{l_1+r_1}{2}$。注意这里的贡献区间与相交的情况不同。因为变量和从原式中提出单独计算的部分相同，上述信息可以在同一棵线段树上维护。
- 再考虑一遍从左向右添加线段时新线段增加的排名期望：
- 设线段 $1,2$ 满足 $l_1< l_2$，还是分相交和包含两种情况考虑：
  - 相交，即 $l_2< r_1< r_2$，此时只有 $s_1,s_2\in[l_2,r_1]$ 才有可能使线段 $2$ 的排名增加，增加的期望 $E=\dfrac{(r_1-l_2)^2}{2(r_1-l_1)(r_2-l_2)}$，在线段树上维护 $\dfrac{(r-x)^2}{2(r-l)}$，$x=l_2$，此时 $a=\dfrac{1}{2(r-l)},b=-\dfrac{r}{r-l},c=\dfrac{r^2}{2(r-l)}$，在统计时乘上 $\dfrac{1}{r_2-l_2}$。贡献区间是 $[r_1+1,+\infty)$，但扫过该线段右端点时就要清除这个贡献（见下）。
  - 包含，即 $l_2< r_2\le r_1$，则只有 $s_1\in[l_2,r_1]$ 时有可能使线段 $2$ 的排名增加。
    - $s_1\in[l_2,r_2]$ 时，期望 $E=\dfrac{r_2-l_2}{2(r_1-l_1)}$；
    - $s_1\in(r_2,r_1]$ 时，期望 $E=\dfrac{r_1-r_2}{r_1-l_1}$。
    - 这时我们将上述的两个式子按 $l_2,r_2$ 分一下类，就可以用两棵线段树分别维护以 $l_2$ 为未知量的函数 $-\dfrac{x}{2(r_1-l_1)}$ 和以 $r_2$ 为未知量的函数 $\dfrac{2r_1-x}{2(r_1-l_1)}$。注意这个以 $l_2$ 为未知量的线段树不能和上述相交的情况合并，因为这里不需要统计时乘 $\dfrac{1}{r_2-l_2}$ 的系数。
    - 上述函数的贡献区间为 $[l_1,r_1]$。
  - 从左往右会遇到一个问题：当当前左端点扫过了某条之前的线段的右端点时，该线段就无法继续贡献。因此我们要在每条右端点处清除该线段对之后的贡献，将上述加入线段树的系数取负再加入一次即可。
- 我们上述的所有处理都是将左端点相同的线段放在一起进行的，因此最后还要统计左端点相同的线段两两间的贡献。这个比较简单，列出式子维护前缀和后缀和即可，这里不再赘述。
- 最后的最后，不要忘了排名从 $1$ 开始，答案要加 $1$。时间复杂度为 $\mathcal O(n\log n)$。
- 如果式子有错请轻喷。另外，强烈建议自己独立推导一遍以上全部内容。
2022.3.7 常州集训 T1 rsa
- 题意：$n=pq,x^c\equiv m\pmod{n},\gcd(c,(p-1)(q-1))=1$，$p,q$ 是质数且 $q-p\le 3\times 10^5$。
- 发现 $\varphi(n)=(p-1)(q-1)$ 且 $x^{\varphi(n)}\equiv 1\pmod{n}$。$c$ 与 $\varphi(n)$ 互质，则必然存在一个 $t$ 满足 $ct\equiv 1\pmod{\varphi(n)}$。那么显然 $x^{ct}\equiv x^1\equiv m^t\pmod{n}$，快速幂即可。
- 问题简化为如何找到 $p,q$。可以设 $q=p+d$，则 $p(p+d)=n$，解得 $p=\dfrac{\sqrt{d^2+4n}-d}{2}$。当 $p$ 随机且 $p,q$ 间无其它质数时，可以直接枚举 $d$。否则设 $k=\sqrt{d^2+4n}$，得到 $k^2=d^2+4n$，直接从下界 $2\sqrt{n}$ 枚举 $k$ 就能够跑过。
2022.3.8 常州集训 T1 permutation
- 题意：定义序列 $p$ 的一步变换为 $p_i=p_{p_i}$，求对于所有长度为 $n$，最大值为 $n$ 的 $n^n$ 种不同序列，每个序列能够由多少个不同的 $1\sim n$ 的排列经过有限次变换得到。输出 $n^n$ 种不同序列的合法排列个数和。$n\le 2\times 10^5$。
- 递推式 $f_n=\sum\limits_{i=1}^{n}f_{n-i}g_{i}\dbinom{n-1}{i-1}(i-1)!$，其中 $g_i$ 代表大小为 $i$ 的置换环能贡献的答案，有 $g_i=(i+1)^{i-1}$；组合数乘上 $\dbinom{n-1}{i-1}$ 因为可以考虑向已有选择插入数的过程，再为防止算重钦定一下第一个位置放什么；最后 $(i-1)!$ 是置换环的圆排列个数。
- 分治 NTT 解决，将原式化为 $f_n=(n-1)!\sum\limits_{i=1}^{n}\dfrac{f_{n-i}}{(n-i)!}g_i$ 即可。~~跑得比 exp 快多了。~~
S2OJ #202 完全平方数
- 考场降智了。设 $a+b=\dfrac{n}{2},a=gx,b=gy$，显然有 $ab=g^2xy$。枚举 $g$ 求所有 $x^2+y^2=\dfrac{n}{2g},x\perp y$ 的正整数解即可。另外，可以只找 $\mu(g)=0$ 的 $g$ 进行枚举并取消 $x\perp y$ 的条件，可以优化复杂度。
S2OJ #203 素数
- 显然用网络流跑二分图最大匹配。但是 $a_i=1$ 是本题处理上的难点。
- 将所有 $a_i$ 奇偶分类，和为质数的连边，第一遍排除掉 $1$ 跑最大匹配为 $x$；加进去剩下的 $1$ 跑最大匹配为 $y$，可以计算出有多少对 $1$ 自己与自己匹配。注意最后多出的操作次数可能选择有出边但不在最大匹配上的点，连边时预处理以下有多少点被连上了边即可。
S2OJ #204 广播
- 感谢这题让我学会了点分树。
- 建树时按 bfs 序插入 vector，倒序后在点分树上从 1 开始进行 bfs，每次取当前父亲 vector 中最后一个元素（最近的元素）更新答案后删去。重复这个过程直到所有点都被访问到。
- zx：点分树上的暴力复杂度一般都是对的。
2022.3.10 常州集训 T2 chess
- 题意：棋盘上只能在左上角填阶梯形，其中第 $i$ 行已经填了 $j$ 个格子对整体的贡献为 $a_ib_j$，求棋盘所有不同填法的贡献和。$n,m\le 5\times 10^5$。
- 不难发现如果单独计算某行某个位置的贡献，可以分别计算其右上和左下阶梯形状的方案乘积，即 $n$ 行 $m$ 列的网格有 $\dbinom{n+m}{m}$ 中不同的走法，对于每个点暴力计算可以得到 $\mathcal O(n^2)$ 的做法。
- 原式为 $\sum\limits_{i=1}^{n}a_i\sum\limits_{j=0}^{m}b_j\dbinom{n-i+j}{n-i}\dbinom{i-1+m-j}{i-1}$，可以将组合数拆开后令 $k=i-j$，原式可化为如下减法卷积的形式： $\sum\limits_{k}(n-k)!(m+k-1)!\sum\limits_{i-j=k}\dfrac{a_i}{(n-i)!(i-1)!}\dfrac{b_j}{j!(m-j)!}$
- 用 NTT $\mathcal O(n\log n)$ 碾过去就行了。
2022.3.10 常州集训 T1 sequence
- 题意：求序列 $a$ 删掉每个 $i$ 时能使得多少个 $a_j(j\neq i)$ 所在的 LIS 长度减小。$n\le 3\times 10^5$。
- DAG 上的支配树模板题。
- 在求 LIS 的过程中，后边的元素 LIS 长度增加依赖与前边的元素，由此形成了支配与被支配的关系。考虑建树，对于当前 $i$ 的 dp 值，我们找到其上一层编号最小/最大的节点找它们的 LCA 即为当前点支配树上的父亲。
CF1270H Number of Components
- 首先需要知道一个结论：序列上每个连通块必然是该序列的一个连续段。证明可以分类讨论。
- 发现如果我们枚举一个权值 $w$，将 $\ge w$ 的变成 $1$，$< w$ 的变成 $0$，则最终的合法序列形如 $11\cdots 100\cdots 0$。我们用权值线段树维护对于每个 $w$ 存在 $01$ 交替的次数，pushup 时向上更新最小值及最小值的个数（即，如果某值域区间只有 $1$ 次 01 交替则最小值个数为该值域区间的答案）。预处理时令 $a_0=10^6+1,a_{n+1}=0$，然后对于每对相邻的 $a_i,a_{i+1}$ 都将对应权值段加 $1$（因为 $w$ 在该权值段时 $a_i$ 和 $a_{i+1}$ 必有一个为 $0$，另一个为 $1$），并将 $a_i$ 处的出现次数加 $1$。修改时撤销掉原来 $a_{i-1},a_i$ 和 $a_i,a_{i+1}$ 之间的贡献，再用新权值加入贡献即可。
S2OJ #1355 如何优雅地送分
- 首先考虑 $2^{F(i)}$ 的意义。发现其在枚举 $i$ 的本质不同质因子的子集，可以考虑改为枚举这个子集 $k$，则恰好有 $\left\lfloor\dfrac{n}{k}\right\rfloor$ 个数字包含 $k$，即： $\sum\limits_{k=1}^{n}\mu^2(k)\left\lfloor\dfrac{n}{k}\right\rfloor$
- 考虑以下的推导过程： $\begin{aligned} &\sum\limits_{i=1}^{n}2^{F(i)}\\ =&\sum\limits_{i=1}^{n}\sum\limits_{d\mid n}\mu^2(d)\qquad&(1)\\ =&\sum\limits_{i=1}^{n}\sum\limits_{d\mid n}\sum\limits_{k^2\mid d}\mu(k)\qquad&(2)\\ =&\sum\limits_{k=1}^{n}\mu(k)\sum\limits_{k^2\mid d}\left\lfloor\dfrac{n}{d}\right\rfloor\qquad&(3)\\ =&\sum\limits_{k=1}^{n}\mu(k)\sum\limits_{i=1}^{\lfloor\frac{n}{k^2}\rfloor}\left\lfloor\dfrac{n}{ik^2}\right\rfloor&(4) \end{aligned}$
- 式子的后一项就是 $\sum\limits_{i=1}^{n}\left\lfloor\dfrac{n}{i}\right\rfloor$ 可以直接整除分块；注意到当 $k>\sqrt{n}$ 时 $\left\lfloor\dfrac{n}{k^2}\right\rfloor$ 为 $0$，所以 $k$ 枚举到 $\sqrt{n}$ 即可。时间复杂度 $\mathcal O(\sqrt{n}\log n)$。
- $(1)\rightarrow(2)$ 的过程证明如下：
- 考虑如果 $\mu^2(d)=1$，说明 $d$ 无平方质因子，$k$ 只能取 $1$ 且 $\mu(k)=1$；
- 否则 $\mu^2(d)=0$，在 $d$ 的所有本质不同的质因子 $p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ 中选择出一些 $a_i \ge 2$ 的相乘组成 $k$，若有 $m$ 个数可选，则枚举子集有 $2^m$ 种选法。设可选集合为 $S$，我们选择了 $T$ 集合，则有 $\sum\limits_{T\subseteq S}\mu(\prod\limits_{p_i\in T}p_i)$，可以将 $|T|$ 相同的用二项式定理合并一下，即 $\sum\limits_{i=0}^{|S|}(-1)^i\dbinom{|S|}{i}$，这个式子的值为 $0$。
S2OJ #1357 你猜是不是找规律
- 首先，一个排列是一个置换环的集合。排好序的排列每个置换环长度为 $1$，乱序的、长度为 $k$ 的置换环需要 $k-1$ 次操作将所有元素放回原位。考虑现在乱序的排列有 $t$ 个置换环，$k$ 次交换能够复原，这时共有 $t+k$ 个乱序的元素，$\dbinom{n}{t+k}$ 可以预处理下降幂解决。
- 我们对于选出来的 $t+k$ 个元素进行 dp。设 $f_{i,j}$ 为用了 $i$ 个元素，形成了 $j$ 个置换环，但钦定不能存在长度为 $1$ 的置换环的方案数，有 $f_{i,j}=(i-1)(f_{i-1,j}+f_{i-2,j-1})$。预处理后对于 $0$ 到 $k$ 输出答案即可。
P4827 [国家集训队] Crash 的文明世界
- 可以先用斯特林数推导原式： $\begin{aligned} &\sum\limits_{i=1}^{n}d_{u,i}^k\\ =&\sum\limits_{i=1}^{n}\sum\limits_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}\dbinom{d_{u,i}}{j}j!\\ =&\sum\limits_{j=0}^{k}\begin{Bmatrix}k\\ j\end{Bmatrix}j!\sum\limits_{i=1}^{n}\dbinom{d_{u,i}}{j}\\ \end{aligned}$
- 然后考虑 dp： $\begin{aligned} f_{u,i}=&\sum\limits_{v\in son_u}\dbinom{d_{u,v}}{i}\\ =&\sum\limits_{v\in son_u}\dbinom{d_{u,v}-1}{i}+\dbinom{d_{u,v}-1}{i-1}\\ =&f_{v,i}+f_{v,i-1} \end{aligned}$
- 剩下的就比较容易转移了。注意当前只是求出了以 $1$ 为根的答案，求所有的 $u$ 可以换根。
P6093 [JSOI2015] 套娃
- 简单贪心，将所有套娃按 $b_i$ 排序，再按顺序，每次贪心地套进去合法套娃中外径最大的即可。用 multiset 维护。
P3703 [SDOI2017] 树点涂色
- 深入理解 LCT access 操作的好题。
- 发现每次都染色到根类似 LCT 的 access，而每次新开一种颜色，代表着一个点到根节点的颜色数为要走的虚边条数 $+1$。初始每个点颜色不同，即所有边均为虚边。记 $d_u$ 为从 $1$ 走到 $u$ 不同的颜色数，2 操作树上差分，3 操作对于 $d$ 数组线段树维护区间最大值。
- 对于 1 操作，我们可以更改 access 的写法。考虑这一过程中一条虚链变成了实链，一条实链变成了虚链，等价于线段树上单点 +1/-1。但考虑到我们找的是原树的节点，因此我们还要暴力找到 splay 上最左侧的点。总体时间复杂度 $\mathcal O(n\log^2 n)$。
S2OJ #272 工作
- 将 $a_i$ 排序后，每次将最右端的 $k$ 个元素减 $1$。
- 但这样的问题是：减完后无法保证 $a$ 序列仍递增。可以找到左端点所在值域段的区间，并减这个区间靠左的一段，这样就保证了 $a$ 序列的单调性。
- 平凡的做法是树状数组上二分。时间复杂度 $\mathcal O(n\log^2 n)$。
S2OJ #266 大水题
- 倍增是解题的核心。
- 先对 $T$ 串建出 AC 自动机，跳 fail 边得到根到每个节点匹配了任意 $T$ 总共多少次。线段树上每个节点维护两个数组 $pos,val$，分别代表从 AC 自动机每个节点出发经过线段树当前节点所代表区间的 $S$ 串后到自动机上的节点位置和匹配的次数。
- 再考虑修改操作。每次做区间修改时，我们可以记下当前修改串倍增后的信息（在 AC 自动机 $u$ 节点走 $2^k$ 步到达的位置、贡献），线段树上修改时以这次询问的编号为标记，下传时直接将倍增数组复制到线段树完整的节点上（因为长度都是 $2$ 的整次幂）。
- 设 AC 自动机上有 $c$ 个节点，时间复杂度为 $\mathcal O((\sum|str|+|S|+Q)\times c\log|S|)$。
S2OJ #352 榜滚(ranklist)
- 省选原题的弱化版。设 $f_{S,i,j}$ 为当前公布成绩的队伍集合为 $S$，当前队伍想要成为榜一 $a_x+b_x-a_{\max}$ 合法的最小值为 $i$（$a_{\max}$ 为封榜前最大的 $a_i$），达到这个最小值时的 $\sum\limits_{x\in S} b_x$ 为 $j$。
- 状态设出来了转移就相对容易了。注意一个队伍的运气对其最少需要的过题数产生的影响。时间复杂度 $\mathcal O(2^nn^2m)$。
AGC032D Rotation Sort
- 发现一个数只可能被移动一次，或根本不移动。现在设 $f_i$ 为钦定当前第 $i$ 个数不移动，确定前 $i$ 个数状态后的最小值，枚举转移点 $j$，考虑将 $(j,i)$ 区间内的数 $> a_i$ 的右移，$< a_i$ 的左移。这样在最优转移点可以保证答案的正确性。
CF493E Vasya and Polynomial
- 为方便表述，下面用 $u,v$ 代指题目中的 $a,b$，$n$ 表示 $f(x)$ 的次数。
- 首先发现一个性质：对于任意满足条件的多项式 $f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n$，必然有 $a_i\le u$，可以分 $a_i=u$ 和 $a_i<u$ 讨论。
- $a_i=u$ 时，$f(x)$ 只有一项。如果 $n=0$ 则只有 $u=v$ 时有解；否则 $f(x)=a_nx^n$，存在满足条件的 $f(x)$ 当且仅当 $t=1$ 且 $u^{n+1}=v$。$u=1$ 时 $v=1$ 无穷多解，否则无解；$u>1$ 是枚举 $n$ 可以 $\mathcal O(\log n)$ 解决。
- $a_i<u$ 时，至多只有一个满足条件的 $f(u)=v$；感性理解，就是 $v$ 在 $u$ 进制下的表示形式唯一。这样就可以在 $u$ 进制下将 $v$ 分解，再带入 $t$ 检验是否满足 $f(t)=u$ 即可。
AGC005D ~K Perm Counting
- 将所有的数和空位置都看作点，将不合法的限制连边，形成了多条链。每条链不能选两个连续的点，统计时设 $f_{i,j,0/1}$ 为统计了 $i$ 个点，打破了 $j$ 次限制，$i-1$ 和 $i$ 这对点是否打破限制。最后容斥一下即可。
P1357 花园
- 首先状压时环形的限制可以通过枚举初始状态 $S$，最后求 $f_{n+m,S}$ 的和解决。这样我们就可以矩乘优化了。
- 我们矩乘时要同时转移所有的合法状态，所以不能用向量转移，因为会互相影响；初始将合法的 $S$ 在矩阵 $F_{S,S}$ 位置上赋为 $1$，最后求的就是 $\sum\limits_{i=0}^{2^m-1}F_{i,i}$。
S2OJ #251 蛐蛐国的修墙方案
- 找出所有置换环，二元环在原序列靠前位置放左括号必定合法，剩下的可以搜索每个置换环第一个位置填左括号还是右括号，然后交替填下去。一个很松的时间复杂度上界是 $\mathcal O(n2^{\frac{n}{4}})$。
S2OJ #248 跳蚤王国的宰相
- 首先以原树的重心为根，发现如果剪掉该重心大小总和 $\ge\dfrac{n}{2}$ 的子树并将它们直接安在另一个节点上，则该节点必然能够成为重心。
- 将重心 $rt$ 的所有 $son_{rt}$ 按子树大小从大到小排序，找到前缀和恰好 $\ge\dfrac{n}{2}$ 的位置。对于每个节点，如果前缀子树中包含了它，则将前缀中其它的子树接上，检验是否足够让根节点不再成为重心。否则检查前缀 $-1$ 是否满足条件。需要注意处理的细节和边界问题。
S2OJ #249 事情的相似度
- 首先求一段前缀的最长公共后缀就是在 SAM 的 parent 树上找到 $len_x$ 最大的 LCA。
- 考虑我们每次添加一个新的前缀，相当于从 parent 树的树根到当前前缀的结尾节点染上了一种新的颜色，这个过程本质上就是 LCT 的 access。用 LCT 维护时需要子树颜色覆盖，同时用树状数组维护后缀最大值。
2022.3.17 常州集训 T1 trans
- 给定序列 $a$，每次操作选择 $i,j$ 使得 $a_i\leftarrow a_i+a_j$，构造方案使得 $a$ 序列每个元素均相等。$n\le 6\times 10^4$，要求操作数 $m\le 10^6$。
- 两种思路：一个是想办法凑出 $2^k$ 并用这个数将所有其它数也消成 $2$ 的整次幂的形式，可以找到一对 $(i,j)$ 使得 $\gcd(a_i,a_j)=1$，然后让两个元素辗转相减。有了 $2^k$ 之后可以先将其它所有元素补全末尾的 0，然后考虑 lowbit 进行修改。
- 另一种是将 $a$ 奇偶分类，将所有非严格最小的奇数加上最小的奇数，再将最小的翻倍，这样所有数都成了偶数，将所有数字除以 $2$，重复以上过程直至序列满足条件。
P3643 [APIO2016] 划艇
- 很自然地想到设 $f_{i,j}$ 为前 $i$ 所学校钦定第 $i$ 所参赛，派出 $j$ 艘划艇的方案数，但这样做依赖值域。
- 可以将值域离散化成一个个区间，计算第 $i$ 所学校派出的划艇数落在离散化后第 $j$ 个区间的方案数。
- 我们可以构造证明从区间 $[0,L]$ 中取 $n$ 个数，要求所有非零数严格递增的方案数为 $\dbinom{L+n}{n}$。回到原问题的转移上，若上一个有学校的区间为 $k$，前 $p$ 所学校不在区间 $j$ 中，$m$ 为 $p+1\sim i$ 中能选的学校数量，方案数为 $\dbinom{m+L-1}{m}$，$L$ 为 $j$ 区间的长度。
- 前缀和优化转移即可。注意要改变枚举顺序。
S2OJ #280 Deck
- 线段树优化建图和 2-SAT 结合的板子。对于每个点预处理出 3 操作管辖的最大区间，线段树上连边即可。
- 注意实现细节，需要将操作离线，然后 dfs 统一连边。
S2OJ #278 走
- 奇怪的搜索 + 剪枝。用 bitset 记录当前的状态，把向左/向右跳转化成格子整体的移动，压缩合法状态数，记忆化搜索即可。
S2OJ #268 抽鬼牌
- 容斥，显然设 $f_{i,j}$ 为前 $i$ 个数，分 $j$ 段，但两段有可能连在一起形成一大段，所以可以在状态中记录 $k$ 代表中间有几段连成了一大段，容斥系数 $(-1)^k$。
- 优化状态的设计方式，设 $f_{i,j,0/1}$，$i,j$ 含义不变，$0$ 代表当前段已经完整地结束，$1$ 代表当前段没有结束，要和后面加入的元素结合形成一大段。$f_{i,j,1}$ 可以理解为当前段伸出一个与下一段连接的接口，即上述 $f_{i,j,k}$ 中的 $k$ 加 $1$。前缀和优化转移可以做到 $\mathcal O(n^2)$。
S2OJ #1366 同桌的你
- 首先如果对于一棵树来说，容易设 $f_{i,0/1}$ 为当前点是否选择了与子节点连边的最大权值，直接转移。输出方案直接记录每个点选择时的前驱节点即可。
- 题目中给定了一个内向基环森林，我们可以对于每棵基环树分别进行考虑。一般的套路是依次断掉环上每一条边跑树形 dp，但在这个题的限制下，我们只需要任选一条边，钦定其是否存在，跑树形 dp 即可。注意到题目给定的内向基环树有很好的性质，我们可以直接将其有向边反向，在树上直接跳就能找到环和环上的边。断开环上相邻的两条边，每条边跑一遍树形 dp，累加答案。
S2OJ #1367 Fair Photography
- 第一次手写 hash table。
- 大致思路就是枚举颜色的集合，哈希表记录左端点，左右端点代表合法区间当且仅当两个端点每种颜色的前缀做差后相等（例如 6 4 2 3 和 8 6 4 5 均可以转化为 4 2 0 1）。时间复杂度 $\mathcal O(2^{\max b_i}n\max b_i)$，卡一卡就过了。
S2OJ #1368 Florida
- 不妨设我们将所有元素分为了 $S,T$ 两个集合，且 $D(S)\le D(T)$。分三种情况考虑二元组 $(i,j)$ 的限制：
  - $T_{i,j}\le D(S)$，$(i,j)$ 没有任何限制；
  - $D(S)< T_{i,j}\le D(T)$，$i$ 和 $j$ 不能同时在 $S$ 中，即限制条件为 $t_i\or t_j$；
  - $T_{i,j}> D(T)$，$i$ 和 $j$ 不能放在一起，即限制条件为 $(t_i\or t_j)\and (\lnot t_i\or\lnot t_j)$。
- 显然这些限制是一个 2-SAT 问题，可以在 $\mathcal O(n^4\log n^2)$ 的时间内解决。
- 考虑优化，发现 $D(T)$ 有用的取值只有 $\mathcal O(n)$ 种，证明可以考虑在完全图上找最大生成树，如果从大到小枚举权值，连边表示 $T_{i,j}> D(T)$，当前边的两个端点已经连通且连上这条边后不破坏二分图的性质，则这条边没有必要统计。这样复杂度优化到了 $\mathcal O(n^3\log n^2)$，可以通过本题。
S2OJ #1358 Yist
- 暴力是 $\mathcal O(\sum\text{deg})$ 的，对于每个点统计一轮贡献 $w_i$，等比数列求和，若 $i$ 在 $s$ 中出现了 $c_i$ 次，则总贡献为 $\dfrac{2^{c_i}w_i}{2^{c_i}-1}$，特判 $c_i=0$ 的情况。
- 根号分治将所有点按度数是否 $\ge\sqrt{n}$ 分为大度点和小度点，小度点直接给周围点加贡献，大度点的贡献在统计其相邻小度点的时候加上。
S2OJ #1359 Ernd
- 对 $S$ 建后缀自动机，在末尾添加字符等于沿着转移边走，在开头添加字符可能停留在当前状态，也可能走到 parent 树上的某个儿子。每次操作对答案的贡献是当前节点 $\text{endpos}$ 集合的大小。为使贡献和最大要尽可能留在当前状态。
- 将 parent 树边反向，和原 SAM 的转移边一起构成一个有向图 $G$，在 $G$ 上进行 dp。令 $f_u$ 为从起点出发走到 $u$ 的最大权值和，有转移 $f_v=\max(f_u+siz_v\cdot(len_u-len_v))$，取整串代表的节点 $p$ 的 dp 值即为答案。时间复杂度 $\mathcal O(n)$。
CF913F Strongly Connected Tournament
- 简述题意：给定 $n$ 个点，在每对点之间连边，若 $i< j$ 则有 $p$ 的概率从 $i$ 连到 $j$，$1-p$ 的概率从 $j$ 连到 $i$。连完边后将完全图缩点，对每个强连通分量重复执行上述过程直到无法操作为止。求期望连边的条数。$n\le 2000$。
- DP。设 $f_{i}$ 为 $i$ 个点的期望连边条数，$f_n$ 为答案。我们考虑在 $i$ 个点的完全图上枚举最后一个强连通分量的大小 $j$，即其它 $i-j$ 个点分别连向了这 $j$ 个点，总共确定了 $j(i-j)+\dfrac{j(j-1)}{2}$ 条边。有如下转移：
- 其中，$g_i$ 表示 $i$ 个点能恰好组成一个强连通图的概率，$h_{i,j}$ 表示在 $i$ 个人中恰好有 $j$ 个人输给了剩下 $i-j$ 个人的概率。注意到这个转移方程中 $f_i$ 会转移到自己，移项就好了。
- $g_i$ 的转移就是简单的容斥，即没有一个点集输给了剩下的所有点：
- $h$ 的转移考虑每次新加入一个点时，如果属于输的那 $j$ 个点，则需要输给 $i-j$ 个点；否则需要赢 $j$ 个点：（注意边界 $h_{i,0}=1$，无实际意义，只是方便转移）
- 时间复杂度 $\mathcal O(n^2)$。
ARC087D Squirrel Migration
- 对每条边统计贡献。若切断一条边，会形成两个连通块 $S_1,S_2$，不妨设 $\abs{S_1}\le \abs{S_2}$，则一条边最多被经过 $2\abs{S_1}$ 次，取重心为根可以最大化权值和。
- 问题转化成了对于所有的 $i$，$p_i$ 和 $i$ 不在同一子树内的方案数。可以容斥，设 $f_i$ 为钦定 $i$ 个点不满足条件，剩下点无限制的方案数。在一个大小为 $s$ 的子树中钦定 $i$ 个点的 $f_i=\dbinom{x}{i}x^{\underline{i}}$，再 $\mathcal O(n^2)$ 背包合并一下即可。
AGC015F Kenus the Ancient Greek
- 以下 $F_i$ 代表斐波那契数列第 $i$ 项，其中 $F_0=F_1=1$。
- 首先最大值必然可以取一对 $(F_i,F_{i+1})(F_i\le x,F_{i+1}\le y)$ 得到。现在我们试图计数。我们称一个能操作 $k$ 次的 $(i,j)$ 为 a good pair of $k$，将 $k$ 相同的这些 good pair 进行一次 $\gcd$ 后的数对称为 excellent pair of $k$，一个 $(i,j)$ 的 excellent pair 代表了所有 $(i,j+ki)(k\ge 0)$ 的 good pair。
- Excellent pair of $k$ 只有 $k$ 个，有 $k-1$ 个可以从 excellent pair of $k-1$ 得到，即 $(i,j)\rightarrow (j,i+j)$。还有一个是 $(F_{k+1},F_{k+1}+F_{k-1})$。这样我们可以 $\mathcal O(\log^2\max x)$ 找到所有的 excellent pair，$\mathcal O(\log\max x)$ 时间处理每组询问。
P3293 [SCOI2016] 美味
- 按位贪心，从高位到低位考虑 $a_i+x$ 和 $b$ 的异或值。假设当前处理到了 $b$ 从低到高数的第 $k$ 位，这一位是 $b$，那么我们只需要查找是否询问的区间 $[l,r]$ 内是否存在一个 $a_i+x$ 满足其第 $k$ 位为 $\lnot b$，换言之，如果到目前为止累加的答案为 $c$，那么就是查 $[l,r]$ 中是否有数在 $[c-x,c-x+2^k-1]$ 中，主席树可以轻松解决这个问题。
P5321 [BJOI2019] 送别
- 可以用平衡树大力分类讨论，但下面介绍更简洁的 LCT 写法。
- 将每个点拆成四个方向单独考虑，对每个点的每个方向找出按题目要求走能走到的下一个位置及方向记为 $\text{next}$，所有点的 $\text{next}$ 构成了一些有向环，每个环断掉一条边后用 LCT 维护。我们维护从每个点出发四个方向的墙是否存在，修改墙的时候先断掉原有指向当前点的边，再根据新的连通性重新连边。注意一个环只断一条边，LCT cut 的同时要连上一条新边。
- 由此，修改操作只需要修改墙的状态，并且改变两个端点的连通性。
- 查询时先找到从 $s$ 和 $t$ 走半个单位长度后到达的位置，再断掉 $t$ 与 $\text{next}_t$ 之间的边，查询 $s$ 到 $t$ 的路径长度即为答案。
ARC096E Everything on It
- 容斥，设钦定 $i$ 个元素打破限制的方案数为 $F_i$，答案即为 $\sum\limits_{i=0}^{n}(-1)^iF_i$。
- 剩下 $n-i$ 个元素无限制，能组成 $2^{n-i}$ 个子集，故有 $2^{2^{n-i}}$ 种选法；再设 $f_i$ 为 $i$ 种元素每种选不超过 $1$ 次的方案数，显然我们可以枚举将这些元素扔掉一些后划分进 $j$ 个集合中，等价于划分出 $j+1$ 个集合（把扔掉的看作一个集合，加一个元素 $0$ 保证垃圾堆非空），即第二类斯特林数 $\begin{Bmatrix}i+1\ j+1\end{Bmatrix}$。最后考虑将 $n-i$ 个数插入这 $j$ 个集合中，总方案要再乘上 $2^{n-i}$ 个集合是否要插入这 $j$ 个集合的某一个中的方案数，即 $(2^{n-i})^j$。综上，本题答案为
P6860 象棋与马
- $p(i,j)=1$ 当且仅当 $i\perp j$ 且 $i+j\equiv 1\pmod{2}$。
- 不妨令 $a\ge b$，分奇偶讨论 $a$ 的贡献：若 $a$ 是偶数贡献为 $\varphi(a)$，$a$ 是奇数贡献为 $\dfrac{\varphi(a)}{2}$，因为此时小于 $a$ 且与 $a$ 互质的数必然一奇一偶成对出现，我们只算偶数。
- 设答案为 $S(n)$，有 $S(n)=2\sum\limits_{i=1}^{n}w_i$，其中 $w_i$ 是 $i$ 的贡献，乘 $2$ 是因为刚才钦定了 $a\ge b$。经过推导可以得到 $S(n)=\sum\limits_{i=1}^{n}\varphi(i)+S(\left\lfloor\dfrac{n}{2}\right\rfloor)$，前一半杜教筛，后一半递归处理。时间复杂度 $\mathcal O(n^{\frac{2}{3}}\log n)$。
P3644 [APIO2015] 八邻旁之桥
- $k=1$ 的时候有经典结论：选中位数一定最优。
- $k=2$ 时我们将所有线段按中点从左到右排序，取左边的一部分走左侧某位置的桥，剩下的走右侧某位置的桥。本质上是动态中位数问题，用对顶堆维护。最后取所有对应前缀后缀之和的最小值。
AGC010E Rearranging
- 所有不互质的数对在安排好后相对位置就不会再变化，所以将所有 $\gcd(a_i,a_j)> 1,a_i\le a_j$ 的 $(i,j)$ 连一条 $i\rightarrow j$ 的有向边，这个 DAG 拓扑排序后可以得到一组合法解。
- 后手希望字典序最大，所以拓扑排序用优先队列；先手希望将这个 DAG 重定向使得字典序最小，可以将最小的卡在前面，按点权从小到大连还没有被遍历过的点。最后跑拓扑排序输出答案。
AGC007E Shik and Travel
- 首先二分答案将原题转化为判定性问题，令 $k$ 为当前二分的权值。显然进入一棵子树后必须遍历完所有叶子节点才能离开。
- 这里有一种不是很常见的、与判定性相关的 dp 思路。设 $f_u(a,b)$ 表示 $u$ 的子树是否存在一个从 $u$ 到第一个叶子节点距离为 $a$，从最后一个叶子节点回到 $u$ 的距离为 $b$，全程合法且遍历完整棵子树的方案。从 $u$ 的左右儿子进行转移，设 $u$ 到左右儿子的距离分别为 $d_{u,l}$ 和 $d_{u,r}$，有转移式 $f_u(a,b)=f_l(a-d_{u,l},i)\and f_r(j,b-d_{u,r})(i+j+d_{u,l}+d_{u,r}\le k)$。
- 需要进行优化。发现当存在 $f_u(x,y)$ 和 $f_u(x’,y’)$ 且 $x\le x’,y\le y’$，那么 $f_u(x’,y’)$ 一定不优，可以忽略掉。将 $f_u$ 的状态按照 $x$ 递增排序，则 $y$ 必然递减。向上合并时增加的状态数为左右子树状态数最小值的二倍，因为可以左右子树交换再转移一次。对于每个 $f_l(a,b)$ 找 $f_r(a’,b’)$ 用双指针维护。
CF618G Combining Slimes
- 题目允许精度误差，因此我们可以大致认为不可能出现 $\delta\ge 40$ 的权值。
- 期望 dp，设 $a_{i,j}$ 为用 $i$ 个格子出现 $j$ 的概率，有 $a_{i,j}=a_{i-1,j-1}\cdot a_{i,j-1}$，再定义 $A_{i,j}$ 为用 $i$ 个格子，钦定最左边出现 $j$ 且仅出现这一个 $j$ 的概率，有 $A_{i,j}=a_{i,j}\cdot(1-a_{i-1,j})$。
- 现在我们可以算答案的期望了。令 $f_{i,j}$ 为最右边的 $i$ 个数中最左边为 $j$ 时，这 $i$ 个数期望的和，不考虑 $1$ 的特殊情况，有：
- 分母上除了一个 $\sum\limits_{k=1}^{j-1}A_{i-1,k}$ 是因为我们要求的是分子上的概率在这个特定的可选集合中相对的概率，这里除掉的就是可选集合的大小。
- 我们要特殊处理 $f_{i,1}$ 因为 $1$ 左边只能放 $2$。与 $a,A$ 类似地记录 $b_{i,j}$ 为最左边放 $2$ 时用 $i$ 个格子出现 $j$ 的概率，$B_{i,j}$ 为 $i$ 个格子唯一出现 $j$ 的概率。转移与 $a,A$ 的类似。
- 答案为 $\sum\limits_{i=1}^nf_{n,i}A_{n,i}$，$n\ge \delta$ 时可以将 $n$ 替换为 $\delta$，改写后就可以矩阵快速幂求解了。
P4180 [BJWC2010] 严格次小生成树
- 本质上就是找到一条边使得增量 $\Delta> 0$ 且最小。
- 对于每条不在生成树中的边，连接后找环上原树边的最大值，如果新边权值等于最大值就找严格次大值。可以倍增维护，也可以 LCT。
P4331 [BalticOI 2004]Sequence 数字序列
- 我们将所有 $a_i,b_i$ 减去 $i$，这样不影响最后答案且可以将原问题弱化成要求 $b$ 单调不降。发现如果 $a$ 单调递增，$b_i=a_i$ 最优；如果 $a$ 单调递减，$b_i=a_{\left\lfloor\frac{n}{2}\right\rfloor}$ 最优。我们可以将 $a$ 分成一些单调不升的连续段，每段中所有 $b_i$ 都取该段的中位数。但存在一个问题：中位数序列仍可能递减，这时可以用可并堆合并两个区间，动态维护中位数。
CF434D Nanami’s Power Plant
- 将每个在 $[l_i,r_i]$ 区间的 $f_i(x)$ 拆成一个点，$f_i(x)$ 代表的点向 $f_i(x+1)$ 代表的点连权值为 $f_i(x)$ 的边。这样如果没有题目中第二条限制，原图的最小割即为答案。
- 将第二条限制变形成 $x_v\ge x_u-d$，即如果割掉 $x_u$，则在 $v$ 上只能割 $x_u-d$ 之后的边，所以从 $u$ 链上的所有 $x$ 向 $v$ 链上 $x-d$ 连 $+\infty$ 的边。最后考虑边界，链要多延伸一个 $r_i+1$ 再连向汇点，否则会出错。
P6880 [JOI 2020 Final] オリンピックバス
- 不知道标题啥意思。
- 翻转边必须在最短路树上，否则翻转没有贡献。以 $1,n$ 为起点建正/反图，目的是对于翻转边分类讨论。初始答案为从 $1$ 到 $n$ 和从 $n$ 到 $1$ 的最短路和，翻转边时打标记代表这条边不能经过，如果翻转就从 $1$ 到 $v$ 再从 $u$ 到 $n$，并补上中间差的权值。大力分类讨论，代码比较难写。
P7916 [CSP-S 2021 T4] 交通规划
- 平面图最小割等于对偶图最短路，$k=2$ 可以直接将平面分成两部分，类似狼抓兔子一题，直接跑最短路。$k> 2$ 时射线上的黑白点将周围一圈分成了多个大点，形成了一个点颜色交替出现的环形。将颜色不同的两两匹配（类似括号匹配），可以在对偶图上预先处理出每一对不同颜色点间的最短路，然后类似括号匹配破环成链进行区间 dp 就可以计算了。建图连边时的需要非常精细的实现。时间复杂度 $\mathcal O(k^3+nmk\log nm)$。

Summary

$3$ 月悄无声息地来到了尾声。今年的春天，春风并没能送来太多的暖，但学校里的花却开得依旧灿烂。当疫情来到第三个年头，我也多少会感到一些烦躁，还会不时回想那些从前的时光。从铺天盖地的新闻中，至少还能不时地看到一丝希望；在每个看似相同的晚上，至少还有陪伴我的一缕斜阳。感觉自己这个月竞赛提升很多，无论从水平上，还是应有的品格上。学会了接纳迎面而来的挫折与日常不起眼的波折，学会了适时遗忘，性格上也变得比以前更加地坚韧。$4$ 月，希望自己能在省选中给自己的努力一个不错的交代，并继续以一贯的坚持和热爱前进。

Records

Welcome!

Hang around and make yourself at home.

Updates may be slow

Due to unstable connection to GitHub, blog posts may not be up-to-date.