uoj2

话说这道题的官方数据还真是有点水啊。。。

细节漏打一堆还过了70。。。。

1、30分做法

暴力枚举0到m，取最大值，时间复杂度（mn），空间复杂度（n）

 1 const maxn=100000+10;
 2 var n,m,maxx,sum,i,j,tmp:longint;
 3     op:array[0..maxn] of string;
 4     t:array[0..maxn] of longint;
 5     s:string;
 6 
 7 function max(x,y:longint):longint;
 8 begin
 9   if x>y then max:=x else max:=y;
10 end;
11 
12 begin
13 readln(n,m);
14 for i:=1 to n do
15 begin
16   readln(s);
17   tmp:=pos(' ',s);
18   op[i]:=copy(s,1,tmp-1);
19   delete(s,1,tmp);
20   val(s,t[i]);
21 end;
22 maxx:=0;
23 for i:=0 to m do
24 begin
25   sum:=i;
26   for j:=1 to n do
27   if op[j]='OR' then sum:=sum or t[j]
28   else if op[j]='XOR' then sum:=sum xor t[j]
29   else sum:=sum and t[j];
30   maxx:=max(maxx,sum);
31 end;
32 writeln(maxx);
33 end.

View Code

2、100分做法

考虑到每个二进制位对答案的贡献相互独立，按位枚举0或1进行异或，贪心求最大值

时间复杂度（nlogm），空间复杂度（n）

const maxn=100000+10;
var n,m,ans,i,j,tmp:longint;
    op:array[0..maxn] of string;
    t:array[0..maxn] of longint;
    a:array[1..30] of longint;
    s,sm:string;
    st:array[0..maxn] of string;
    bool:boolean;

function max(x,y:longint):longint;
begin
  if x>y then max:=x else max:=y;
end;

procedure work1(k,c:longint);
var i,tmp:longint;
begin
  for i:=1 to n do
  begin
    if st[i,k]='1' then tmp:=1 else tmp:=0;
    if op[i]='OR' then c:=c or tmp
    else if op[i]='XOR' then c:=c xor tmp
    else c:=c and tmp;
  end;
  if c=1 then ans:=ans+a[k]
  else if sm[k]='1' then bool:=true; 
end;

function work(k,c:longint):boolean;
var i,tmp:longint;
begin
  for i:=1 to n do
  begin
    if st[i,k]='1' then tmp:=1 else tmp:=0;
    if op[i]='OR' then c:=c or tmp
    else if op[i]='XOR' then c:=c xor tmp
    else c:=c and tmp;
  end;
  if c=1 then
  begin
    ans:=ans+a[k];
    if (sm[k]='1') then bool:=true;
    work:=true;
  end
  else work:=false;
end;

begin
a[30]:=1;
for i:=29 downto 1 do a[i]:=a[i+1]*2;
readln(n,m);
for i:=30 downto 1 do
  if (m and (1<<(i-1))>0) then sm:=sm+'1' else sm:=sm+'0';
for i:=1 to n do
begin
  readln(s);
  tmp:=pos(' ',s);
  op[i]:=copy(s,1,tmp-1);
  delete(s,1,tmp);
  val(s,t[i]);
  for j:=30 downto 1 do
    if (t[i] and (1<<(j-1))>0) then st[i]:=st[i]+'1' else st[i]:=st[i]+'0';
end;
ans:=0;
bool:=false;
for i:=1 to 30 do
begin
  if work(i,0) then continue;
  if (bool)or(sm[i]='1') then work1(i,1);
end;
writeln(ans);
end.