锐客网

  1. 首页 > it技术 > >

[AtCoder|[AtCoder Grand Contest 035]

A. XOR Circle
题意：
给定 n ( n < = 1 0 5 ) n(n< =10^5) n(n<=105)个数字 a [ 1 ] a[1] a[1]~ a [ n ] a[n] a[n]，询问是否能够将其重排成一个首位相接的环形数组，使得每个 a [ i ] ( 1 < = i < = n ) a[i](1< =i< =n) a[i](1<=i<=n)等于与其相邻的两个数字的异或和。
题解：
很显然重排后数组满足以下形式
a [ i ] a[i] a[i] ^a [ i + 1 ] a[i+1] a[i+1] ^a [ i + 2 ] a[i+2] a[i+2] =0 0 0
a [ i + 1 ] a[i+1] a[i+1] ^a [ i + 2 ] a[i+2] a[i+2] ^a [ i + 3 ] a[i+3] a[i+3] =0 0 0
所以 a [ i ] a[i] a[i]等于 a [ i + 3 ] a[i+3] a[i+3]
先讨论数组全零的情况，这个情况肯定有解；
对于剩下的情况，很显然，如果n不是3的倍数的话，必然无解。
那么我们分2类讨论：
当整个数组只有2种数字的时候，那么一定是 N / 3 N/3 N/3个 0 0 0和 2 ? N / 3 2*N/3 2?N/3个其他数字，否则一定不行。
当整个数字只有3种数字 x , y , z x,y,z x,y,z的时候，那么一定是这三种数字的数量相同，并且 x x x ^y y y ^z z z =0 0 0，否则不行。
然后其他情况都不行。

#include #define ll long long using namespace std; int n,a[100004]; settr; mapmert; int main(){ scanf("%d",&n); for(int i=1; i<=n; i++)scanf("%d",&a[i]); for(int i=1; i<=n; i++){ tr.insert(a[i]); } if(tr.size()==1 && (*tr.begin())==0){ return puts("Yes"),0; } if(tr.size()==2){ if(n%3!=0)return puts("No"),0; mert.clear(); int x=-1; for(int i=1; i<=n; i++){ mert[a[i]]++; if(a[i]!=0)x=a[i]; } if(mert[0]==n/3&&mert[x]==n*2/3){ return puts("Yes"),0; } else return puts("No"),0; } if(tr.size()==3){ if(n%3!=0)return puts("No"),0; mert.clear(); for(int i=1; i<=n; i++){ mert[a[i]]++; } int p=0; for(int x:tr){ if(mert[x]!=n/3)return puts("No"),0; p^=x; } if(p)return puts("No"),0; else return puts("Yes"),0; } return puts("No"),0; return 0; }

B.Even Degrees
题意：
给定一个 n n n个点 m m m条边的无向图，要求给每条边重定向，使得每个点的出度都是偶数。
题解：
这是个很迷的构造方法…
首先 m m m如果是奇数，那么一定不行。
你先随便从一个点开始dfs，然后从搜索树的所有的叶子节点 x x x开始，对于所有 x x x连出的边（除了连向自己父亲的边），如果这条边的终点的深度小于 x x x，那么将这条边对应的无向边的起点设为 x x x；然后对于 x x x在搜索树中的父亲节点 f a fa fa，根据当前 x x x的出度来调整边 < f a , x > < fa,x> 方向。
正确性：
对于你做完的每个点来说，他的出度已经确定了，而他的所有除了根节点以外的祖先都有至少一次的调整出度的机会，而根节点的出度已经被保证了，因为总出度 s u m sum sum确定（为偶数），除了根节点以外所有点的出度已经确定，他们都是偶数，那么他们的和s u su su 也是偶数，那么显然根节点出度 s u m ? s u sum-su sum?su也为偶数。
#include #define ll long long #define pa pair using namespace std; int n,m; int cu[200004]; int dir[200004],dep[200004]; vectorG[200004]; vectorans; void dfs(int x,int fa){ for(int i=0; i

C.Skolem XOR Tree
题意：
给定一个 n n n，然后你构建一个点数为 2 n 2n 2n的树，编号为 i i i和 n + i n+i n+i的点的权值是 i i i，然后这个树满足，对于任意 i i i， i i i到 n + i n+i n+i的路径上的点的权值的异或和等于 i i i
题解：
首先对于 n n n为 2 2 2的幂的情况无解。
【[AtCoder|[AtCoder Grand Contest 035]】然后对于 n > = 3 n> =3 n>=3切n为奇数的情况，
由于对于任何偶数 x x x， x x x^ 1 1 1= x + 1 = x+1 =x+1 同时( x + 1 ) (x+1) (x+1)^ 1 1 1 = x = x =x
那么就把连续的奇偶数字放在一起挂在节点 1 1 1上。
[AtCoder|[AtCoder Grand Contest 035]
文章图片
对于偶数的情况，我们先按照奇数来做，最后剩 n n n和 2 ? n 2*n 2?n，然后你需要找两个数字 a , b a,b a,b使得 a a a ^1 1 1 ^b b b =n n n 然后把 n n n连在与节点 1 1 1直接相连的，权值为 a a a的点上，把 2 ? n 2*n 2?n连在与节点 1 1 1直接相连的，权值为 b b b的点上即可。
#include #define ll long long #define pa pair using namespace std; vectorans; settr; int n; void output(){ for(int i=0; i

    推荐阅读


    上一篇：HTML|HTML中font 和 span标签有什么区别

    下一篇：HTML|HTML 用Table布局商城首页