a^b（AcWing89）
题目链接：a^b
涉及到快速幂的应用，详情见0x01位运算
AC代码：
点击查看代码
# include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL qmi(LL a,LL b,LL p)
{
LL res=1;
while(b)
{
if(b&1) res=(res%p*a%p)%p;
a=a%p*a%p;
b>>=1;
}
return res%p;
}
int main()
{
LL a,b,p;
cin>>a>>b>>p;
cout<<qmi(a,b,p)<<endl;
return 0;
}
64位整数乘法（AcWing 90）
题目链接：64位整数乘法
涉及龟速乘，即把一个数展开为2^i的和，然后将每一项都与另一个数相乘，总和即为最终结果
本题我是将b展开，每一项与a相乘然后相加，不能用一个数来储存2^i,因为这个数与a相乘可能会溢出，即使这两个数都不大于p
AC代码：
点击查看代码
# include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
int main()
{
ULL a,b,p;
ULL i=1;
ULL res=0;
cin>>a>>b>>p;
while(b)
{
if(b&1) res=(res+a%p)%p;
a=a*2%p;
b>>=1;
}
cout<<res<<endl;
}
最短Hamilton路径 （AcWing 91）
题目链接：最短Hamilton路径
Hamilton路径是指从第一个点到最后一个点并经过每一个点的路径
本题是利用二进制的状态压缩，用一个整数（即数组的第一维）来储存状态，如果m>>k&1==1就说明现在储存的路径f[m][i]经过了k这个点，即使i!=k;
AC代码：
点击查看代码
# include<bits/stdc++.h>
using namespace std;
const int N=20,M=1<<N;
int p[N][N],f[M][N];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>p[i][j];
memset(f,0x3f,sizeof f);
f[1][0]=0;
for(int i=1;i<(1<<n);i++)
for(int j=0;j<n;j++)
if((i>>j)&1)
for(int k=0;k<n;k++)
if(i-(1<<j)>>k&1)
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+p[k][j]);
cout<<f[(1<<n)-1][n-1]<<endl;
}
起床困难综合症（AcWing 998）
题目链接：起床困难综合症
本题是按位运算的一个典型，我们只需要对整数的32位（0~31位）从高位到低位进行枚举，使用这一位对每一扇门的防御力的对应位进行op操作，然后找到使这一位op操作的结果做大的值，对对应位赋值即可。
本题我用c代表可以使最终攻击力最大的初始攻击力，用res代表最大的最终攻击力，每一次枚举c的位时，要求是在不影响更高位且c<=m的前提下对c的这一位进行赋值。
但是令我倍感疑惑的是用long long都过不了这一题，即使数据范围仅为1e9；
AC代码：
点击查看代码
# include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=1e5+10;
string op[N],str[3]={"AND","OR","XOR"};
ULL p[N];
ULL n,m;
int main()
{
ULL res=0,c=0;
ULL a=0;
cin>>n>>m;
for(int i=0;i<n;i++) cin>>op[i]>>p[i];
for(int i=31;i>=0;i--)
{
int ant=0,t;
for(int k=0;k<2;k++)
{
t=k;
for(int j=0;j<n;j++)
{
if(op[j]==str[0]) t&=p[j]>>i&1;
if(op[j]==str[1]) t|=p[j]>>i&1;
if(op[j]==str[2]) t^=p[j]>>i&1;
}
if(t>ant)
{
ant=k;
break;
}
}
if(c+ant*(1<<i)<=m)
{
c+=ant*(1<<i);
res+=t*(1<<i);
}
}
cout<<res<<endl;
}