CF1941 BCDEF 题解

B

如果要将 \(a_1\) 删成 0，只能对 \(a_2\) 进行操作：\(a_1\gets 0,a_2\gets a_1-2\times a_1,a_3\gets a_3-a_1\)。\(a_1=0\) 后，要将 \(a_2\) 删成 0，只能对 \(a_3\) 进行相同的操作；要将 \(a_3\) 删成 0，只能对 \(a_4\) 进行相同的操作……依此类推。可以看出，这是唯一可行的删除方法。

不难发现，如果整个数组能够删空，那么对 \(a_{n-1}\) 操作后，我们将同时得到 \(a_{n-1}=a_n=0\)，此时答案为 YES，否则答案为 NO。当然，如果在中途发现操作进行不了，比如对 \(a_3\) 操作时发现 \(a_3<2\times a_2\)，删完之后会出现负数，则数组一定删不空，直接输出 NO 后 break 即可。

遍历一次数组，时间复杂度 \(O(n)\)。

C

如果 map 和 pie 单独出现，应该直接删除中间的字母 a 和 i——如果遇到 mmap 或者 piee 这样的字符串，删除头尾的字母可能消不掉该单词。而当出现 mapie 子段时，显然应该删除 p。

遍历字符串，当 s[i:i+5] == "mapie" 时，答案 +1，循环变量 +5；否则检查 s[i:i+3] == "map || s[i:i+3] == "pie"，成立则答案 +1，循环变量 +3。时间复杂度 \(O(n)\)。

D

用 unordered_set 记录每一轮球可能在的位置，每一轮对 set 中的所有元素进行更新。元素最多出现在 \(n\) 个位置，共有 \(m\) 轮，注意最后要对答案排序，时间复杂度 \(O(nm+n\log n)\)。

E

先求出在每一行架桥的最小值，再用前缀和求出连续 \(k\) 行的最小和，这要求每一行求最小值的复杂度不超过 \(O(m)\)。

动态规划，考虑设 \(dp_{i,j}\) 表示第 \(i\) 行架桥，在第 \(j\) 列放了桥墩时截至该列的最小造价，显然有 \(dp_{i,j}=\min_{t=j-d-1}^{j-1}dp_{i,t}+a_{i,j}+1\)。复杂度 \(O(md)\) 的求最小值部分可以单调队列优化至 \(O(m)\)，满足条件。

dp 代码如下：

rep(i, 1, n) {
        dp[i][1] = 1, q.push_back(1);
        rep(j, 2, m) {
            while (!q.empty() && j - q.front() - 1 > d) q.pop_front(); // 清除超出距离的状态
            dp[i][j] = dp[i][q.front()] + a[i][j] + 1;
            while (!q.empty() && dp[i][q.back()] > dp[i][j]) q.pop_back(); // 清除比当前点远、还比当前点贵的状态
            q.push_back(j);
        }
        sum[i] = sum[i - 1] + dp[i][m];
        while (!q.empty()) q.pop_back(); // 注意清空队列
    }

F

要让最大差值最小，必须将新问题插入间隔最远的那对 \(a_i,a_{i+1}\) 之间，答案为次大差值和最大差值分开的两段取 \(\max\)。次大差值本身不会改变，我们只需要研究怎样分隔最大差值能使答案最小。

枚举 model，对每个 model 二分出一个 function，使得 \(d_i+f_j\le \lfloor\dfrac{a_{i}+a_{i+1}}{2}\rfloor\) 且 \(f_j\) 最大。对于这个 model，最优的分界点是 \(d_i+f_j\) 或者 \(d_i+f_{j+1}\)。用这两个可能的分界点和次大差值分别更新答案即可。

复杂度 \(O(n+m\log k)\)。