有两个容积分别为 a 单位和 b 单位的容器。有一个长度为 n 的操作序列，每次操作将一个容器中的水向另一个倒 v_i 单位，若有一个容器为空或满则中断。问对于所有可能的初始水量，求操作后 A 容器每一种水量的可能性。
2. 分析
首先不难注意到一点，两个容器的总水量不变。
这个也算是一个典型套路，记住就好。
我们假装将两个容器底部接通。
那么一次体积为 v 的挪水操作就相当于 v 次体积为 1 的挪水操作，除非某一个容器满了或空了。
我们可以认为，在数轴上 -a 和 b 分别有两个点，称为“容积上限点”。
而原点是 “分隔点”。
若干体积水可以理解为一条线段，挪水则是线段的左右滑动。但是：
若当前状态符合这个定义，因为操作被拆分成了若干左 1 或右 1。
当左 1 时，若若干线段受 -a 限制。
则它们的左侧不可能有更多线段（否则超出 -a 限制），此时右侧的线段因为平移量只有 1 所以全部不受限。即左端进行了额外一格的吞并。
同理可以证明右 1 的 b 限制和左右的原点限制。
也就是只要算出左右的重叠长度即可。
3. 代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
#define maxn 10005
#define maxv 1005
using namespace std;
int _, n, a, b, v[maxn], ans[maxv][maxv];
void work() {
int sum = 0;
cin >> n >> a >> b;
for(int i = 1; i <= n; i++) cin >> v[i], sum += v[i];
for(int w = 0; w <= a + b; w++) { //枚举线段长度
int l = max(a - w, 0ll), r = min(a + b - w, a); //因为显然数组不能访问负的位置，所以将左右中的限制和线段都向右平移 $a$。
int L = l, R = r;//初始状态的左端点上下界
for(int i = 1; i <= n; i++) {
r += v[i];
l += v[i];
r = min(r, R);
l = min(l, R);
r = max(r, L);
l = max(l, L);
}
if(l == r) {
for(int i = L; i <= R; i++) {
ans[a - i][i + w - a] = a - l;
}
continue;
}
for(int i = L; i < l - sum; i++) {
ans[a - i][i + w - a] = a - l;
}
for(int i = l - sum; i < r - sum; i++) {
ans[a - i][i + w - a] = a - (i + sum);
}
for(int i = r - sum; i <= R; i++) {
ans[a - i][i + w - a] = a - r;
}
//l-sum 和 r-sum 分别是当前合并后左端点上下界的线段在平移前的左端点值。因为这个表是要根据初始值绘制的。
}
for(int i = 0; i <= a; i++) {
for(int j = 0; j <= b; j++) {
cout << ans[i][j] << ' ';
}cout << endl;
}
}
signed main() {
ios_base::sync_with_stdio(false);
_ = 1;
while(_--) work();
}
CF1867 题解
CF1867D
1. 题意
一个无边图，每次操作选择 k 个点，将它们原有出边删去后顺次连接成环。现给出每个点的出边终点编号，问这张图是否可以通过有限次操作得到。
每次操作形成一个长度为 k 的环。我们来研究一下能否通过若干操作形成一个其他长度的环。
考虑一条环上边 B\to C 及其环上前驱 A\to B，当 A\to B 形成时，B 必然在成环序列里。那么 B 的出边就会被刷新。所以任一条边的成边时间不早于其环上前驱。
可这是个环啊。我们对环用一圈这个不等式，就变成了一个等式：环上所有边成边时间相同！可是我们又注意到，一次操作只能形成长度为 k 的环。所以任意环长度必须为 k。
从一个点开始跳后继，由于每个点的出边不但是唯一而且是存在的，所以可以无限地跳下去。而图中的点有 n 个，跳 n+1 次一定跳到过某个节点多次，即每个点都能跳到一个环上。
考虑环外的边 A\to B 是如何建立的。若形如 X\to A 的边已经全部建立完成，那么选择最终状态某个环上任意 k-2 个异于A,B 的点，建立一个环即可。因为 B 的出边会在后续操作中被更正，而这次操作也不会影响 A 的入边。
而操作中 A 的前驱因为在环上，最后一次操作时会被直接更正，无需操心。因此，在环信息正确的情况下，任意环外边都是可以被建立的。
坑
所以要特判 $1$。推一下发现每个点必须自环。没别的坑了。
### 3. 代码
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
using namespace std;
int n, k, f[200005], don[200005], ctn[200005];
bool work() {
cin >> n >> k;
for(int i = 1; i <= n; i++) don[i] = 0;
for(int i = 1; i <= n; i++) cin >> f[i];
if(k == 1) {
for(int i = 1; i <= n; i++) if(i != f[i]) return false;
return true;
}
for(int i = 1; i <= n; i++) {
if(don[i] == 0) {
int cnt = 0, r;
for(r = i; !don[r]; r = f[r]) {
ctn[r] = cnt;
cnt++;
don[r] = i;
}
if(don[r] != i) continue;
if(cnt - ctn[r] != k) return false;
}
}
return true;
}
signed main() {
int _;
cin >> _;
while(_--) {
cout << (work() ? "Yes\n" : "No\n");
}
}
```
# CF1935 题解
## CF1935A
### 1. 题意
给定一个字符串 $s$ 和一个正**偶数** $n$，你要对 $s$ 进行恰好 $n$ 次操作。每次操作形如以下两者**之一**。
1. 左右翻转 $s$。形式化地，设其长度为 $m$，则同时执行 $s_i := s_{m+1-i}$。
2. 将 $s$ 拼接上 $s$ 的左右翻转。形式化地，先令 $t=s$，然后对 $t$ 做 $1$ 操作，再 $s:=s+t$。其中 $+$ 指字符串拼接。
问能得到的字典序最小的字符串。
$2\le n\le 10^9,|s|\le 100$。
### 2. 分析
设最初的字符串为 $s_0$，翻转后为 $s_1$。
那么可以简单归纳证明，无论操作多少次，最后字符串一定以 $s_0$ 或 $s_1$ 开头。
那么我们为了让字典序最小，可以贪心地取一个较小的前缀，并进行分类讨论。确定了开头之后，我们还希望后面的东西尽可能少。
+ $s_0\le s_1$。
则答案就是 $s_0$。因为 $s_0$ 翻转偶数次还是 $s_0$。
+ $s_0>s_1$。
因为 $n$ 是偶数，则 $s_0$ 翻转偶数次的答案是 $s_0$。为了达成 $s_1$ 作为开头，我们只能对它翻转 $n-1$ 次，然后做一次 $2$ 操作。答案是 $s_0+s_1$。
### 3. 代码
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#define maxn 800005
#define int long long
using namespace std;
int n;
string s;
void work() {
cin >> n >> s;
string rvs = s;
reverse(rvs.begin(), rvs.end());
if(s > rvs) { //字符串的比较是比较字典序
cout << rvs + s << '\n';
}
else cout << s << '\n';
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
int _; cin >> _; while(_--) work();
}
```
## CF1935B
### 1. 题意
给定一个长度为 $n$ 的序列 $\{a_n\}$。问是否存在一种划分方案，把序列划分成若干个区间，使得每个数被划分到恰好一个区间，且每个区间的 $\operatorname{mex}$ 相等。若存在请给出任意一组。
对于自然数序列 $\{b_m\}$，它的 $\operatorname{mex}$ 表示其中最小的未出现的的自然数。即 $\min x\in \mathbb{N}$，使得 $\forall 1\le i\le m,b_i\neq x$。
$0\le a_i<n,2\le n\le 10^5$。
### 2. 分析
此处采用一种经典的刻画 $\operatorname{mex}$ 的方法。
对于一个数列 \{b_m\}，若其 $\operatorname{mex}$ 为 $x$，则：
+ $\forall 0\le i<x,\ \exists j,\ b_j=i$。即任意不超过 $x$ 的自然数都出现了
+ $\forall j,\ b_j \neq x$，即 $x$ 没有出现
同时成立。
如果这个序列被划分成了至少三段，我们考虑任意两段，它们同时满足这两条性质，因此合并后也满足这两条性质，故合并后 $\operatorname{mex}$ 不变。
所以如果存在方案。则一定存在划分为 $2$ 个区间的方案。枚举断点，用 `multiset` 维护两侧的 $\operatorname{mex}$ 即可。
在实现时，我们可以根据定义即“最小没有出现自然数”优化代码，因为值域较小，可以维护要维护的集合在值域上的补集，每次查询取其中最小值即可。
又因为前缀是正向维护，后缀是反向维护，所以每一次修改之后都是上一次的超集，所以不需要考虑删数的问题。
### 3. 代码
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#define maxn 200005
#define int long long
using namespace std;
set<int> st;
int n, a[maxn], pre[maxn], suf[maxn];
// pre 记录从 1 到 i 的 mex，suf 记录从 i 到 n 的 mex
void work() {
cin >> n;
st.clear(); //多测清空
for(int i = 0; i <= n; i++) { //一定要记得比值域多放进去一个，比如 ai 的最大值是1000，就要把 0~1001都放进去
st.insert(i); // 值域作为全集
}
for(int i = 1; i <= n; i++) {
cin >> a[i];
st.erase(a[i]); //集合加数等价于补集删数
pre[i] = *st.begin(); // 取最小值
}
st.clear();
for(int i = 0; i <= n; i++) {
st.insert(i);
}
for(int i = n; i >= 1; i--) {
st.erase(a[i]);
suf[i] = *st.begin();
}
for(int i = 2; i <= n; i++) {
if(suf[i] == pre[i - 1]) { //若 1~i 和 i+1~n 的 mex 相等，输出方案。
cout << "2\n1 ";
cout << i - 1 << '\n' << i << ' ' << n << '\n';
return ;
}
}
cout << "-1\n"; //否则无解
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
int _; cin >> _; while(_--) work();
}
```
## CF1935C
### 1. 题意
给定两个长度为 $n$ 的序列 $\{a_n\},\{b_n\}$ 和一个正整数 $T$，求最大的 $k$，使得存在一个长度为 $k$ 的序列 $\{p_k\}$，满足 $\forall i\neq j,p_i \neq p_j$，且 $\sum\limits_{i=1}^k a_i+\sum\limits_{i=1}^{k-1} |b_i-b_{i+1}|\le T$。
$1\le n\le 2000$。
### 2. 分析
注意到选好 $p$ 的内容之后调整顺序并不会对第一项产生影响。而按 $b$ 大小排序可以让第二项最小。
所以我们先把两个序列对应位置不变地按 $b$ 不降排序。
然后，由于已经排好序，第二项只会受选定的位置右端点与左端点 $b$ 的差有关。
所以可以枚举左端点扫描右端点。若左右端点分别为 $l,r$，则此时选定的 $a$ 的和不能超过 $T-(b_r-b_l)$。可以直接用线段树上二分做，但是不想写线段树。
考虑能否贪心。当左右端点确定时，选的一定是区间中 $a$ 最小的一段前缀。左右端点事实上可以不选，因为计算的左右端点比选中的左右端点更大只会导致条件更严格（不会算出错误答案），且枚举到正确左端点并扫到正确右端点时一定会计算这一组，除非有更优解（正确答案一定被计算）。
如果每次加入一个新的 $a$，调整 $T-(b_r-b_l)$ 的限制，当选中的数超限时就删除最大的，这样对吗？
在某一个位置选定区间中最小若干个值的时候，由于扫描右端点只会让限制更严格，所以曾经的宽松限制一定能容下这些数存在。又因为是每次删最大的，所以比它们更大的一定先被删掉。
所以贪心是正确的。
### 3. 代码
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#define maxn 200005
#define int long long
using namespace std;
int n, l;
struct node {
int a, b;
bool operator<(node y)const {
if(b == y.b) return a > y.a;
return b < y.b;
}
} a[maxn];
priority_queue<int> q; //可用 multiset 代之，千万不要 set
void work() {
cin >> n >> l; // 这里的 l 是叙述中的 T
for(int i = 1; i <= n; i++) {
cin >> a[i].a >> a[i].b;
}
int ans = 0;
sort(a + 1, a + n + 1); //按 b 排序
for(int i = 1; i <= n; i++) {
while(!q.empty()) q.pop();
int sum = 0;
int cnt = 0;
for(int j = i; j <= n; j++) {
q.push(a[j].a); //扫一个新的点，把 a 暂时选上
cnt++; //统计个数
sum += a[j].a; //记录已经选择的数的和
while(sum + a[j].b - a[i].b > l && !q.empty()) { //超出限制
sum -= q.top();
q.pop();
cnt--;
}
ans = max(ans, cnt); // 一定要记得更新一次端点就更新一次答案
}
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
int _; cin >> _; while(_--) work();
}
```
## CF1935D
### 1. 题意
给你一个正整数 $c$ 和一个自然数集合 $S$（值域为 $c$），问有多少组 $0\le x\le y\le c$，满足 $x+y\notin S,y-x\notin S$。
$1\le n\le 3\times 10^5,1\le c\le 10^9
2. 分析
问有多少组值域内的 x\le y 使得 x+y\in S 显然是好做的，遍历 S 并计算即可。
所以可以考虑容斥。
为了方便，可以数形结合。我们取横纵坐标均在 [0,c] 的整点。