2023 逆天记录 - 2

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\) 时，图上可能有一个或两个方点。两个方点时可以枚举度数，计算方式同上。