6.1.3.pas

usacoCHAPTER6程序,非常恶心的动态规划转移方程,位运算等等

{
ID:LXYXYNT3
PROB:cowxor
LANG:PASCAL
}
const
  inf='cowxor.in';
  ouf='cowxor.out';
  maxn=100000;

var
  a:array[1..4300000] of boolean;
  b:array[0..maxn] of longint;
  s,t,nn,i,j,m,n,p,q:longint;

begin
  assign(input,inf);reset(input);
  assign(output,ouf);rewrite(output);
  readln(n);
  b[0]:=0;
  for i:=1 to n do
  begin
    readln(m);
    b[i]:=b[i-1] xor m;
  end;
  nn:=b[1];
  fillchar(a,sizeof(a),false);
  s:=1;t:=1;
  for i:=1 to n do
  begin
    p:=1;
    for j:=1 to 21 do
     if a[(p shl 1+((b[i] shr (21-j)) and 1) xor 1)] then p:=p shl 1+((b[i] shr (21-j)) and 1) xor 1
                                                     else p:=p shl 1+(b[i] shr (21-j)) and 1;
    if b[i] xor (p xor (1 shl 21))>nn then
    begin
      nn:=b[i] xor (p xor (1 shl 21));
      t:=i;
    end;
    p:=b[i]+1 shl 21;
    for j:=21 downto 1 do
    begin
      a[p]:=true;
      p:=p shr 1;
    end;
  end;
  for s:=t downto 1 do
   if b[s-1] xor b[t]=nn then break;
  writeln(nn,' ',s,' ',t);
  close(input);
  close(output);
end.