人的惰性是无法战胜的，所以本文缓鸽。

• CF R 737
  • C Moamen and XOR
  • D Ezzat and Grid
  • E Assiut Chess
• CF R 738
  • D Mocha and Diana
  • E Mocha and Stars
• SDPTT2021 R3D2
  • T1 体育测试
  • T2 贸易
  • T3 密码
• AGC 005
  • A STring
  • B Minimum Sum
    • 算法一
    • 算法二
  • C Tree Restoring
  • D ~K Perm Counting
  • E Sugigma: The Showdown
  • F Many Easy Problems
• CF R 740
  • Div.2 D/Div.1 B Up the Strip
  • Div.2 E/Div.1 C Bottom-Tier Reversals
  • Div.2 F/Div.1 D Top-Notch Insertions
  • Div.1 E Down Below
• NOI 2021
  • D1T1 轻重边
  • D1T2 路径交点
  • D1T3 庆典
  • D2T1 量子通信
  • D2T2 密码箱
  • D2T3 机器人游戏

CF R 737

比赛链接

题目评分：800-1100-1700-2200-2800

AB 是水题，不写了不写了。

C Moamen and XOR

套路题，这种东西直接按位考虑。

从高到低考虑每一位，分类讨论一下：

如果我们让当前位的 $\And$ 值 $>\oplus$ 值，那么只有在 $n$ 为偶数的时候才能成立，且只有一种方法，然后假设现在是第 $k$ 位，剩下的 $(k-1)n$ 位可以乱取共 $2^{(k-1)n}$ 方法。

如果我们让当前位的 $\And$ 值 $=\oplus$ 值，按奇偶性讨论：

若 $n$ 为奇数：$\And$ 值 $=1$ 时，可以使 $\oplus$ 值也 $=1$，只有一种方案；$\And$ 值 $=0$ 时，想要使 $\oplus$ 值等于 $1$，有 $\displaystyle {\sum^n_{i=0\And i\equiv 0 \pmod 2}\binom{n}{i}}$ 种方案。发现这两个方案的总种数可以预处理。

若 $n$ 为偶数：$\And$ 值不能 $=1$，那么只有 $\And$ 值 $=0$ 的情况，那么类似上述处理，有 $\displaystyle{\sum^{n-2}_{i=0\And i\equiv 0 \pmod 2}\binom{n}{i}}$ 种方案，同样可以预处理。

直接暴力做即可，时间复杂度 $O(t(k+n))$。

D Ezzat and Grid

设 $f_i$ 表示强势保留第 $i$ 行，最多保留的行数，那么转移方程为：

$\displaystyle f_i=\max^{i-1}_{j=1} c(i,j)(f_j+1)$

其中 $c(i,j)$ 表示第 $i$ 行与第 $j$ 行能否拼在一起。

朴素转移是 $O(n^3)$ 的，能过有鬼了。

考虑线段树优化，对于第 $i$ 行中被染黑的每一段，做一遍区间对 $f_i$ 取 $\max$，而当转移第 $i$ 行的时候，对染黑的每一段取 $\max$。

这样，我们用线段树将 dp 条件与转移合在了一起，实现上需要一棵支持区间取 $\max$，区间查 $\max$ 的线段树，时间复杂度 $O(n\log n)$。

E Assiut Chess

趣题，如果下次课件我还做趣题选讲的话可能会选进来😃，但显然我不会做这样的事情了。

考虑直接从 $(1,1)$ 出发，开始一行一行的排除。

如果国王往下了，那说明它以无路可走，直接往下一行。

否则的话，一个格子一个格子的逼国王往下，你感觉是一个优秀的做法。

但是，如果国王直接偷鸡，你下去了，他上来了，咋办，直接重新逼他。

实现非常简单，可过。

CF R 738

比赛链接

题目评分：900-900-1200-(1200-2500)-2200。

ABC 不写了。

D Mocha and Diana

