2017.2.18[codevs3311][bzoj3668]NOI2014D1T1起床困难综合症-白红宇

2017.2.18[codevs3311][bzoj3668]NOI2014D1T1起床困难综合症

阅读量：5047 次

发布时间：2019-06-12

本文共 1612 字，大约阅读时间需要 5 分钟。

体面就不贴了

暴力：

1）O(nm)枚举

2）中间有AND 0，直接跳过前面的，从这之后开始

3）操作种类全一样，根据交换律，预处理即可

期望得分60，实际得分50，原因是数据说好的m>=2然而事实上第一个点m=0……

正解：

第一次提交：想着所有的运算都有结合律……光荣WA烂……

正确思路：

1.该位取0时经过n次操作结果取1 这自然是最理想的情况必须选择0

2.情况1不满足该为取1时经过n次操作结果取1 且取1后值不超过m 这样我们也选择1

3.上两种情况不满足则该位取0一定比取1小更不容易超过m

第二次提交：60分

第三次提交：70分

第四次提交：100分

AC总时间耗费: 162ms

发现自己刷水题都要好久……蒟蒻

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #define N 10001010 #define M 100000001011 #define RG register12 #define inf 0x3f3f3f3f13 #define Inf 99999999999999999LL14 using namespace std;15 typedef long long LL;16 char ch[5];17 bool flag,hh[33];18 int n,m,high,ans,sum,op[N],num[N];19 inline int Max(RG const int &a,RG const int &b){ return a>b?a:b;}20 inline int gi(){21 RG int x=0;RG char c=getchar();22 while(c<'0'||c>'9') c=getchar();23 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();24 return x;25 }26 inline void suan(){27 RG int now=m;28 while(now){29 ++high;30 hh[high]=now&1;31 now>>=1;32 }33 }34 inline void work(){35 n=gi();m=gi();suan();36 for (RG int i=1;i<=n;++i){37 scanf("%s",ch+1);38 if(ch[1]=='A') op[i]=1;39 if(ch[1]=='O') op[i]=2;40 num[i]=gi();41 if(!op[i]) sum^=num[i];42 else if(op[i]<2) sum&=num[i];43 else sum|=num[i];44 }45 if(!high){46 printf("%d\n",sum);47 return;48 }49 //for (RG int i=1;i<=high;++i) cout<
             
              <
              
               =1;--i){51 ans<<=1;52 RG int now=sum>>(i-1);53 //cout<
               <<' '<
                
                 <
                 
                  >=(i-1);68 if(now&1) ++ans;69 else flag=1;70 }71 //cout<
                  <<' '<
                   
                    <