随机乱做 Part 1

标签：题面 pastebin Part 随机 https ubuntu com dp

「CF1712F」Triameter（启发式合并）
「CF1479D」Odd Mineral Resource（随机化 + 主席树二分）
「CF1363F」Rotating Substrings（神仙 dp）
「CF1550E」Stringforces（二分 + 状压 dp）
「CF1383E」Strange Operation（dp）
「CF1539E」Game with Cards（二分 + ST 表 + dp）
「CF1704D」Magical Array（性质 + 哈希）
「CF1704E」Count Seconds（暴力 + 拓扑排序）
「CF1539F」Strange Array（线段树）
「CF1614E」Divan and a Cottage（动态开点线段树）

「CF1712F」Triameter（启发式合并）

题面

这是一道好题阿。

考虑加边之后，\(d(u,v)=\min(dis(u,v),f_u+f_v+x)\)，其中 \(dis(u,v)\) 为 \(u\) 和 \(v\) 的树上距离，\(f_u\) 为 \(u\) 到最近的叶子节点的距离。原因显然。

问题的关键来了：求树上与两点距离有关式子的最值可以考虑启发式合并，因为合并子树的时候两点的 \(\bf{LCA}\) 就是当前 dfs 到的点。

考虑维护一个 \(vec_{u,i}\) 表示 \(u\) 子树内 \(f=i\) 的点的最大深度。

那么合并的时候可以直接取 \(\max\)。

对于求解答案，我们每一次启发式合并的时候就遍历每一个询问，看这个询问的答案能否 \(+1\)。具体的，当我们合并 \(u\) 和 \(v\) 时（\(size_{vec_u}>size_{vec_v}\)），枚举 \(i:0\sim size_{vec_v}-1\)，当 \(j=\max(0,ans+1-i-x)<size_{vec_u}\) 且 \(dis(vec_{u,j},vec_{v, i})\ge ans+1\) 时，\(ans\) 就可以 \(+1\)。

为什么呢？因为此时若选择 \(vec_{u,j}\) 和 \(vec_{v,i}\) 对应的点，那么 \(dis\ge ans\) 并且 \(j+i+x=ans\)，满足条件。

秒极！！！！！！！！！！！！！！！！！！！！！11

代码：https://pastebin.ubuntu.com/p/pjXCBt75MT/。

「CF1479D」Odd Mineral Resource（随机化 + 主席树二分）

题面

好题啊。

这种路径出现了奇数次之类的就要想到异或（虽然确实也想到了）。

下一步特别神奇：对每种颜色赋一个随机权值，然后建一棵主席树，查询的时候在主席树上二分。

可能这种有关出现的问题都与随机权值有关吧……

关于主席树二分：首先肯定要在 \([l,r]\) 中异或和不为 \(0\)，然后看 \([l,mid]\) 中异或和是否为 \(0\)，如果不为零就递归下去找，否则就在 \([mid+1,r]\) 中寻找。

代码：https://pastebin.ubuntu.com/p/T7qy6dcc5v/。

「CF1363F」Rotating Substrings（神仙 dp）

题面

太神仙了吧……

无解显然就是组成 \(s\) 和 \(t\) 的字符集合不同。

考虑操作的过程其实就是把一个字符往前面提任意个位置，那么我们就需要最小化移动的字符个数，即最大化不动的点的个数。

设 \(f_{i,j}\) 表示 \(s_{1\dots i}\) 与 \(t_{1\dots j}\) 匹配的最小移动次数。注意到这里的匹配其实是在 \([i+1,n]\) 中再选一些数出来移动到前面使得它们匹配。

神奇的一步出现了：对于移动的字符的贡献的计算，我们考虑在它的原始位置计算。

转移：

