UOJ Logo insilent的博客

博客

#关于16. 【NOI2014】起床困难综合症

2018-01-04 03:16:06 By insilent

时间复杂度大概为n*log m

这个好像能直接看别人代码啊


直接用位运算 其实我百度了


知之为知之,不知百度之;

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,a[100005],b[100005],f[35],ans,tot;
int cal(int x)//根据记录的门的种类进行位运算
{
    for(int i=1;i<=n;i++)
        if(a[i]==1)
            x=(x&b[i]);
        else 
            if(a[i]==2)
                x=(x|b[i]);
            else 
                x=(x^b[i]);
    return x;
}
int main()
{
    cin>>n;
    cin>>m;
    for(int i=1;i<=n;i++)
    {
        char s[5];
        scanf("%s",s);
        if(s[0]=='A')//记录门的种类
            a[i]=1;
        else 
            if(s[0]=='O')
                a[i]=2;
            else 
                a[i]=3;
        scanf("%d",&b[i]);
    }
    int t=cal(0);
    for(int i=0;i<=30;i++)
        f[i]=(cal(1<<i)&(1<<i));
      for(int i=30;i>=0;i--)
    {
        if((1<<i)&t)ans+=(1<<i);
        else if((tot+(1<<i)<=m)&&f[i])
        {
            tot+=f[i];
            ans+=f[i];
        }
    }
    printf("%d",ans);
    return 0;
}

评论

poorpool
代码是AC后才能看见的orzzz
NaCl
发表这一评论的目的在于,试验能否在评论区中 使 == 用 --- Markdown。
NaCl
发表这一评论的目的在于,试验能否在评论区中 - 使 - 用 - Markdown。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。