【bzoj3668】[Noi2014]起床困难综合症

2015.07.10 10:25 Fri | 36次阅读 | 旧日oi | 固定链接 | 源码

题目大意

求1个[0,m]的数,使得经过opt x[i](i=1~n,opt=and,or,xor)之后得到的数最大。m<=10^9,n<=10^5

题解

嗯,又是一道水题是吧,每一位都是独立的,所以我们从高到低枚举每一位是0或者1,看经过操作后的的值是什么,然后加起来就行了。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char s[5];
int n,m,x[100005],op[100005],ans;
int main()
{
    //freopen("sleep.in", "r", stdin);
    //freopen("sleep.out", "w", stdout);
    cin>>n>>m;
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        scanf("%s%d",s,&x[i]);
        if(s[0]=='A') op[i]=1;
        else if(s[0]=='O') op[i]=2;
        else op[i]=3;
    }
    for(i=30;i>=0;i--)
    {
        k=0;
        for(j=1;j<=n;j++)
        {
            if(op[j]==1) k&=(x[j]&(1<<i));
            else if(op[j]==2) k|=(x[j]&(1<<i));
            else k^=(x[j]&(1<<i));
        }
        if(k) ans+=k;
        else if((1<<i)<=m)
        {
            k=1<<i;
            for(j=1;j<=n;j++)
            {
                if(op[j]==1) k&=(x[j]&(1<<i));
                else if(op[j]==2) k|=(x[j]&(1<<i));
                else k^=(x[j]&(1<<i));
            }
            if(k) ans+=k,m-=(1<<i);
        }
    }
    cout<<ans<<endl;
}```