【省选模拟】3 月

3.3

昵称

方案数可能爆 long long 但只需要知道是否 \(>\) 某个数时可以时刻对 \(10^{18}\) 取 \(\min\)
按数位填数：枚举长度+不允许前导 \(0\iff\) 长度 \(\max\)+允许前导 \(0\)（注意输出）

帝国防卫

考场做法是 \(O(n\log n\log^{2}x)\) 的线段树维护 bfs 序（不过是在线的）

另一个做法是整体二分每个点变为合法的时间，修改可以给 \(\log\) 级祖先打标记（注意减掉同一次修改父亲对儿子的影响），询问跳 \(\log\) 级祖先求和。为了解决下取整后相加，每个点要维护 \(\log\) 个标记，时间复杂度 \(O(n\log n\log^{2}x)\)

使用虚树可以做到 \(O(n\log n\log x)\)，但并不会

3.4

出俩板子啥意思啊

过路费

70pts：枚举第 \(k\) 大边的权值 \(x\)，那么要求走 \(\ge k\) 条权值 \(\ge x\) 的边，其余边权值看做 \(0\)，跑分层图最短路即可。时间复杂度 \(O(m^{2}k\log m)\)

考场打表发现谷很少，写了随机化三分，但没卡好时 T 了。赛后调参通过

正解：考虑优化掉分层图。可以把所有边权 \(-x\) 并与 \(0\) 取 \(\max\)，然后正常跑最短路，用最短路 \(+kx\) 更新答案。分 \(x\) 与最终答案中第 \(k\) 大边的大小关系易证答案不会更小。

通过不合法情况不优规避掉判断合法性。在判断合法性成为瓶颈时要往这方面想，可能对直觉和证明技巧要求较高

3.5

小 G 的约数

赛时使用打表猜出了结论，但采用了最劣的 \(O(2^{\omega(n)})\) 容斥实现

