ACM入门之三-位运算全解.ppt

位运算解决的常见问题 1.判断二进制下第i位是否是1 2.把二进制下第i位变为1 or 0 3.求一个数字二进制下有多少个1 异或运算的妙用 xor运算通常用于对二进制的特定一位进行取反操作，因为异或可以这样定义：0和1异或0都不变，异或1则取反。? xor运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即(a?xor?b)?xor?b?=?a。 xor运算可以用于简单的加密，比如我想对我MM说1314520，但怕别人知道，于是双方约定拿我的生为密钥。1314520?xor=我就 诉MM。MM再次计xor值，得到1314520，于是她就明白了我的意思。 求数组中出现次数超过一半的元素 求数组中出现次数超过一半的元素-循环法 for (int i=1;i=n;i++) { int num=0; for (int j=1;j=n;j++) if (arr[i]==arr[j]) num++; if (numn/2) { coutarr[i]endl; break; } } 求数组中出现次数超过一半的元素 求数组中出现次数超过一半的元素-Map法 mapint,int vis; for (int i=1;i=n;i++) { vis[arr[i]]++; //vis保存的是每一个数字出现的次数， vis[5]=6表示5出现了6次 if (vis[arr[i]]n/2) { coutarr[i]endl; break; } } 求数组中出现次数超过一半的元素 求数组中出现次数超过一半的元素-中位数法 sort(arr+1,arr+n+1); coutarr[(n+1)/2]; 求数组中出现次数超过一半的元素 求数组中出现次数超过一半的元素-二进制法 int num[33]; for (int i=1;i=n;i++) { int now=1; for (int k=0;k31;k++,now=now*2) //枚举1，2，4，8，... if ((nowarr[i])0) num[k]++; //位运算的操作，对这两个数字做与操作， //例如，arr[i]是1101，now是8也就是1000，那么他俩与之后的结果就是1000 //如果，arr[i]是1101，now是2也就是0010，那么他俩与之后的结果就是0000 //换句话说，如果二进制下对应那一位是0，与出来的结果就是0，否则则是一个大于0的数字 } int now=1,ans=0; for (int k=0;k31;k++,now=now*2) if (num[k]n/2) ans+=now; coutansendl; 求数组中出现次数超过一半的元素--打架法 求数组中出现次数超过一半的元素--势力法 1）势力5的一个人走进广场中央，现在广场中央有一个人，势力是5 2）势力1的一个人走进广场中央，他发现广场中央有一个势力是5的人，于是同归于尽，现在广场上没有人 3）势力5的一个人走进广场中央，现在广场中央有一个人，势力是5 4）势力4的一个人走进广场中央，他发现广场中央有一个势力是5的人，于是同归于尽，现在广场上没有人 5）势力1的一个人走进广场中央，现在广场有一个人，势力是1 6）势力1的一个人走进广场中央，现在广场有两个人，势力是2 …… 求数组中出现次数超过一半的元素--势力法 可以发现，每一次火拼，势力最大（也就是出现次数最多的那个数字）的那个每次最多只会死亡一个。而火拼最多会进行N/2次，出现频率最高的那个数字最多只会损失N/2个，而题上告诉我们出现次数已经超过了一半，因此广场上剩下的那个团伙的编号必然是出现次数做多的那个！这样一来，代码就非常好写了。 求数组中出现次数超过一半的元素-势力法 int now=0,num=0; //now表示现在广场上面的团伙的编号，num表示当前有几个这样的人 for (int i=1;i=n;i++) { if (num==0) //如果广场上