逆天记录 - 2

P5366 [SNOI2017] 遗失的答案

好题！首先判掉 $G\nmid L$ 的情况，接下来将 $n$ 与 $L$ 都除上 $G$。

假设 $L$ 分解质因数后的集合为 $\{(p_i,\alpha_i)\}$，原问题等价于选出一个 $\{1,2,\dots n\}\cap\{x|L\equiv 0\pmod{x}\}$ 的子集 $S$，满足对于任意的 $(p_i,\alpha_i)$，$\min_{x\in S} cnt_{p_i}(x)=0$，$\max_{x\in S}cnt_{p_i}(x)=\alpha_i$。

由于 $\omega(L)=|\{(p_i,\alpha_i)\}|$ 很小，最大只有 $8$，因此考虑状压。

定义一个长度为 $16$ 的二进制数 $s$，前八位表示对于每个 $(p_i,\alpha_i)$，是否满足 $\min_{x\in S} cnt_{p_i}(x)=0$，后八位则表示对于每个 $(p_i,\alpha_i)$，是否满足 $\max_{x\in S}cnt_{p_i}(x)=\alpha_i$。

从而每个 $1\sim n$ 中的 $L$ 的因数都可以被表示为值域为 $[0,2^{16})$ 的整数，原问题等价于选择一些数，使得他们的或和等于 $2^{16}-1$。

首先把二进制表示 $s$ 相同不同的数归为一类，假设第 $i$ 类的二进制表示为 $s_i$，个数为 $c_i$。

考虑 dp，令 $f_{i,j}$ 表示考虑了前 $i$ 种二进制数，其状态的或和 $=j$ 的方案数，则有：

$$f_{i,j}\to f_{i+1,j}\\ f_{i,j}\to f_{i+1,j|s_{i+1}}\times (2^{c_{i+1}}-1)$$

但是询问中需要钦定某个数不能选，因此考虑做出前缀与后缀的 dp，假设分别为 $f,g$。

则对于每个 $i$，我们需要将 $f_{i-1}$ 与 $g_{i+1}$ 合并，而这是一个或卷积的过程，可以直接 FWT 完成。合并后，枚举前后缀合并后的状态，找出 $s_i|mask=2^{16}-1$ 的 $mask$，将其 dp 值相加后乘上 $2^{cnt_i-1}$ 即可（由于钦定了选择一个数，另外 $cnt_i-1$ 个数是否选择随意）。

时间复杂度 $O(d(L)\times \omega(L)\times2^{2\omega(L)}+q\times \omega(L))$。

CF1805F2 Survival of the Weakest (hard version)

神奇的 3100，代码量不大，结论不难猜，但是证明有些困难。

如果不考虑时间问题直接模拟，发现 $a$ 的值域会过大，导致无法使用平凡的变量存储。

考虑缩小值域：将 $a$ 从小到大排序后，维护 $b_i:=a_i-a_1$，在比较 $a_i+a_j$ 与 $a_{i'}+a_{j'}$ 时只需要比较 $b_i+b_j$ 与 $b_{i'}+b_{j'}$ 即可。

考虑 $b$ 的值域，操作后新的序列（设为 $c$） 中，$c_1=b_1+b_2$，$c_{n-1}\le b_1+b_n$（考虑选取 $b_1+b_2,b_1+b_3,\dots,b_1+b_n$ 可以使最后一个值取到 $b_1+b_n$，因此最后一个值一定小于等于 $b_1+b_n$）。新的 $b'$ 中，$b'_{n-1}=c_{n-1}-c_1=b_n-b_2$，因此值域不会增大。

于是找到了一种合理的存贮 $a$ 序列且能进行大小比较的方式。

能够比较后，考虑暴力做法：如何在一个长度为 $n$ 的序列中取出两两之和前 $n-1$ 小的。

考虑维护一个堆，存贮接下来可能出现的较小的和与他们对应相加的编号。

初始时，堆中放入 $a_2+a_1,a_3+a_1,\dots,a_n+a_1$。每次去除最小的一对 $(x,y)$ 后，将 $a_x+a_{y+1}$ 加入堆中。不难发现每次可能的最小值一定会在堆中，这样模拟一次的复杂度为 $O(n\log n)$。

