首页 > 其他 > 详细

位运算学习笔记（20180815）

时间：2018-08-15 23:30:36      阅读：169      评论：0      收藏：0      [点我收藏+]

位运算学习笔记（20180815）

A poj 3748

?裸的位运算的题目，要么用bitset直接修改，不过to_ullong()不知道为何炸了，只能用to_ulong()

?要么用运算符操作,挂运算符操作的代码：

#include<iostream>
#include<bitset>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int main()
{
   int r,x,y;
   scanf("%x,%d,%d",&r,&x,&y);
   r=(r&(~(1<<x)));//将第x位赋值为0
   r=(r|(1<<y));//将第y位赋值为1
   r=(r|(1<<(y-1)));
   r=(r&(~(1<<(y-2))));
   printf("%x\n",r);
   return 0;
}

B hdu 3711

?新定义函数$f(a,b)$为a,b两数在二进制下不同数位的个数，给出m个a，和n次询问，询问给出数b，在a中找到一个数，使得$f(a,b)_{min}$

?计算$f(a,b)$可以直接选择用bitset暴力匹配，但更可以巧用位运算的性质：a^b可以使得位同为1，位异为0,再统计所以为1的数位即可。

#include<iostream>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<string>
#include<algorithm>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
int main()
{
    int T;
    while(~scanf("%d",&T))
    {
    while(T--)
    {
        ll a[20000],b;
        memset(a,0,sizeof(a));
        // memset(b,0,sizeof(b));  
        int m,n;
        scanf("%d %d",&m,&n);
        for(int i=0;i<m;i++)
            scanf("%lld",&a[i]);
        sort(a,a+m,greater<ll>());
        for(int i=0;i<n;i++)
        {
           scanf("%lld",&b);
           ll minn=INT_MAX,jmin=-1;
           for(int j=0;j<m;j++)
           {
               ll tmp=a[j]^b;
               bitset<1000> res(tmp);
               int t=res.count();
               if(t<=minn)
               {
                   minn=t;
                   jmin=a[j];
               }
           }
           printf("%lld\n",jmin);
        }
    }
    }
    return 0;
}

C poj 2453

?给出数I，求出大于数I的最小数m，使得m表示成二进制形式时1的个数与I的相等

?考虑极端情形：当数位只有一其余均为0的时候，最小数m只可能为I左移一位的情形。即数m的最大范围为$[m+1,2m]$。故枚举即可。

#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
typedef long long ll;
int main()
{
    ll q;
    while(~scanf("%lld",&q)&&q)
    {
        bitset<100> s(q);
        int t=s.count();
        for(int i=q+1;;i++)
        {
            bitset<100>r(i);
            if(r.count()==t)
            {
                cout<<i<<endl;
                break;
            }
        }
    }
    return 0;
}

D hdu 3006

?给出若干集合求可以组成的不同的并集的个数

?状态压缩裸题，将每个集合用二进制数位储存(bitset)并在输入过程中求并。最后统计

#include<bits/stdc++.h>
using namespace std;
int a[1<<15];
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m)&&n&&m)
    {
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)
        {
            int t;
            cin>>t;
            bitset<100>q;
            for(int i=0;i<t;i++)
            {
                int tmp;
                cin>>tmp;
                q[tmp-1]=1;
            }
        unsigned long res=q.to_ulong();
        a[res]=1;
        for(int i=0;i<(1<<m);i++)
        {
            if(a[i])
            {
                a[i|res]=1;
            }
        }
        }
        int cnt=0;
        for(int i=0;i<(1<<m);i++)
        {
            if(a[i]) cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

E poj 1573

?黑白棋问题(关灯问题),比较好想的想法是dfs，不太好想的想法是位运算

dfs:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=10;
const int INF=0x3f3f3f;
const int r[5]={-1,0,0, 0,1};
const int c[5]={ 0,1,0,-1,0};
int grid[maxn][maxn];
int ans=INF;
bool judge()
{
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(grid[i][j]!=grid[0][0]) return false;
        }
    }
    return true;
}
void flip(int x,int y)
{
    for(int i=0;i<5;i++)
    {
        if(x+r[i]>=0&&x+r[i]<4&&y+c[i]>=0&&y+c[i]<4)
        grid[x+r[i]][y+c[i]]=!grid[x+r[i]][y+c[i]];
    }
}

