NOI2014 Day2 废话题解 - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
NOI2014 Day1 废话题解
BZOJ3631 Squirrel

NOI2014 Day2 废话题解

Hoblovski posted @ 2014年8月07日 02:30 in Solutions with tags bzoj NOI2014 , 1159 阅读
不能多说,T1犯SB之后直接Ag滚出了...刚好差60分Au.23333333
 
T1 给定一个串S,定义Numi=|{j | S[1..j]=S[i-j+1..i],j<i-j+1}|
求Π(Numi+1).
 
考场上想到了KMP和Hash乱搞但是估计5e8会被卡掉于是果断暴力30分23333
然后被告知KMP50分,Hash乱搞写得好80分........
正解是用KMP构造一颗Fail树然后直接在Fail树上面DFS之后维护栈乱搞...
jc大爷用O(NlgN)的维护栈+二分水过简直Orzzzzzzz
恩我们构建Fail树之后直接Numi=根到该结点上面位置不大于i>>1的点计数...
然后就Ag滚出233333
 
T2 告诉你一个随机排列生成算法之后随机(?)生成一个N×M的棋盘
找一条左上右下的排序后字典序最小的简单路
 
出题人丧心病狂 卡空间卡常数大样例充满恶意还有充满恶意的随机的构造数据......
Pascal无人权直接给C++跪了”Pascal的编译器要慢一点......”
一眼贪心,选1之后1的左下右上标为禁区之后如果2不在禁区里面那么选2,这么乱搞
然后暴力直接给你卡成30分(?)...
我们考虑禁区的形状,发现任何时候我们要标记的禁区是一个矩形然后我们可以筛法??
好像有个筛法写挫了90分2333333......然后蒟蒻很逗比的用了ZKW线段树维护这个轮廓
之后就是卡常数啊卡常数压位啊压位....然后就水过去了
 
T3 给你一颗带权有根树,每个点有属性a,b,p,l.
这个点出发能够直接走到距离它不超过l的祖先,代价为a距离+b.
求每个点回到根的最小代价.
 
考场上看出来是动态凸包的算法了...介于动态凸包蒟蒻实在是太怕了,至今只写过2题.
于是我就30分滚出了,还有10分可以cdq分治实在是感觉写了不划算(写了490分还是Ag).
然后正解就是线段树套可持久化凸包简直吓尿太神了......
其实一点也不神.
其实我是傻吊,正解明明是点分治之后动态凸包.
T3题解http://hoblovski.is-programmer.com/posts/63654.html
 
T1 30分 T2 100分 T3 30分最终得分和估分一模一样233333.....
 
T1 A掉有100多人简直膝盖跪烂Orzzzzzzz...
T2 各种乱搞算法的处所,D1T2也是各种乱搞23333...
T3 事实上考场上我想到了树上cdq分治,受树上莫队的启发,不过我太弱了.
 
以下是乱搞代码
program bzoj3670;
 
type tnode=record
        n,next:longint;
     end;
     snode=record
        n,t1:longint;
     end;
  
const maxn=1000017;
      maxm=3000017;
      mo=1000000007;
 
var str:array[0..maxn] of char; 
    pre,g:array[0..maxn] of longint;
    mem:array[0..maxm] of tnode;
    s:array[0..maxn] of snode;
    n,m,top,memsize,caseno:longint;
 
procedure insnbs(u,v:longint); inline;                                          begin
inc(memsize); with mem[memsize] do begin n:=v; next:=g[u]; end; g[u]:=memsize;  end;
 
procedure init;
var i,j:longint;
begin
n:=0; while not seekeoln do begin inc(n); read(str[n]); end; readln; 
fillchar(pre,sizeof(pre),0); j:=0; pre[1]:=0; for i:=2 to n do begin
        while (j>0)and(str[j+1]<>str[i]) do j:=pre[j]; 
        inc(j,byte(str[j+1]=str[i])); pre[i]:=j;
end; fillchar(g,sizeof(g),0); memsize:=0; for i:=1 to n do insnbs(pre[i],i); 
end;
 
function dfs(u:longint):int64;
var i,j:longint;
begin
dfs:=1; top:=1; s[top].n:=u; s[top].t1:=g[u]; i:=1;
while top>0 do begin
        if s[top].t1=0 then begin
                dec(top); j:=s[top].n>>1; while s[i].n>j do dec(i);  
        end else begin
                inc(top);                       s[top].n:=mem[s[top-1].t1].n;
                s[top].t1:=g[s[top].n];         s[top-1].t1:=mem[s[top-1].t1].next;
                j:=s[top].n>>1; while s[i+1].n<=j do inc(i); dfs:=dfs*i mod mo;
        end;