强的构造题。

首先最后的答案一定为 $n-\min(m_1,m_2)-1$，且任意顺序加边不影响答案。

选取一个中心点 $u$，先尝试让所有的点与之连边。

设此时在 $A$ 图中不与 $u$ 连通的点集为 $L$，B 图中不与 $u$ 连通的点集为 $R$。

那么 $L$ 与 $R$ 无交集，直接随意连边即可。

E Mocha and Stars

莫比乌斯反演板子？

设 $f(a_1,a_2,\ldots,a_n)$ 为 $a_1,a_2,\ldots,a_n$ 这种方案是否满足前两个条件。

答案为：

$\sum^{r_1}_{a_1=l_1}\sum^{r_2}_{a_2=l_2}\cdots\sum^{r_n}_{a_n=l_n}f(a_1,a_2,\ldots,a_n)[\gcd(a_1,a_2,\ldots,a_n)=1]$

直接莫比乌斯反演：

$\sum^m_{d=1}\mu(d)\sum^{\lfloor\frac{r_1} {d}\rfloor}_{a_1=\lfloor\frac{l_1} {d}\rfloor}\sum^{\lfloor\frac{r_2} {d}\rfloor}_{a_2=\lfloor\frac{l_2} {d}\rfloor}\cdots \sum^{\lfloor\frac{r_n} {d}\rfloor}_{a_n=\lfloor\frac{l_n} {d}\rfloor}f(a_1,a_2,\ldots,a_n)$

后面的问题是经典背包，前缀和优化可以做到 $O(\frac {nm}{d})$。

SDPTT2021 R3D2

测试题，不公开。

T1 体育测试

dp 好题。

设 $f_{i,j}$ 表示前 $i$ 个里放了 $j$ 个二类数的方案总数。

若当前位置有 $k$ 个一类数结束，那么方案数是排列数，可以轻松算出。

同时转移二类数，每次只放一个二类数，同样贡献可以轻松算出。

时间复杂度 $O(n^2)$。

T2 贸易

二合一？

首先将问题拆成两问，第一问是求出 $f_x$，表示长度为 $x$ 的路径为 $f_x$ 条，第二问是求答案。

第一问朴素做是 $O(n^2)$ 的，不大行，注意如果定了根就类似一个卷积，使用点分治套 FFT 即可做到 $O(n\log^2 n)$。

第二问可以化柿子，总之化出来一个关于 $f_i$ 相关的多项式，需要多项式多点求值解决，时间复杂度 $O(m\log^2n)$。

不过我不会多点求值，所以这题没写。

T3 密码

妙妙题。

两个程序用同一个随机种子生成 $m$ 个长为 $n$ 的 $01$ 串。

考虑编码后的字符串表示该 $01$ 串选或不选，那么可以使用线性基解决。

也就是说，我们使用随机出的字符串表示出是否被异或起来，那么解码只需要做异或就行了。

需要 bitset 优化，时间复杂度 $O(\frac{n^3}{w})$。

AGC 005

比赛链接

题目评分：1054-1828-1976-2943-3276-3440

A STring

水题，直接用个栈，不断处理一下即可。

B Minimum Sum

经典题，数据结构各显神通，肯定得枚举一个位置算贡献。

算法一

我没有脑子，这题直接线段树一下，做一遍二分，二分出每一个位置所能成为答案的最大左右区间，乘法原理计数即可。

时间复杂度 $O(n\log^2n)$。

算法二

我学习过单调栈，这题不是单调栈裸题吗。

记录每个数踢出去的数的个数，那么当前数的向前的最多可延展的区间也可以出来，类似的，向后的最多可延展的区间个数也可以出来。

时间复杂度 $O(n)$。

C Tree Restoring

智商题，没有智商的 cnyz 被区分了。

考虑 $a_i$ 的最大值是如何来的，显然是一条直径，那么，$\min a_i\ge \max a_i$。

