2022.3

2022.3

ますます多くの野菜，どうすればいいの？？？？？

这个月比较摸（因为回学校上课了）

同样只是挑有意思的题写

3.1

T2

给你一个字符串 \(S\)，求字典序第 \(n\) 小的包含 \(S\) 的字符串。

\(|S|\leq 1000,n\leq 10^{18}\)。

建出 KMP 自动机然后在上面 DP，\(f_{i,j}\) 表示填到第 \(i\) 位，自动机上走到节点 \(j\) 的方案数，转移就是枚举当前位填什么字符，最后试填法求答案。

复杂度 \(O(|S|^2|\Sigma|)\)，\(\Sigma\) 为字符集。

3.4

T1，T2 都是普及组小朋友做的题

T3

给你一个 \(n\) 个点 \(m\) 条边的有向图，一条路径的权值是经过的前 \(k\) 大的边权之和，求最短路。

\(n,k\leq 1000, m \leq 2000\)。

先枚举第 \(k\) 大的边权 \(x\)，我们将所有边的边权都减去 \(x\)（并与 \(0\) 取 \(\max\)）。
然后直接在这张图上跑 dijkstra，把跑出的最短路加上 \(x\times k\) 作为答案即可。

想一想就发现这个正确性很对。

好像也很简单，但我还是没做出来，怎么回事呢？

3.5

T2 是非常好的构造题，T3 是很无聊的根号题（把两种询问分别分块，还要用到 bitset 求 DAG 可达性，经典的分块卡空间做法）。

T1

对于偏序集 \((D(n),|)\)，其中 \(D(n)\) 是 \(n\) 的正约数集合，我们要求它的最长反链。

设正整数 \(n=\prod_{i=1}^k p_i^{\alpha_i}\)，其中 \(p_i\) 为互不相同的质数，\(\alpha_i\in \mathbb{N}_{+}\)。我们记 \(\deg(n)=\sum_{i=1}^{k}\alpha_i\) 为 \(n\) 的度。

有一个结论就是，考虑集合 \(U=\{d|\deg(d)=\lfloor m/2 \rfloor,d|n\}\)，那么，\(U\) 就是一个最长反链的构造。

下面给出证明。

有空再写

3.7

T1 又是构造题，T3 是及其暴力的状压。

T2

这是今天最喜欢的题，

3.8

T1

3.11

摸了，耶！

3.12

接着摸，耶！

3.14

T1

T2

T3

3.15

T1

题目很容易转化成，给你一个立方体，其中一些点是障碍点，对每个点求包含它的子立方体个数，要求子立方体中不含障碍点。

先容斥一下，求出 \(f_{t,i,j,k}\) 表示 \((i,j,k)\) 在 \(t\) 方向那个区域中的合法子立方体数量（\(t\) 的取值从 \(1\) 到 \(8\) 分别表示 \(8\) 个方向）。现在，对于一个点 \((i,j,k)\) 通过 \(f\) 就可以容斥出不经过该点的合法立方体数量（这个式子总共 \(26\) 项），用总方案数去减就是包含该点的数量。

现在求 \(f\)，如果是二维怎么做？想到 [GXOI/GZOI2019]与或和，显然可以单调栈 \(O(n^2)\) 求出。加上第三维，就 \(O(n^2)\) 暴力枚举第三维上的每个子区间，该子区间长度为 \(d\) 那就是把厚度为 \(d\) 的这一厚层中的障碍点都放到一层上，让后按二维做法做即可。总复杂度 \(O(n^4)\)。不过由于计算 \(8\) 个方向再加上单调栈的常数，并没有比 \(O(n^5)\) 做法表现好很多。

T2

题意

数轴上有一些黑白区间，一部分区间已经被指定了颜色，你要指定未染色区间的颜色，使得数轴上对于每个点，覆盖他的黑区间个数和白区间个数差的绝对值小于等于 \(1\)。

这个建图真是太妙了啊啊啊啊啊啊啊啊啊

离散化之后，对于一个区间 \([l,r]\)，把它看成从 \(l\) 向 \(r\) 连一条有向边，染色就是给边定向。对于奇度数的点，我们把它们依次连到一起，然后就变成了欧拉回路。因为对于欧拉回路，覆盖在一个点上所有边朝两个方向的数量相等，除去为了处理奇度数点连的边，绝对值之差也不会超过 \(1\)。

然后就是混合图求欧拉回路（应该很经典吧，但我第一次听说这个/qd）

做法：网络流

1. 将所有无向边随意定向

2. 计算每个点的入度和出度，如果入度和出度奇偶性不同，返回无解

3. 把所有入度大于出度的点向汇点连一条容量为 \((入度-出度)/2\) 的边，所有出度大于入度的点从源点连一条容量为 \((出度-入度)/2\) 的边，原图中的边依然保留。

