[BZOJ4260] Codechef REBXOR

전송 문
http://www.lydsy.com/JudgeOnline/problem.php?id=4260
제목 의 대의
주어진 시퀀스, 최대 (xl1) xor xl1+1 xor ...xr1)+(xl2 xor xl2+1 xor ...xr2)
해제
xor 는 교환 율 을 지원 하기 때문에 우 리 는 xor 접두사 와 xl1 을 유지 합 니 다. xor xl1+1 xor ...xr1 = sum [r1] xorsum [l1 - 1] 문제 가 구 (sum [r1] 로 바 뀌 었 다. xor sum[l1−1])+(sum[l2−1] xor sum [r2]) 우 리 는 예전 에 sum 매 거 진 i 를 뒤로 삽입 하여 dp [i]: [1, i] 에서 최대 또는 세그먼트 를 얻 은 다음 에 뒤에서 sum 을 새로운 Trie 에 추가 하고 l2 를 매 거 했다. 첫 번 째 구간 은 dp 값 O (1) 를 통 해 조회 하고 두 번 째 구간 은 sum [l2 - 1] 을 새로운 Trie 에 올 려 두 번 째 구간 의 최대 치 를 얻 은 다음 에 답 을 업데이트 했다.
const
  maxn=400005;
var
  x,sum,dp:array[0..maxn]of longint;
  son:array[1..2,0..maxn*31,0..1]of longint;
  i,j,k:longint;
  n,a,tail,ans:longint;
function max(a,b:longint):longint;
begin
  if a<b then exit(b) else exit(a);
end;

procedure init(kind,a:longint);
var i,tt,b:longint;
begin
  tt:=0;
  for i:=30 downto 1 do
    begin
      if (a and (1<<(i-1)))=0
      then b:=0 else b:=1;
      if son[kind,tt,b]=0
      then begin inc(tail); son[kind,tt,b]:=tail; end;
      tt:=son[kind,tt,b];
    end;
end;

function f(kind,a:longint):longint;
var i,tt,b,c,anss:longint;
begin
  tt:=0; anss:=0;
  for i:=30 downto 1 do
    begin
      if (a and (1<<(i-1)))=0
      then b:=0 else b:=1;
      c:=b xor 1;
      if son[kind,tt,c]<>0
      then begin anss:=anss+(1<<(i-1)); tt:=son[kind,tt,c]; end
      else begin tt:=son[kind,tt,b]; end;
    end;
  exit(anss);
end;

begin
  readln(n); sum[0]:=0;
  for i:=1 to n do
    begin
      read(x[i]);
      sum[i]:=sum[i-1] xor x[i];
    end;
  tail:=0;
  for i:=1 to n do
    begin
      init(1,sum[i-1]);
      dp[i]:=max(dp[i-1],f(1,sum[i]));
    end;
  tail:=0; ans:=0;
  for i:=n downto 1 do
    begin
      init(2,sum[i]);
      a:=f(2,sum[i-1]);
      ans:=max(ans,dp[i-1]+a);
    end;
  writeln(ans);
end.
Python 사용 cxOracle Oracle Oracle 데이터베이스 연결
asp. net 웹 페이지 속기 3

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage