Codeforces Round 1034 (Div. 3) A-G 题解

发布于：2025-07-03 ⋅ 阅读:(48) ⋅ 点赞:(0)

本来可以AK的，就因为 D 这个__东西，害得我G都没看，我赛时要是看G了直接秒掉。
算法题基本上对我来说不难，主要是思维题。全场8000多人过我都想不出来，我思维还是太菜了。

全员排行（Friends only）：
请添加图片描述
Rated用户排行（Friends only）：
请添加图片描述

A. Blackboard Game

题意

黑板上有 n n n 个整数： 0 ∼ n − 1 0\sim n-1 0∼n−1，每次， Alice \text{Alice} Alice 先从剩下的数中选一个数 a a a 并把它擦掉， Bob \text{Bob} Bob 再选一个数 b b b，使得 a + b   m o d   3 = 0 a+b\bmod3=0 a+bmod3=0，然后擦掉，最后一个不能选数的人输。若双方都已最佳策略玩游戏，赢得比赛的人是谁？

思路

将 n n n 个数分为 4 4 4 类： A , B , C , D A,B,C,D A,B,C,D，分别表示   m o d   4 = 0 , 1 , 2 , 3 \bmod4=0,1,2,3 mod4=0,1,2,3。每次 Alice \text{Alice} Alice 从 A A A 中选， Bob \text{Bob} Bob 就只能从 C C C 中选，记为 ( A , C ) (A,C) (A,C)，同理 ( C , A ) , ( B , D ) , ( D , B ) (C,A),(B,D),(D,B) (C,A),(B,D),(D,B)，那么只有当 A , B , C , D A,B,C,D A,B,C,D 的个数相同时，即 n   m o d   4 = 0 n\bmod4=0 nmod4=0 时， Bob \text{Bob} Bob 才有可能获胜，其余情况 Alice \text{Alice} Alice 胜。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int T;
	cin>>T;
	while(T--){
		int n;
        cin>>n;
        if(n%4==0){
            cout<<"Bob\n";
        }else{
            cout<<"Alice\n";
        }
	}
	return 0;
}

B. Tournament

题意

n n n 个人，第 i i i 个实力为 a i a_i ai​。每次你可以任选两个人，移走实力较差的那个人（若两人相同，任意移走一个），直到只剩下 k k k 个。问：是否存在一种方案，使得 j j j 个人能留到最后。

思路

k ≥ 2 k\ge 2 k≥2 时，可以一直不选 j j j， j j j 就一定不会被移走；否则， k = 1 k=1 k=1， j j j 一定会被选中，所以它必须得是实力最强的那一个，即 a j = m x a_j=mx aj​=mx，其中 m x mx mx 表示 a i a_i ai​ 的最大值。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int v[maxn];
void solve(){
	int n,j,k;
	cin>>n>>j>>k;
	for(int i=1;i<=n;i++) cin>>v[i];
	if(k>=2){
		cout<<"YES\n";
		return;
	}
	int val=v[j];
	sort(v+1,v+1+n);
	if(v[n]==val){
		cout<<"YES\n";
	}else{
		cout<<"NO\n";
	}
}
int main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

C. Prefix Min and Suffix Max

题意

你有一个所有数字都不同的长度为 n n n 的数组 a a a，在一次操作中：

  • 可以选择一个前缀，将这个前缀全部删掉，替换成这些数的最小值
  • 可以选择一个后缀，将这个前缀全部删掉，替换成这些数的最大值

可以选择整个数组。

对于每个 a i a_i ai​，是否存在一种方案，使得执行任意次操作以后，整个数组只包含一个元素且与 a i a_i ai​ 相等。可以输出 1，不能输出 0。

思路

对于每个 a i a_i ai​，先考虑比较明显的一种方案：

  • 选择前缀 1 ∼ i − 1 1\sim i-1 1∼i−1，后缀 i + 1 ∼ n i+1 \sim n i+1∼n，此时序列变成 3 3 3 个数：设为 a , b , c a,b,c a,b,c，可以发现， a > b > c , a < b > c a>b>c,a<b>c a>b>c,a<b>c 都是可以的，也就是除了 a < b < c a<b<c a<b<c 的情况，其它都可以将它变为 b b b。

