0x01.基本算法 — 位运算

声明：
本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记，主要是因为我三本都买了 按照《算法竞赛进阶指南》的目录顺序学习，包含书中的少部分重要知识点、例题解题报告及我个人的学习心得和对该算法的补充拓展，仅用于学习交流和复习，无任何商业用途。博客中部分内容来源于书本和网络（我尽量减少书中引用），由我个人整理总结（习题和代码可全都是我自己敲哒）部分内容由我个人编写而成，如果想要有更好的学习体验或者希望学习到更全面的知识，请于京东搜索购买正版图书：《算法竞赛进阶指南》——作者李煜东，强烈安利，好书不火系列，谢谢配合。

---

下方链接为学习笔记目录链接（中转站）

学习笔记目录链接

---

ACM-ICPC在线模板

一、位运算

m位二进制，通常最低位为第0位

二、memset函数

memset函数，memset(a,val,sizeof a);将val填充到a 的每个字节上，所以如果a是一个long long型的指针，不能写sizeof a，而应该写(n+1)*8（long long是8个字节）。其中memset只能赋值出“每8位都相同”的int。

综上所述，0x7f7f7f7f是memset函数所能初始化的最大数值，但是一般我们经常初始化最大值的时候，用memset(a,0x3f,sizeof a)来给数组赋值0x3f3f3f3f的值。

三、移位运算

$1<<n=2^n$
$n<<1=2n$
$n>>1=floor(n/2.0)$ —>除以2向下取整
“整数/2”在C++中是“除以2向零取整”

四、二进制状态压缩

注意下表的第k位都是从第0位开始的

这个表格对应下面的状压DP例题

对，没错，还是我写的

五、成对变换

六、lowbit

lowbit定义为非负整数n在二进制表示下“最低位的1及其后边的所有0”构成的数值，例如$n=10=(1010{)}_2$，则$lowbit(n)=2=(10{)}_2$
x&(-x)
lowbit配合hash可以找出整数二进制表示下的所有的是1 的位数。

const int N=1<<20; int H[N+1]; for(int i=0;i<=20;i++) H[1<<i]=i; while(cin>>n) { 
     while(n>0){ 
     cout<<H[n&-n]<<" "; n-=n&-n; } cout<<endl; } 

七、相关习题

0.AcWing 26. 二进制中1的个数

class Solution { 
      public: int NumberOf1(int n) { 
      int res = 0; while (n) { 
      n -= n & -n; res += 1; } return res; } }; 

1.Acwing 89. a^b（快速幂）

#include  
        using namespace std; using ll = long long; const int maxn = 1e5 + 6; int n, m, s, t; int ai[maxn]; int a, b, p; ll qpow(int a, int b, int mod) { 
       ll res = 1; while(b) { 
       if(b & 1) res = 1ll * res * a % mod; a = 1ll * a * a % mod; b >>= 1; } return res % mod; } int main() { 
       scanf("%d%d%d", &a, &b, &p); cout << qpow(a, b, p) << endl; return 0; } 

2.AcWing 90. 64位整数乘法 （快速乘）

#include 
         #define ls (p<<1) #define rs (p<<1|1) //#define mid (l+r)/2 #define over(i,s,t) for(register long long i=s;i<=t;++i) #define lver(i,t,s) for(register long long i=t;i>=s;--i) //#define int __int128 using namespace std; typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A const ll N=1e5+7; const ll mod=1e9+7; const double EPS=1e-10;//-10次方约等于趋近为0 inline ll qmul(ll x,ll y,ll p) { 
        ll z=(long double)x/p*y; ll res=(unsigned long long)x*y-(unsigned long long)z*p; return (res+p)%p; } ll a,b,c; int main() { 
        scanf("%lld%lld%lld",&a,&b,&c); printf("%lld\n",qmul(a,b,c)); return 0; } 

3.AcWing 91. 最短Hamilton路径（状压DP）

状压DP一个明显的特征，行或列一定是一个大一个小，那么把小的那一维，用一个数转换成二进制数来表示这一维上的状态。

这道题就是很经典很明显就是要用状态压缩动态规划。

那么这道题中对于任意一个点 $j$ 来说，只能是从所有没有走过 $j$ 点的状态转移过来的。这点非常重要。然后考虑转移方程。本题中暴力会T，而问题中的数据范围仅有20 ，所以可以经过状态压缩来求解。用$1<<n$这样一个二进制数表示当前问题的状态。如走过点0，1，4的话当前的状态就是10011，表示走过0，1，4三点，即状态的第n位为1，那么第n点就已经走过了。

直接枚举这个二进制串，2^20把所有的可能情况都枚举一遍，因为对于每一个点来说都只有1或者0即走过或者没走过。那么枚举每一个状态i，并枚举每一个点j。对于点j来说，若状态i的第j位为1，那么当前的状态就可以由所有未经过j点的状态中的任意一点k到达。所以就可以开始转移。还需再判断一下，若当前状态i中k是走过的，那么j就可以由k经过由k走向j的这一条路转移过来（任意点都可以相互走动）。

