bzoj3668 [Noi2014]起床困难综合症——贪心

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3668

一开始想着倒序推回去看看这一位能不能达到来着，因为这样好中途退出(以为不这样会T)；

没想到正着的0和1可能出现一样的结果...

这是WA代码：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int const maxn=1e5+;

int n,m,t[maxn],ans,cnt[],op[maxn],c;

char ch[];

int cal(int x)

{

    memset(cnt,,sizeof cnt);

    int ret=;

    while(x)cnt[++ret]=x%,x/=;

    return ret;

}

int main()

{

    scanf("%d%d",&n,&m);

    int mx=;

    for(int i=;i<=n;i++)

    {

        scanf("%s%d",&ch,&t[i]);

        if(ch[]=='A')op[i]=;//&

        if(ch[]=='O')op[i]=;//|

        if(ch[]=='X')op[i]=;//^

        mx=max(mx,t[i]);

    }

    int k=cal(mx);

    for(int i=k;i;i--)

    {

//        if(ans+(1<<(i-1))>m)continue;

        bool flag=;int nw=;

        for(int j=n;j;j--)

        {

            cal(t[j]);

            if(op[j]==&&nw==&&cnt[i]==){flag=;break;}

            if(op[j]==&&nw==&&cnt[i]==){flag=;break;}

            if(op[j]==)nw^=cnt[i];

        }

        if(!flag)

        {

            if(nw==)ans+=(<<(i-));

            else if(c+(<<(i-))<=m)c+=(<<(i-)),ans+=(<<(i-));

        }

    }

    printf("%d",ans);

    return ;

}

囧

而且 i 不是从 mx 的最高位开始而是从 m 的最高位开始的...

也不用中途退出什么的，因为位数没有那么大；

可以先用0得到一个 ans 作为底线，然后看看能不能通过某些位上放1让答案更大。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int const maxn=1e5+;

int n,m,t[maxn],ans,cnt[],op[maxn],c;

char ch[];

int cal(int x)

{

    memset(cnt,,sizeof cnt);

    int ret=;

    while(x)cnt[++ret]=x%,x/=;

    return ret;

}

int main()

{

    scanf("%d%d",&n,&m);

    int mx=;

    for(int i=;i<=n;i++)

    {

        scanf("%s%d",&ch,&t[i]);

        if(ch[]=='A')op[i]=,ans&=t[i];//&

        if(ch[]=='O')op[i]=,ans|=t[i];//|

        if(ch[]=='X')op[i]=,ans^=t[i];//^

    }//得到输入0后的ans

    int k=cal(m);k--;

    for(int i=k;i>=;i--)

    {

        int tmp=(<<i);

        if(tmp>m||(ans&(<<i)))continue;

        for(int j=;j<=n;j++)

        {

            if(op[j]==)tmp&=t[j];

            if(op[j]==)tmp|=t[j];

            if(op[j]==)tmp^=t[j];

        }

        if(tmp&(<<i))ans|=(<<i),m-=(<<i);

    }

    printf("%d",ans);

    return ;

}