至此，我们在 $O(n^2\log n)$ 复杂度内解决问题，可以通过 Easy Version。

考虑如何优化。感性理解下，较大的 $b_i$ 是不会出现在下一轮中的。考虑证明：

如果 $b_n$ 在这一轮操作中没有被忽视（即在下一轮中他作为一个数之中的一个元素），那么一定满足 $b_n\le b_2+b_3$（因为若 $b_n>b_2+b_3$，那么 $b_1+b_2,b_1+b_3,\dots,b_1+b_{n-1},b_2+b_3$ 这 $n-1$ 个数会被放入下一轮，$b_n$ 就被忽视了），因此 $b_n\le b_2+b_3\le 2b_3$。

而操作后的序列中的最后一个数变成了 $b_n+b_1-(b_1+b_2)=b_n-b_2$，如果再操作一次，那么最后一个元素将 $\le (b_n-b_2)-(b_3-b_2)=b_n-b_3\le b_3$。因此，$b_n$ 在两次操作后至少减半。

考虑将 $b_n$ 推广到所有的 $b_i$ 仍然成立，因此只需要保留前 $L=2\log V+\epsilon$ 个元素，证明：

对于一次对序列 $b$ 的操作：

• 若 $b_L\ge b_2+b_3$，那么 $b_1,b_2,\dots b_L$ 就可以确定新的序列。
• 若 $b_L< b_2+b_3$，那么可以确定新的 $b'_1,b'_2,\dots,b'_{L-1}$，再操作一次后可以确定新的 $b''_1,b''_2,\dots,b''_{L-2}$，而已经证明了 $b_L\ge 2b''_{L-2}$，因此这样的 $b_L$ 不会超过 $2\log V$ 次。

综上，$L=2\log V+\epsilon$ 得证。取前 $L$ 小的 $a$ 进行模拟即可。

时间复杂度优化为 $O(n\log V\log\log V)$，可以通过 Hard Version。

CF1552H Guess the Perimeter

第一次询问将所有 $200\times 200$ 个点涂上色，询问得到的结果即为矩形的面积。

接下来 $3$ 次询问考虑求出矩形的长，假设矩形长为 $h$，宽为 $w$。询问方法很神奇。

首先有一个结论：当询问将所有横坐标为 $d$ 倍数的点染色色后，当且仅当 $d\mid h$ 时，返回的面积交为 $\frac{wh}{d}$。证明显然。

把这个询问运用于二进制上。尝试超出最大的 $k$ 使得 $2^k|d$，那么在询问横坐标为 $2^k$ 倍数的点时，返回的结果位 $\frac{wh}{2^k}$；当询问横坐标为 $2^{k+1}$ 倍数的点时5，返回的结果为 $\frac{w(h\pm 2^k)}{2^{k+1}}$。将两次结果乘 $2$ 做差处理后，即可求出 $w$，随后可以求出 $h$，即可求出答案。

由于 $k\in [1,7]$，因此求最大的 $k$ 可以使用二分，恰好需要 $\lceil\log_2 7\rceil=3$ 次询问。加上记忆化后可以不用询问直接得到 $2^{k+1}$ 的结果（若 $k=7$，则 $2^{k+1}$ 答案必定为 $0$）。

这样，原问题在不超过 $4$ 次询问内得到解答。

CF573D Bear and Cavalry

将所有人与马按照能力值排序后，有结论：第 $i$ 个人对应的马在 $[i-2,i+2]$ 之间。

证明考虑如果有一对 $(i,i+3)$ 的匹配，必定可以做出调整使其依然合法，并根据排序不等式，证明不劣于当前匹配方式。

进一步的，所有的匹配只可能有如下三种类型：

• 第 $i$ 个人与第 $i$ 匹马匹配。
• 第 $i,i+1$ 个人与第 $i,i+1$ 匹马匹配。
• 第 $i,i+1,i+2$ 个人与第 $i,i+1,i+2$ 匹马匹配。

证明可以分类讨论并进行调整。

得出结论后，设 $f_{i}$ 表示按能力值排序后前 $i$ 个人与前 $i$ 匹马对应后的能力值最大值。

