Codeforces Round 746 Div. 2（ABC）

cf746 div2

@[TOC] cf746 div2

第一次直接循环超时了，要直接计算答案

#include
#define fo(a,b,c)  for(int a=b;a>t;
    while(t--){
        cin>>n>>h;
        int a[n];
        fo(i,0,n) cin>>a[i];
        sort(a,a+n);
        if(h<=a[n-1]){cout<<1<0) ans++;
        if(h%m>a[n-1]) ans++;
        cout< 
B. Hemose Shopping 思维 
 
 
n个数，每次移动可以交换i，j上的数，|i-j|>=x
 
 
 
 
解题思路：
 如果n>2x，所有数字都可以移动，一定可以排好序。否则区间n-x~x-1（编号从0开始）的数不会被移动，检查是这些数否处于正确位置即可
 
 
#include
#define fo(a,b,c)  for(int a=b;a>t;
    while(t--){
	cin >> n >> x;
	int a[n],b[n];
	for (int i = 0;i < n;++i) 
		cin >> a[i],b[i] = a[i];
	sort(b,b+n);
	if (n >= 2 * x){
		puts("YES");
		continue;
	}
		bool f = 1;
		for (int i = n - x;i < x;++i)
			if (a[i] != b[i]) {
				f = 0;
				break;
			}
		if (f) puts("YES");
		else puts("NO");
	}
    return 0;
}


 
C. Bakry and Partitioning DFS 
 
 
一棵树有n个节点，n-1条边，是否可以删除x条边（1<=x 
 
 
 
解题思路：
 x^x=0，如果所有节点的异或为0，那么删除一条边就可以分为相等的两部分
 x ^ x ^ x = x，如果可以分成三部分，各部分异或都和总异或相等，也符合要求
 
 
#include
#define fo(a,b,c)  for(int a=b;a g[N],a;
void dfs(int u,int v) {
	for (auto i : g[u]) {
		if (i == v) continue;
		dfs(i,u);
		if (ans == a[i]) res++;
		else a[u] ^= a[i];
	}
}

void solve() {
	cin >> n >> k;
	ans = res = 0;
	for (int i = 1;i <= n;++i)
		g[i].clear();
	a.resize(n + 1);
	for (int i = 1;i <= n;++i) {
		int x;cin >> x;
		a[i] = x;
		ans ^= x;
	}
	for (int i = 1;i <= n - 1;++i) {
		int x,y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	if (ans == 0) {
		puts("YES");
		return;
	}
	if (k > 2) {
		dfs(1,0);
		if (res >= 2) {puts("YES");return;}
	}
		puts("NO");
}

int main() {
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}