P1469找筷子dgdger

乍听起来好像不难，桶是一个好东西，可是一看数据：对于100%的数据，N<=10000001，筷子长度不大于10^9。

桶直接就淘汰掉了。

但是其实我第一次A用的却是桶，直接上代码：

#include#include#include#includeusingnamespacestd;intn,t,a[10000010];intmain(){scanf("%d",&n);for(inti=0;i0){printf("%d\n",i);//如果在遍历桶的时候找到了那根落单的筷子就直接输出。break;}}return0;}靠的是一股巧劲儿。

直到我做完这题不久后，我得知了一个神奇的东西：^异或符号

0^0=0,0^1=10异或任何数＝任何数

1^0=1,1^1=01异或任何数－任何数取反

任何数异或自己＝把自己置0

异或运算符的特点是：数a偶数次异或同一个数b（例如：a=a^b^b）仍然为原值a。

所以我们只要在输入的时候一直异或，就可以得到落单的那跟筷子的长度（我刚知道的时候像发现了新大陆一样）。

代码如下：

#include#includeusingnamespacestd;intn,m,ans=0;intmain(){scanf("%d",&n);//输入一共有几根筷子for(inti=0;i