260113 模拟赛

260109 模拟赛 T1

因为我懒所以就放这了。

给定一个字符串 \(s\)，选择一个子串 \(t\) 满足长度不超过给定的常数 \(k\)，最大化 \(t\) 在 \(s\) 中不重叠的出现次数 \(cnt\) 与 \(len(t)-1\) 的乘积 \(cnt(len-1)\)。

\(|s|\le 2\times 10^5\)

考虑对每个 \(len\) 求出最大的 \(cnt\)，记为 \(f_{len}\)。注意到 \(if_i\le n\)（常数忽略不计），而固定一个 \(len\) 可以用哈希或者 SA \(O(n)\) 求出，此时分治就是对的，时间复杂度为 \(O(\sqrt n)\)。

证明考虑 \(f_{2^ki}\le \frac{n}{2^ki}\)，只有 \(\sqrt{\frac{n}{2^k}}\) 种。这玩意对 \(k\) 求和是 \(O(\sqrt n)\) 级别的。

T1

对于一个排列 \(p_{1\sim n}\)，称一次操作为选择若干二元组 \((x_1,y_1),\cdots(x_k,y_k)\)，使得 \(x_1,y_1,\cdots x_k,y_k\) 之中没有重复的数字，然后分别交换 \(p[x_i],p[y_i]\)。

记 \(f(p)\) 表示使得 \(p\) 有序的最少的操作次数，\(g(p)\) 表示使得 \(p\) 有序且操作次数最少的前提下，操作序列的方案数。两种方案不同，当且仅当存在某一个数字在两种方案中对应的另一个数字不同（不存在算 \(0\)）。

现在排列有 \(k\) 个位置没有确定。请你对于所有可能的排列求出 \(f(p)\) 和 \(g(p)\) 之和。

\(n\le 10^5,~k\le 12\)

考虑如何对一个固定的排列求答案。注意到一个置换环会产生 \(len\) 的贡献，两个长度相等的置换环可以匹配并一起产生 \(len\) 的贡献。把一种长度的置换环一起考虑，其方案数 \(f(len,cnt)\) 可以从 \(f(len,cnt-1),f(len,cnt-2)\) 递推而来。于是做完了。

注意到给定的排列形如若干个置换环和不超过 \(k\) 条链，我们可以将链进行任意拼接，形成完整的置换环。于是枚举 \(k\) 条链的贝尔数即可。

T2

给定一个长度为 \(2n-1\) 的序列，值域为 \([-k,k]\)，你可以任意填它的偶数项。然后你选择一个区间，然后捣蛋鬼选择一个区间，你的得分为你的区间和减去捣蛋鬼的区间和。两区间可以有交，可以包含，也可以为空。捣蛋鬼的区间中不能包含负数。捣蛋鬼会最小化你的得分。请你最大化你的得分。

\(n\le 5000\)

首先你肯定只会填 \(-1\) 和 \(k\)。然后肯定是你选择的区间外面都填 \(-1\)。记全局最大值为 \(mx\)，你选择的区间为 \([l,r]\)，那么捣蛋鬼的区间和为 \(\max\bigl(mx,\max_{[l',r']\subseteq [l,r]}sum(l',r')\big)\)（\([l',r']\) 中不能包含负数）。

显然有 \(a[l-1],a[r+1]<0\)，\(a[l],a[r]\ge 0\)（顶到边界了不管）。考虑给定的奇数位中的那些负数。我们尝试证明，对于你选择的区间 \([l,r]\)，有 \(l-1,r+1\) 是奇数（\(l=1\) 或 \(r=n\) 的情况除外）。考虑 \(r\ne n\) 且 \(r+1\) 是偶数，那么 \(a[r+1]=-1\)。视 \(a[r+2]\) 的存在性以及正负性向区间右边追加 \(1\sim 2\) 个（非负）数，你的区间和增加 \(\Delta\ge 0\)，捣蛋鬼的区间和增加 \(\le\Delta\)，所以得分增加，得证。

由于以上结论未经过对拍，所以请读者慎重。

考虑给定的奇数位中，两个负数中间的那一段非负数。由于这段中最多被插入区间长度个 \(-1\) 作为分隔，因此对捣蛋鬼的贡献只有本质不同（指得到的区间和/最大子段和不同）的区间长度个。于是我们枚举捣蛋鬼的答案，然后贪心填入尽可能少的 \(-1\)，然后跑最大子段和即可。由于捣蛋鬼的答案只有 \(O(n)\) 种有用（指算出来的最大子段和不同），因此可以二分或者分治做到 \(O(n^2\log nk)\)，其实可以通过。