ACM入门之三-位运算课件.pptx

ACM 程序设计;2;3;4;目录;目录;7;位运算;9;10;11;12;13;14;15;16;17;#include stdio.h main() { int n1 = 15; short n2 = 15; unsigned short n3 = 15; unsigned char c = 15; n1 = 15; n2 = 15; n3 = 15; c = 6; printf( n1=%x,n2=%d,n3=%d,c=%x,c4=%d, n1,n2,n3,c,c 4); } 上面程序的输出结果是: n1=78000,n2=-32768,n3=32768,c=c0,c4=3072;19;20;#include stdio.h main() { int n1 = 15; short n2 = -15; unsigned short n3 = 0xffe0; unsigned char c = 15; n1 = n12; n2 = 3; n3 = 4; c = 3; printf( n1=%x,n2=%d,n3=%x,c=%x,n1,n2,n3,c); } 上面的程序输出结果是： n1=3,n2=-2,n3=ffe,c=1;22;位运算解决的常见问题;异或运算的妙用;HDU3782xxx定律;HDU3782xxx定律--数据样例;标准程序;求数组中出现次数超过一半的元素;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; } } ;求数组中出现次数超过一半的元素;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; ;求数组中出现次数超过一半的元素--打架法;求数组中出现次数超过一半的元素--势力法;求数组中出现次数超过一半的元素--势力法;int now=0,num=0; //now表示现在广场上面的团伙的编号，num表示当前有几个这样的人 for (int i=1;i=n;i++) { if (num==0) //如果广场上面没有人，那么就让这个人站在广场中央 { num=1; now=arr[i]; } else { if (now==arr[i]) //如果是同一伙人，加入团队 num++; else //如果不是同一伙人，同归于尽其中一个 num--; } } coutnowendl;