接下来，我们单独研究 a < b < c a<b<c a<b<c 的情况，考虑原数组，相当于 a i a_i ai​ 大于前面的最小值，且小于后面的最大值，也就是说前缀最多选到 i − 1 i-1 i−1，后缀最多选到 i + 1 i+1 i+1，否则就把 a i a_i ai​ 覆盖了，然而，这样总是无法将长度缩小到 1 1 1。所以当且仅当 a < b < c a<b<c a<b<c 时，不可以；其余情况都可以。

前缀最小值和后缀最大值可以用数组预处理，也可以用 set 维护、

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int v[maxn];
void solve(){
	int n;
	cin>>n;
	multiset<int> p,s;
	for(int i=1;i<=n;i++){
		cin>>v[i];
		s.insert(v[i]);
	}
	p.insert(inf); s.insert(0);//边界情况，防止1和n的时候出错
    string ans="";
	for(int i=1;i<=n;i++){
		s.erase(s.find(v[i]));
		int prv=*p.begin();//前缀最小值
		int nxt=*s.rbegin();//后缀最大值
		if(prv<v[i]&&v[i]<nxt){
			ans+="0";
		}else{
			ans+="1";
		}
		p.insert(v[i]);
	}
	cout<<ans<<endl;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

D. Binary String Battle

题意

有一个长度为 n n n 的 01 01 01 字符串 s s s，每次按顺序进行以下操作：

  • Alice \text{Alice} Alice 选择一个长度为 k k k 的子序列，并把它们全部变成 0；

  • Bob \text{Bob} Bob 选择一个长度为 k k k 的字串，并把它们全部变成 1。

若双方都以最佳策略操作，问：是否可以有某一时刻，整个字符串都是 0。

若可以，输出 Alice，否则输出 Bob。

思路

结论：若 1 的个数 ≤ k \le k ≤k 或 2 k > n 2k>n 2k>n， Alice \text{Alice} Alice 胜。

第一个不用证明了，一次就结束了。

第二个引述自 UKBwyx \color{red}{\text{UKBwyx}} UKBwyx 大佬的证明：

  • 若 2 k > n 2k>n 2k>n，假设上一轮是全 1（对 Alice \text{Alice} Alice 最差的局面），可以从左右端分别开始选，左右边的 0 尽可能一样多。而每次 Bob \text{Bob} Bob 只能顾及一边，所以若干次后，可以造出两边各有 n − k n-k n−k 个 0 的局面。不管 Bob \text{Bob} Bob 选哪边，都至少有 n − k n-k n−k 个0，即只有 m m m 个1， Alice \text{Alice} Alice 就可以获胜。
  • 否则， Bob \text{Bob} Bob 可以在场上任选一个是 1 的位置，不可能构造出上述情况。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n,k;
    string s;
    int cnt=0;
	cin>>n>>k>>s;
	s=" "+s;
	for(int i=1;i<=n;i++){
		if(s[i]=='1') cnt++;
	}
	if(cnt<=k){
		cout<<"Alice\n";
	}else if(2*k>n){
		cout<<"Alice\n";
	}else{
		cout<<"Bob\n";
	}
}