void dfs(int x,int y,int t)
{
    if(judge())
    {
        ans=min(ans,t);
        return ;
    }
    if(x>3||y>3||x<0||y<0) return ;
    int nx=(x+1)%4;
    int ny=y+(x+1)/4;
    dfs(nx,ny,t);
    flip(x,y);
    dfs(nx,ny,t+1);
    flip(x,y);
    return ;
}
int main()
{
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            char tmp;
            cin>>tmp;
            grid[i][j]=(tmp==‘b‘)?0:1;
        }
    }
    dfs(0,0,0);
    if(ans==INF) cout<<"Impossible\n";
    else cout<<ans<<endl;
    return 0;
}

位运算：

#include<cstdio>
#include<cstdlib>
using namespace std;
int ans=999999;
int mi[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
void search(int x,int f,int st)/*x表当前第几位，f表棋盘状态，st代表翻转次数*/
{
    if((f==65535)or(f==0))
{
    if(st<ans) ans=st;
    return;
}
    if(x==17) return;
    if(st>=ans) return;
    search(x+1,f,st);
    f^=(1<<((17-x)-1));//改变自己
    if(x%4!=0) f^=(1<<((17-x-1)-1));//改变右边的
    if(x%4!=1) f^=(1<<((17-x+1)-1));//改变左边的
    if(x>4) f^=(1<<((17-x+4)-1));//改变上面的
    if(x<=12) f^=(1<<((17-x-4)-1));//改变下面的
    search(x+1,f,st+1);
    }
int main()
{
    int s=0;
    for(int i=1;i<=4;i++)
    {
    for(int j=1;j<=4;j++)
    {
    char ch;
    scanf("%c",&ch);
    if(ch==‘b‘) s+=mi[16-4*i+4-j];/*把矩阵变成一个数，第i位为1代表第(i/4)行第(i%4)（0代表4）列是Black;*/
    }
    scanf("\n");
    }
    search(1,s,0);
    if (ans==999999) printf("Impossible\n");
    else printf("%d\n",ans);
    return 0;
}

F hdu 1429

bfs+位运算

注意C++11结构体的新语法

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<bitset>
#include<stack>
#include<map>
#include<set>
using namespace std;
int n,m,t;
struct node
{
    int x,y,t,k;
};
char Map[22][22];
bool vis[22][22][1030];
int dx[]={-1,0,0,1};
int dy[]={0,-1,1,0};
queue<node>Ac;
inline void init()
{
    while(Ac.size()) Ac.pop();
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>Map[i][j];
            if(Map[i][j]==‘@‘)
            {
                Ac.push(node{i,j,0,0});
                vis[i][j][0]=1;
            }
        }
        if(i!=n-1) getchar();
    }
}


inline void bfs()
{
    node now;
    while(Ac.size())
    {
        now=Ac.front();
        Ac.pop();
        if(Map[now.x][now.y]==‘^‘&&now.t<t)
        {
            cout<<now.t<<endl;
            return ;
        }
        for(int i=0;i<4;i++)
        {
            int tx=now.x+dx[i];
            int ty=now.y+dy[i];
            if(tx<0||ty<0||tx>=n||ty>=m||Map[tx][ty]==‘*‘||vis[tx][ty][now.k]) continue;
            if(isupper(Map[tx][ty])&&!(now.k&1<<(Map[tx][ty]-‘A‘))) continue;
            int k=now.k;
            if(islower(Map[tx][ty]))
            {
                k=now.k|(1<<(Map[tx][ty]-‘a‘));
            }
            if(!vis[tx][ty][k])
            {
                vis[tx][ty][k]=1;
                Ac.push(node{tx,ty,now.t+1,k});
            }
        }
    }
    puts("-1");
}