4. 跑最大流，如果源点连出的边没有全部满流，返回无解。否则，将所有有流量的边反向，就是构造出的答案

正确性显然

T3

这个题真的

题意

一棵有边权的树，要求用最小的代价遍历这棵树。有 \(m\) 条额外边，第 \(i\) 条额外边的边权为 \(a_i\)，对于所有的 \(K\in [0,m]\)，计算在前 \(K\) 条额外边中选一些加入后遍历树边的最小代价。

\(n,m\leq 10^5\)。

容易发现的是，如果不加额外边，每条边都要恰好经过两次，加入一条额外边 \((x,y)\)，相当于原树上 \(x\) 到 \(y\) 之间路径上的边只需经过一次。

记原树中所有边权和为 \(sum\)，\(f_i\) 表示在树上选 \(i\) 条不相交路径的最长长度。将 \(a_1\) 到 \(a_K\) 排序后，记前缀和为 \(s\)。那么，加 \(i\) 条额外边的答案就是 \(ans_i=2\times sum-f_i+s_i\)，稍微想一想就发现，\(s\) 是下凸的，\(f\) 是上凸的，那么 \(ans\) 就是下凸的（凸函数加凸函数仍然是凸的）。如果我们用平衡树维护 \(a\) 的话，就可以直接在平衡树上二分出最小的 \(ans\)。

那么接下来就是求 \(f\) 了，我们可以考虑一种反悔贪心策略，我们每次求出树上的直径，然后把直径上所有边权变为相反数，再加一条路径的时候就再次求出直径，如果经过了之前经过的取反的边，实际上就相当于把重复部分的贡献减去了，两条相交路径除去重复部分后，就又拼成了两条不相交的路径，重复的部分就被反悔掉了（这个思路真是太神了）。

现在我们只需要一种数据结构，支持一下两个操作：

1. 将树上一条链上的边权变为相反数

2. 求树的直径

这个做法好像就比较多了（？），比如 LCT 之类的，但我只看懂了一种

首先对每个边建点，边权放到点上，再对整棵树进行三度化，然后轻重链剖分（上一步的三度化保证了这时每个点最多只有一个轻儿子）。

考虑如何维护直径，注意到一条路径会经过若干条重链，但这其中有且仅有一条重链，使该路径形如：从 \(u\) 的轻儿子走到 \(u\)，在重链上从 \(u\) 走到 \(v\)，从 \(v\) 的轻儿子下去（这种情况可能退化，即 \(u\) 和 \(v\) 可以重合，也可以不从轻儿子走下去，但维护起来是不影响的）。

用数据结构维护每条重链，具体地，对于数据结构上代表 \([l,r]\) 的节点，维护四个信息，\(l\) 到 \(r\) 的点权和，从左边过来再在 \([l,r]\) 中走轻儿子下去的最大值，类似的从右边过来的最大值，还有区间的答案，pushup 的方式类似区间最大子段和。因为还有修改操作，所以以上信息都要维护两份，分别表示现在的点权的值以及点权取相反数后的值。修改的时候直接 swap 两者即可，区间修改直接打懒标记就可以了。

为了做到总复杂度一个 \(\log\)，我们采用全局平衡二叉树维护轻重链剖分。（应该是可以做到一个 \(\log\) 的，但因为我的实现要把每条重链的答案塞到 set 里维护全局答案，每次经过维护重链的一个 BST 的根都要更新 set 中的值，结果好像还是两个 \(\log\)）

总之，这道题就做完了，总复杂是 \(O(n\log n)\) 或 \(O(n\log^2 n)\)，思路很清晰，但写代码强烈建议在脑子清醒的时候写。

3.17

今天的题是我们去年在北京组的题，竟然真做模拟赛了 233333

T1

题面真是太眼熟了（hxx 的题）

来源 CF1083F

很好的分块

T2

zzz 的题，好像是 Atcoder 的题，但找不到原题了

这个原根用的挺妙的，有空写一下

T3

记忆化搜索好（？）题，各种分类讨论码了 5.8K /cy

3.18

T1

T2

T3

3.21

T1

T2

3.28

T1

打开题面，交互题贴脸

其实挺简单的，还剩半个小时的时候会了，但因为要去做核酸就没写

T2

题意

给你一个序列，求把它划分成若干段的所有方案的各段 \(\operatorname{mex}\) 乘积之和。

\(n\leq 10^6\)，时间限制 1s

显然的状态转移方程

\[f_i=\sum\limits_{j=0}^{i-1}f_j\times\operatorname{mex}\limits_{k=j+1}^{i}\{a_k\} \]

