Codeforces Round # 746-Div. 2-C Bakry and Partitioning题解

• 题目链接
• 题目分析
• 源代码
• 吐槽

题目链接放在Bakry and Partitioning，大意就是给一棵有 n n n个节点的树，树上每个节点 i i i都带有一个权值 a i a_i ai​，现在要把这棵树分成满足条件的x个联通分支（2 ⩽ x ⩽ k , k leqslant xleqslant k,k ⩽x⩽k,k为题目给定的值）：每个联通分支所有节点的权值做异或运算后得到一个值而且所有 x x x个值要相等。如果存在满足条件的分法则输出 Y E S YES YES，否则输出 N O NO NO。

先说下题目思路，由异或的运算规则可以得到两条性质：

1. ∀ x ∈ N , x ( n ) : = x   x o r   x ⋯ x o r   x forall xin mathbf N,x^{(n)}:=x mathrm{xor} xcdotsmathrm{xor} x ∀x∈N,x(n):=x xor x⋯xor x(一共 n n n个 x x x)，则当 n n n为偶数时， x ( n ) = 0 x^{(n)}=0 x(n)=0；当 n n n为奇数时， x ( n ) = x x^{(n)}=x x(n)=x.
2. x   x o r   0 = x x mathrm{xor} 0=x x xor 0=x.

由此我们可以得到，当给定的数可被分为偶数个满足条件的联通分支时，所有节点的异或值为0（充要条件）。我们只需要将树分为任意的两个联通分支即可；当给定给定的数只可被分为奇数个满足条件的联通分支时，此时设所有节点的异或值为 x ( x ≠ 0 ) x(xneq0) x(x​=0)，我们在树中需要找到两支互不相交的异或值均为 x x x的联通分支，然后将它们与树的其余部分分开，从而形成三个异或值为 x x x的联通分支，如果找不到的话说明没有满足题目要求的分法。
具体实现步骤如下：

1. 读取数据并建图，然后对所有节点的权值求异或，最后得到值 x x x，转步骤2.
2. 如果 x = 0 x=0 x=0，则直接输出 Y E S YES YES，转步骤1；否则转步骤3.
3. 如果 k = 2 k=2 k=2，则直接输出 N O NO NO，转步骤1；否则转步骤4.
4. 以 1 1 1为根节点对树进行 D F S DFS DFS，在遍历同时寻找互不相交的异或值等于 x x x的联通分支个数 n u m num num.如果 n u m > = 2 num>=2 num>=2，则输出 Y E S YES YES,转步骤1；否则输出 N O NO NO，转步骤1.

#include
#include
#include
#include
using namespace std;
const int N=1e5+5;
int t,n,k,a[N],tree[N],head[N],to[N*2],cnt,num,xorall=0;
bool vis[N];
vectornxt(N<<1,0);
void X_OR(int x,int pre)
{
    tree[x]=a[x];
    for(int i=head[x];i;i=nxt[i])
    {
        int &nod=to[i];
        if(nod==pre) continue;
        X_OR(nod,x);
        tree[x]^=tree[nod];
    }
    if(tree[x]==xorall) num++,tree[x]=0;
    return;
}
inline void addedge(int u,int v)
{
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
    return;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        memset(head,0,sizeof head);
        nxt.push_back(0);
        cnt=num=xorall=0;
        for(int i=1;i<=n;i++) scanf("%d",a+i),xorall^=a[i];
        for(int i=1;i1) printf("YESn");
        else printf("NOn");
    }
    return 0;
}

在比赛中拿到这个题时我本来打算用并查集做的后来发现并不行，然后就白白的浪费了时间；在比赛结束后，我试着开普通数组做这道题，结果ac了但耗费了600多ms,后来才发现memset函数非常耗时！！！ 一般对于 1 0 5 ∼ 1 0 6 10^5sim10^6 105∼106这种长度的数组使用 m e m s e t memset memset函数时，耗时已经非常可观了，为此我思考了一下，决定取消每次对链式前向星的 t o to to数组使用该函数，然后把 n x t nxt nxt数组改成了 v e c t o r vector vector，这才把时间降到不到300ms。至于 h e a d head head数组我没想好怎么改，如果有大神能指点的话感激不尽。