int main(){
	int T=1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

E. MEX Count

题意

定义 MEX \text{MEX} MEX 表示一个集合中未出现过的最小非负整数。数组 a a a 长度为 n n n， 0 ≤ a i ≤ n 0\le a_i\le n 0≤ai​≤n，问：对于每个整数 k k k ( 0 ≤ k ≤ n ) (0\le k\le n) (0≤k≤n)，从 a a a 种删除恰好 k k k 个数可以获得多少种不同的 MEX \text{MEX} MEX。

思路

设 c n t i cnt_i cnti​ 表示 i i i 在数组中出现的次数， a n s k ans_k ansk​ 表示每个 k k k 对应的答案。

我们可以考虑：对于每一个 MEX = i ( 0 ≤ i ≤ n ) \text{MEX}=i(0\le i\le n) MEX=i(0≤i≤n)，删除多少个数可以满足此状况。计删除个数为 f f f。

可以想一下，要是 MEX \text{MEX} MEX 为 i i i 的条件是什么：是 0 ∼ i − 1 0\sim i-1 0∼i−1 的所有数每个至少出现一次，且 i i i 没有出现。

对于已经满足条件 “是 0 ∼ i − 1 0\sim i-1 0∼i−1 的所有数每个至少出现一次”：

  • f f f 的最小值，就是将所有的 i i i 删掉，即 f min ⁡ = c n t i f_{\min}=cnt_i fmin​=cnti​；
  • f f f 的最大值，在把所有的 i i i 删掉的基础上，把 > i >i >i 的全部删掉，然后把 0 ∼ i − 1 0\sim i-1 0∼i−1 每个数只保留一个，即 f max ⁡ = n − i f_{\max}=n-i fmax​=n−i。

此时，这个 i i i 对所有 f min ⁡ ≤ k ≤ f max ⁡ f_{\min}\le k\le f_{\max} fmin​≤k≤fmax​ 的 k k k 贡献为 1 1 1，也就是把 a n s f min ⁡ ∼ f max ⁡ ans_{f_{\min} \sim f_{\max}} ansfmin​∼fmax​​ 都 + 1 +1 +1。

再考虑上面的假设，如果不满足“是 0 ∼ i − 1 0\sim i-1 0∼i−1 的所有数每个至少出现一次”，则无论删掉多少个数， MEX \text{MEX} MEX 都不可能为 i i i，则这个 i i i 对答案的贡献一定为 0 0 0。

接下来讲一下如何维护上面说的区间 + 1 +1 +1 操作：差分，计 C i = a n s i − a n s i − 1 ( i > 0 ) C_i=ans_i-ans_{i-1}(i>0) Ci​=ansi​−ansi−1​(i>0)

则这个区间加操作转化成了把 C f min ⁡ C_{f_{\min}} Cfmin​​ 加一， C f max ⁡ + 1 C_{f_{\max}+1} Cfmax​+1​ 减一。

然后计算 a n s ans ans 数组：对于 i = 0 i=0 i=0， a n s i = C i ans_i=C_i ansi​=Ci​，对于 i > 0 i>0 i>0， a n s i = a n s i − 1 + C i ans_i=ans_{i-1}+C_i ansi​=ansi−1​+Ci​。

最后输出所有 a n s i ( i = 0 ∼ n ) ans_i(i={0\sim n}) ansi​(i=0∼n) 即可。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int cnt[maxn];
int ans[maxn];
void solve(){
	int n;
	cin>>n;
	for(int i=0;i<=n;i++) cnt[i]=0;ans[i]=0;//多测记得清空
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		cnt[x]++;
	}
    //此处我不想再开一个数组C了，直接在ans上操作
	for(int i=0;i<=n;i++){
		ans[cnt[i]]++;
		ans[n-i+1]--;
		if(cnt[i]==0) break;//有一个不可以，后面的一定都不可以
	}
	for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
	for(int i=0;i<=n;i++) cout<<ans[i]<<" ";
	cout<<endl;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

F. Minimize Fixed Points

题意

构造一个长度为 n n n 的排列 p p p，满足以下条件：

  • 对于 2 ≤ i ≤ n 2\le i\le n 2≤i≤n， gcd ⁡ ( p i , i ) > 1 \gcd(p_i,i)>1 gcd(pi​,i)>1；
  • 对于 1 ≤ i ≤ n 1\le i\le n 1≤i≤n，使 p i = i p_i=i pi​=i 的数量最小

思路

首先， 1 1 1 肯定排在第一位，不然就不满足条件 1 1 1 了。

然后我们可以想到，对于大于 n 2 \dfrac{n}{2} 2n​ 的质数 k k k，一定满足 p k = k p_k=k pk​=k：

  • 证明：如果不等的话，比它小的不可能一定与之互质，不满足条件 1 1 1，比它大的至少得是 2 k 2k 2k 才能不互质，但是因为 n 2 > k \dfrac{n}{2}>k 2n​>k ，所以 2 k > n 2k>n 2k>n，他就不是排列了。

初始，令 p p p 全部为 0 0 0。

剩下的数我们从最大的 ≤ 2 n \le \dfrac{2}{n} ≤n2​ 的质数开始，从大往小考虑：

  • 对于质数 k k k ：找到所有的倍数 2 k , 3 k , 4 k , . . . , r k 2k,3k,4k,...,rk 2k,3k,4k,...,rk ，且满足 p i k = 0 p_{ik}=0 pik​=0 的 i k ik ik，直到最大的 r r r 使得 r k ≤ n rk\le n rk≤n，然后令 p i k = j k p_{ik}=jk pik​=jk， j j j 为上一个满足条件的系数。特别地， p k = r k p_k=rk pk​=rk。
  • 简单地说，就是把所有是 k k k 的倍数的且没有用过的数，全员向左平移，然后把最左边的移到最右边去。
  • 举个例子，比如说 n = 13 , k = 3 n=13,k=3 n=13,k=3 时，令 p 6 = 3 p_6=3 p6​=3， p 9 = 6 p_{9}=6 p9​=6， p 12 = 9 p_{12}=9 p12​=9，最后， p 3 = 12 p_3=12 p3​=12。
  • 可以证明，每个数的 r ≥ 2 r\ge 2 r≥2，因为系数等于就算别的数用过了某个自己也可以用的数， k 2 , k 3 , . . . k^2,k^3,... k2,k3,... 这种数是一定不会被占用的。

最后输出时，若 p i = 0 p_i=0 pi​=0，输出 i i i 即可；否则输出 p i p_i pi​。

质数直接提前用埃式筛预处理好就行了。

时间复杂度约为： O ( n log ⁡ n ) O(n \log n) O(nlogn)。

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200005;
int ans[maxn];
bool prime[maxn];
vector<int> p;
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
        ans[i]=0;
	}
	int pos=lower_bound(p.begin(),p.end(),n/2)-p.begin();
	for(int i=pos;i>=1;i--){
		if(p[i]>n/2) continue;
		int prv=p[i];
		for(int j=2*p[i];j<=n;j+=p[i]){
			if(ans[j]==0){
				ans[j]=prv;
				prv=j;
			}
		}
		ans[p[i]]=prv;
	}
	
    //这一步多余了，相当于把2单拎出来，可以直接和上面合并起来写
	int prv=2;
	for(int i=4;i<=n;i+=2){
		if(ans[i]==0) ans[i]=prv,prv=i;
	}
	ans[2]=prv;
    
	for(int i=1;i<=n;i++){
		if(ans[i]==0) cout<<i<<" ";
		else cout<<ans[i]<<" ";
	}
	cout<<endl;
}