int main()
{
    while(~scanf("%d%d%d\n",&n,&m,&t))
    {
        init();
        bfs();
    }
    return 0;
}

G Hdu 2533

八皇后问题，回溯打表或者位运算都要写熟

#include<bits/stdc++.h>
using namespace std;
int a[100],n,ans;
void dfs(int depth)
{
    if(depth==n)
    {
        ans++;
        return ;
    }
    else
    {
    for(int i=0;i<n;i++)
    {
        a[depth]=i;
        bool flag=true;
        for(int j=0;j<depth;j++)
        {
            if(a[j]==a[depth]||j-a[j]==depth-a[depth]||j+a[j]==depth+a[depth])
            {
                flag=false;
                break;
            }
        }
        if(flag) dfs(depth+1);
    }
    }
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        memset(a,0,sizeof(a));
        ans=0;
        dfs(0);
        cout<<ans<<endl;
    }
    return 0;
}

位运算：

#include<bits/stdc++.h>
using namespace std;
int lim,sum;
void dfs(int row,int left,int right)
{
    if(row==lim)
    {
        sum++;
        return ;
    }
    else
    {
        int pos,p;
        pos=lim&(~(row|left|right));
        while(pos!=0)
        {
            p=pos&-pos;
            pos=pos-p;
            dfs(row+p,(left+p)<<1,(right+p)>>1);
        }
    }
}
int main()
{
    int n;
    while(~scanf("%d",&n)&&n)
    {
        sum=0;
        lim=(1<<n)-1;
        dfs(0,0,0);
        cout<<sum<<endl;
    }
    return 0;
}

总结：

知识点与方法：

1.各种取位技巧，四种基本位运算(与或非异或)

2.快速幂

3.状态压缩与其在dp、搜索中的应用

4.lowbit运算，GCC内置函数

5.bitset的应用

---恢复内容结束---

# 位运算学习笔记（20180815）

A poj 3748

?裸的位运算的题目，要么用bitset直接修改，不过to_ullong()不知道为何炸了，只能用to_ulong()

?要么用运算符操作,挂运算符操作的代码：

#include<iostream>
#include<bitset>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int main()
{
   int r,x,y;
   scanf("%x,%d,%d",&r,&x,&y);
   r=(r&(~(1<<x)));//将第x位赋值为0
   r=(r|(1<<y));//将第y位赋值为1
   r=(r|(1<<(y-1)));
   r=(r&(~(1<<(y-2))));
   printf("%x\n",r);
   return 0;
}

B hdu 3711

?新定义函数$f(a,b)$为a,b两数在二进制下不同数位的个数，给出m个a，和n次询问，询问给出数b，在a中找到一个数，使得$f(a,b)_{min}$

?计算$f(a,b)$可以直接选择用bitset暴力匹配，但更可以巧用位运算的性质：a^b可以使得位同为1，位异为0,再统计所以为1的数位即可。

#include<iostream>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<string>
#include<algorithm>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
int main()
{
    int T;
    while(~scanf("%d",&T))
    {
    while(T--)
    {
        ll a[20000],b;
        memset(a,0,sizeof(a));
        // memset(b,0,sizeof(b));  
        int m,n;
        scanf("%d %d",&m,&n);
        for(int i=0;i<m;i++)
            scanf("%lld",&a[i]);
        sort(a,a+m,greater<ll>());
        for(int i=0;i<n;i++)
        {
           scanf("%lld",&b);
           ll minn=INT_MAX,jmin=-1;
           for(int j=0;j<m;j++)
           {
               ll tmp=a[j]^b;
               bitset<1000> res(tmp);
               int t=res.count();
               if(t<=minn)
               {
                   minn=t;
                   jmin=a[j];
               }
           }
           printf("%lld\n",jmin);
        }
    }
    }
    return 0;
}