end;
end;
 
begin
readln(caseno); while caseno>0 do begin dec(caseno);
        init; writeln(dfs(0));
end;
end.
program bzoj3671;
 
const maxn=25000017;
      maxr=5017;
      mask=1<<16-1;
 
var a,p:array[0..maxn] of longint;
    tr1,tc1,tr2,tc2:array[0..maxr*5] of longint;
    n,row,col,zkwr,zkwc:longint;
 
procedure init;
var i,j,k,t,pa,pb,pc,pd:longint;
begin
readln(a[0],pa,pb,pc,pd); readln(row,col,k); n:=row*col;
for i:=1 to n do a[i]:=(int64(pa)*a[i-1]*a[i-1]+int64(pb)*a[i-1]+pc)mod pd;
for i:=1 to n do begin j:=a[i]mod i+1; a[i]:=a[j]; a[j]:=i; end;
while k>0 do begin dec(k); readln(i,j); t:=a[i]; a[i]:=a[j]; a[j]:=t; end;
k:=0; for i:=1 to row do for j:=1 to col do begin inc(k); p[a[k]]:=(i<<16)or j; end;
end;
 
function flag(x,y:longint):boolean;
var i,j:longint;
begin
i:=x+zkwr; j:=col-y; while i>0 do begin if (tr1[i]>=y)or(tr2[i]>j) then exit(false); i:=i>>1; end;
i:=y+zkwc; j:=row-x; while i>0 do begin if (tc1[i]>=x)or(tc2[i]>j) then exit(false); i:=i>>1; end;
exit(true);
end;
 
procedure mark(x,y:longint);
var l,r,k:longint;
begin
l:=x+zkwr; r:=row+zkwr+1; k:=y-1; while l xor r<>1 do begin
        if (l and 1=0)and(tr1[l xor 1]<k) then tr1[l xor 1]:=k;
        if (r and 1=1)and(tr1[r xor 1]<k) then tr1[r xor 1]:=k;
        l:=l>>1; r:=r>>1;
end;
l:=y+zkwc; r:=col+zkwc+1; k:=x-1; while l xor r<>1 do begin
        if (l and 1=0)and(tc1[l xor 1]<k) then tc1[l xor 1]:=k;
        if (r and 1=1)and(tc1[r xor 1]<k) then tc1[r xor 1]:=k;
        l:=l>>1; r:=r>>1;
end;
l:=zkwr; r:=x+zkwr; k:=col-y; while l xor r<>1 do begin
        if (l and 1=0)and(tr2[l xor 1]<k) then tr2[l xor 1]:=k;
        if (r and 1=1)and(tr2[r xor 1]<k) then tr2[r xor 1]:=k;
        l:=l>>1; r:=r>>1;
end;
l:=zkwc; r:=y+zkwc; k:=row-x; while l xor r<>1 do begin
        if (l and 1=0)and(tc2[l xor 1]<k) then tc2[l xor 1]:=k;
        if (r and 1=1)and(tc2[r xor 1]<k) then tc2[r xor 1]:=k;
        l:=l>>1; r:=r>>1;
end;
end;
 
procedure work;
var i,j,k,x,y:longint;
begin fillchar(a,sizeof(a),0);
zkwr:=1; while zkwr<row+2 do zkwr:=zkwr<<1; fillchar(tr1,sizeof(tr1),0); fillchar(tr2,sizeof(tr2),0);
zkwc:=1; while zkwc<col+2 do zkwc:=zkwc<<1; fillchar(tc1,sizeof(tc1),0); fillchar(tc2,sizeof(tc2),0);
for i:=1 to n do begin x:=(p[i]>>16)and mask; y:=p[i]and mask;
        if flag(x,y) then begin inc(a[0]); a[a[0]]:=i; mark(x,y); end;
end; write(a[1]); for i:=2 to a[0] do write(' ',a[i]); writeln;
end;
 
begin
init;
work;
end.
{$INLINE ON}
program bzoj3672;

type point=record x,y:int64; end;
     tedge=record n,next:longint; end;
     pnode=^tnode;
     tnode=record
        v,e:point;
        p:longint;
        l,r:pnode;
     end;

const maxn=200017;
      maxm=200017;
      maxint=longint($3f3f3f3f);
      eps=1e-9;
      nuv:point=(x:-1;y:-1);
      nev:point=(x:0;y:0);

