Codeforces Round956(div2) A~C

A. Array Divisibility

题意:对于所有k = 1~n,能被j = 1~n 整除,要求以这些j作为下标a[j]的和也能够被k整除

思路:题目有点绕,但是仔细读懂题目其实会发现,其实就是从1到n按顺序输出一遍...,别被样例忽悠了

void solve(){
	int n;
	cin >> n;
	for(int i = 1;i<=n;i++){
		cout << i << " ";
	}
	cout << endl;
}

B. Corner Twist

题意:给定两个个n*m的矩阵填充0或1或2的a和b,进行数次操作,每次任选一个长宽不小于2的子矩阵,对于该子矩阵的两对对角而言,其中一对数值+1并mod3,另外一对+2并mod3,问能否将a变为b

思路:首先先将b矩阵每个值减去a矩阵每个值(小于0就加上一个模数),得到新矩阵c,此时问题转换为能否将一个均为0的n*m矩阵转换为该新矩阵c,观察对于每次操作,固定将两行和两列的值+3,因此对于c矩阵,判断每行每列的和是否mod3为0,是则可以转换,不是则不可以。代码如下:

void solve(){
	string a[505];
	string b[505];
	int c[505][505];
	int n,m;
	vector<int> h(n+5),w(m+5);
	cin >> n >> m;
	
	for(int i = 1;i<=n;i++)
			cin>>a[i];
	for(int i = 1;i<=n;i++){
		cin>>b[i];
		for(int j = 0;j<m;j++){
			int res = ((b[i][j]-'0') - (a[i][j]-'0'))<0?(b[i][j]-'0') - (a[i][j]-'0')+3:(b[i][j]-'0') - (a[i][j]-'0');
			c[i][j+1] = res;
		}
	}
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=m;j++)
			h[i] += c[i][j];
		
	for(int i = 1;i<=m;i++){
		for(int j = 1;j<=n;j++){
			w[i] += c[j][i];
		}
	}
	for(int i = 1;i<=n;i++){
		if(h[i]%3 != 0){
			cout << "NO" << endl;
			return;
		}
	}
	for(int i = 1;i<=m;i++){
		if(w[i]%3 != 0){
			cout << "NO" << endl;
			return;
		}
	}
	cout << "YES" << endl;
}

C. Have Your Cake and Eat It Too

题意:三个人选蛋糕,每个人按顺序选,选到的价值必须是总价值/3向上取整

思路:如果是两个人,那么要么第一个人先选要么第二个人先选,总共就两种情况,现在变成三个人,同理,最多有六种情况,进行分类讨论即可。

优化1:一种一种列出来可以,但是太长太耗时了,这次是6个,下次万一来更多个甚至更多咋办,所以我们可以用next_permutation函数进行排列。

函数介绍:bool next_permutation(iterator start,iterator end),当当前序列不存在下一个排列时,函数返回false,否则返回true,我们可以把a看作是0,b看作是1,c看作是2,作为数组索引方便写代码,代码如下:

void solve(){
	int n;  cin >> n;
	int tot = 0;
	vector<int> a[3];
	for(int i = 0;i<3;i++)
		for(int j = 1;j<=n;j++){
			int num;cin>>num;
			a[i].push_back(num);
			if(i == 0)
				tot+=num;
		}
	array<int,3> prem{0,1,2};
	do{
		int l[5];
		int r[5];
		int cur = 0;
		bool ok = true;
		for(int i = 0;i<3;i++){//按prem顺序依次选
			l[prem[i]] = cur;
			int sum = 0;
			for(int j = cur;j<n;j++){//找到大于tot/3上取整为止
				sum+=a[prem[i]][j];
				if(sum >= (tot+2)/3){//找到了 设置r
					r[prem[i]] = cur;
					cur+=1;
					break;
				}
				cur+=1;
			}
			if(sum < (tot+2)/3){//找不到 该种排列无解
				ok = false;
				break;
			}
		}
		if(ok){//有解 输出结果
			for(int i = 0;i<3;i++){
				cout << l[i]+1 << " "<<r[i]+1<< " ";
			}
			cout << endl;
			return;
		}
	}while(next_permutation(prem.begin(),prem.end()));
	cout << -1 << endl;//所有排列都无解  输出结果
}

 优化2:对于每个人查找价值大于tot/3上取整的过程,时间复杂度为O(n),这里可以用前缀和加二分进行优化,把时间复杂度降低到O(logn),代码如下:

void solve(){
	int n;  cin >> n;
	int tot = 0;
	vector<int> a[3];
	for(int i = 0;i<3;i++)
		for(int j = 0;j<n;j++){
			int num;cin>>num;
			int last = j-1<0?0:a[i][j-1];
			a[i].push_back(num+last);
			if(i == 0)
				tot+=num;
		}
	array<int,3> prem{0,1,2};
	do{
		int l[5];
		int r[5];
		int cur = 0;
		bool ok = true;
		
		for(int i = 0;i<3;i++){//按prem顺序依次选
			int solt = prem[i];
			l[solt] = cur;
			int tar = cur-1<0?(tot+2)/3:(tot+2)/3+a[solt][cur-1];
			auto it = lower_bound(a[solt].begin(),a[solt].end(),tar);//二分查找第一个大于等于tar的值
			if(it == a[solt].end()){//找不到
				ok = false;
				break;
			}else{//找到了
				r[solt] = it-a[solt].begin();
				cur = r[solt]+1;
			}	
		}
		if(ok){//有解 输出结果
			for(int i = 0;i<3;i++){
				cout << l[i]+1 << " "<<r[i]+1<< " ";
			}
			cout << endl;
			return;
		}
	}while(next_permutation(prem.begin(),prem.end()));
	cout << -1 << endl;//所有排列都无解  输出结果
}