容易想到，如果 $\max a_i$ 是奇数，那么最小点得有两个，同理，$\max a_i$ 为偶数时，最小点得有一个，同时，$a_i$ 除了最大值和最小值，之间的至少有 $2$ 个。

那么这些都判一下就行了，时间复杂度 $O(n)$。

D ~K Perm Counting

正着求很不好求，考虑容斥。

显然可以将原本的不能选的关系抽象成一个二分图，那就是会变成若干条链，且相邻的边不能取，将链拍平到序列上考虑 DP。

设 $f_{i,j,0/1}$ 表示现在在第 $i$ 位选了 $j$ 条边，且当前这条边选了或没选，有转移：

$f_{i,j,0}=f_{i-1,j,0}+f_{i-1,j,1}\\f_{i,j,1}=f_{i-1,j-1,0}$

直接暴力 dp，可以做到 $O(n^2)$ 的时间复杂度，注意判当前是不是链头。

好像用多项式可以优化到 $O(n\log n)$？不过我不会。

E Sugigma: The Showdown

博弈好题。

考虑什么时候会陷入无限循环，称一条树 $a$ 上的边 $(u,v)$ 是横跳边，当且仅当 $\text{dist}_b(u,v)\ge 3$，这是不需要证明的。

容易发现，我们可以处理出所有可达的点，容易使用 dfs 解决，只需要比较某个点到两个起始点的距离。

如果在可达的点组成的连通块中出现了横跳边，那么可以无限循环，否则的话，A 想让轮数最多，那只能到一个距离出发点最远的点来等死，容易发现轮数是最大的。

时间复杂度 $O(n)$。

F Many Easy Problems

考虑枚举每个点算贡献，容易发现：

$f(i)=\sum^n_{u=1}\binom{n}{i}-\sum_{v\in son(u)}\binom{siz_v}{i}$

其中 $son(u)$ 表示与 $u$ 相连的节点集合，$siz_u$ 表示子树大小。

可以看做是枚举每一个点，用所有答案减去不包含的答案。

化柿子：

$f(i)=n\binom{n}{i}-\sum^n_{u=1}\sum_{v\in son(u)}\binom{siz_v}{i}$

接着化简后面这一坨：

$\sum^n_{u=1}\sum_{v\in son(u)}\binom{siz_v}{i}\\\sum^n_{j=i}cnt_j\binom{j}{i}$

其中 $cnt_i$ 表示 $siz=i$ 的子树出现了几次。

拆掉组合数：

$\frac 1 {i!}\sum^n_{j=i}\frac{cnt_j(j!)}{(j-i)!}\\\frac 1 {i!}\sum^{n-i}_{j=0}\frac{cnt_{j+i}(j+i)!}{j!}$

后面的柿子是一个卷积形式，令 $F_i=cnt_ii!$，$G_i=\frac {1}{i!}$，那么：

$\frac 1 {i!}\sum^{n-i}_{j=0}F_R(n-i-j)G_j$

使用 FFT 优化，时间复杂度 $O(n\log n)$。

顺带说一句，$924844033$ 的原根为 $5$。

CF R 740

比赛链接与另一个比赛链接 。

题目评分：

• Div.1：1300-1900-2000-2600-3000-3300
• Div.2：800-1300-1300-(1700-1900)-2000-2600

Div.2 D/Div.1 B Up the Strip

设 $f_i$ 表示从 $n$ 到 $i$ 的方案总数。

使用减法转移的话，也就是 $f_i=f_i+\sum_{j=i+1}^n f_j$。

而使用除法，考虑填表法，考虑一个除数 $d$，那么能够被影响的是 $[di,di+d-1]$ 这样一个区间。

发现这两个东西都可以后缀和优化，所以减法转移可以做到 $O(1)$，而除法呢，容易发现这是个调和级数 $O(\log n)$ 的。

Div.2 E/Div.1 C Bottom-Tier Reversals

