Educational Codeforces Round 160 (Rated for Div. 2)

Swap and Delete

题目

输入长度为 \(n\) 的二进制字符串，输出执行操作需要的最小成本，使得对于操作之后得到的字符串 \(t\) 的每个字符 \(t_{i}\)，都有 \(t_{i}\neq s_{i}\)，其中 \(1\leq i\leq |t|\)。有两种操作：

• 从字符串 \(s\) 中删除一个字符，操作的成本为 \(1\)。
• 交换字符串 \(s\) 中的两个字符，操作的成本为 \(0\)。

数据范围：\(1\leq n\leq 2\cdot 10^{5}\)。

思路

由于只有删除操作会导致成本增加，所以我们只需要让字符串 \(t\) 尽可能长就好。首先对字符串 \(s\) 中的 \(0\) 和 \(1\) 计数，然后贪心的构造字符串 \(t\)，如果 \(s_{i}=0\)，则 \(t_{i}=1\)，反之亦然，直到不能增加长度为止。最后最小成本就是 \(n-|t|\)。

Game with Multiset

题目

输入一个整数 \(m\) 表示查询的次数，以及 \(m\) 行查询，每行包含两个整数 \(t_{i}\) 和 \(v_{i}\)。初始时你有一个空的多重集合（multiset）：

• 如果 \(t_{i}=1\)，将元素 \(2^{v}\) 加入集合。（\(0\leq v_{i}\leq 29\)）
• 如果 \(t_{i}=2\)，询问 \(v_{i}\) 是否可以表示为当前集合的某个子集之和，并输出 YES 或 NO。（\(0\leq v_{i}\leq 10^{9}\)）

数据范围：\(1\leq m\leq 10^{5}\)。

思路

• 方法一：使用数组对 \(t_{i}=1\) 的 \(v_{i}\) 计数，对于每个询问，从低到高遍历 \(v_{i}\) 的二进制 \(1\)。假设当前遍历到 \(2^{k}\)，如果集合中存在 \(2^{k}\) 则当前位可以被表示（假设集合中有 \(c_{k}\) 个 \(2^{k}\)），并且集合中剩余的 \(2^{k}\) 可以合并为 \(\frac{c_{k}-1}{2}\) 个 \(2^{k+1}\)，然后遍历下一位，这样最终可以判断 \(v_{i}\) 是否能被集合表示。
• 方法二：使用数组对 \(t_{i}=1\) 的 \(v_{i}\) 计数，对于每个询问，从高到低遍历 \(v_{i}\) 的二进制 \(1\)。假设当前遍历到 \(2^{k}\)，则执行 \(v_{i}=v_{i}-(\min{(v_{i}>>k,c_{k})}<<k)\) 操作（假设集合中有 \(c_{k}\) 个 \(2^{k}\)），表示将集合中的元素尽可能填补到 \(v_{i}\) 中，最终 \(v_{i}\) 还需要多少值，如果最终 \(v_{i}=0\) 则它可以被集合表示。

Array Collapse

题目

输入长度为 \(n\) 的数组 \(p\)，其中的元素互不相同。输出执行任意次操作能够得到的不同数组个数，结果对 \(998244353\) 取余。每次操作可以选择 \(p\) 的一个子数组（假设为 \([i,j]\)），将子数组中除最小值之外的所有数删除。

数据范围：\(1\leq n\leq 3\cdot 10^{5}\)，\(1\leq p_{i}\leq 10^{9}\)。

思路

• 方法一：使用分治 + 线段树的时间复杂度为 \(O(n\log{n})\) 的思路，比赛时大概就是这个思路，不过想岔了一点。对于区间 \([i,j]\)，使用线段树找到区间最小值的下标，然后左右分治求不同数组的个数，最后将两者相乘。这个方法还有一些特殊情况需要维护，具体看代码。
• 方法二：参考灵神视频单调栈优化 DP，将 \(f[i]\) 定义为以 \(p[i]\) 结尾的子序列个数，然后利用动态规划转移，最后将所有 \(f[i]\) 求和得到答案。单调栈这个规律有点难想，具体看视频吧。