var g,fa,anc,q,size,sons:array[0..maxn] of longint;
    a,b,f,dr,lim:array[0..maxn] of int64;
    mem:array[0..maxm] of tedge;
    flag:array[0..maxn] of boolean;
    n,memsize,casetype,frt,rer:longint;
    treap,null:pnode;

operator <(a,b:point) c:boolean; inline; begin exit((a.x<b.x)or((a.x=b.x)and(a.y<b.y))); end;
operator -(a,b:point) c:point; inline; begin c.x:=a.x-b.x; c.y:=a.y-b.y; end;
operator *(a,b:point) c:extended; inline; begin exit(extended(a.x)*b.y-extended(b.x)*a.y); end;
operator =(a,b:point) c:boolean; inline; begin exit((a.x=b.x)and(a.y=b.y)); end;

function min(i,j:int64):int64; inline; begin if i<j then exit(i) else exit(j); end;
function max(i,j:int64):int64; inline; begin if i>j then exit(i) else exit(j); end;

function sgn(r:extended):longint; inline;                begin
if r<-eps then exit(-1); if r>eps then exit(1); exit(0); end;

procedure insnbs(u,v:longint); inline;                                          begin
inc(memsize); mem[memsize].n:=v; mem[memsize].next:=g[u];  g[u]:=memsize;       end;

procedure treap_init;                                                                           begin
new(null); with null^ do begin v.x:=-1; v.y:=-1; p:=maxint; l:=null; r:=null; end; treap:=null; end;

procedure lrot(var i:pnode); inline; var j:pnode;
begin j:=i^.r; i^.r:=j^.l; j^.l:=i; i:=j; end;

procedure rrot(var i:pnode); inline; var j:pnode;
begin j:=i^.l; i^.l:=j^.r; j^.r:=i; i:=j; end;

procedure insert(var i:pnode;j:point);
begin
if i=null then begin
        new(i); with i^ do begin
                v:=j; p:=random(maxint); e:=nev; l:=null; r:=null;
        end;
end else if j<i^.v then begin
        insert(i^.l,j); if i^.l^.p<i^.p then rrot(i);
end else begin
        insert(i^.r,j); if i^.r^.p<i^.p then lrot(i);
end;
end;

procedure delete(var i:pnode;j:point);
begin
if j=i^.v then
        if i^.l=null then i:=i^.r
        else if i^.r=null then i:=i^.l
        else if i^.l^.p<i^.r^.p then begin
                rrot(i); delete(i^.r,j);
        end else begin
                lrot(i); delete(i^.l,j);
        end
else if j<i^.v then delete(i^.l,j) else delete(i^.r,j);
end;

function prev(i:pnode;j:point):pnode; inline;
begin
prev:=null; while i<>null do
        if not(i^.v<j) then i:=i^.l
        else begin prev:=i; i:=i^.r; end;
end;

function next(i:pnode;j:point):pnode; inline;
begin
next:=null; while i<>null do
        if (i^.v<j)or(i^.v=j) then i:=i^.r
        else begin next:=i; i:=i^.l; end;
end;

procedure update(i:point);
var t1,t2:pnode;
begin
t1:=treap; t2:=next(treap,i); while t1^.v<>i do
        if i<t1^.v then t1:=t1^.l else t1:=t1^.r;
if (t2=null)or(t1=null) then t1^.e:=nev else t1^.e:=t2^.v-t1^.v;
end;

procedure addpoint(a:point);
var rp,lp,np:point;
begin
lp:=prev(treap,a)^.v; if lp=nuv then begin
        rp:=next(treap,a)^.v; while true do begin
                np:=next(treap,rp)^.v; if np=nuv then break;
                if sgn((rp-a)*(np-a))>=0 then begin
                        delete(treap,rp); rp:=np;
                end else break;
        end; insert(treap,a); update(a); exit;
end;
rp:=next(treap,a)^.v; if rp=nuv then begin
        lp:=prev(treap,a)^.v; while true do begin
                np:=prev(treap,lp)^.v; if np=nuv then break;
                if sgn((lp-a)*(np-a))<=0 then begin
                        delete(treap,lp); lp:=np;
                end else break;
        end; insert(treap,a); if lp<>nuv then update(lp); exit;
end;
if sgn((a-lp)*(rp-lp))>=0 then exit;
while true do begin
        np:=prev(treap,lp)^.v; if np=nuv then break;
        if sgn((a-lp)*(np-lp))>=0 then begin
                delete(treap,lp); lp:=np;
        end else break;