强构造，不过我是傻逼没想到突破口。

先考虑判无解，容易发现翻转不改变某个数所在位置的奇偶性，可以直接判无解。

操作步数为 $\frac 5 2n$，这启示我们，对于每一个数对 $(i,i+1)$，使用 $5$ 次操作把他丢到对应的位置。

比如序列 $1,6,4,5,3,7,2$，我们想要将 $6,7$ 放到最后，考虑如下方案：

• 操作奇数所在的位置，即 $6$，序列变为 $\color{red}{7}\color{black},3,5,4,\color{red}{6}\color{black},1,2$。
• 操作偶数所在位置的前一位，即 $4$，序列变为 $\color{black}4,5,3,\color{red}7\color{black},\color{red}6\color{black},1,2$。
• 操作偶数所在位置的下一个位置，即 $6$，序列变为 $\color{black}1,\color{red}6\color{black},\color{red}7\color{black},3,5,4,2$。
• 操作奇数所在位置，即 $3$，序列变为 $\color{red}7\color{black},\color{red}6\color{black},1,3,5,4,2$。
• 逆转整个序列，序列变为 $\color{black}2,4,5,3,1,\color{red}6\color{black},\color{red}7$。

按照这个方式模拟整个过程即可，时间复杂度 $O(n^2)$。

Div.2 F/Div.1 D Top-Notch Insertions

数据结构与组合的精妙结合。

发现最后的序列顺序是确定的，比如 $a_1\le a_2\le a_3$，容易发现如果只有 $\le$ 可以直接隔板出答案。

但是会有插入的情况，如果发生一次形如 $(x,y)$ 的插入，意味着 $a_x<a_y$。

那么，依据隔板法，总的方案数为 $\binom{2*n-1-c}{n}$，其中 $c$ 表示 $<$ 的个数。

考虑维护这个 $<$，一个数前面是 $<$，那么一定有数被插入到了前面，考虑维护一个集合 $S$，初始时里面被放进了 $1\sim n$。

倒序处理每一个插入，对当前插入，设排名为 $y_i$ 的数为 $p$，排名为 $y_i+1$ 的数为 $q$，删除 $p$ 并为 $q$ 打上标记，最后 $c$ 即为打上标记的数的个数。

使用线段树上二分，时间复杂度 $O(m\log n)$，注意别写成了 $O(n\log n)$。

Div.1 E Down Below

*3000 神题。

考虑二分答案转化成判定性问题，好了现在问题变成给定一个 $x$，问能否走完。

如果没有第三个条件，直接贪心，爽哉，傻逼题！！！！1

完了，有了第三个条件怎么做，我只好自闭。

考虑我们现在已经走过的点集为 $S$，考虑现在这些点中开始 BFS 找路，发现合法的路径要么是一个 $\rho$ 形，要么是一个走出去再走回 $S$，这两都可以在 BFS 中找出来。

那么，做 $n$ 次 BFS，每次扩展 $S$，在 $S$ 大小为 $n$ 时就发现有解。

每次 $S$ 至少增加 $1$，那么时间复杂度就是 $O(n^2\log v)$ 的，实际上可能完全跑不满。

NOI 2021

圆梦，个人认为题目难度：D1T1-D2T1-D1T2-D2T2-D1T3-D2T3。

这届 NOI 往前五年以内最烂稳了，往后不知道有没有更烂的。——p_b_p_b

D1T1 轻重边

听说被喷了？不过个人认为还可以。

首先如果直接按照轻重边的定义写的话，不大可能写的出结果。

考虑转化问题，比如说，时间戳？

为每个点打上一个时间戳，一条边被称为轻边，当且仅当两个点的时间戳不同。

那么，操作一就可以变为一次树上路径覆盖，也就是覆盖为一个新的时间戳。

操作二拍平到序列上，就是不同颜色段个数。

初始化要在开始的时候对每个点打不同的时间戳，这样就可以使每条边都是轻边。

