5月杂题

1.CF1805F2 Survival of the Weakest (hard version)

先对 \(a\) 排序。先想想 F1，可以发现难点在于值域很大，但你发现我们可以把所有数减掉 \(a_1\) ，如果还剩 \(x\) 个操作就把答案加上 \(a_12^x\) 即可。每次一操作完就减，这样你可以发现序列中的最大值不会增大，这就做完了。

考虑 F2。 猜点结论，我们并不需要一直维护整个序列。设定阀值 \(L\) ，只取 \(a\) 中的一小段前缀来维护，并且操作完之后也只保留 \(L\) 这么长。发现对完了。

想想怎么证，不妨设 \(a_1=0\) ，若 \(a_2+a_3\le a_L\) ，说明 \(a'_1\) 到 \(a'_L\) 都是不需要 \(a_{L+1}\) 参与的。所以保留是正确的。否则的话至少 \(a'_1\) 到 \(a'_{L-1}\) 不需要 \(a_{L+1}\) 参与，有 \(a'_i=a_{i+1}-a_2\) 。再操作一次后至少前 \(L-2\) 个数是对的，我们有 \(a''_{L-2}\le a'_{L-1}-a'_{2}=a_L-a_2-(a_3-a_2)=a_L-a_3\) 。由于 \(2a_3\geq a_2+a_3>L\) ，则 \(a_L-a_3\le \frac{a_L}{2}\) ，于是 \(2a''_{L-2}\le a_L\) 。我们可以看做有效的部分减少了 \(2\) 。

由于每次减 2 时 \(a_L\) 减半，所以只需要把 \(L\) 约设为 \(2\log V\) 即可。复杂度 \(O(n\log V\log \log V)\) 。

2.hdu5404 Random Inversion Machine

考虑怎么对一个划分方案算答案。权值是每段的逆序对的个数的乘积，我们拆成在每个段内选一对数 \(u,v\)，来计算对于每一对数都满足 \(u>v\) 的概率。思考这个概率该怎么算，如果 \(u,v\) 都不是关键位置，那乘上 \(\frac{1}{2}\) 就好了；两个都是关键位置不合法；然后考虑剩下的限制怎么处理。首先我们不妨直接要求 \(p_{x_1}<p_{x_2}<\dots<p_{x_m}\) ，算完答案后再乘上 \(m!\) 。我们把 \(p_u<p_v\) 的限制看成 \(u\) 连向 \(v\) 的边。我们知道，若形成了内向树，那直接用 \(\prod \frac{1}{sz_i}\) 计算即可。考虑剩下的限制，相当于 \(x_i\) 上可能会挂上一个点 \(u\)，但边的方向有可能是 \(x_i\) 指向 \(u\) ，可以把它给容斥掉。为了方便计算，我们分析一下现在 \(\prod \frac{1}{sz_i}\) 的形式，其实就是 \(\frac{1}{sz_{x_m}!}\) 乘上那些被挂了点的 \(x_i\) 对应的 \(sz_{x_i}-1\) 。

现在考虑 dp ，设 \(f_{i,j,k}\) 是 \([1,i]\) 被划分成 \(j\) 段，且 \([1,i]\) 最后一个关键点对应的 \(sz\) 为 \(k\) 的所有方案权值之和，我们不要管 \(\frac{1}{sz_{x_m}!}\) ，最后乘上即可。转移考虑枚举 \(i,k\) 以及下一个段的末尾 \(r\) ，我们在枚举 \(r\) 的同时更新两个需要的系数 \(x,y\)，最后转移即 \(xf_{i,j,k}\rightarrow f_{r,j+1,k}\) ，\(yf_{i,j,k+t}\rightarrow f_{r,j+1,k+t+1}\) 。 其中 \(t\) 是 \((i,r]\) 的关键点个数。复杂度 \(O(n^4)\) 。

3.hdu5415 CRB and Substrings

考虑建出 sam。对于每个节点，考虑其 endpos 下标相邻的两个数 \(x,y\) 。对于 \(i\in (len_{f_u},len_u]\) ，若一个区间 \([l,r]\) 包含了 \([x-i+1,y]\) ，那就会让其答案减 1。

建出 fail 树来处理 endpos ，考虑做启发式合并，你发现所有合并一共只会产生 \(O(n\log n)\) 对不同的相邻二元组 \((x,y)\) 。我们对每个二元组处理出其第一次出现时对应的 \(len_u\) 和被分开时的 \(len_u\) 即可。考虑每次算答案，我们令 \(a_i\) 是 \([i-k+1,i]\) 的答案，初始 \(a_i=\tbinom{k+1}{2}\) ，然后每个二元组对 \(a\) 的贡献可以写成两段一次函数的形式，容易通过差分处理，这样就计算出了每个长度为 \(k\) 的子串的本质不同子串个数了。最后要找字典序最小者，通过哈希+二分算 lcp 来判字典序即可。

4.拟阵交

是这样一个过程，现在我们在求 \((U,I_1)\) 和 \((U,I_2)\) 的交。

不断拓展我们的独立集 \(S\) ，对于 \(x\in S,y\notin S\) ，如果 \(S-x+y\) 在 \(I_1\) 中就连边 \((x,y)\) ；在 \(I_2\) 中就连边 \((y,x)\) 。最后看有没有一条路径，从 \(y\notin S\) 且满足 \(S+y\) 在 \(I_1\) 中的点出发，最后走到 \(y\notin S\) 且满足 \(S+y\) 在 \(I_2\) 中的点。有的话就找一条最短的，把路径上状态全部翻转，否则就结束过程。

出现最多的一类拟阵应该是，\(U\) 是边，\(I\) 是所有不形成环的边集。