Codeforces Round #764 (Div. 3)（A、B、C、D、G）

Codeforces Round #764 (Div. 3)（A、B、C、D、G） A. Plus One on the Subse

求出最大值与最小值只差即可
ACcodr

#include

using namespace std;

typedef long long ll;
const int N=2000010,mod=998244353;


void Test(){
	int n;
	int mi=0x3f3f3f3f,ma=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		mi=min(x,mi);
		ma=max(x,ma);
	}
	cout<>t;
	while(t--)
	Test();
} 

B. Make AP

题意：给出三个数a、b、c，让其中一个数乘以一个正整数m，问可不可以是a b c成为等差数列
解析：分别固定ab、bc、ac ，求出另一个位置的数应该是多少，判断是不是成倍数关系，注意这里的倍数应该是一个正整数
ACcoder：

#include

using namespace std;

typedef long long ll;
const int N=2000010,mod=998244353;


void Test(){
	ll a,b,c;
	cin>>a>>b>>c;
	ll d=a-b;
	ll e=b-d;
	if(e%c==0&&e/c>0){
		cout<<"Yesn";
		return ;
	}
	
	 d=c-b;
	 e=b-d;
	if(e%a==0&&e/a>0){
		cout<<"Yesn";
		return ;
	}
	
	d=a+c;
	if(d%2==0&&d/2%b==0&&d/2/b>0){
		cout<<"Yesn";
		return ;
	}
	cout<<"Non";
}


int main(){
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	Test();
} 

C. Division by Two and Permutation

题意：给定一个数组a，选择若干个a[i]，使a[i]=a[i]/2，可以进行多次。问a最终是不是可以成为n的排列
题解：将所有大于n的数一直除以2，直到小于等于n为止，此时a数组所有的数全都小于等于n，再把a中出现次数大于1的数尽量减少（将他们除以2），直到不能 *** 作为止，再看此时a是不是n的排列
ACcoder：

#include

using namespace std;

typedef long long ll;
const int N=2000010,mod=998244353;

int ma[N];

void Test(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) ma[i]=0; 
	vectorv;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		while(x>n) x/=2;
		while(ma[x]&&x!=0) x/=2;
		v.push_back(x);
		ma[x]=1;
	}
	sort(v.begin(),v.end());
	int flag=0;
	for(int i=1;i<=n;i++){
		if(v[i-1]!=i) flag=1;
	}
	if(flag) printf("NOn");
	else printf("YESn");
}


int main(){
	ios::sync_with_stdio(false);
	int t;
	scanf("%d",&t);
	while(t--)
	Test();
} 

D. Palindromes Coloring

题意：给定一个字符串s，将s打乱分成k段（可以舍弃一些字符）让着k段都成为回文串，问这k段中最短的串最长是多少
题解：要想组成回文串，相同的字符肯定要分配在这个串的两侧，预处理出来有多少对相同的字符，将这些相同字符的尽量平均分给k个串，剩下的单个的字符尽量平均插在这k个串的中间
ACcoder：

#include

using namespace std;

typedef long long ll;
const int N=2000010,mod=998244353;

int ma[N];

void Test(){
	int n,k;
	string s;
	cin>>n>>k;
	cin>>s;
	int cnt=0;
	
	for(int i='a';i<='z';i++) ma[i]=0;
	for(int i=0;i=k) res++;
	res = max(1, res);
	cout<>t;
	while(t--)
	Test();
}

G. MinOr Tree

题意：给出一些边和这条边的权值，给定的这些边组成一棵树，怎样选边才能使这棵树上的所有边的权值 或 的值最小
题解：因为边的最大值只有1e9，可以从高位到低位遍历，判断如果这一位取0是否可以组成一棵树，如果不能组成一棵树，就必须要把这二进制的这一位加上，这样时间复杂度就是O(n*logn)，在判断的时候可以利用并查集来把可以加的边搞到一个集合里
ACcoder

#include

using namespace std;
typedef long long ll;
int n,m;

const int N=200010;
int p[N];

int find(int x) {
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}

struct Node {
	int u,v,w;
};
ll res=0;

vector f(vector &v,int idx) {
	int len=v.size();
	int cnt=0;
	for(int i=1; i<=n; i++) p[i]=i;
	vectorv1;
	for(int i=0; i>idx&1)==0) {
			if(find(v[i].u)!=find(v[i].v)){
				p[find(v[i].u)]=find(v[i].v);
				cnt++;
			}
			v1.push_back(v[i]); 
		}
	}
	if(cnt==n-1) return v1;
	else {
		res+=(1<>n>>m;
	vectorv;
	while(m--) {
		int x,y,z;
		cin>>x>>y>>z;
		v.push_back({x,y,z});
	}
	for(int i=30; i>=0; i--) {
		v=f(v,i);
	}

	int len=v.size();
	cout<>t;
	while(t--)
		Test();
}