Codeforces Round 932 (Div. 2)（A,B,C,D）

比赛链接

AB都是思维，更确切地说，A考了字符串字典序，很经典的贪心考点，B考了MEX运算。C出的还是比较好的，dp方法值得学习。D题是个不太好想的容斥，主要是变量有点多，容易搞混。

---

A. Entertainment in MAC

题意：

恭喜你，你被硕士援助中心录取了！但是，你在课堂上感到非常无聊，厌倦了无所事事，于是你给自己想了一个游戏。

给你一个字符串 $s$ 和一个偶整数 $n$ 。你可以对它进行两种运算：

1. 将反向字符串 $s$ 添加到字符串 $s$ 的末尾（例如，如果 $s=$ cpm，那么在执行操作后 $s=$ cpmmpc ）。
2. 将当前字符串 $s$ 倒转（例如，如果 $s=$ cpm，则在执行操作后 $s=$ mpc）。

需要确定在进行精确的 $n$ 操作后，可以得到的词序最小的 ${}^{†}$ 字符串。请注意，您可以按照任意顺序进行不同类型的运算，但必须总共进行 $n$ 次运算。

${}^{†}$ 当且仅当以下条件之一成立时，字符串 $a$ 在词法上比字符串 $b$ 小：

• $a$ 是 $b$ 的前缀，但是 $a\ne b$ ；
• 在 $a$ 和 $b$ 不同的第一个位置上，字符串 $a$ 的字母在字母表中出现的时间早于 $b$ 中的相应字母。

思路：

发现新构造出来的字符串最前面 $|s|$ 个字符要么是 $s$，要么是反向的 $s$。正向好说，不用操作就是。而要保证进行偶数次操作后，最前面是反向的 $s$，那么一定需要先用一下操作 $2$，再用一下操作 $1$。

为了字典序最小，我们后面一定是一直使用操作 $2$。因此我们只需要比较一下正向 $s$ 和反向 $s$ 哪个小，如果是正向的，那么就只用操作 $2$，否则先用一下操作 $1$，之后一直用操作 $2$。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int T,n;
string s,t;int main(){cin>>T;while(T--){cin>>n>>s;t=string(s.rbegin(),s.rend());if(s<=t)cout<<s<<endl;else cout<<t+s<<endl;}return 0;
} 

---

B. Informatics in MAC

题意：

在硕士援助中心，Nyam-Nyam 接受了一项信息学方面的家庭作业。

有一个长度为 $n$ 的数组 $a$ ，你想把它分成 $k>1$ 个子段 ${}^{†}$ ，使每个子段上的 ${\mathrm{MEX}}^{‡}$ 都等于相同的整数。

请帮助 Nyam-Nyam 找到合适的除法，或者确定不存在合适的除法。

${}^{†}$ 将数组划分为 $k$ 个子数段的定义是 $k$ 对整数 $(l_1,r_1),(l_2,r_2),\dots ,(l_k,r_k)$ ，使得 $l_i\le r_i$ 和每个 $1\le j\le k-1$ ， $l_{j+1}=r_j+1$ ，以及 $l_1=1$ 和 $r_k=n$ 。这些对表示子段本身。

数组中的 ${}^{‡}\mathrm{MEX}$ 是不属于该数组的最小非负整数。

例如

• 数组 $[2,2,1]$ 的 $\mathrm{MEX}$ 是 $0$ ，因为 $0$ 不属于该数组。
• 数组 $[3,1,0,1]$ 中的 $\mathrm{MEX}$ 是 $2$ ，因为 $0$ 和 $1$ 属于数组，而 $2$ 不属于数组。
• 数组 $[0,3,1,2]$ 中的 $\mathrm{MEX}$ 是 $4$ ，因为 $0$ 、 $1$ 、 $2$ 和 $3$ 属于数组，而 $4$ 不属于数组。

思路：

每段区间都不含某个数，说明这个数在整段区间上肯定从来没出现过。所以我们要选就选在原序列中没出现的数。我们要一段区间上的 $MEX$ 等于某个数 $x$，就需要这段区间上包含 $1\sim x-1$ 的所有数。所以我们要每段区间的 $MEX$ 值都等于某个数 $x$ 的话，$x$ 只可能是最小的原序列没出现的数。我们只要对这个数验证一下即可。

