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

比赛链接

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

A. Entertainment in MAC

题意：

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

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

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

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

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

$a$ 是 $b$ 的前缀，但是 $\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\gt 1$ 个子段 $^{\dagger}$ ，使每个子段上的 $\operatorname{MEX} ^{\ddagger}$ 都等于相同的整数。

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

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

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

例如

数组 $[2, 2, 1]$ 的 $\operatorname{MEX}$ 是 $0$ ，因为 $0$ 不属于该数组。
数组 $[3, 1, 0, 1]$ 中的 $\operatorname{MEX}$ 是 $2$ ，因为 $0$ 和 $1$ 属于数组，而 $2$ 不属于数组。
数组 $[0, 3, 1, 2]$ 中的 $\operatorname{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, \ldots, p_k$ （ $\le p_i \le n$ ，所有 $p_i$ 都是不同的）的信息所花费的时间由公式计算得出：

$\Large \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}}+\dots+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^3log\,n)$ 的（区间排序占 $O(nlog\,n)$ ）。我们希望有个 $O(n^2log\,n)$ 的做法。所以我们考虑能否从上一个区间直接推过来。

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

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

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

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（动态规划）：

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

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

而第一维为 $i$ 的 $d p 1, d p 2$ 之和 $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$ 。对于这个集合，需要计算出使 $\leq x \leq y \leq c$ ， $x + y$ 不包含在集合 $s$ 中，并且 $y - x$ 也不包含在集合 $s$ 中， $(x, y)$ 对的个数。

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

思路：

容斥原理。很好的题。

$x, y$ 是任取的，我们当然不可能任取，用屁股想都会超时。因此从 $x + y, y - x$ 下手。假设 $x+y=a\not\in s,y-x=b\not\in s$ ，则有 $x=\dfrac{a-b}2,y=\dfrac{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$ 合法，以及如何计数。

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

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

总对数显然是 $C_{c+1}^2=(c+1)*(c+2)/2$ 。（ $x, y$ 可选 $0\sim c$ 的数，包括 $0$ ）
我们让 $a$ 去等于已有的数，得到的就是 $a$ 合法的对数。假设这个数是 $t$ ，那么 $x + y = t$ ，又因为 $y\ge x$ ，所以得到的总的合法对数为 $t /2 + 1$ 。
同理，我们让 $b$ 去等于已有的数，得到的就是 $b$ 合法的对数。假设这个数是 $t$ ，那么 $y - x = t$ ，因为 $y\le t$ ，所以得到的总的合法对数为 $c - t + 1$ 。
$a, b$ 同时合法的话，需要 $x=\dfrac{a-b}2,y=\dfrac{a+b}2$ 算出来的 $x, y$ 为正整数，因此 $a, b$ 需要奇偶性相同。我们统计一下给出的数中有多少个奇数 $o$ 和偶数 $e$ ，总数就是 $C_e^2+C_o^2=e*(e+1)/2+o*(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=t
			ans-=c-t+1;//y-x=t
			if(t&1)o++;
			else e++;
		}
		ans+=1ll*o*(o+1)/2;
		ans+=1ll*e*(e+1)/2;
		cout<<ans<<endl;
	}
	return 0;
}