Codeforces Round #878 (Div.3)（CF1840） 赛后总结与题解。

前言

很久都没有半夜打比赛了，只能说打完睡了一个好觉。（废话）

题解区

A

题目大意

对一个字符串 $a$ 进行加密后得到一个新字符串 $s$。

加密规则如下：

• 在字符串 $a$ 的每个字符之后，添加任意(可能为零)数量的小写字母，与字符本身不同。
• 在每次这样的添加之后，我们将被补充的字符添加在已添加的字符后。

给出已加密字符串 $s$，求出加密之前的字符串。

思路

依照加密规则，我们可以知道，在原字符串 $a$ 的，每个字符之后，必定会存在与之相同的字符，且两个字符之间的所有字符就是被添加的地方，删去中间与相同字符即可。

code

// by mornstar
// Jun/06/2023 22:40
#include<bits/stdc++.h>
using namespace std;
int main(){
	int T;
	cin>>T;
	while(T--){
		int n;
		char last;
		string s;
		cin>>n>>s;
		for(int i=0;i<n;i++){
			if(i==0)	last=s[0];
			else if(s[i]==last){
				cout<<last;
				i++;
				last=s[i];
			}
		}
		cout<<endl;
	}
}

B

题目大意

给定 $n$ 和 $k$，求有多少个 $k$ 为的二进制数（可以有前导零）小于等于 $n$;

$1\le n,k\le 10^9$

思路

我们知道，$k$ 位的二进制数可以表示 $[0,2^k-1]$ 之间的所有数。

所以当 $n\le 2^k-1$ 时，区间 $[0,n]$ 内的束都可以被表示出来，所以答案为 $n+1$。

否则就只能表示 $[0,2^k-1]$ 之间的数，答案为 $2^k$。

注意：当 $k\ge 30$ 时 $2^k$ 就已经超过 $10^9$，此时答案一定为 $n+1$。

code

// by mornstar
// Jun/06/2023 22:52
#include<bits/stdc++.h>
using namespace std;
int main(){
	int T;
	cin>>T;
	while(T--){
		long long n,k;
		cin>>n>>k;
		if(k>30||n<pow(2,k))	cout<<n+1<<endl;
		else	cout<<(int)pow(2,k)<<endl;
	}
}

C

题目大意

给定 $n$，$k$，$q$ 和一个长度为 $n$ 的序列 $a$。

在 $a$ 中选出一个连续的序列，序列的长度需大于等于 $k$ 并且最大值小于等于 $q$。

共有多少种选法？

思路

我们可以注意到，序列中大于 $q$ 的数将整个序列分成了若干个互不重叠的段。

因为要选择连续的一段，所以肯定不能越过大于 $q$ 的数。

对于一个满足条件的子区间，要从中截取一个长度大于等于 $k$ 的区间，有多少种方法呢？很明显，对于一个长度为 $l$ 的子区间，方案总数为：
$$\sum _{i=1}^{l-k+1}i$$
而这个可以预处理出来。

code

// by mornstar
// Jun/06/2023 23:24
#include<bits/stdc++.h>
using namespace std;
long long n,k,q,a[200005],sum[200005],ans,cnt;
int main(){
	for(int i=1;i<=200005;i++)	sum[i]=sum[i-1]+i;
	int T;
	cin>>T;
	while(T--){
		ans=cnt=0;
		cin>>n>>k>>q;
		for(int i=1;i<=n;i++)	cin>>a[i];
		for(int i=1;i<=n;i++){
			if(a[i]>q){
				if(cnt>=k)	ans+=sum[cnt-k+1];
				cnt=0;
			}else{
				cnt++;
			}
		}
		if(cnt>=k)	ans+=sum[cnt-k+1];//末尾区间特判。
		cout<<ans<<endl;
	}
}

D

题目大意

给定 $n$ 和一个序列 $k$，然后选择任意三个数 $a$，$b$，$c$，使得 max ⁡ i = 1 n { min ⁡ { ∣ k i − a ∣ \max_{i=1}^{n}\{\min\{\left | k_i-a \right | maxi=1n​{min{∣ki​−a∣，$\left|k_i-b\right|$，$\left|k_i-c\right|\}\}$ 最小。

输出这个最小值。

$1\le n\le 2\times 10^5$。
$1\le k_i\le 10^9$。

思路

将数组从小到大排序。

容易发现，整个序列可以分成连续三部分。在第一部分中： min ⁡ { ∣ k i − a ∣ \min\{\left | k_i-a \right | min{∣ki​−a∣，$\left|k_i-b\right|$，$\left|k_i-c\right|\}=\left|k_i-a\right|$，另外两个部分同理。

而对于第一个区间 $[1,r]$，因为其单调不递减，容易得到
max ⁡ i = 1 r { min ⁡ { ∣ k i − a ∣ , ∣ k i − b ∣ , ∣ k i − c ∣ } } = max ⁡ i = 1 r { ∣ k i − a ∣ } = max ⁡ { ∣ k 1 − a ∣ , ∣ k r − a ∣ } \begin{aligned} \max_{i=1}^{r}\{\min\{\left | k_i-a \right |,\left | k_i-b \right |,\left | k_i-c \right |\}\} &= \max_{i=1}^{r}\{\left | k_i-a \right |\} \\ &=\max\{\left | k_1-a \right |,\left | k_r-a \right |\} \end{aligned} i=1maxr​{min{∣ki​−a∣,∣ki​−b∣,∣ki​−c∣}}​=i=1maxr​{∣ki​−a∣}=max{∣k1​−a∣,∣kr​−a∣}​
这时候，问题来到了如何找到一个 $a$ 使得 max ⁡ { ∣ k 1 − a ∣ , ∣ k r − a ∣ } \max\{\left | k_1-a \right |,\left | k_r-a \right |\} max{∣k1​−a∣,∣kr​−a∣} 最小。

很明显，当 $a=\lceil \frac{k_1+k_r}{2}\rceil$ 时这个值最小，为 $\lceil \frac{k_r-k_1}{2}\rceil$，另外两个区间以此类推。

借此，我们可以枚举三个区间的两个交界处来确定三个区间 $O(1)$ 计算答案。

于是，我们可以写出以下代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[200005],ans;
int main(){
	int T;
	cin>>T;
	while(T--){
		bool flag=0;
		ans=INT_MAX;
		cin>>n;
		for(int i=1;i<=n;i++)	cin>>a[i];
		if(n<=3){
			cout<<0<<"\n";
			continue;
		}
		sort(a+1,a+n+1);
		for(int i=1;i<=n-2;i++){
		//i为第一个区间的右端点
			if((a[i]-a[1]+1)/2>=ans)	break;
			//如果前面的区间和已经大于目前最优答案，在枚举下去就没有必要了。
			for(int j=i+1;j<=n-1;j++){
			//j为第二个区间的右端点
				if((a[j]-a[i+1]+1)/2>=ans)	break;
				ans=min(ans,(max(max(a[i]-a[1],a[j]-a[i+1]),a[n]-a[j+1])+1)/2);
			}
		}
		cout<<ans<<"\n";
	}
}

时间复杂度 $O(n^2)$，并不能通过此题。

让我们想一想如何去优化。

首先，在第一个区间右端点确定的情况下，剩下的两个区间最大值要尽可能小，那么剩余两个区间产生的贡献就要尽可能相等（想一想，为什么）。

因为第二个区间的右端点越往后，$k_r$ 的值就越大，即第二个区间的贡献越来越大，同时第三个区间的贡献越来越小。

于是，我们可以想到一个思路——二分。

如果第二个区间的贡献比第三个区间的贡献小，则第二个区间的右端点还可以往后移。

否则第二个区间的右端点只能往前移。

AC code

// by mornstar
// Jun/07/2023 00:27
#include<bits/stdc++.h>
using namespace std;
int n,a[200005],ans;
int main(){
	int T;
	cin>>T;
	while(T--){
		ans=INT_MAX;
		cin>>n;
		for(int i=1;i<=n;i++)	cin>>a[i];
		if(n<=3){
			cout<<0<<"\n";
			continue;
		}
		sort(a+1,a+n+1);
		for(int i=1;i<=n-2;i++){
			if((a[i]-a[1]+1)/2>=ans)	break;
			//同上
			int l=i+1,r=n;
			while(l<r){
				int mid=(l+r)>>1;
				ans=min(ans,(max(max(a[i]-a[1],a[mid]-a[i+1]),a[n]-a[mid+1])+1)/2);
				if((a[mid]-a[i+1]+1)/2<=(a[n]-a[mid+1]+1)/2)	l=mid+1;
				else	r=mid;
			}
			//二分
		}
		cout<<ans<<"\n";
	}
}

时间复杂度 $O(n\log n)$。

总结区

这次对于我来说考得还蛮好，但是不要存有侥幸心理，交明知道过不了的暴力程序，否则