容易发现，$f_{i}$ 只会从 $f_{i-1},f_{i-2},f_{i-3}$ 得来，因此可以直接放到线段树上用矩阵乘法维护。

修改就是序列 ddp 的过程。时间复杂度 $O(k^3n\log n)$，其中 $k$ 为矩阵大小，$k=3$。

P9479 [NOI2023] 桂花树

将原题面的两个条件转化一下：

• 对于 $[1,n]$ 中点构成的虚树，就是给出的树。
• 对于任意的前缀 $[1,x]$ 构成的虚树，其所包含的点的编号都要 $\le x+k$。

因此原问题就是一个树虚树个数的问题。

考虑 $k=0$ 时，每个点要么插在原来的一条边上，要么挂在一个点下面，方案数 $2sz-1$。

考虑 $k>0$ 时，我们要给每一个点 $>x$ 的点预留好位置。设 $f_{i,S}$ 表示考虑了前 $i$ 个点构成的虚树，已经预定了接下来 $k$ 个点中 $S$ 集合点位置的方案数。

转移时分三种情况：

• 不用 $>x$ 的点，同 $k=0$，系数 $2sz-1$。
• 用 $>x$ 的点，把他放在一条边中间，然后挂在这个点下面，系数 $sz-1$。
• 填补之前一个预定的位置，系数 $1$。

按照对应的系数转移即可，时间复杂度 $O(mk2^k)$。

CF1370F2 The Hidden Pair (Hard Version)

约定称两个隐藏点为 $s,t$。

第一次询问问所有点，这样可以得到 $s$ 与 $t$ 的距离 $len$ 与 $s$ 到 $t$ 路径上的一个点。

以这个点为根，进行 dfs，求出每个点的深度。接下来要求出 $s,t$ 中深度较深点的深度。

考虑二分这个深度。询问时问出这个深度的所有点，如果答案 $=len$，那么较大深度一定大于二分值。二分后的同时还能求出深度较大点的编号（不妨设其为 $s$）。

考虑如何求出 $t$。以 $s$ 为根进行 dfs，询问所有深度 $=len$ 的点，返回的点即为 $t$。

这样的询问次数为 $1+\log n+1=12>11$，还差一次。

由于较大的深度一定 $\ge\lceil\frac{len}{2}\rceil$ 且 $\le len$，因此可以省去一次二分，恰好 $11$ 次。

P9060 [Ynoi2002] Goedel Machine

考虑对于整个序列的答案怎么算。令 $c_p$ 表示所有数中 $p$ 的倍数的数的个数。

对于每个质数 $p$，当选出子集中所有数都是 $p$ 的倍数时，会有 $p$ 的贡献，因此贡献是 $p^{2^{c_p}-1}$。

对于每个质数算出贡献后相乘就是答案吗？答案是否定的。

加入所有数都是 $p^2$ 的贡献，那么这个子集的贡献是 $p^2$，但按照原来方法只计算了 $p$，增量为 $p$，因此还要乘 $p^{2^{c_{p^2}}-1}$，再增量同理。

因此对于每个质数的每次次幂，都可能对答案产生贡献。把所有质数和质数的次幂拿出来，就有 $O(\frac{n}{\log n}\times \log n)=O(n)$ 个。

一种朴素的计算方法是通过莫队。但是增加或删除元素需要枚举所有质因子与质因子倍数，但次是 $O(\log^2n)$ 的，因此总复杂度 $O(n\sqrt n\log^2n)$，无法通过。

考虑对质数进行根号分治。

对于 $>\sqrt n$ 的质数，每个数中最多只有一个，且只能是一次幂，这部分做莫队是可以做到 $O(n\sqrt n)$ 的。

对于 $\le \sqrt n$ 的质数即其次幂，一共只有 $O(\sqrt n)$ 种，对他们做前缀和，每次询问之枚举每个质数与其次幂，并提前预处理每种出现次数的贡献即可，时间复杂度 $O(n\sqrt n)$。

因此设 $n,m,V$ 同阶，最终时间复杂度 $O(n\sqrt n)$。

CF283E Cow Tennis Tournament