条件 \(3\) 可以转化成：\(\forall i，问题即为求 \(n\) 约数集合的最长反链长度

记 \(f(x)\) 为 \(x\) 分解质因数后指数和，\(g(x)=\sum_{d|n}[f(d)=x]\)。使用 Dilworth 定理转化为最小链划分数，答案为 \(\max g=g(\lfloor\frac{f(n)}{2}\rfloor)\)

\(g(\lfloor\frac{f(n)}{2}\rfloor)\) 显然为答案下界，只需要构造一种方案。证明可以看官方题解

实现上可以对质因子指数背包，也可以直接贪心地最小链覆盖（每次取是当前链尾倍数、未覆盖的最小因子加入当前链。显然新开链不优，否则划分到哪个链都一样）

约数有关问题从质因子角度打表考虑归纳

? G 的连通图

考虑取 \(L=\prod_{p\in\mathbb{P},p，那么除了 \(L+1\) 都连通了。

找一个 \(>\sqrt{n}\) 的质数 \(a\mid L+1\)，让 \(L+1\) 和 \(L+a+1\) 连边，这样 \(L+a\) 可能又不连通了。让 \(ka+1\) 也是质数且 \(ka+1\mid L+a\)，即可让 \(L+a\) 和 \(L+(k+1)a+1\) 连边（\(a>\sqrt{n}\) 是为了让 \(L+a^{2}\) 不在区间内，这样 \(L+xa,1 可以通过 \(p\mid x\) 连通）
实际上取 \(k=2\)，在 \(n\ge35\) 的时候都是找得到这样的 \(a\) 的（不会证明），对于 \(n<35\) 暴力打表即可

求 \(L\) 采用暴力 CRT，这样只需要写高精乘低精

for(int i = ceil(sqrt(n)); ; ++i)
	if( !vis[i] && !vis[2*i+1] ) { a = i; break; } // vis[prime] = 0
ans = 1, mod = 2ll*a*a+a; // L = -1 (mod a), L = -a (mod 2a+1)
Rep(i,1,n) if( !vis[i] && i != a && i != 2*a+1 ) (mul *= i) %=mod, ans = ans * i;
for(LL now = mul; now != mod-3*a-1; ckadd(now,mul), ++cnt); // CRT
ans = ans * cnt;
ans.write(); // 只有 ans 为高精

小 G 的 DAG

套路题，但考场上愣是没想到根号重构

分组处理询问。使用 bitset \(O(1)\) 查询两点是否可达。对于操作一，每根号次 \(O(n)\) 重构（按时间倒序操作，每个点只被覆盖一次）；有效的操作二为询问点最后一次被覆盖到当前时间之间的，对操作时间分块求最小值。时间复杂度 \(O(\frac{n^{2}}{\omega}+n\sqrt{n})\)

3.6

高维游走 \(\star\)

设第一阶段在 \(m\) 维上走了 \(a_i\) 步，那么疲劳度为 \(\sum i\times a_{i}\)，方案数为 \(\displaystyle{t_{0}\choose a_{1},\cdots,a_{m},t_{0}-\sum a}\prod{t_{i}\choose a_{i}}\)

由库默尔定理得模 \(2\) 意义下方案数不为 \(0\) 要求 (t[0]&a[i])==a[i], (a[i]&a[j])==0, (t[i]&a[i])==0。考虑构造 \(31\times m\) 的 \(0,1\) 矩阵 \(b\)，\(b[i,j]=1\) 当且仅当 \(j=0\) 或 \(a_j\) 的第 \(2^i\) 位可以为 \(1\)。问题转化为给矩阵每一行选一个 \(b[i,j]=1\) 的 \(j\)，贡献 \(2^{i}j\) 疲劳度，求有多少种疲劳度的方案数为奇数

考虑 DP for DP。将疲劳度进位到 \(i+1\) 位（\(0\sim i\) 位始终为 \(0/1\)，\(0\le\) 第 \(i+1\) 位 \(）。设 \(f[i,s]\) 为前 \(i\) 行，\(i+1\) 位取值集合为 \(s\) 的疲劳度种数（\(s\) 为状压，第 \(j\) 位为 \(1\) 代表疲劳度的 \(i+1\) 位可以为 \(j\)，“可以”代表方案数 \(\equiv1\pmod2\)）
转移枚举第 \(i\) 位选的数并进位，使用异或完成方案数模 \(2\)

预处理转移即可做到 \(O(T2^{m}m\log t)\)

写之前一定要理清思路，非常绕

过山车 (bzoj4261)

棋盘问题，每个点与四连通点匹配：黑白染色， 往网络流上想

\(w=0\) 只需要判断是否存在合法路径，观察到每个点的度数为 \(2\)，使用二分图匹配分配度数即可

费用与当前格的轨道有关。考虑新建两个虚点，分别代表与左右连边、与上下连边，那么流量分别流到两个虚点代表弯道，流到同一虚点代表直道，但网络流中无法对分散的流量计算费用，因此补集转化为算直道的最小费用。

该点向两个虚点分别连 \((1,w_{i,j}),(1,0)\) 的边，由于是最小费用流，流量流到不同虚点一定走费用为 \(0\) 的边，与题意相符

由于图是四分图且边权范围很小，dinic 显著快于 EK（求助：本题 SPFA 的 SLF 是负优化）

费用流不好直接计算费用时考虑算补集

木棍 \(\star\)

把给定区间右端点 \(-k\) 变为对木棍左端点的限制。显然若存在方案，木棍左端点坐标可以为整数

梳理一下限制：

1. 区间 \([l,r]\) 中最多 \(\lceil\frac{r-l}{k}\rceil\) 根木棍
2. 区间 \([l,r]\) 中至少 \(f(l,r)\) 根木棍。\(f(l,r)=\sum[l\le a_{i}][b_{i}\le r]\)（注意连这类边只需要 \(O(n^{2})\) 二维前缀和，不要像我一样 naive 地写 \(O(n^{2}\log n)\) 扫描线）
3. 区间 \([x_{i},y_{i}]\) 中最多 \(c_i\) 根木棍

记 \(s_i\) 为左端点坐标 \(\le i\) 的木棍数，则可以把限制表示成对 \(s\) 差分约束。使用 hall 定理可以推出这些限制是充要条件，当且仅当出现负环无解

点数高达 \(10^{9}\)，合理猜想只需要判断给定区间左端点 \(-1\)、右端点（称为关键点，第 \(3\) 类边的端点一定都是关键点）的导出子图即可，点数降为 \(O(n)\)
证明：如果负环上出现相邻的第 \(1/2\) 类边可以直接合并，不会使权值增加。然后考虑负环上一个非关键点，其左右一定分别为第 \(1,2\) 类边，向第 \(1\) 类边的另一端点移动至第一个关键点不会使权值增加（第 \(2\) 类边权值不变）。

朴素求解时间复杂度 \(O(n^{3})\)（边数 \(O(n^{2})\)），卡时可以通过（本题 SLF 优化效果显著）

是用线段树优化转移，时间复杂度 \(O(n^{2}\log n)\)

卡时判负环（可能可以加上 SPFA 优化）
利用关键点的导出子图来减小规模（不会证明可以猜想）

3.7

分裂

不难发现把球全分裂成 \(n\) 后共有 \(n!\) 个球

记 \(m=\min\{x|x!\ge n\}\)。先把球分裂成若干个 \(m-1\) 和若干个 \(m\)，此时的球数 \(n-m，由于 \(m\le20\)，因此差距并不大，考虑据此调整。对于 \(x+1\) 个编号 \(x\) 的球，可以变为 \(1\) 个 \(x-1\) 和 \(x+1\) 个 \(x+1\)，总球数 \(+1\)。对编号 \(m-1,m,m+1\) 的球进行类似的调整即可。

这三个位置上的球数有 \(O(m!)\) 个，只需要 \(O(m^{2})\) 个就能结束调整，因此 \(n\) 较大时一定有解。实际上精度很高，除了 \(1\) 和无解的 \(3,5,8\) 都不需要特判

构造方法：先快速逼近答案，再微调

未来 \(\star\)

用 \(s[i]\) 表示 \(i\) 次操作后的矩阵

把颜色映射为 \(0,1,2\)，则题目所述的变换可以表示为 \(s[i,j]\equiv-s[i-1,j-1]-s[i-1,j]\pmod3\)

这个形式使得 \(s[i-1,j-1],s[i-1,j]\) 之间独立开了，考虑直接算 \(s[0]\) 对 \(s[m]\) 的贡献。转移路径为倒置的杨辉三角，不难发现 \(s[0,i]\) 对 \(s[0,j]\) 的贡献系数为 \({m\choose i-j}\)（\(i,j\) 均为模 \(m\) 意义下）

由于是在模 \(3\) 意义下进行，可以对 \(m\) 三进制分解。这样每次要算 \(s[0]\) 对 \(s[3^{i}]\) 的贡献，由 Lucas 定理得对于 \(s[3^{i},j]\)，只有 \(s[0,j],s[0,j+3^{i}]\) 的系数不为 \(0\)，\(O(1)\) 即可

时间复杂度 \(O(n\log m)\)，非常优秀

回忆

强调一下 \(nm\le40\)，不妨设 \(m\le n\)，则 \(m\le6\)

考虑插头 DP。状态除了要记录轮廓线，还要记录当前出现的最大连通块大小、轮廓线上各连通块大小（最多 \(4\) 个，因此采用 \(8\) 进制最小表示法）。转移看当前格会和哪些连通块合并，更新大小即可

并不会算复杂度，不过跑起来松松松

明显是某种算法但不会算复杂度时：敢写敢 AC 暴搜估算

3.8

我 \(\star\)

不难想到把操作化为有向边。问题转化为操作一条有向边会使起点的权值转移到终点，求所有边操作至少一次后最多多少点有权值

对于一个点，操作其一条出边后可以紧接着操作其他出边，后面的操作不会引起权值合并，因此只需要将每个点操作一次
对于一个 SCC：若其中有点无初始权值，那么一定存在方案使得操作完该 SCC 中所有点并不发生合并，且可以指定最后空出的点；否则一定存在只合并一次的方案。因此 SCC 与点并无本质不同，可以使用 tarjan 缩点成 DAG

可以使用最小链覆盖求解，也有更简单的做法：

• 对于有权值且有出边的点，连边 \((S,i,1)\) 表示至少操作一次；建虚点并连边 \((i',i,\inf),(i',T,1)\) 代表该点被操作后就空出来了（拆点是为了避免直接 \(S\rightarrow i\rightarrow T\)）
• 对于无权值的点，连边 \((i,T,1)\) 代表可以无合并地接纳一个权值
• 对于原图中的边连流量 \(\inf\)，表示可以操作任意次

流量流到 \(T\) 相当于权值转移到本来无权值的点，最大流即最多多少权值不被合并

基环树做法不一定能直接迁移到图上，但可以通过环的性质来思考 SCC

想不出

本题中 \(E=2V-n\)，使用欧拉公式 \(R=E-V+2\) 转化为最大化交点个数

斜率为 \(\sqrt{3}\)，因此不存在交点为射线端点的情况，对坐标稍作变化可以把射线方向转化为向左/向下

考虑相对关系为 左上 右下 的两点，要么左上的点向下、右下的点向左，要么同向。否则调整为第一种情况不会影响原来的交点，且这两条线增加了一个交点。因此可以得到若 \((x,y)\) 向左，\(\forall x'>x,y' 向左，向右也有类似的结论

据此不难得到一定存在一条分界线，该线左上的点向下、右下的点向左。可以贪心地确定分界线：若左上的点多就向下，否则向左。正确性可以感性理解。使用 BIT 可以做到 \(O(n\log n)\)

题目名称

3.9

鱼死网破

纵坐标相同显然可以差分。问题是可能出现多个墙挡在一个鱼头胖士兵与一点之间，因此需要去重（只保留最上面的并）。\(O(nk)\) 做法类似括号匹配，不过 \(O(nk^{2})\) 也可

防水墙很少因此可以以防水墙端点为中心，用射线对一个半平面差分。射线的权值为 \(1/-1\)，极角排序后二分找到某点左侧的射线

本题不卡精，但实际上所有操作可以用整数实现

漏网之鱼

删数更好维护 mex ，因此不断左移右端点。由于 mex 单调，取 min 转化为区间覆盖

历史版本和有两种思路：强行懒标记维护，记录每个区间和需要累加多少次到历史和；

浑水摸鱼

讲过的题不会做/kk

暴力为把每个后缀的最小标号插入 trie
另一个常见部分分为 \(A_{i}\le30\) 且随机，那么可以认为较长的区间是两两不同的，对较短的暴力即可

考虑用 SA 的方法求本质不同子串，最小标号与相同颜色的位置有关，因此转化哈希方式即可使用二分+主席树 \(O(n\log^{2}n)\) 求 LCP，再用 stable_sort （比较不是 \(O(1)\) 时快于 sort）做后缀排序即可

// 不存长度查询 hash 值
uLL qry(int ql,int qr,int u,int l=1,int r=n) {
	if( !u ) return 0;
	if( ql <= l && r <= qr ) return t[u].h;
	int mid = l+r>>1;
	if( qr <= mid ) return qry(ql,qr,ls(u),l,mid);
	if( mid < ql ) return qry(ql,qr,rs(u),mid+1,r);
	return qry(ql,mid,ls(u),l,mid)*base[qr-mid] + qry(mid+1,qr,rs(u),mid+1,r);
}