首页 > 代码库 > BZOJ 3668:起床困难综合症(贪心)

BZOJ 3668:起床困难综合症(贪心)

分析:按位贪心即可。

技术分享
program sleep;
var
  a,g:array[0..150000]of longint;
  n,i,m,ans,t,len,x,y,v:longint;
  c:char; s:string; e:boolean;
function cheak(x,y:longint):longint;
var i:longint;
begin
  for i:=1 to n do
   begin
     if g[i]=1 then x:=x and (a[i] shr (y-1) and 1);
     if g[i]=2 then x:=x or (a[i]  shr (y-1) and 1);
     if g[i]=3 then x:=x xor (a[i] shr (y-1) and 1);
   end;
  exit(x);
end;
begin
   assign(input,sleep.in);
reset(input);
assign(output,sleep.out);
rewrite(output);
  readln(n,m);
  for i:=1 to n do
   begin
     readln(s); t:=pos( ,s); c:=s[1];
     if c=A then g[i]:=1;
     if c=O then g[i]:=2;
     if c=X then g[i]:=3;
     val(copy(s,t+1,length(s)-t),a[i]);
   end;
   ans:=0; e:=false;
   for i:=30 downto 1 do
    begin
      if cheak(0,i)=1 then begin x:=0; y:=1; end
       else if cheak(1,i)=1 then
        begin
          if (e=false)and(m shr (i-1)=0) then begin x:=0; y:=0; end
                else begin x:=1; y:=1; end;
        end
      else begin x:=0; y:=0; end;
      v:=v+x*(1 shl (i-1));
      ans:=ans+y*(1 shl (i-1));
      if v<m shr (i-1) then e:=true;
    end;
   writeln(ans);
   close(input); close(output);
end.
View Code

 

BZOJ 3668:起床困难综合症(贪心)