2
总所周知,计算机的存储方式是许多许多的0和1,也就是二进制,那么这也决定了2这个数字的重要地位。
2进制
数数时把逢十进一改变成逢二进一那么它就成了二进制,鉴于二进制的特殊性(每一位只有0和1),我们可以用它来做很多事情,比如说状态压缩。
位运算
在二进制下的运算称为位运算,C++下主要的位运算符有以下
>> //在二进制下把所有位向右移,每移一位相当于除以2
<< //在二进制下把所有位向左移,每移一位相当于乘以2
& //按位与
| //按位或
^ //按位异或
~ //按位取反
这些运算符给了我们很大的运用空间,第一个作用是…卡常?
好像位运算会比直接加减乘除要快,因此会在各种dalao的代码中见到如下表达式。
l+r>>1 <=> (l+r)/2
(n<<1)+(n<<3) <=> 10*n
n<<1|1 <=> 2*n+1
a^1 <=> a%2?--a:++a
a&1 <=> a%2?1:0
~a&1 <=> a%2?0:1
~a <=> a!=-1
// ...
这种东西自己慢慢总结就好。
而它更重要的作用在于直接对二进制位的操作
x^=y^=x^=y //swap(x,y)自己yy一下就好
x>>1 //去掉最后一个1
x<<1 //在最后加上一个0
x<<1|1 //在最后加上一个1
x|1 //最后一位变成1
(x|1)^1 //最后一位变成0
x^1 //最后一位取反
x|(1<<i-1) //右数第i位变成1
x&(!(1<<i-1)) //右数第i位变成0
x&((1<<i)-1) //取末i位
x^(1<<i-1) //右数第i位取反
(x<<i-1)&1 //取右数第i位
x|((1<<i)-1) //把末i位全部变成1
x^((1<<i)-1) //末i位取反
x&(x+1) //把右边连续的1变成0
x|(x+1) //把右起的第一个0变成1
x|(x-1) //把右边连续的0变成1
(x^(x+1))>>1 //取右边连续的1
x&(x^(x-1)) //去掉右起第一个1的左边,当然也可以写成x&-x,它就是lowbit啊
这样的话我们就可以用一个二进制数来干很多奇奇怪怪的事情了,这便是状态压缩所依赖的基础啊_(:зゝ∠)_
二分与倍增的思想
说到2,当然自然而然地也会想到二分与倍增。
二分不用多说,主要就有两个东西,二分查找和二分答案。它的基本思想就是通过均匀分割区间使查找时的剪枝最优。
二分所能解决的问题一定要有单调性,否则它将失去正确性。
倍增,简单地理解就是先把每一段区间所对应的子问题先求出来,再通过区间的拼凑来回答询问。
它基于所有的的数互相拼凑可以拼凑出所有的整数
比如说: 线段树,归并排序,ST表,都有一点倍增的感觉。
而倍增最经典的应用自然是在路径上跳了吧。
首先可以预处理出离每个点的点是谁,接着再从大到小贪心地找,简单来说就是能跳多远跳多远。这个能,指的是不能超过目标,因为再往回跳浪费时间。
LCA也算是这个应用的一部分吧。
二分与二进制的关系
这是一个非常妙的思想。 这里以一道题目来阐述这个思想。
题意:给定n个数,求任意两个数按位异或/按位或/按位与的最大值。
对于异或来说,我们可以直接上字典树对吧。
而对于按位与/按位或,其中一种做法是贪心地从高位往低位凑。
不过我这里有一个奇妙的算法。
首先字符集不大,我们先把所有的数放到一个桶中,然后我们…二分！
要使或/与的值最大,那么我们从高位往低位贪心地过程中限制了某些位置一定为1。
我们考虑换一下之前那个桶的定义,设:
那么考虑在第i位时,一个数x如果被一个数y包含,那么要么是y在i这一位比x多了1,要么是这一位相同而在更高的位不同。
因此我们二分的时候可以理解为除以2,这样右边的就是更高位,左边就是低位,直接把右边的数加到左边就可以了,然后我们就可以愉悦地贪心了。
int f[1<<20],a[100005],n;
void init(int l,int r){
if(l==r) return;
int m=l+r>>1;
init(l,m),init(m+1,r);
for(int i=0;i<=m-l;++i) f[i+l]+=f[i+m+1];
}
inline void work(){
memset(f,0,sizeof(f));
for(int i=1;i<=n;++i) ++f[a[i]];
init(0,(1<<20)-1);
int ans=-1;
for(int i=1,cur,res;i<=n;++i){
cur=res=0;
for(int d=19;d>-1;--d){
if(c==3){//or
if(!((a[i]>>d))&1){//如果这一位是0就去凑1
cur+=(1<<d);
if(f[cur]) res+=(1<<d);
else cur-=(1<<d);
}else res+=(1<<d);
}else{//and
if((a[i]>>d)&1){//如果这一位是1才有可能增大答案
cur+=(1<<d);
if(f[cur]>1) res+=(1<<d);
else cur-=(1<<d);
}
}
}
ans=max(ans,res);
}
printf("%d\n",ans);
}
Summary
2这个数字还有着无穷的潜力等着去发掘啊。