一、二进制基础
计算:主要有与&,或|,异或^等。
&:两者均为1则1,否则为0
|:两者均为0则0,否则为1
^:两者相同即为0,否则为1
部分重要计算:
1.判断数字x二进制第i位是否等于1
if(((1<<(i?1))&x)>0)
解释:将1左移i-1位,即1在第i位上,将其与x进行与运算判断是否大于0即判断是否为12.将数字x二进制第i位改成1
x=x|(1<<(i?1))
解释:得到第i位的1,将其或运算3.将数字x二进制最右边的第一个1去掉
x=x&(x?1)
例如:集合中,二进制1010101即表示选取
引例:
“......提壶去打酒,遇店加一倍,遇花喝一斗。”
一共遇到5次店,10次花,酒正好喝完,求遇到酒和花的次数的组合可能数。
long long solve(){int ans = 0;for(int i = 0;i < (1<<14); i++) {int tot_1 = 0;int tot_0 = 0;int num = 2;for (int j = 0; j < 14; j++) {if (i&(1<<j)) { // 判断i从右数第j+1位是否为1tot_1++;num = num*2;}else {tot_0++;num = num - 1;}}if(tot_1 == 5 && tot_0 == 9 && num == 1) {++ans;}}return ans;
}
二进制枚举
要求实现:在N个数字中找不重复的数字,通过加法凑成X的方案数。
long long solve(int a[],int N,int X) {int ans = 0;for(int i = 0; i < (1<<N);i++) {int num = 0;for(int j = 0; j < N; j++) {if(i&(1<<j)) {num+=a[j];}}if(num == X) ans++;}return ans;
}
状压DP:
在元素规模相对较小(20)且要表示每个元素取或者不取的时候,可以使用。
TSP问题(NP-完全):