Codeforces Round #932（Div.2）
怎么只会 A 啊。
\(\text{Problem A}\)
题目大意
对于一个字符串 \(s\)，可以进行 \(n\) 次操作（\(n\) 为偶数），每次操作有两种形式：
- 令 \(t\) 为 \(s\) 的反串，\(s = s + t\)。
- 令 \(t\) 为 \(s\) 的反串，\(s = t\)。
要求操作完后 \(s\) 的字典序最小，并输出 \(s\)。
\(1 \le n \le 10^9, 1 \le |s| \le 100\)。
题目思路
考虑到一个字符串越短越好，所以我们尽量是用第二种形式的，发现如果 \(s\) 比 \(s\) 的反串的字典序要小，那么进行 \(n\) 次操作 \(2\) 后必然还是 \(s\)，显然是字典序最小的。
但是如果 \(s\) 比 \(s\) 的反串的字典序要大，那么显然最优的做法是第一次进行操作 \(1\)，后面进行操作 \(2\)，否则到最后就反不到字典序最小的串了，具体来说，答案就是 \(s\) 的反串拼上 \(s\)。
\(\text{Problem B}\)
题目大意
给你一个长度为 \(n\) 的序列 \(a\)，要求分成若干段（段数不为 \(1\)），使得每段的 \(\text{mex}\) 相同。
\(1 \le n \le 10^5, 0 \le a \le n\)。
题目思路
对于区间仔细分析后发现是可以合并的，具体来说：
- 对于 \(\text{mex}(i, k) = \text{mex}(k + 1, j) = x\)，可以得出 \(\text{mex}(i, j) = x\)。
简单证明一下就是考虑 \([i, k]\) 中没有出现 \(x\)，\([k + 1, j]\) 中也没有出现 \(x\)，那么 \([i, j]\) 中也没有出现 \(x\)，因此得 \(\text{mex}(i, j) = x\)。
那么问题就变得很简单了，因为划分 \(k\) 段合法是划分 \(2\) 段合法的充分条件，所以只要能划分出 \(2\) 段就可以了，预处理前缀/后缀 \(\text{mex}\) 就好了。
\(\text{Problem C}\)
题目大意
给你 \(n\) 个二元组 \((a_i, b_i)\)，要求从中选出 \(k\) 个二元组并任意打乱，设其下标集合 \(S = \{p_1, p_2, ..., p_k\}\)，要求在 \(\sum\limits_{i = 1}^k a_i + \sum\limits_{i = 2}^k |b_{p_i} - b_{p_{i - 1}}| \le l\) 的情况下将 \(k\) 最大化。
\(1 \le n \le 2000\)。
题目思路
我们考虑一个事情，如果选出了 \(k\) 个且下标集合 \(S = \{p_1, p_2, ..., p_k\}\)，那么当 \(p_1 \le p_2 \le ... \le p_k\) 的时候是这个集合所有顺序排列中值最小的，此时的代价是 \(\sum\limits_{i = 1}^k a_i + b_{p_k} - b_{p_1}\)。
因此我们考虑枚举这个集合中的下标最小值和下标最大值，在这中间，很明显元素是按照 \(a\) 的大小从小往大放，直到放到不能放为止，这可以用堆来做，发现是三方的，然后我们在枚举最大值的时候顺便加进去计算，时间复杂度就是 \(O(n^2 \log_2 n)\)。
\(\text{Problem D}\)
题目大意
给定一个大小为 \(n\) 的集合 \(S\)，其中元素大小 \(\le c\)，问满足以下条件的数对 \((x, y)\) 的个数有多少对：
- \(x, y \in \mathbb{Z}, 0 \le x \le y \le c\)。
- \(x + y \notin S, y - x \notin S\)。
\(1 \le n \le 3 \times 10^5, 0 \le c \le 10^9\)。
题目思路
首先发现这个一看就很容斥的样子，考虑容斥完我们要计算什么：
\[ans = \sum_{i = 0}^c \sum_{j = i}^c 1 - \sum_{i = 0}^c \sum_{j = i}^c [i + j \in S] - \sum_{i = 0}^c \sum_{j = i}^c [j - i \in S] + \sum_{i = 0}^c \sum_{j = i}^c [i + j \in S] \times [j - i \in S] \]考虑第一项的值，就是 \(\frac{(c + 1)(c + 2)}{2}\)。
考虑第二项的值，发现对于每一个 \(i \le \frac{s_i}{2}\)，都有一个与之对应的 \(j\) 形成单射，就是 \(\sum\limits_{i = 1}^n \left(\frac{s_i}{2} + 1\right)\)。
考虑第三项的值，发现对于每一个 \(s_i \le i \le c\)，都有一个与之对应的 \(j\) 形成单射，就是 \(\sum\limits_{i = 1}^n \left(c - s_i + 1\right)\)。
考虑第四项的值，在此之前，我们要想明白一个事情，对于一对 \((i, j)\) 如果产生贡献，那么只会对应到一组 \((s_x, s_y)\) 上，换句话说，\(i = \frac{s_x - s_y}{2}, j = \frac{s_x + s_y}{2}\)，当且仅当满足这个条件，才会对答案产生贡献，不难发现就是奇数的 \(s\) 两两组合，偶数的 \(s\) 两两组合。
标签：专区,le,题目,limits,text,sum,Codeforces,mex From： https://www.cnblogs.com/alexande/p/18059254