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 , 1805 阅读
不能多说,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.
Avatar_small
Punjab 10th Board Bl 说:
2021年10月23日 14:20

Punjab School Education Board has issued the PSEB 10th Model Paper 2022. Candidates can practise by downloading pdf files of past year exam papers from the Punjab board for class X. Aspirants will learn about the question paper by solving them, Punjab 10th Board Blueprint 2022 including the marking structure, types of questions asked, exam time, and so on. The PSEB Class 10th Exam 2022 will take place from 2022. (tentative). For more information on PSEB 10th 2022 Model Paper, read the article.

Avatar_small
Bushra 说:
2022年12月27日 21:17

Very interesting blog. Alot of blogs I see these days don't really provide anything that I'm interested in, but I'm most definately interested in this one. Just thought that I would post and let you know. magic mushrooms near me

Avatar_small
Bushra 说:
2022年12月28日 23:12

Great article Lot's of information to Read...Great Man Keep Posting and update to People..Thanks Scrap Car Removal Services

Avatar_small
SAAD 说:
2022年12月29日 01:19

I love the way you write and share your niche! Very interesting and different! Keep it coming! Pest control Newmarket

Avatar_small
Bushra 说:
2022年12月30日 00:01

I recently found many useful information in your website especially this blog page. Among the lots of comments on your articles. Thanks for sharing. Kumkum Bhagya

Avatar_small
Bushra 说:
2022年12月31日 15:17

What a fantabulous post this has been. Never seen this kind of useful post. I am grateful to you and expect more number of posts like these. Thank you very much. modular vault room

Avatar_small
10thmodelquestionpap 说:
2023年5月20日 23:02

professional writers who have come together for dedicated news coverage of latest happenings around the country (India). Our team comprises of professional writers & citizen journalists with diverse 10thmodelquestionpaper.in range of interest in Journalism who are passionate about publishing the Education Updates with transparency in general public interest is a initiative of professional writers


登录 *


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