杂题选讲

· · 算法·理论

CF2062C Cirno and Operations

由于差分的特性，所以要么反翻转一次，要么不翻转。翻转更多次效果是等效的。

翻转一次就等价于最后差分出来的取相反数。于是直接暴力模拟即可。

QOJ9980. Boolean Function Reconstruction

有解的充要条件是对于 \forall T\subset S，f(T)\le f(S)。

首先我们可以找到所有满足 f(S)=1 的 S，将其中 x_i=1 的变量与起来。对于所有表达式或起来。这样子长度是 O(n2^n) 的。

由于按位与和按位或运算的特殊性，对于 S，若 f(S)=T，那么其超集肯定为真。

我们只需要高维前缀和统计一下，找到最小的一些 S，其个数最多是 15\choose 7 的级别。这个时候暴力构造可以做到 O(n{n\choose n/2})，还是不行。

可以发现上述做法浪费了一些公共部分，于是我们对于所有变量找到其公共部分，对于含它的放在一起，不含的放在另一侧进行构造。比如对于包含 x_1 表达式 f_1 和不包含 x_1 的表达式 f_2。我们就是可以列出 (x_1~\mathrm{and}~f_1)~\mathrm{or}~f_2 这样子的结构，然后在 f_1 和 f_2 内部分别对于 x_2 进行如上处理。这个过程可以在字典树上面完成。

P7738 [NOI2021] 量子通信

注意到 256=16^2，直接划分成 16 份。k_i\le 15，根据抽屉原理一定有一个公共块，直接暴力寻找然后枚举判断即可。其中单个块内期望个数是 \dfrac{n}{2^{16}}。

CF1758D Range = √Sum

构造初始序列 $1,2,3..,n$ 之后，调整法。令 $n\to n+2$，为了保持极差于是可以整体 $+1$ 和后缀（除了最后一个数） $+1$。通过这些调整使得和变成 $(n+1)^2$ 即可。 ## P6776 [NOI2020] 超现实树 只需要判定一条无限长的链的存在性。 假设在右子树内，如果左子树为空的话直接递归，否则必须只有一个点，不然的话可以构造出一个左边多一个无法加的点，右边不断伸长的链，这样子就不合法了。于是我们把给的 $m$ 颗树重新编号成为一种编号方式的树。然后遍历每个节点判定即可。 ## P7736 [NOI2021] 路径交点 对于 $k=2$ 的时候，首先两两匹配可以看成排列。交点个数其实就是 $p_i$ 排列逆序对数量，奇数 $-1$，偶数 $+1$，可以发现这个和行列式定义一样，于是直接对于邻接矩阵求一个行列式，也就是 $\det(A)$。 对于 $n_1=n_i$ 的时候，可以直接把求出相邻两列的行列式，然后再相乘，也就是 $\prod \det(A)$。因为偶数贡献 $+1$，奇数贡献 $-1$，两个奇数遇到就会变成偶数，其贡献也会变成 $(-1)\times (-1)=1$，因此上述按照贡献法是对的。 对于一般情况就不是排列了，也不是 $n\times n$ 的矩阵了。其实很容易猜到就是先 $\prod A$，将其变成 $n\times n$ 的矩阵，然后再求 $\det$。至于证明的话，就是 $\prod A$ 中 $(i,j)$ 就是第一列的 $i\to$ 最后一列的 $j$ 的路径方案数。而且还自动满足了路径不能重合这个条件，因为重合路径的逆序对差为 $1$，就抵消了。 ## ARC106E Medals 二分答案之后是一个二分图匹配。 有一个很重要的观察就是答案不会超过 $2nk$。 直接上 Hall 定理，直接高维前缀和判定一下就行了。注意判定的时候，交难求，正难则反一下变成并就很好做了。 ## P8991 [北大集训 2021] 出题高手 利用前缀和转化，设前缀和序列为 $S$。那么对于一个 $S_r$，贪心来想其可能的 $S_{l-1}$ 必然是一个后缀 $\min$（不妨设 $S_r>S_{l-1}$）。于是我们放到单调栈里面求解，随机序列前缀和的后缀 $\min$ 个数大概是 $O(\sqrt n)$ 级别的，这样子可以大幅减少可能的状态数。 同时因为是随机情况，所以可以发现可能作为答案的区间长度必然不会太长，取阈值为 $B=2000$ 即可。以上两个优化可以将可能区间个数大幅降低。 然后就是一个单点加，矩阵求 $\max$ 了。可以扫描线 $+$ 树状数组解决。这样子在 $\sqrt n$ 的基础上带一个 $\log$。也可以分块求解，这样子 $O(1)$ 修改，$O(\sqrt n)$ 查询就实现了平衡。 ## QOJ5061. Allin 由于有 $4$ 张未知牌，所以手中至少是炸弹。进一步分析其实是必须有同花顺。 剩下同花顺对于已经显示的 $5$ 张牌就有要求了。对于十几种情况进行暴力讨论一下就行了。 ## UOJ75.智商锁 可以用矩阵树定理算出 $G$ 的生成树个数 $f(G)$。 将两个图拼接起来个数就是 $f(G_1)\times f(G_2)$。我们随机 $5000$ 个大小为 $20$ 的图，两两拼接之后再两两组合，第一次直接暴力枚举，第二次用哈希表寻找。 ## ZJU 整洁度 > 对于两个串，其整洁度为最长公共 border 的长度。求一个串的所有前缀任意排列之后，相邻整洁度之和。同时有 $m$ 次修改，每次在末尾添加或者删除字符。$n,m\le 5\times 10^5。

第一步是很显然的转化，就是离线求出 fail 树上 LCA 深度之和。

如何重排？有一个结论就是按照 dfs 序重排就是最优的。

直接按照 P3320 [SDOI2015] 寻宝游戏 里面的方法用 std::set 维护 dfs 序即可，可以支持动态维护。

动态加减字符可能会让复杂度爆掉，我们直接建立 KMP 自动机就行了。

P6113 【模板】一般图最大匹配

存在线性代数做法。假如存在边 i\to j，我们就在对应位置填上 x_{i,j}，在对称位置填上 -x_{i,j}。

求一下行列式，如果存在完美匹配，那么 \det(A)\neq 0。证明就是对于奇偶环讨论一下，然后会消掉的。

推论是最大匹配数就是 \dfrac{\mathrm{rank(A)}}{2}，高斯消元可解。

其中随机数 x_{i,j}\in [0,P-1]，在模 P 的意义下求解。

对于多项式 \sum a_ix^i\equiv 0\pmod P，错误率是 \dfrac{n}{P}。