比赛T1T2

T1

不难看出,就是给你一串数和初始数,初始数对于每一个数异或两次

最精彩的就是,异或同一个数两次,还是同一个数(惊不惊喜)

其实二进制也就1和0

所以每一位的情况也就四种

0^1^1=0

1^0^0=1

0^0^0=0

1^1^1=1

所以最终的答案输出初始数即可

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
    char s[1000010];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%s",s);
    scanf("%s",s);
    printf("%s",s);
    return 0;
}

T2

这道题我们求得书上异或路径,所以也可以运用上一道题的知识

因为两个数相同异或指为0

所以我们只需要搜索一遍,然后记录路上的路径异或值,然后求两点的距离的时候,我们将两个点的值异或即可(也就是两点一直向上,总会到一个点使得两点都会搜索到,这点就是最近公共祖先,而两点之间的距离必定经过最近公共祖先且不会再经过他的祖先,异或可以消去这一部分)

比赛T1T2

 

 绿色异或,会抵消黄色部分,剩下即是路径异或值(下面的含有链式前向星)

#include<bits/stdc++.h>
using namespace std;
int head[200010],to[200010],vl[200010],nxt[200010],cnt;
void add(int u,int v,int w)
{
    cnt++;
    to[cnt]=v;
    vl[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
bool s[100010];
int d[100010];
void dfs(int u,int v)
{
    s[u]=1,d[u]=v;
    for(int i=head[u];i;i=nxt[i])
        if(!s[to[i]])dfs(to[i],v^vl[i]);
}
int main()
{
    int n,m,u,v,w;
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0);
    while(m--)
    {
        scanf("%d%d",&u,&v);
        printf("%d\n",d[u]^d[v]);
    } 
    return 0;
} 

 

上一篇:C. The Tag Game(Educational Codeforces Round 22)


下一篇:并查集