BZOJ3668 NOI2014 起床困难综合症题解&代码_起床困难综合症代码-CSDN博客

本文链接：https://blog.csdn.net/Rainbow6174/article/details/50858493

本文介绍了一道看似无法解决的问题的O(n)解法，通过位运算和按位枚举的方法来找到最优解。文章提供了详细的算法思路及C++实现代码。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

本题看起来完全不可做…实际上是O(n)的。
冬令营虽然挂了233333但是前一天的练手题倒是秒出…至于题解这么晚…大概是因为我今天比较闲得蛋疼…
最开始虽说选择的范围是m，但是考虑到关于攻击力的所有运算都是位运算，那么大胆猜想按位枚举出m…猜对了
按位非0即1枚举出m的情况，存入ans[]
然后由高位向低位暴力选就行辣…注意即使数字稍小一点了也不要让选出的数大于m，用flag记录当前数是否等于m即可

/**************************************************************
    Problem: 3668
    User: Rainbow6174
    Language: C++
    Result: Accepted
    Time:736 ms
    Memory:2052 kb
****************************************************************/

#include<iostream>
#include<stdio.h>
using namespace std;
const int maxn=100005;
const int maxnum=(int)((1LL<<31)-1);
char s[5];
int n,m,flag,Ans,op[maxn],t[maxn],ans[32][2];
int change(int s,int bit,int x)
{
    if(op[x]==1)
        s&=(t[x]&(1<<bit))?1:0;
    if(op[x]==2)s|=(t[x]&(1<<bit))?1:0;
    if(op[x]==3)//s^=t[x];
        s^=(t[x]&(1<<bit))?1:0;
    return s;
}
int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%s%d",s,&t[i]);
        if(s[0]=='A')op[i]=1;
        if(s[0]=='O')op[i]=2;
        if(s[0]=='X')op[i]=3;
    }
    for(int i=30;i>=0;i--)
    {
        int t0=0,t1=1;
        for(int j=0;j<n;j++)
        {
            t0=change(t0,i,j);
            t1=change(t1,i,j);
        }
        ans[i][0]=t0;
        ans[i][1]=t1;
    }
    for(int i=30;i>=0;i--)
    {
        if(m&(1<<i))
            if(ans[i][1]>ans[i][0])Ans|=1<<i;
            else flag=1,Ans|=ans[i][0]<<i;
        else if(flag)Ans|=max(ans[i][1],ans[i][0])<<i;
                else Ans|=ans[i][0]<<i;
    }
    printf("%d\n",Ans);
    return 0;
}