0x01位运算例题

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;
}
上一篇:字符串哈希


下一篇:【NOI P模拟赛】大阶乘(斯特林数)