C poj 2453

?给出数I，求出大于数I的最小数m，使得m表示成二进制形式时1的个数与I的相等

?考虑极端情形：当数位只有一其余均为0的时候，最小数m只可能为I左移一位的情形。即数m的最大范围为$[m+1,2m]$。故枚举即可。

#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
typedef long long ll;
int main()
{
    ll q;
    while(~scanf("%lld",&q)&&q)
    {
        bitset<100> s(q);
        int t=s.count();
        for(int i=q+1;;i++)
        {
            bitset<100>r(i);
            if(r.count()==t)
            {
                cout<<i<<endl;
                break;
            }
        }
    }
    return 0;
}

D hdu 3006

?给出若干集合求可以组成的不同的并集的个数

?状态压缩裸题，将每个集合用二进制数位储存(bitset)并在输入过程中求并。最后统计

#include<bits/stdc++.h>
using namespace std;
int a[1<<15];
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m)&&n&&m)
    {
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)
        {
            int t;
            cin>>t;
            bitset<100>q;
            for(int i=0;i<t;i++)
            {
                int tmp;
                cin>>tmp;
                q[tmp-1]=1;
            }
        unsigned long res=q.to_ulong();
        a[res]=1;
        for(int i=0;i<(1<<m);i++)
        {
            if(a[i])
            {
                a[i|res]=1;
            }
        }
        }
        int cnt=0;
        for(int i=0;i<(1<<m);i++)
        {
            if(a[i]) cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

E poj 1573

?黑白棋问题(关灯问题),比较好想的想法是dfs，不太好想的想法是位运算

dfs:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=10;
const int INF=0x3f3f3f;
const int r[5]={-1,0,0, 0,1};
const int c[5]={ 0,1,0,-1,0};
int grid[maxn][maxn];
int ans=INF;
bool judge()
{
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(grid[i][j]!=grid[0][0]) return false;
        }
    }
    return true;
}
void flip(int x,int y)
{
    for(int i=0;i<5;i++)
    {
        if(x+r[i]>=0&&x+r[i]<4&&y+c[i]>=0&&y+c[i]<4)
        grid[x+r[i]][y+c[i]]=!grid[x+r[i]][y+c[i]];
    }
}

void dfs(int x,int y,int t)
{
    if(judge())
    {
        ans=min(ans,t);
        return ;
    }
    if(x>3||y>3||x<0||y<0) return ;
    int nx=(x+1)%4;
    int ny=y+(x+1)/4;
    dfs(nx,ny,t);
    flip(x,y);
    dfs(nx,ny,t+1);
    flip(x,y);
    return ;
}
int main()
{
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            char tmp;
            cin>>tmp;
            grid[i][j]=(tmp==‘b‘)?0:1;
        }
    }
    dfs(0,0,0);
    if(ans==INF) cout<<"Impossible\n";
    else cout<<ans<<endl;
    return 0;
}

位运算：

#include<cstdio>
#include<cstdlib>
using namespace std;
int ans=999999;
int mi[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
void search(int x,int f,int st)/*x表当前第几位，f表棋盘状态，st代表翻转次数*/
{
    if((f==65535)or(f==0))
{
    if(st<ans) ans=st;
    return;
}
    if(x==17) return;
    if(st>=ans) return;
    search(x+1,f,st);
    f^=(1<<((17-x)-1));//改变自己
    if(x%4!=0) f^=(1<<((17-x-1)-1));//改变右边的
    if(x%4!=1) f^=(1<<((17-x+1)-1));//改变左边的
    if(x>4) f^=(1<<((17-x+4)-1));//改变上面的
    if(x<=12) f^=(1<<((17-x-4)-1));//改变下面的
    search(x+1,f,st+1);
    }
int main()
{
    int s=0;
    for(int i=1;i<=4;i++)
    {
    for(int j=1;j<=4;j++)
    {
    char ch;
    scanf("%c",&ch);
    if(ch==‘b‘) s+=mi[16-4*i+4-j];/*把矩阵变成一个数，第i位为1代表第(i/4)行第(i%4)（0代表4）列是Black;*/
    }
    scanf("\n");
    }
    search(1,s,0);
    if (ans==999999) printf("Impossible\n");
    else printf("%d\n",ans);
    return 0;
}

F hdu 1429

bfs+位运算

注意C++11结构体的新语法

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<bitset>
#include<stack>
#include<map>
#include<set>
using namespace std;
int n,m,t;
struct node
{
    int x,y,t,k;
};
char Map[22][22];
bool vis[22][22][1030];
int dx[]={-1,0,0,1};
int dy[]={0,-1,1,0};
queue<node>Ac;
inline void init()
{
    while(Ac.size()) Ac.pop();
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>Map[i][j];
            if(Map[i][j]==‘@‘)
            {
                Ac.push(node{i,j,0,0});
                vis[i][j][0]=1;
            }
        }
        if(i!=n-1) getchar();
    }
}


