Codeforces Round #746 (Div. 2) C.D

Problem Analysis

题目描述：对于给定的一棵树，判断能否通过删除 1 1 1~ k − 1 k-1 k−1条边，使删边后的森林中的每个连通块的异或和相等。

思路：思路比较巧妙：对于异或操作，我们容易知道对于任意整数 n n n：

1. n   x o r   n = 0 n xor n = 0 n xor n=0 ；
2. 0   x o r   n = n 0 xor n = n 0 xor n=n；
3. 1 , 2 → n   x o r   n   x o r   n = n 1,2 rightarrow n xor n xor n= n 1,2→n xor n xor n=n。

那么对于整棵树而言，如果异或和为 0 0 0，那么必然可以通过删去一条边得到两个异或值相等的连通块，此时直接输出yes。

如果异或值不为 0 0 0，设为 n n n，那么至少有 3 3 3个以上的连通块异或值为 n n n，才有机会得到预期答案。但要注意，如果 k ≤ 2 kleq2 k≤2，那么无法分割连通块。

Accepted Code

#include 
#define pb push_back
#define int long long
using namespace std;

inline int read(){
    int f = 1, x = 0; char s = getchar(); 
    while(s < '0'||s > '9'){ if(s =='-') f = -1; s = getchar(); } 
    while(s >= '0' && s <= '9'){ x = x * 10 + s - '0'; s = getchar();}
    return x *= f; 
}

const int N = 2e5 + 10;
int a[N];

vector g[N];

int sum, xorsum;

int dfs(int now, int pre){
    int ret = a[now];
    for(int i = 0; i < g[now].size(); i++){
        int v = g[now][i];
        if(v != pre) ret ^= dfs(v, now);
    }
    if(ret == xorsum) ret = 0, sum++;
    return ret;
}

inline void solve(){
    int n = read(), k = read(); xorsum = 0;
    for(int i = 1; i <= n; i++) a[i] = read(), xorsum ^= a[i];
    for(int i = 1, u, v; i <= n - 1; i++){
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    if(!xorsum){
        cout << "YES" << endl;
    }
    else if (k >= 3){
        sum = 0;
        dfs(1, 0);
        if(sum > 2) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    else cout << "NO" << endl;
    for(int i = 1; i <= n; i++) g[i].clear();
}


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

Problem Analysis

一道交互题。，。好久没写交互了

思路很简单，直接查询，根据回答二分即可。

Accepted Code

#include 
using namespace std;

inline int read(){
    int f = 1, x = 0; char s = getchar(); 
    while(s < '0'||s > '9'){ if(s == '-') f = -1; s = getchar(); } 
    while(s >= '0' && s <= '9'){ x = x * 10 + s - '0'; s = getchar();}
    return x *= f; 
}

const int N = 1e3 + 10;
vector g[N];
int dfn[N], id[N], pre[N], num = 0, times = 0;

inline void dfs(int now, int fa){
    dfn[now] = ++num;
    id[num] = now;
    for(auto v : g[now]){
		if(v == fa)  continue ;
		pre[v] = now ;
		dfs(v , now) ;
	}
}

inline int ask(int l, int r){
    times++; 
    if(times > 12) exit(0);
    int t = 0;
    printf("? %d", r - l + 1);
    for(int i = l; i <= r; i++) printf(" %d", id[i]);
    printf("n");
    fflush(stdout);
    int ans = read();
    return ans;
}

signed main(){
    int n = read();
    for(int i = 1; i <= n - 1; i++){
        int u = read(), v = read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 1);
    int res = ask(1, n), l = 2, r = n, fg = 2;
    while(l <= r){
        int mid = l + r >> 1;
        if(ask(1, mid) == res) fg = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf("! %d %dn", pre[id[fg]], id[fg]);
    fflush(stdout);
    return 0;
}