一堆小玩意，放到一起。
题意：给定一个n个元素数列，保证有一个数\(a\)的出现次数超过\(\lfloor\frac n2 \rfloor\)，求这个数。
数据范围\(n<=3000000,a_i\le2147483647,\)时限0.5s，空间2M。
也就是说你就只开几个变量就行了。（虽然考试的时候有人拿hash玄学乱搞过了）
首先这个时间卡掉了排序，空间和数据范围卡掉了桶的做法。我们考虑利用“数\(a\)的出现次数超过\(\lfloor\frac n2 \rfloor\)”这个特性。
我们发现（反正我没发现我太弱了55555）如果两两删去两个不同的元素，最后剩下的一定是元素\(a\)。证明考虑最坏的情况，所有其他元素一起来删掉\(a\)，那么由于\(a\)的个数超过一半，一定可以删掉其他所有的元素而自身有保留元素。
于是我们就得到了一种\(O(n)\)模拟的方法，而且只需要四个\(int\)变量：\(n\)，输入的\(x\)，计数器\(cnt,ans\)。具体地，我们每次输入一个数的时候，进行如下操作：
- 如果\(cnt=0\)，则用\(x\)更新\(ans\)，将\(cnt\)设为\(1\)。
- 如果\(x\ne ans\)，则将当前计数器\(cnt-1\)。（也就是用不同的元素互相消去）
- 反之\(cnt+1\)。(也就是统计相同的元素个数)
依题意模拟即可。
scanf("%d",&n);
while(n--){
int x;scanf("%d",&x);
if(ans!=x){
if(--cnt<=0)ans=x,cnt=1;
}
else cnt++;
}
反正我觉得不会考，但是考了就考了吧。
格雷码是一个二进制数系，其中两个相邻数的二进制位只有一位不同。
给出手动构造方法：
- 翻转最低位得到下一个格雷码。
- 翻转最右边的1的左边一位得到下一个格雷码。
交替操作1，2共\(2^{k-1}\)次可得到k位的格雷码序列。举个例子，3位格雷码序列为：
\[000,001,011,010,110,111,101,100 \]注意我们说的格雷码下标是从0开始的，即\(G(0)=000,G(4)=110\)。
然后是计算法：第\(n\)位格雷码为：
\[G(n)=n \oplus \lfloor\frac n2\rfloor \]int g(int n){
return n^(n>>1);
}
然后是它的逆变换。\(n\)的二进制第\(i\)位与其格雷码\(g\)的二进制第\(i\)位的关系(最高位为\(k\))：
\[n_{k-i}=\bigoplus_{j=0}^ig_{k-j} \]int getn(int g){
int n=0;
for(;g;g>>=1)n^=g;
return n;
}