正难则反，考虑计算不是三元环的三元组个数。那么就是两个点都指向一个点。

考虑从前往后做扫描线，用线段树维护每个点的反转次数，然后计算出每个点的入度即可。

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

CF542B Duck Hunt

考虑将猎物往左走看成猎人往右走，那么猎人在 $t$ 时刻开枪能射杀 $l_i\le t\le r_i$ 的猎物 $i$。

令 $f_{i,j}$ 表示考虑了 $r\le i$ 的猎物，上一次开枪在时刻 $j$，能射杀的最多猎物数量。

考虑转移，$f_{i,\sim}$ 到 $f_{i+1,\sim}$ 转移时，先不考虑杀新的鸭子，那么等价于 $\sim\le i$ 的保留原来的值，$\sim=i+1$ 的要取前缀 $\max$。

再考虑开枪，那么就能让 $f_{i+1,[l,i+1]}$ 的值 $+1$，而且这个操作只有 $O(n)$ 次。

直接做复杂度 $O(V\log V)$，但是考虑 dp 的值域是 $O(n)$ 的，因此接的前缀 $\max$ 种类数也是 $O(n)$ 的，直接维护会变化的位置即可。

时间复杂度被优化为 $O(n\log V)$。

ABC313F Flip Machines

对于 $x\not=y$ 的机器 $(x,y)$，如果他被操作到了至少一次，那么他的期望价值是 $\frac{a_i+b_i}{2}$。

因此，对于 $x=y$ 的机器 $(x,y)$，如果 $a_x< b_x$，那么就选择他来操作一次，否则是没用的。

接下来考虑将所有卡片分成两个集合，对于 $a_i>\frac{a_i+b_i}{2}$ 的卡片分到 $S$，其余分到 $T$。那么操作 $S$ 中卡片期望会减少，操作 $T$ 中卡片期望会增加。

对于所有的机器，如果 $x,y$ 同属一个集合，那么 $S$ 中不选最优，$T$ 中选择最优。

剩下的问题是对于 $x\in S,y\in T$ 的卡片是否选择，要求出这个值的最大期望。假设 $n=|S|,m=|T|$。

考虑以下两种做法：

• 枚举 $S$ 集合中的每个元素是否被选到，那么可以选所有与 $S$ 中选到的元素有边的 $T$ 中的元素，直接求和。时间复杂度 $O(2^nm)$。
• 考虑 dp，令 $f_{i,k}$ 表示考虑了 $S$ 中的前 $i$ 张卡片，与 $T$ 中的 $k$ 集合点右边的 $S$ 集合最小负贡献。最后枚举每个 $T$ 中的卡片是否被边覆盖。时间复杂度 $O(2^mn)$。

由于 $n+m\le N=40$，所以直接对于 $n,m$ 大小分治即可，时间复杂度 $O(2^{n/2}n)$。

P9535 [YsOI2023] 连通图计数

删掉每个点后的连通块个数等价于这个点在圆方树上的度数。称圆方树上的一个度数 $>2$ 的点为非平凡方点。

首先考虑 $m=n-1$ 的情况，原图是一棵树，由 prufer 序列易得树的形态为 $\dfrac{(n-2)!}{\prod(a_i-1)!}$。

考虑圆方树上只有圆点与方点之间有边，因此圆方树的边数即为 $\sum a_i$，点数即为 $\sum a_i+1$。

当 $m=n$ 时，图上圆点个数为 $n$，非平凡方点个数为 $1$，因此平凡方点的个数为 $\sum a_i-n$。

考虑所有点度数和为 $2\sum a_i$，因此非平凡方点的度数为 $2\sum a_i-\sum a_i-2(\sum a_i-n)=2n-\sum a_i$。

随后可以根据 prufer 序列得出圆方树的形态为 $\dfrac{(n-1)!}{(2n-\sum a_i-1)!\prod (a_i-1)!}$，然后还要乘上方点对应环的形态 $\dfrac{(2n-\sum a_i-1)!}{2}$。

当 $m=n+1$ 时，图上可能有一个或两个方点。两个方点时可以枚举度数，计算方式同上。

CF1861F Four Suits

