NOI2014 Day1 废话题解

program bzoj3668;
 
const maxd=31;
 
var op:array[0..maxd] of longint;
    n,m:longint;
 
function max(i,j:longint):longint; begin if i>j then exit(i) else exit(j); end;
function trans(i,j:longint):longint; begin case j of 2:exit(i); 3:exit(i xor 1); else exit(j); end; end;
 
function getop(var i:longint):longint;
var ch:char;
begin
read(ch); case ch of 'A':getop:=1; 'O':getop:=2; 'X':getop:=3; end;  while ch<>' ' do read(ch); readln(i);
end;
 
procedure init;
var i,j,k:longint;
begin
filldword(op,length(op),2); readln(n,m); for i:=1 to n do case getop(j) of
        1:for k:=0 to 31 do if j>>k and 1=0 then op[k]:=0;
        2:for k:=0 to 31 do if j>>k and 1=1 then op[k]:=1;
        3:for k:=0 to 31 do if j>>k and 1=1 then op[k]:=op[k]xor 1;
end;
end;
 
function f(n:longint):longint;
var i:longint;
begin
f:=0;
for i:=0 to n do f:=f or(max(trans(0,op[i]),trans(1,op[i]))<<i);
if n>-2 then f:=f or(trans(0,op[n+1])<<(n+1)); for i:=n+2 to maxd do f:=f or(trans((m>>i)and 1,op[i])<<i);
end;
 
function dp:longint;
var i:longint;
begin
dp:=f(-2); for i:=0 to maxd do if m>>i and 1=1 then dp:=max(dp,f(i-1));
end;
 
begin
init;
writeln(dp);
end.

{$INLINE ON}
program bzoj3669;
 
const maxn=50017;
      maxm=100017;
      maxint=longint($3f3f3f3f);
 
var e:array[0..maxm,1..4] of longint;
    e1:array[0..maxm,1..3] of longint;
    p,p0:array[0..maxn] of longint;
    n,m,m1,mw1,mw2:longint;
 
function min(i,j:longint):longint; inline; begin if i<j then exit(i) else exit(j); end;
function max(i,j:longint):longint; inline; begin if i>j then exit(i) else exit(j); end;
 
function find(u:longint):longint;                            begin
if p[u]<0 then exit(u); p[u]:=find(p[u]); exit(p[u]);        end;
 
procedure union(u,v:longint);                                                                        begin
if p[u]<p[v] then begin inc(p[u],p[v]); p[v]:=u; end else begin inc(p[v],p[u]); p[u]:=v; end;        end;
 
procedure qsort1(l,r:longint);
var i,j,k,o:longint;
begin
i:=l; j:=r; k:=e[l+random(r-l+1),3];
repeat
        while e[i,3]<k do inc(i);
        while e[j,3]>k do dec(j);
        if i<=j then begin
                o:=e[i,1]; e[i,1]:=e[j,1]; e[j,1]:=o;
                o:=e[i,2]; e[i,2]:=e[j,2]; e[j,2]:=o;
                o:=e[i,3]; e[i,3]:=e[j,3]; e[j,3]:=o;
                o:=e[i,4]; e[i,4]:=e[j,4]; e[j,4]:=o;
                inc(i); dec(j); 
        end;
until i>j;
if i<r then qsort1(i,r);
if j>l then qsort1(l,j);
end;
 
procedure qsort2(l,r:longint);
var i,j,k,o:longint;
begin
i:=l; j:=r; k:=e1[l+random(r-l+1),3];
repeat
        while e1[i,3]<k do inc(i);
        while e1[j,3]>k do dec(j);
        if i<=j then begin
                o:=e1[i,1]; e1[i,1]:=e1[j,1]; e1[j,1]:=o;
                o:=e1[i,2]; e1[i,2]:=e1[j,2]; e1[j,2]:=o;
                o:=e1[i,3]; e1[i,3]:=e1[j,3]; e1[j,3]:=o;
                inc(i); dec(j); 
        end;
until i>j;
if i<r then qsort2(i,r);
if j>l then qsort2(l,j);
end;
 
function con(l1,l2:longint):boolean;
var i,u,v:longint;
begin
fillchar(p,sizeof(p),$ff); for i:=1 to m do if e[i][3]>l1 then break else if e[i][4]<=l2 then begin
        u:=find(e[i][1]); v:=find(e[i][2]); if u<>v then union(u,v); if find(1)=find(n) then exit(true);
end; exit(false);
end;
 
function getl2(l1,l,r:longint):longint;
var i,mid,u,v:longint;
begin
if not con(l1,r) then exit(maxint); fillchar(p,sizeof(p),$ff); fillchar(p0,sizeof(p0),$ff); m1:=0;
for i:=1 to m do if e[i][3]>l1 then break else if e[i][4]<=r then begin
        inc(m1); move(e[i],e1[m1],8); e1[m1][3]:=e[i][4];
end; qsort2(1,m1); l:=1; r:=m1; while l<>r do begin
        mid:=(l+r)>>1; for i:=l to mid do begin
                u:=find(e1[i][1]); v:=find(e1[i][2]); if u<>v then union(u,v); 
        end; if find(1)=find(n) then begin p:=p0; r:=mid; end else begin p0:=p; l:=mid+1; end;
end; exit(e1[l][3]); 
end;
 
procedure init;
var i,j,k:longint;
begin
readln(n,m); mw1:=0; mw2:=0; for i:=1 to m do begin
        readln(e[i,1],e[i,2],e[i,3],e[i,4]); mw1:=max(mw1,e[i][3]); mw2:=max(mw2,e[i][4]);
end; qsort1(1,m);
end;
                                         
function ans:longint;
var l1,l2,l,r,mid:longint;
begin
if not con(mw1,mw2) then exit(-1); 
ans:=maxint; l:=1; r:=mw1; while l<>r do begin
        mid:=(l+r)>>1; if con(mid,mw2) then r:=mid else l:=mid+1; 
end; l1:=l; l2:=mw2; while l1<=mw1 do begin
        l2:=getl2(l1,1,l2); ans:=min(ans,l1+l2); 
        l:=l1; r:=mw1; while l<>r do begin
                mid:=(l+r)>>1+1; if getl2(mid,1,l2)=l2 then l:=mid else r:=mid-1; 
        end; l1:=l+1;
end;
end;
 
begin
init;
writeln(ans);
end.