inline void bfs()
{
    node now;
    while(Ac.size())
    {
        now=Ac.front();
        Ac.pop();
        if(Map[now.x][now.y]==‘^‘&&now.t<t)
        {
            cout<<now.t<<endl;
            return ;
        }
        for(int i=0;i<4;i++)
        {
            int tx=now.x+dx[i];
            int ty=now.y+dy[i];
            if(tx<0||ty<0||tx>=n||ty>=m||Map[tx][ty]==‘*‘||vis[tx][ty][now.k]) continue;
            if(isupper(Map[tx][ty])&&!(now.k&1<<(Map[tx][ty]-‘A‘))) continue;
            int k=now.k;
            if(islower(Map[tx][ty]))
            {
                k=now.k|(1<<(Map[tx][ty]-‘a‘));
            }
            if(!vis[tx][ty][k])
            {
                vis[tx][ty][k]=1;
                Ac.push(node{tx,ty,now.t+1,k});
            }
        }
    }
    puts("-1");
}



int main()
{
    while(~scanf("%d%d%d\n",&n,&m,&t))
    {
        init();
        bfs();
    }
    return 0;
}

G Hdu 2533

八皇后问题，回溯打表或者位运算都要写熟

#include<bits/stdc++.h>
using namespace std;
int a[100],n,ans;
void dfs(int depth)
{
    if(depth==n)
    {
        ans++;
        return ;
    }
    else
    {
    for(int i=0;i<n;i++)
    {
        a[depth]=i;
        bool flag=true;
        for(int j=0;j<depth;j++)
        {
            if(a[j]==a[depth]||j-a[j]==depth-a[depth]||j+a[j]==depth+a[depth])
            {
                flag=false;
                break;
            }
        }
        if(flag) dfs(depth+1);
    }
    }
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        memset(a,0,sizeof(a));
        ans=0;
        dfs(0);
        cout<<ans<<endl;
    }
    return 0;
}

位运算：

#include<bits/stdc++.h>
using namespace std;
int lim,sum;
void dfs(int row,int left,int right)
{
    if(row==lim)
    {
        sum++;
        return ;
    }
    else
    {
        int pos,p;
        pos=lim&(~(row|left|right));
        while(pos!=0)
        {
            p=pos&-pos;
            pos=pos-p;
            dfs(row+p,(left+p)<<1,(right+p)>>1);
        }
    }
}
int main()
{
    int n;
    while(~scanf("%d",&n)&&n)
    {
        sum=0;
        lim=(1<<n)-1;
        dfs(0,0,0);
        cout<<sum<<endl;
    }
    return 0;
}

总结：

知识点与方法：

1.各种取位技巧，四种基本位运算(与或非异或)

2.快速幂

3.状态压缩与其在dp、搜索中的应用

4.lowbit运算，GCC内置函数

5.bitset的应用

位运算学习笔记（20180815）

原文：https://www.cnblogs.com/wongdark2017/p/9484606.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！