欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

CF 673 div2 BCD

程序员文章站 2022-06-26 15:19:05
B. Two Arrays题意:给n个数,把他分成0,1两组,f(x) = 每组内任意两个数字和=T的对数使f(0) + f(1) 最小#include using namespace std;const int maxn = 1e5 + 10;int t,n,T;int x,ans[maxn];map mp;int main(){ios::sync_with_stdio(0);cin >> t;...

传送门

B. Two Arrays

题意:给n个数,把他分成0,1两组,
f(x) = 每组内任意两个数字和=T的对数
使f(0) + f(1) 最小

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int t,n,T;
int x,ans[maxn];
map<int,int> mp;
int main(){
	ios::sync_with_stdio(0);
	cin >> t;
	while(t--){
		mp.clear();
		cin >> n >> T;
		for(int i = 0; i < n; i++) {
		   cin >> x;
		   if(mp.count(T-x) == 1)
		       ans[i] = mp[T - x] ^ 1;
		   else ans[i] = 0;
		   mp[x] = ans[i];
	   }
		for(int i = 0; i < n; i++){
		    if(i) cout << " " << ans[i];
		    else cout << ans[i];
		}
		cout << endl;

	}
	return 0;
}

C. k-Amazing Numbers

题意:给n个数字,当长度分别为1,2…n的时候,公共的最小数字是几,没有-1

分析:
当长度越长的时候,这个数字越小
给的n个数字的范围是1-n
假设长度为i的时候,最小的公共数字为x,然后扩展,看看其他的是否也是x
具体看代码吧

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int t,n,arr[maxn],last[maxn],ans[maxn];
void Init(){
	for(int i = 1; i <= n; i++){
		arr[i] = last[i] = 0;
		ans[i] = -1;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin >> t;
	while(t--){
		cin >> n;
		Init();
		for(int i = 1; i <= n; i++){
			int x;
			cin >> x;
			/*arr表示和上一个数字之间差着几个数,
			如果是1,说明相邻 ,即长度为1的时候,是最小值 ,例如aa 
			是2的话,说明隔着1个数字,长度为2的时候符合,例如aba 
			以此类推...
			*/ 
			arr[x] = max(arr[x],i - last[x]);
			last[x] = i;//记录x的位置 
		}
		for(int i = 1; i <= n; i++){
			/*arr[i]已经是前半部分的分段的最小值了,
			要满足整个数组,
			所以考虑后半部分,后半部分也就是n - last[i] + 1*/
			arr[i] = max(arr[i], n - last[i] + 1);
			for(int j = arr[i];j <= n && ans[j] == -1;j++)
				ans[j] = i;
		} 
		for(int i = 1; i <= n; i++){
			if(i != 1) cout << " ";
			cout << ans[i];
		}
		cout << endl;
	}
	return 0;
}

D. Make Them Equal

分析:先把每个数字都加到1上,其他数字变为0;
然后再把1上的数字分到其他数字上

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;
int t,n;
long long a[maxn],sum;
int main(){
	ios::sync_with_stdio(0);
	cin >> t;
	while(t--){
		cin >> n;
		sum = 0;
		for(int i = 1; i <= n; i++){
			cin >> a[i];
			sum += a[i];
		}
		if(sum % n){
			cout << "-1" << endl;
			continue;
		}
		cout << 3 * n << endl;
		for(int i = 1; i <= n; i++){
			int x1 = (a[i] % i) ? (i - a[i] % i) : 0;
				/*为什么变化时,a[1]会是正的?
				因为a[i] % i的数据范围[1,i -1],,在上一步1相当于j的时候,a[j] = a[j] + i * x,
				所以走这一步的时候,不会变成负的*/
			cout << 1 << " " << i << " " << x1 << endl;//相当于把第二个数字变成i的倍数 
		
			cout << i << " " << 1 << " " << (a[i] + x1)/i << endl;//a[i] = a[i] - i * x; 此时a[i] = 0; 
		}
		sum /= n;
		for(int i = 1; i <= n; i++)
			cout << 1 << " " << i << " " << sum << endl;
	
	}
	return 0;
}

本文地址:https://blog.csdn.net/xcfkaixin/article/details/108863840

相关标签: CF