signed main(){
	int n=100005;
	for(int i=2;i<=n;i++){
		prime[i]=1;
	}
	for(int i=2;i<=n;i++){
		if(prime[i]){
			for(int j=i*i;j<=n;j+=i){
				prime[j]=0;
			}
		}
	}
	for(int i=2;i<=n;i++){
		if(prime[i]){
			p.pb(i);
		}
	}
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

G. Modular Sorting

题意

有一个长度为 n n n 的数组，每个 0 ≤ a i < m 0\le a_i<m 0≤ai​<m。

维护两种操作：

  • 1 i x：把 a i a_i ai​ 的值改为 x x x
  • 2 k：每次操作可以任选一个 i i i，然后将 a i a_i ai​ 改为 ( a i + k )   m o d   m (a_i+k)\bmod m (ai​+k)modm。问：是否存在一种方式，使得 a a a 单调不减，若存在，输出 YES，否则输出 NO。

注意：操作 2 2 2 并没有真的改变原数组，只是一个假设。

思路

根据裴蜀定理，经过若干次操作后，每个 a i a_i ai​ 可以变动 gcd ⁡ ( m , k ) \gcd(m,k) gcd(m,k) 的倍数（必须保持在 0 ∼ m − 1 0\sim m-1 0∼m−1 之间）。换句话说，无论怎么变 a i   m o d   gcd ⁡ ( m , k ) a_i \bmod \gcd(m,k) ai​modgcd(m,k) 总是不变的。

  • 比如 m = 10 , k = 4 m=10,k=4 m=10,k=4 时， gcd ⁡ ( m , k ) = 2 \gcd(m,k)=2 gcd(m,k)=2，这时 5 5 5 可以且只可以变成 1 , 3 , 7 , 9 1,3,7,9 1,3,7,9 或不变。

有了这个结论以后，我们可以考虑枚举 gcd ⁡ \gcd gcd， gcd ⁡ ( m , k ) \gcd(m,k) gcd(m,k) 一定时 m m m 的因数，所以要枚举 m m m 的因数。

然后对于第 i i i 个因数 f a c i fac_i faci​ ，记录 p i , j = v j   m o d   f a c i p_{i,j}=v_j\bmod fac_i pi,j​=vj​modfaci​，要想使这个递增，可以使每个元素加上 0 0 0 个或多个 f a c i fac_i faci​，最多的哪个要加多少个呢：

  • 很明显，如果 p i > p i − 1 p_i>p_{i-1} pi​>pi−1​，就要加一次，最后那一个就要加上 [ 满 足 p i > p i − 1 的 数 量 总 和 ] [满足 p_i>p_{i-1} 的数量总和] [满足pi​>pi−1​的数量总和] 个 f a c i fac_i faci​。将上述个数记为 n u m i num_i numi​。

设 t o k to_k tok​ 表示 k k k 为 m m m 的第几个因数。

所以，先预处理出 p p p 和 n u m num num，然后：

  • 对于第 1 1 1 种操作，我们要遍历所有的因数，把原来这一位影响答案的数量减去，再把改完以后这一位影响答案的数量加上。
  • 对于第 2 2 2 种操作，设 t o gcd ⁡ ( k , m ) = c to_{\gcd(k,m)}=c togcd(k,m)​=c ，如果 p c p_{c} pc​ 的最后一个元素加上 n u m c × c num_c\times c numc​×c 小于 m m m 就可以，否则就不行。

总时间复杂度： O ( m + n m + q m ) O(\sqrt m+n\sqrt m +q\sqrt m) O(m ​+nm ​+qm ​)。

C++ 代码

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(v) (int)v.size()
using namespace std;
const int inf=3e18;
const int maxn=500005;
int v[maxn],to[maxn];
vector<int> p[300];
int num[300];
void solve(){
	int n,m,q;
	cin>>n>>m>>q;
    for(int i=0;i<=m;i++) to[i]=0;
	for(int i=1;i<=n;i++) cin>>v[i];
	vector<int> fac;
	for(int i=1;i*i<=m;i++){
		if(m%i==0){
			fac.pb(i);
			if(i*i!=m) fac.pb(m/i);
		}
	}
	sort(all(fac));
	for(int i=0;i<sz(fac);i++){
		to[fac[i]]=i;
		num[i]=0;
		p[i].clear();
		p[i].resize(n+2);
		for(int j=1;j<=n;j++){
			p[i][j]=v[j]%fac[i];
			if(p[i][j]<p[i][j-1]){
				num[i]++;
			}
		}
		p[i][n+1]=inf;//最后一位改变后，它的后面一位不会对答案有影响，防止第65行和68时计算出错
	}
	while(q--){
		int opt;
		cin>>opt;
		if(opt==1){
			int pos,x;
			cin>>pos>>x;
			v[pos]=x;
			for(int i=0;i<sz(fac);i++){
				if(p[i][pos]<p[i][pos-1]) num[i]--;
				if(p[i][pos+1]<p[i][pos]) num[i]--;
				p[i][pos]=x%fac[i];	
				if(p[i][pos]<p[i][pos-1]) num[i]++;
				if(p[i][pos+1]<p[i][pos]) num[i]++;
			}
		}else{
			int k;
			cin>>k;
			k=__gcd(m,k);
			if(p[to[k]][n]+num[to[k]]*k<m){
				cout<<"YES\n";
			}else{
				cout<<"NO\n";
			}
		}
	}
	
}
signed main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布