如果 \(s_i=t_j\)，那么 \(f_{i,j}=f_{i-1,j-1}\)。
如果 \(s_i\) 移到前面去，那么就有 \(f_{i,j}=f_{i-1,j}+1\)。
如果是匹配了 \(t_{1\dots j-1}\) 之后，再从后面拿一个与 \(t_j\) 相同的字符到 \(i\) 之后，贡献是 \(f_{i,j}=f_{i,j-1}\)，条件是 \([i+1,n]\) 里 \(t_j\) 的字符数量要比 \([j+1,n]\) 里 \(t_j\) 的字符数量多。

边界就是 \(f_{0,i}=0\)，仔细想想发现其实是对的。

至于整个算法为什么是对的，题解里有一个比较好的解释。

代码：https://pastebin.ubuntu.com/p/4dvsC4QQ8T/。

「CF1550E」Stringforces（二分 + 状压 dp）

题面

首先肯定是二分答案 \(mid\)。

预处理出 \(nxt_{i,j}\) 表示在 \(i\) 后有连续 \(mid\) 个字符 \(j\) 的最近右端点，然后设 \(f_S\) 表示集合 \(S\) 中的字母已经满足条件的最近右端点，转移枚举当前最后一个满足的字母是 \(c\)，然后 \(f_{S}\leftarrow\min(f_S,nxt_{f_{T}+1,c})\)，其中 \(T\) 就是 \(S\) 去除 \(c\) 后的结果。

check 只需要判断 \(f_U\) 是否 \(\le n\)。

代码：https://pastebin.ubuntu.com/p/3Bg9sVNwXC/。

「CF1383E」Strange Operation（dp）

题面

不难发现题目的操作其实就是把序列分成若干段，然后把每一段都变成一个数，值是里面所有数的或。问改后的序列有几种情况。

首先，首尾的 0 都是可以单独考虑的，方案数为 \((cntL+1)(cntR+1)\)，接下来我们只需要考虑中间的情况。

对于中间的数，一个 1 可以被删除当且仅当它的两端都有 1。

把中间两个 1 之间连续 0 的个数抠出来变成一个序列，例如 \(s=\texttt{0010001101001010}\) 对应的序列就是 \(A=\{3,0,1,2,1\}\)。

那么我们就相当于要找到能与原来的 \(A\) 序列匹配的 \(B\) 序列的个数，这里的“匹配”是指找到一个对应关系使得能将 \(A\) 序列划分成若干段，每一段都和 \(B\) 序列对应，段内最小值要 \(\ge\) \(B\) 序列里对应的值。

然后怎么想 dp 都会算重……自闭了。

感觉接下来的有点像 UOJ748 机器人表演，就是贪心匹配一个最早的位置。也就是设 \(f_i\) 表示匹配到 \(i\) 位置的方案数，那么如果这个位置上填 \(j\)，从 \(k\) 位置转移过来就要满足 \([k+1,i-1]\) 中的 \(A\) 值都要 \(<j\)，因为 \(i\) 值最早的匹配位置。所以只要记录填 \(j\) 之后前面最大的 \(A_k\ge j\)，然后前缀和转移就行了。

代码：https://pastebin.ubuntu.com/p/rj2WRN9CBT/。

「CF1539E」Game with Cards（二分 + ST 表 + dp）

题面

这种交换先后手的题目，可以考虑枚举在那个地方交换先后手，然后进行 dp。

也就是设 \(dp_{i,0/1}\) 表示 \(i\) 这个位置填 \(0/1\) 是否可行，转移就枚举上一次交换在哪里，看这个区间是否满足条件。

举例来说，如果 \(i\) 要填 \(0\)，那么前面就一定有一个 \(j\) 满足 \(dp_{j,1}=1\) 并且中间所有的 \(k\) 都在 A 的区间中、\(k_j\) 在 \([j,i]\) 的 B 的区间中。前者可以记一个前缀和，后者可以提前二分 + ST 表预处理出来。填 \(1\) 类似。

具体的，dp 的时候需要动态维护，开一个 set 就行了。

代码：https://pastebin.ubuntu.com/p/kGSpMnmS45/。