直接树链剖分，用线段树维护一下，时间复杂度 $O(n\log^2n)$。

D1T2 路径交点

$n_1=n_k$ 与 $n_1\le 100$ 的限制，不由得想到矩阵乘法。

事实上，本题的解法其实比较简单，考虑将邻接矩阵乘起来并求行列式。

然后？没了。你问我为什么是对的，可以使用 LGV 引理证明。

引理：交点的奇偶性可以对应排列的奇偶性，证明吗，不会。

那么就可以直接丢到 LGV 引理上来证明了。

时间复杂度 $O(n^3)$。

D1T3 庆典

发现同一个 SCC 中的点是互达的，也就是说，如果我能访问一个 SCC 中的任意一个点，则必然也可以访问其他这个 SCC 中的点。

直接缩点，然后会缩出一个 DAG，随便选取一个 DAG 的生成树，其实选节点标号尽量大的是绝对对的。

现在考虑询问，容易发现每次涉及到的点很少，直接建出虚树，这个虚树的点数会很少，我们直接在上面添加上加的边。

如果，一个虚树上的点，既可以被起始点 $s_i$ 到达，又可以在虚树的反树上被终止点 $t_i$ 到达，则这个点被称为好点。

如果一条边的两边均是好点，那么这条边上的点都是好点。

最终的答案即为好点的权值和，时间复杂度 $O(n\log n+q\log n+\sum k\log n)$。

注意本题的实现上需要卡常，建议不要使用倍增 LCA，如果你倍增 LCA 卡过去了那我请你抽烟。

D2T1 量子通信

容易发现字典是随机的，同时一共是 $256$ 位，最大混淆值只有 $15$。

对 $256$ 位的 $01$ 串分段成 $16$ 段，如果一个串被混淆了，那么这 $16$ 段至少有一段不变，找出这一段不变的，对于这一段找出字典中的串，暴力对比即可。

好像挺一句话的，不过就这样。

D2T2 密码箱

公式其实无约分的必要，所以直接考虑分别计算分子和分母，考虑使用矩阵维护。

所以考虑矩阵刻画操作，比如说思考加上一个 $a_i$ 有什么影响。

$\frac{a'}{b'}=\frac{1}{a_i+\frac a b}=\frac{b}{a_i\times b+a}$

也就是说 $a'=b$，$b'=a_i\times b+a$。

也就是：

$\begin{bmatrix} a' \\ b' \end{bmatrix} = \begin{bmatrix}0 & 1 \\1& a_i \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix}$

那么我们就可以用矩阵刻画求答案了，考虑刻画 W 和 E 操作。

W 操作：$a_k\to a_k+1$：考虑构造一个矩阵 $A$ 使得 $\begin{bmatrix}0 & 1 \\1& a_k \end{bmatrix}A=\begin{bmatrix}0 & 1 \\1& a_k+1 \end{bmatrix}$。

不难构造出 $A=\begin{bmatrix}1 & 1 \\0& 1 \end{bmatrix}$

之后是 E 操作，要分 $a_k>1$ 与 $a_k=1$ 两种情况。

只讨论 $a_k>1$ 的情况，类上，构造出给末位减一的矩阵 $\begin{bmatrix}1 & -1 \\0& 1 \end{bmatrix}$。

再进行添加，添加两个 $\begin{bmatrix}0 & 1 \\1& 1\end{bmatrix}$，乘起来得 $\begin{bmatrix}0 & -1 \\1& 2\end{bmatrix}$。

猜测另一种情况也是一样的，验证出也是一样的。

那么直接维护矩阵连乘积，矩阵反转积，矩阵翻转积，矩阵翻转反转积。

直接 FHQ 硬上，时间复杂度 $O(q\log n)$。

卡常小 trick：循环展开矩阵乘法。

D2T3 机器人游戏

神仙题，只有提高知识点的大毒瘤。

丢篇题解跑。