Codeforces Round 746 div.2 CDE

这场没打，赛后看了一下题值得补

C. Bakry and Partitioning

题意：给出一棵 \(n\) 节点的树，每个点有权值 \(a_i\)，问能否割去至少一条，至多 \(k-1\) 条边，使得割完后各个连通块的权值异或和相等。

显然，如果整棵树的异或和为0，那么任选一条边割得到的两个连通块异或和都相等。（异或的性质）

如果整棵树异或和为 \(x\) ，那么问题就等价于能不能把树拆出三个异或和为 \(x\) 的连通块（三个可以合并成一个，所以能拆成更多块的也一定能拆成三块）

dfs地去找，当某个子树的异或和为 \(x\) 时，记录并将这个子树清零，跑完之后看找到了几个即可

记得对 \(k=2\) 特判

int n, k;
int a[maxn], xs[maxn];
int xsum, ans;
struct Edge{
    int t, nt;
}e[maxn << 1];

int head[maxn], cnt = 0;

inline void add(int x, int y){
    e[++cnt].t = y;
    e[cnt].nt = head[x];
    head[x] = cnt;
}

void dfs(int p, int fa){
    xs[p] = a[p];
    for(int i=head[p];i;i=e[i].nt){
        int v = e[i].t;
        if(v != fa){
            dfs(v, p);
            xs[p] ^= xs[v];
        }
    }
    if(xs[p] == xsum){
        ans++;
        xs[p] = 0;
    }
}

void solve(){
    cin >> n >> k;
    xsum = cnt = ans = 0;
    for(int i=1;i<=n;i++) head[i] = 0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        xsum ^= a[i];
    }
    for(int i=1;i<n;i++){
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    if(xsum == 0){
        cout << "YES\n";
    }else{
        if(k <= 2){
            cout << "NO\n";
            return;
        }
        dfs(1, 0);
        if(ans > 2) cout << "YES\n";
        else cout << "NO\n";
    }
}

D. Hemose in ICPC ?

题意：交互题，现有一棵 \(n\) 节点的树，每个边有边权（边权未知），可以进行至多12次询问：每次询问一个点集，回复是这个点集中 \(Dist(a,b)\) 的最大值，\(Dist(a,b)\) 定义为 \(a\) 到 \(b\) 路径上所有边权的gcd，求使 \(Dist(a,b)\) 最大的 \(a,b\)

首先可以看出要找的就是权值最大的边，gcd是纯唬人的。

第一次查询先查询所有的点，这样就可以知道最大的边权是多少。

查询次数为12，数据规模 \(n<1000\)，如果我们能以某种方式把树映射到序列上，且序列上连续的点在树上也连续，就可以二分地询问，找最大边的位置（因为连续，所以序列上两点之间就是边）。

欧拉序即可保证连续性。

ps：一开始用dfs序糊里糊涂过了，不能保证连续性但也能通过某种玄学的巧合AC，正确性不是很显然，我也讲不清楚，就不介绍了

int n;
struct Edge{
    int fr, t, nt;
}e[maxn << 1];

int head[maxn], cnt = 0;
int vis[maxn], vp = 0;
int a[maxn << 1];

inline void add(int x, int y){
    e[++cnt].t = y;
    e[cnt].fr = x;
    e[cnt].nt = head[x];
    head[x] = cnt;
}

void dfs(int p, int fa){
    a[++cnt] = p;
    for(int i=head[p];i;i=e[i].nt){
        int v = e[i].t;
        if(v != fa){
            dfs(v, p);
            a[++cnt] = p;
        }
    }
}

int getans(int l, int r){
    vp++;
    int k = 0, res;
    for(int i=l;i<=r;i++){
        if(vis[a[i]] != vp) vis[a[i]] = vp, k++;
    }
    cout << "? " << k;
    for(int i=1;i<=n;i++){
        if(vis[i] == vp) cout << ' ' << i;
    }
    cout << endl;
    fflush(stdout);

    cin >> res;
    return res;
}

void solve(){
    cin >> n;
    cnt = 0;
    for(int i=1;i<n;i++){
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    cnt = 0;
    dfs(1, -1);

    int mx;
    cout << "? " << n << ' ';
    for(int i=1;i<n;i++) cout << i << ' ';
    cout << n << endl;
    fflush(stdout);
    cin >> mx;

    int l = 1, r = cnt, mid;
    while(l + 1 < r){
        mid = (l + r) / 2;
        if(getans(l, mid) == mx){
            r = mid;
        }else{
            l = mid;//二分部分小改一下 因为要找的是两点间的连边
        }
    }
    cout << "! " << a[l] << ' ' << a[r] << '\n';
}

E. Bored Bakry

题意：给一个长度为 \(n\) 的序列 \(a\)，找到最长的子区间 \(a_l..a_r\) 使得子区间所有元素的与运算和大于异或和

对每一位考虑，在第 \(k\) 位上，与和为1的条件是区间所有数第 \(k\) 位全是1；异或和为1的条件是区间中第 \(k\) 位为1的数量是奇数个

那么可以注意到如果区间长度为奇数，任一位上与和为1的时候异或和也一定为1，与和不可能大于异或和

现在考虑，对于特定一个区间，如何判断它是否满足条件：

• 首先它的长度必须为偶数
• 从高位到低位枚举，如果它在第 \(k\) 位时第一次满足了区间第 \(k\) 位全为1，那么比 \(k\) 更高的位上1数量必须都为偶数

可以维护一个前缀异或和（记为 \(xsum\)），从高位到低位枚举到第 \(k\) 位时，\(xsum(i)\)表示仅考虑前 \(k-1\) 位值时，前 \(i\) 位的异或和

第二个条件其实就相当于 \(xsum(r) = xsum(l-1)\)，因为前面这些位上的1都是偶数个

那么做法就很显然了：从高位到低位枚举，每一层中对于每一个1的位置 \(r\)，去找最小的满足条件的 \(l\)，同时维护 \(xsum\) 即可

关于找最小的 \(l\) ，记录同一段连续1内每一个 \(xsum\) 值最早出现的位置即可（详见代码）

int gtw(int x, int w){ return (x >> (w-1)) & 1;}

int n, a[maxn], p[maxn];
int xsum[maxn], pos[maxn * 2];

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }

    int ans = 0;
    for(int k=21;k>=1;k--){
        int l = 1, r;
        while(l < n){
            while(l <= n && gtw(a[l], k) == 0) l++;
            if(l > n) break;
            r = l + 1;
            while(r <= n && gtw(a[r], k) == 1) r++;
            r--;
            for(int j=l-1;j<=r;j+=2) pos[xsum[j]] = -1;
            for(int j=l-1;j<=r;j+=2){
                if(pos[xsum[j]] == -1) pos[xsum[j]] = j;
                else ans = max(ans, j - pos[xsum[j]]);
            }

            for(int j=l;j<=r;j+=2) pos[xsum[j]] = -1;
            for(int j=l;j<=r;j+=2){
                if(pos[xsum[j]] == -1) pos[xsum[j]] = j;
                else ans = max(ans, j - pos[xsum[j]]);
            }
            l = r + 1;
        }
        for(int i=1;i<=n;i++){
            p[i] += a[i] & (1 << (k-1));
            xsum[i] = xsum[i-1] ^ p[i];
        }
    }
    cout << ans << '\n';
}