那么枚举每一个状态i，并枚举每一个点j。对于点j来说，若状态i的第j位为1，那么当前的状态就可以由所有未经过j点的状态中的任意一点k到达。所以就可以开始转移。还需再判断一下，若当前状态i中k是走过的，那么j就可以由k经过由k走向j的这一条路转移过来。

转移方程：

$f[state][j]=f[stat{e}_k][k]+weight[k][j]$，其中state表示当前的状态，state_k表示state去掉j点后k的状态。

当前的状态在j点的时候的最短路就等于从状态的第k点转移到j点加上从k走到j所走的路程，取整个过程中的最小值即可

最后答案为$f[(1<<n)-1][n-1]$表示状态为$1<<n)-1$，且当前在n-1这个点上。因为题目中是从0到n-1的，其中状态$1<<n)-1$的二进制串，如果n=10那么这个二进制串是：00——后面10个1代表0~9这10个点都走完了（因为1<

#include 
           #define ls (p<<1) #define rs (p<<1|1) //#define mid (l+r)/2 #define over(i,s,t) for(register long long i=s;i<=t;++i) #define lver(i,t,s) for(register long long i=t;i>=s;--i) //#define int __int128 using namespace std; typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A const ll N=1e5+7; const ll mod=1e9+7; const double EPS=1e-10;//-10次方约等于趋近为0 ll n,m; ll f[1<<20][20]; ll weight[20][20]; int main() { 
          scanf("%lld",&n); over(i,0,n-1)over(j,0,n-1) scanf("%lld",&weight[i][j]); memset(f,0x3f,sizeof f);//要求取最小值所以都初始化为最大值 f[1][0]=0;//起点第0点走过了，最短距离为0 for(int i=1;i<(1<<n);++i) for(int j=0;j<n;++j) //必须先判断一下状态i的第 j 位==1（也就是 j 点走过了） if((i>>j)&1)//因为第j点的状态是由没有走过 j 点的状态转移过来的,所以更新的是走过j点的数组 for(int k=0;k<n;++k)//枚举所有能走到j 点的点 if(((i^(1<<j))>>k)&1)//如果当前的状态i 去掉j点之后的状态，走过k点的话就可以转移了//因为是从k走到j点的嘛 f[i][j]=min(f[i][j],f[i^(1<<j)][k]+weight[k][j]);//把i中的j去掉，必须是从未走过j点的状态转移到走过j点的状态+从k走到j的路程 printf("%lld\n",f[(1<<n)-1][n-1]); return 0; } 

4.AcWing 998. 起床困难综合症（位运算）

位运算优化 $O(logm\ast m)$

二进制位运算最大的特点在于每次计算之后没有进位与借位，每一位计算的时候都是独立计算

根据独立计算可得，我们可以确定攻击的二进制的每一位，自然而然就确定答案的每一位了

如何确定攻击的每一位填1还是填0

填1必须满足：

• 该位为1了以后总和不能大于最大的攻击力（不能超限）
• 填1了之后运算过后答案的二进制位上还是1

其余情况填1也会变成0，否则就大于了m，还不如填0有效（填0可能经过多次运算变成1，使得答案更大）

#include 
              #define ls (p<<1) #define rs (p<<1|1) //#define mid (l+r)/2 #define over(i,s,t) for(register long long i=s;i<=t;++i) #define lver(i,t,s) for(register long long i=t;i>=s;--i) //#define int __int128 using namespace std; typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A const ll N=1e5+7; const ll mod=1e9+7; const double EPS=1e-10;//-10次方约等于趋近为0 pair<string,int>a[N]; ll n,m; ll calc(ll bit,ll now)//计算当前第bit位的数now经过变换后的数 { 
             for(int i=1;i<=n;++i){ 
             ll x=(a[i].second>>bit)&1;//看这个数的第bit位是否为1 if(a[i].first=="AND")now&=x; else if(a[i].first=="OR")now|=x; else now^=x; } return now; } int main() { 
             cin>>n>>m; over(i,1,n) { 
             char str[5]; ll tmp; scanf("%s%lld",str,&tmp); a[i]=make_pair(str,tmp); } ll val=0,ans=0; for(int bit=29;bit>=0;bit--)//第29~第0位,因为2^29>m { 
             ll res0=calc(bit,0);//取0 ll res1=calc(bit,1);//取1 /* if(val+(1< 
            
              res0)//第bit位可以取1且取1经过变换还是1 val+=(1< 
              
              //lyd专门给我发邮件说这道题的标程写错啦（好吧是我subscribe了他的github） 
              //原程序贪心策略有问题，应该改成下面的程序: 
              if 
              (res0 
              == 
              1 
              )ans 
              += res0 
              <<bit 
              ; 
              //确实这个应该放在前边，因为0能得1肯定比1得1优，所以应该先判断0的结果。 
              else 
              { 
                
              if 
              (val 
              += 
              ( 
              1 
              <<bit 
              ) 
              <= m 
              && res1 
              == 
              1 
              ) val 
              += 
              1 
              <<bit 
              ,ans 
              += res1 
              <<bit 
              ; 
              } 
              } 
              printf 
              ( 
              "%lld\n" 
              ,ans 
              ) 
              ; 
              return 
              0 
              ; 
              } 
              
            

拓展练习

1.luoguP4310 绝世好题

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！$(\grave{•}\omega \acute{•})✧$