end;
while true do begin
        np:=next(treap,rp)^.v; if np=nuv then break;
        if sgn((a-rp)*(np-rp))<=0 then begin
                delete(treap,rp); rp:=np;
        end else break;
end; insert(treap,a);
update(a); update(prev(treap,a)^.v);
end;

function tanpoint(a:point):point;
var t1:pnode;
begin
tanpoint.x:=0; tanpoint.y:=0;
if treap=null then begin tanpoint.x:=maxint; exit; end;
t1:=treap; while t1<>null do begin
        if sgn(t1^.e*a)<0 then t1:=t1^.r
        else begin tanpoint:=t1^.v; t1:=t1^.l; end;
end;
end;

function centre(root:longint):longint;
var i,j,head,tail,t1,ans:longint;
begin
frt:=0; rer:=1; q[1]:=root; while frt<rer do begin
        inc(frt); head:=q[frt]; t1:=g[head];
        while t1<>0 do begin tail:=mem[t1].n;
                if not flag[tail] then begin
                        inc(rer); q[rer]:=tail;
                end; t1:=mem[t1].next;
        end; size[head]:=0; sons[head]:=0;
end; ans:=maxint; for i:=rer downto 1 do begin
        j:=q[i]; inc(size[j]); sons[fa[j]]:=max(sons[fa[j]],size[j]);
        t1:=max(sons[j],rer-size[j]); if t1<ans then begin
                ans:=t1; centre:=j;
        end; inc(size[fa[j]],size[j]);
end;
end;

procedure qsort(l,r:longint);
var i,j,k,o:longint;
begin
i:=l; j:=r; k:=q[l+random(r-l+1)];
repeat
        while lim[q[i]]>lim[k] do inc(i);
        while lim[q[j]]<lim[k] do dec(j);
        if i<=j then begin
                o:=q[i]; q[i]:=q[j]; q[j]:=o;
                inc(i); dec(j);
        end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;

procedure update(u,root:longint);
var i,j,ac,head,tail,t1:longint;
    tp:point;
begin
frt:=0; rer:=1; q[1]:=u; while frt<rer do begin
        inc(frt); head:=q[frt]; t1:=g[head];
        while t1<>0 do begin tail:=mem[t1].n;
                if not flag[tail] then begin
                        inc(rer); q[rer]:=tail;
                end; t1:=mem[t1].next;
        end;
end; qsort(1,rer); treap:=null;
ac:=0; head:=u; while head<>root do begin
        head:=fa[head]; inc(ac); anc[ac]:=head;
end; if ac>0 then begin
        j:=1; for i:=1 to rer do begin u:=q[i];
                while (j<=ac)and(dr[anc[j]]>=lim[u]) do begin
                        tp.x:=f[anc[j]]; tp.y:=dr[anc[j]]; addpoint(tp); inc(j);
                end; if j>1 then begin
                        tp.x:=a[u]; tp.y:=1; tp:=tanpoint(tp);
                        f[u]:=min(f[u],dr[u]*a[u]+b[u]+tp.x-a[u]*tp.y);
                end;
        end;
end else begin
        for i:=1 to rer do begin u:=q[i];
                if dr[root]>=lim[u] then
                        f[u]:=min(f[u],dr[u]*a[u]+b[u]+f[root]-a[u]*dr[root]);
        end;
end;
end;

procedure init;
var i,head,t1:longint;
begin
fillchar(g,sizeof(g),0); memsize:=1;
readln(n,casetype); for i:=2 to n do begin
        readln(fa[i],dr[i],a[i],b[i],lim[i]); insnbs(fa[i],i);
end; frt:=0; rer:=1; q[1]:=1; while frt<rer do begin
        inc(frt); head:=q[frt]; inc(dr[head],dr[fa[head]]);
        t1:=g[head]; while t1<>0 do begin
                inc(rer); q[rer]:=mem[t1].n; t1:=mem[t1].next;
        end; lim[head]:=dr[head]-lim[head];
end; fillchar(flag,sizeof(flag),0); fillchar(f,sizeof(f),$3f); f[1]:=0;
end;

procedure work(root:longint);
var u,t1:longint;
begin
u:=centre(root); flag[u]:=true;
if u<>root then begin
        work(root); update(u,root); work(u);
end else begin
        update(u,root); t1:=g[u]; while t1<>0 do begin
                if not flag[mem[t1].n] then work(mem[t1].n);
                t1:=mem[t1].next;
        end;
end;
end;

procedure answer; var i:longint;
begin for i:=2 to n do writeln(f[i]); end;

begin
treap_init;
init;
work(1);
answer;
end.

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter