Codeforces Round 917 (Div. 2)

Least Product

题目

输入长度为 \(n\) 的数组 \(a\)，输出能够使 \(\prod_{i=1}^{n}{a_{i}}\) 最小的最小操作次数。每次操作可以选择数组中的任意元素 \(a_{i}\)，如果 \(a_{i}<0\)，则可以将其改为 \([a_{i},0]\) 中的任意整数，否则可以将其改为 \([0,a_{i}]\) 中的任意整数。

数据范围：\(1\leq n\leq 100\)，\(-10^{9}\leq a_{i}\leq 10^{9}\)。

思路

由于操作只会让所有元素乘积的绝对值变小，所以如果乘积是非正数，则不需要进行操作，否则只需进行一次操作，将任意一个元素改为 \(0\)。

Erase First or Second Letter

题目

输入长度为 \(n\) 的字符串 \(s\)，输出进行任意次操作能够得到的不同非空字符串的个数。每次操作可以删除字符串的第一个字符或者第二个字符。

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

思路

• 方法一：枚举剩余字符串的第一个字符下标 \(i\)，对于每个 \(i\) 都可以通过不断删除第二个字符得到 \(n-i\) 个不同的字符串。然后思考什么时候会出现相同的字符串，假设两次枚举的第一个字符分别为 \(i\) 和 \(j\)（\(i<j\)），只有当 \(s_{i}=s_{j}\) 时才有可能出现相同字符串，进一步观察可以发现，对 \(i\) 操作得到的 \(n-i\) 个不同的字符串总是包含对 \(j\) 操作得到的 \(n-j\) 个不同的字符串。所以，假设字符串 \(s\) 中有 \(m\) 个不同的字符，每个字符第一次出现的位置分别为 \(k_{0},k_{1},\dots,k_{m-1}\)，则答案为 \(\sum_{i=0}^{m-1}(n-k_{i})\)。
• 方法二：枚举剩余字符串的第二个字符下标 \(i\)，对于每个 \(i\) 它的贡献为 \([0,i-1]\) 中不同字符的个数。

Watering an Array

题目

输入长度为 \(n\) 的整数数组 \(a\)，长度为 \(k\) 的整数数组 \(v\)，以及整数 \(d\)。输出执行 \(d\) 次操作能够得到的最大分数。有两种类型的操作：

• 假设当前执行第 \(i\) 次操作，则将数组 \(a\) 的前缀 \([a_{1},a_{b_{i}}]\) 都加 \(1\)。其中 \(b_{i}=v_{((i-1)\bmod k)+1}\)。
• 将 \(a_{j}=j\) 的元素个数加到分数中，然后将数组中的所有元素都置为 \(0\)。（下标从 \(1\) 开始）

数据范围：\(1\leq n\leq 2000\)，\(1\leq k\leq 10^{5}\)，\(k\leq d\leq 10^{9}\)，\(0\leq a_{i}\leq n\)，\(1\leq v_{i}\leq n\)。

思路

如果数组 \(a\) 中的元素都为 \(0\)，显然最大分数为 \(\lfloor\frac{d}{2}\rfloor\)，对应的方案为交替执行两种操作。也就是说，解决问题的关键是确定何时第一次将数组 \(a\) 重置。这可以通过枚举实现，但是由于 \(d\) 很大，肯定不能直接枚举范围 \([1,d]\)。进一步观察可以发现，对前缀进行 \(2n\) 次加法，再重置最多得到 \(n\) 分，而先重置再交替执行操作，能够得到的分数大于等于 \(n\)，所以只需要枚举范围 \([1,2n]\)。

Yet Another Inversions Problem

题目

输入长度为 \(n\) 的数组 \(p\)，表示 \([1,2n-1]\) 中所有奇数的一个排列。输入长度为 \(k\) 的数组 \(q\)，表示 \([0,k-1]\) 中所有整数的一个排列。定义长度为 \(nk\) 的数组 \(a\)，对于 \(0\leq i<n\) 和 \(0\leq j<k\)，有 \(a_{i\cdot k+j}=p_{i}\cdot 2^{q_{j}}\)。输出数组 \(a\) 的逆序数，结果对 \(998244353\) 取余。

数据范围：\(1\leq n,k\leq 2\cdot 10^{5}\)，\(1\leq p_{i}\leq 2n-1\)，\(0\leq q_{i}<k\)。

思路

可以将数组看作 \(n\times k\) 的矩阵，逆序数可以分为行内和行间。所有行的行内逆序数都是数组 \(q\) 的逆序数，使用归并排序或者树状数组即可求解，所以难点在如何快速求出行间的逆序数。首先尝试两两枚举所有行，然后观察对于确定的两个行，它们的逆序数有什么特点。由此可以发现，两行之间的逆序数大概是一个等差数列之和，项数和其他边界条件是由 \(p_{i}\) 和 \(p_{j}\) 的大小关系确定的。具体来说，假设 \(p_{i}<p_{j}\)，等差数列是由满足 \(p_{i}\cdot 2^{z}<p_{j}\) 条件的最大的 \(z\) 确定的，确定 \(z\) 需要花费 \(O(\log{n})\) 的时间。从而可以得到时间复杂度为 \(O(n^{2}\log{n}+k\log{k})\) 的朴素解法。（总是假设 \(i<j\)）

下面解释等差数列是如何得到的，假设 \(p_{i}\cdot 2^{z}<p_{j}\)（\(z\geq0\)），将对应的两行合并之后可以得到如下序列：

$$ p_{i}\cdot 2^{0},p_{i}\cdot 2^{1},\dots,p_{i}\cdot 2^{z},p_{j}\cdot 2^{0},p_{i}\cdot 2^{z+1},p_{j}\cdot 2^{1},\dots,p_{i}\cdot 2^{k-1},p_{j}\cdot 2^{k-z-1},\dots,p_{j}\cdot 2^{k-1} $$

要求逆序数，可以通过对每个 \(p_{i}\) 项前面有多少个 \(p_{j}\) 项计数，然后求和得到。可以发现，\(p_{i}\cdot 2^{z+1}\) 前面有 \(1\) 个 \(p_{j}\) 项，\(p_{i}\cdot 2^{z+2}\) 前面有 \(2\) 个 \(p_{j}\) 项，\(p_{i}\cdot 2^{k-1}\) 前面有 \(k-1-z\) 个 \(p_{j}\) 项。得到逆序数为 \(\frac{(k-z)(k-1-z)}{2}\)。

同理，假设 \(p_{j}\cdot 2^{z}<p_{i}\)（\(z\geq0\)），将对应的两行合并之后可以得到如下序列：

$$ p_{j}\cdot 2^{0},p_{j}\cdot 2^{1},\dots,p_{j}\cdot 2^{z},p_{i}\cdot 2^{0},p_{j}\cdot 2^{z+1},p_{i}\cdot 2^{1},\dots,p_{j}\cdot 2^{k-1},p_{i}\cdot 2^{k-z-1},\dots,p_{i}\cdot 2^{k-1} $$

可以发现，\(p_{i}\cdot 2^{k-z-1}\) 到 \(p_{i}\cdot 2^{k-1}\) 的逆序数都为 \(k\)，总和为 \(k(z+1)\)。剩余部分的逆序数构成首项为 \(z+1\)，尾项为 \(k-1\)，公差为 \(1\) 的等差数列，总和为 \(\frac{(k+z)(k-1-z)}{2}\)。得到逆序数为 \(\frac{(k+z)(k-1-z)}{2}+k(z+1)\)。

如何降低时间复杂度？通过上述分析，可以知道对于任意 \(p_{i}\) 和 \(p_{j}\)，它们之间的逆序数是由 \(z\) 决定的。也就是说，如果给定 \(p_{i}\) 和 \(z\)（\(z\) 为任意整数），对于任意满足 \(p_{i}\cdot 2^{z}<p_{j}<p_{i}\cdot 2^{z+1}\) 条件的 \(p_{j}\) 来说，\(p_{i}\) 和 \(p_{j}\) 之间的逆序数都是相同的。注意，当 \(z<0\) 时，对不等式变形得到 \(p_{i}\cdot 2^{-1}<p_{j}\cdot 2^{-z-1}<p_{i}\)，此时的 \(z\) 和上面逆序数公式中的 \(z\) 不同，并且需要处理整数除法的舍入问题（存在一些边界情况）。

要快速求出区间中 \(p_{j}\) 的个数，可以使用树状数组/线段树，从而可以得到 \(O(n\log{\min(\log{n},k)}+k\log{k})\) 的解决方案。外层循环枚举 \(p_{i}\)（倒序遍历数组 \(p\)，因为之前的讨论都基于 \(i<j\) 的假设），内层循环枚举 \(z\)（大小由 \(n\) 和 \(k\) 限制），然后使用树状数组求区间和，之后可以 \(O(1)\) 时间内计算出该区间的 \(p_{j}\) 和当前枚举的 \(p_{i}\) 之间的逆序数。

PS：还有另一种写法，只需要对树状数组的前缀求和，而不是区间求和，写起来好像更简单，但是没看懂。好难，溜了。