code：

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
const int maxn=1e5+5;int T,n;
int a[maxn];int main(){cin>>T;while(T--){cin>>n;set<int> S;for(int i=1;i<=n;i++){cin>>a[i];S.insert(a[i]);}int x;for(int i=0;;i++)if(S.find(i)==S.end()){x=i;break;}vector<pair<int,int> > ans;for(int l=1,r=1,t;l<=n;){t=0;S.clear();do{S.insert(a[r++]);while(S.find(t)!=S.end())t++;if(r>n && t!=x){//将最后一段不完整的段归入到前一段l=ans.rbegin()->first;ans.pop_back();break;}
//				cout<<l<<" "<<r<<endl;}while(t!=x);ans.push_back(make_pair(l,r-1));l=r;}if(ans.size()>1){cout<<ans.size()<<endl;for(auto x:ans)cout<<x.first<<" "<<x.second<<endl;}else cout<<-1<<endl;}return 0;
}

---

C. Messenger in MAC

题意：

凯夫特梅鲁姆硕士生援助中心的新信使计划进行一次更新，开发人员希望在更新中优化向用户显示的信息集。目前共有 $n$ 条信息。每条信息由两个整数 $a_i$ 和 $b_i$ 表示。读取数字为 $p_1,p_2,\dots ,p_k$ （ $1\le p_i\le n$ ，所有 $p_i$ 都是不同的）的信息所花费的时间由公式计算得出：

$$\sum _{i=1}^k{a}_{p_i}+\sum _{i=1}^{k-1}|b_{p_i}-b_{p_{i+1}}|$$

请注意，读取由一个编号为 $p_1$ 的报文组成的报文集所需的时间等于 $a_{p_1}$ 。此外，读取一组空信息所需的时间为 $0$ 。

用户可以确定他愿意在信使中花费的时间 $l$ 。信使必须告知用户信息集的最大可能大小，其阅读时间不超过 $l$ 。请注意，信息集的最大大小可以等于 $0$ 。

流行信使的开发人员未能实现这一功能，因此他们要求您解决这一问题。

思路1（堆）：

上面的描述很神秘，实际上表达的意思很简单。就是可以乱序地不重复地成对选出一些 $a,b$，使得选出数的序列的 $a$ 的和以及相邻两项 $b$ 的差的绝对值相等。总和不超过 $L$ 的前提下，使得选出的数尽可能多。

为了最小化 ${\sum }_{i=1}^{k-1}|b_{p_i}-b_{p_{i+1}}|$ 我们不妨把每对数按 $b$ 来进行排序，按顺序选出若干个数后，因为有大小关系，绝对值号可以直接拆掉，前一项与后一项相消，也就是 $b_{p_k}-b_{p_{k-1}}+b_{p_{k-1}}-b_{p_{k-2}}+\cdots +b_{p_2}-b_{p_1}$ 那么它就变成了 $b_{p_k}-b_{p_1}$。把 $p_1$ 看成选取区间的左端点， $p_k$ 看成右端点的话，则原式就相当于在区间 $[l,r]$ 中选取若干个数，使得 $a_i$ 之和加上 $r-l$ 小于等于 $L$（左右端点必选），问最多能选多少个数。

朴素的想法是先枚举右端点，然后枚举左端点，然后贪心地选区间内最小的前几个数。但是这样最坏是 $O(n^{3}logn)$ 的（区间排序占 $O(nlogn)$）。我们希望有个 $O(n^{2}logn)$ 的做法。所以我们考虑能否从上一个区间直接推过来。

一个想法是：枚举右端点 $r$，然后左端点 $l$ 从 $r$ 向 $1$ 推。使用堆来存储区间 $[l,r]$ 中最小的若干个值，使得它们的和 $\le L-(r-l)$（这意味着我们以 $l,r$ 为左右端点的时候，选取的就是堆中的数，因为总和满足前面的条件，因此在值上是满足条件的）。

不过这个想法有个比较明显的缺陷，就是有可能我们推到某个左端点 $l$ 根本没选 $a_l$，而是直接将它踢出了堆，这样就不符合左右端点必选的条件了。不过这样还是可以得到正确答案的，因为这种不符合条件的情况一定无法更新答案。

为什么呢？假设我们推到了某个左端点 $l$ 却没有选上 $a_l$，那么我们此时堆中最靠左的数的位置 $l^{\prime }$ 作为左端点时，堆中数的总和加上 $r-l^{\prime }$ 一定更小，比这个情况更有可能更新答案。前面的情况已经更新过答案了，因此这个情况一定无法更新答案。这就保证了正确性。

code：

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=2005;int T,n;
ll L;
pair<int,int> x[maxn];int main(){cin>>T;while(T--){cin>>n>>L;for(int i=1;i<=n;i++){cin>>x[i].second>>x[i].first;}sort(x+1,x+n+1);int ans=0;for(int r=1;r<=n;r++){priority_queue<int> h;ll tot=0;for(int l=r;l>=1;l--){h.push(x[l].second);tot+=x[l].second;while(tot+x[r].first-x[l].first>L && !h.empty()){tot-=h.top();h.pop();}if(tot+x[r].first-x[l].first<=L)ans=max(ans,(int)h.size());}}cout<<ans<<endl;}return 0;
} 

思路2（动态规划）：

我们在选数的时候需要知道那些数是第一个选上的数，哪一个是最后一个选上的数，所以设 $dp1[i][j]$ 表示前 $i$ 个数中选出 $j$ 的最小值，$dp2[i][j]$ 表示前 $i$ 个数中选出 $j$ 个，并且最后一个数选 $a_j$ 的最小值。

$dp1$ 我们就正常选数即可，只需要特判一下当前状态选择的是否是第一个数，$dp2$ 由 $dp1$ 来推，这样 $dp2$ 得到的就是一种选取方式，即若干个 $a$ 的值减去 $b_l$ 再加上 $b_r$。

而第一维为 $i$ 的 $dp1,dp2$ 之和 $i-1$ 的有关，所以我们可以优化掉第一维。这样就变成了 jiangly 大佬的写法了。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set> 
using namespace std;
typedef long long ll;
const ll inf=1e18;
const int maxn=2005;int T,n;
ll l;
pair<int,int> itv[maxn];int main(){cin>>T;while(T--){cin>>n>>l;for(int i=1;i<=n;i++)cin>>itv[i].second>>itv[i].first;sort(itv+1,itv+n+1);vector<ll> dp1(n+1,inf),dp2(n+1,inf);for(int i=1;i<=n;i++){ll a=itv[i].second;ll b=itv[i].first;for(int j=n;j>=1;j--){dp1[j]=min(dp1[j],dp1[j-1]+a);dp2[j]=min(dp2[j],dp1[j-1]+a+b);}dp1[1]=min(dp1[1],a-b);dp2[1]=min(dp2[1],a);}for(int i=n;i>=1;i--){if(dp2[i]<=l){cout<<i<<endl;break;}if(i==1){cout<<0<<endl;}}}return 0;
}

---

D. Exam in MAC

题意：

硕士生援助中心公布了入学考试，考试内容如下。

给考生一个大小为 $n$ 的集合 $s$ 和一个奇怪的整数 $c$ 。对于这个集合，需要计算出使 $0\le x\le y\le c$ ， $x+y$ 不包含在集合 $s$ 中，并且 $y-x$ 也不包含在集合 $s$ 中， $(x,y)$ 对的个数。

你的朋友想进入中心工作。请帮助他通过考试！

思路：

容斥原理。很好的题。

$x,y$ 是任取的，我们当然不可能任取，用屁股想都会超时。因此从 $x+y,y-x$ 下手。假设 $x+y=a\notin s,y-x=b\notin s$，则有 $x=\frac{a-b}{2},y=\frac{a+b}{2}$。显然 $b\le a$，并且当 $a,b$ 不同时，得到的 $x,y$ 一定不同（也就说有多少对不同的 $a,b$，就有多少对不同的 $x,y$）。

题目说 $x+y,y-x$ 不在集合 $s$ 中，也就是 $a,b$ 不在集合 $s$ 中。我们只要找到所有不在集合 $s$ 中的数，让 $a,b$ 去等于这些数，就能得到一对对 $x,y$。但是问题在于如何保证得到的 $x,y$ 合法，以及如何计数。

一开始的想法是因为 $\frac{a-b}{2}\le \frac{a+b}{2}\le c$，所以枚举 $a$，然后去算 $b$ 的个数，不过还是太麻烦了，当 $c$ 很大的时候还需要将一整段进行压缩，整段求和，暴力来算会T。

所以尝试反着来求。用总的对数减去 $a$（也就是 $x+y$） 合法的对数和 $b$（也就是 $y-x$） 合法的对数，最后再加上 $a,b$ 同时合法的对数，剩下的就是不合法的对数。

1. 总对数显然是 $C_{c+1}^2=(c+1)\ast (c+2)/2$。（$x,y$ 可选 $0\sim c$ 的数，包括 $0$）

2. 我们让 $a$ 去等于已有的数，得到的就是 $a$ 合法的对数。假设这个数是 $t$，那么 $x+y=t$ ，又因为 $y\ge x$，所以得到的总的合法对数为 $t/2+1$。

3. 同理，我们让 $b$ 去等于已有的数，得到的就是 $b$ 合法的对数。假设这个数是 $t$，那么 $y-x=t$ ，因为 $y\le t$，所以得到的总的合法对数为 $c-t+1$。

4. $a,b$ 同时合法的话，需要 $x=\frac{a-b}{2},y=\frac{a+b}{2}$ 算出来的 $x,y$ 为正整数，因此 $a,b$ 需要奇偶性相同。我们统计一下给出的数中有多少个奇数 $o$ 和偶数 $e$，总数就是 $C_e^2+C_o^2=e\ast (e+1)/2+o\ast (o+1)/2$。

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;int T,n,c;int main(){cin>>T;while(T--){cin>>n>>c;ll ans=1ll*(c+1)*(c+2)/2;int o=0,e=0;for(int i=1,t;i<=n;i++){cin>>t;ans-=t/2+1;//x+y=tans-=c-t+1;//y-x=tif(t&1)o++;else e++;}ans+=1ll*o*(o+1)/2;ans+=1ll*e*(e+1)/2;cout<<ans<<endl;}return 0;
}