我们来看看，怎么在 \(i\) 变化的同时维护那个 \(\operatorname{mex}\)。首先我们发现这个 \(\operatorname{mex}\) 一定是单调不上升的，也就是一个一个的段，考虑加进来一个 \(a_i\)，又发现只会改变 \(\operatorname{mex}\) 等于 \(a_i\) 的那部分值，也就是说，会将一个段分裂成若干小段（这部分很像 2.19 T1），总共只有 \(O(n)\) 次区间修改。

大致流程就是

每次找到 \(\operatorname{mex}\) 等于 \(a_i\) 的一段 \([l,r]\)，然后求出 \(\operatorname{mex}\limits_{j=r}^{i}a_j\)（就是新的 \(\operatorname{mex}\) 值，这个可以线段树求），设它等于 \(x\)，找到 \(r\) 前面第一个等于 \(x\) 的位置 \(j\)，把 \([j+1,r]\) 的 \(\operatorname{mex}\) 值都设为 \(x\)，然后把 \(r\) 赋值为 \(j\)，继续上面过程知道 \(l。

至于怎么求区间 \(\operatorname{mex}\)，考虑用权值线段树维护 \([1,i]\) 中每个树最后出现位置的最小值，然后在线段树上二分找到第一个最后出现位置小于 \(j\) 的值，就是 \([j,i]\) 的 \(\operatorname{mex}\)。

还有就是原序列中大于 \(n\) 的值没用，可以直接设成 \(n\)，不用再离散化了，区间 \(\operatorname{mex}\) 都是以 \(i\) 为右端点的，不用写主席树了，找 \(r\) 前面第一个等于 \(x\) 的位置也是直接 \(O(1)\) 维护了，不用再用 vector 存下标再二分了，\(f\) 值再区间修改时直接算贡献就行了，不用再线段树维护了。

然而以上睿智写法全部出现在我的代码里/cy

T3

一个长度为 \(n\) 序列 \(a\)，Alice 要把它重新排列后交给 Bob，Bob 可以不断交换相邻的互质的两个数，Alice 希望最后字典序最小，Bob 希望字典序最大，求最终序列。

\(n\leq 2000\)。

对于 Bob 来说，不互质的两个数的相对位置是无法改变的，如果对于不互质的 \(a_i,a_j\ (i 我们连一条从 \(i\) 到 \(j\) 的边，得到一个 DAG，那么最终序列就是字典序最大的拓扑序。

现在问题就是 Alice 会怎么排列序列，也就是说，对于不互质的 \(a_i,a_j\) 我连一条 \(i\) 和 \(j\) 间的无向边，现在要给无向边定向。

其实我们对这个无向图 dfs，对于 \(x\)，每次选权值最小的点 \(y\) dfs 下去，连边 \((x,y)\)，得到的图就是对于 Alice 最优的选择。

虽然这个感觉很对，但我还是觉得题解的做法更清楚一些

首先不同联通块之间肯定没有影响，最终把它们多路归并即可。而对于每个连通块，我们可以为它确定一个唯一的入度为零的点最为起点（选择权值最小的），这样 Bob 只能先选它。

确定这个点之后，我们可以把它相邻的点打上标记，然后删掉该点，原图变成若干连通块，对于每个连通块，我们在标记的点中选择最权值小的点最为起点，然后递归下去即可。

还有一个问题，如果得到所有联通块？边数是 \(O(n^2)\) 级别，无法接受。考虑优化建图，对于每个质数建一个点，每个数向它的所有质因子连边，这样边数降为 \(O(n\omega(a_i))\)，而连通性不变，太棒了！

这样我们的复杂度就是 \(O(n\sqrt{a_i}/\ln a_i+n^2(\log n+\omega(a_i)))\) 前边那个是分解质因数的复杂度。

3.29

T2

给你一个边上有字符的树，\(m\) 个询问，每次询问给你一个字符串 \(s\)，问书上存不存在一条路径上的字符串等于 \(s\)。

\(n,\sum s\leq3\times 10^4\)。

这就是个暴力题...

设 \(f_{x,j,k}\) 表示树上从下往上走到 \(x\)，能否匹配 \(s_j\) 的长 \(k\) 的前缀，\(g_{x,j,k}\) 表示从 \(x\) 往下走，能否匹配 \(s_j\) 长 \(k\) 的后缀，前后缀拼一下就是答案了。

这个 dp 状态数为 \(O(n\sum s)\)，不过转移都可以 bitset 优化，也就能做到 \(O(\dfrac{n\sum s}{\omega})\)。

不过这个东西写 dfs 会 MLE，要提前 dfs 一遍把拓扑序记录下来，然后用一个循环 dp。以后写题可以注意一下，卡时间和卡空间都可以试试这样把 dfs 改成循环。

T3

还不会...