对于每个人，枚举最终选择的是哪个物品，那么最优情况一定是把剩下的所有这种卡牌尽可能分给他。

二分答案，判定剩下的所有人的所有物品是否能够都 $\le L$。限制形如：每个人需要选择 $ret_i$ 的物品，第 $i$ 个人还能选择 $b_{i,j}$ 的 $j$ 种物品，每种物品还剩下 $c_j$ 个，判定能否让所有人都选满物品。

考虑暴力判定，由源点向每个左部点连一条流量为 $ret_i$ 的边，每个左部点向每个右部点连一条流量为 $b_{i,j}$ 的边，每个右部点向汇点连一条流量为 $c_j$ 的边，跑最大流判定是否 $=\sum ret_i$。

由于最大流 $=$ 最小割，因此只需要求出最小割即可。右部点只有 $4$ 个，因此可以 $2^4$ 枚举每个右部点被割到 $S$ 集合还是 $T$ 集合。

枚举完后，对于每个左部点，他被分到 $S$ 集合还是 $T$ 集合，每个左部点的割的贡献是独立的，取较小的相加即可。

发现每个左部点较小的割的和形如 $val+\sum \min\{v_i,L-w_i\}$，那个 $\min$ 可以算出切换左右的 $L$ 的时刻，按照这个切换时刻从小到大排序，二分即可。

时间复杂度 $O(nm^22^m\log n\log V)$，其中 $m=4$。

P5812 [IOI2019] 天桥

好题，但是搬到 NOIP 模拟赛属实逆天，场上只会 $57$。

考虑如果不存在横跨 $s$ 和 $t$ 的天桥，那么显然不会向左走，且每次上下行一定在某一个天桥的左右端点处。

出现横跨 $s$ 的天桥时，如果要上这座天桥，一定是向左走或向右走到一个最近能上去的房子，然后上去走这座天桥。

因此对于这些天桥，直接将其以 $s$ 或 $t$ 为分界拆成若干段天桥即可。

考虑上行或下行后一定是走到一个距离他最近的天桥继续走，因此连边时只要将某一个天桥的某个端点向那幢楼的前驱和后继连边即可，找前驱后继可以直接扫描线 + 线段树维护。

这样点数和边数都是 $O(m)$ 的，直接跑单源最短路即可，时间复杂度 $O(m\log m)$。

CF1267G Game Relics

最优策略一定是先抽卡，后买卡。

考虑如果当前已经获得了 $i$ 张卡，那么通过抽卡获得下一张卡的概率是 $\frac{n-i}{n}$，因此期望抽 $\frac{n}{n-i}$ 次，其中最后一次花费是 $x$，其余均为 $\frac{x}{2}$，因此期望花费是 $(\frac{n-i}{n}-1)\times\frac{x}{2}+x$。

但是这与买卡不好直接比较，又由于买所有卡都是等价的（后面全都是买卡），因此可以看作随即买一张卡，则期望花费是 $\frac{sum-s}{n-i}$，其中 $s$ 表示已经获得的卡的价格之和。

这样就可以直接贪心比较，选择较小的作为下一步决策。

随后通过 dp 算出所有形如抽了 $i$ 张卡，抽中卡的价格之和为 $s$ 的局面的出现概率 $f_{i,s}$，乘上期望花费相加即可。

P5331 [SNOI2019] 通信

朴素的费用流可以先进行拆点，将每个点拆成入点和出点，每个点可以从前面的任意一个点连一条费用为代价的边，连一条从虚点连来的费用为 $W$ 的边。

但这样建图的点数是 $O(n)$ 的，边数是 $O(n^2)$ 的，无法通过。

考虑优化，对于整个序列进行分治。由于边是从左向右连结的，因此在分治 $[l,r]$ 时，只需要处理 $[l,mid]$ 中的点向 $(mid,r]$ 中的点连的边。

将两边的点按照点权排序，假设处理左边点权 $\le$ 右边点权的边，那么给右边排序后的每个点建一个虚电，从左边的点先向右边第一个 $\ge$ 他的权值的点连边，再在右边相邻的点之间连一条链即可。

这样点数与边数都变为 $O(n\log n)$，直接跑费用流即可。