# OJ记录（11.4.8）

1.神题A+B problem（代码最短奖）

/************************************************************** Problem: 1000 User: ImSB Language: Pascal Result: Accepted Time:0 ms Memory:244 kb ****************************************************************/ var a,b:byte;begin read(a,b);write(a+b)end.

2.

3.

## [FJOI2007]轮状病毒

f[i]=f[i-1]*2+g[i-1];g[i]=f[i-1]+g[i-1];

(f为i这个点所在的联通块没有和根相连，g反之)。

4.

## [ZJOI2006]物流运输

dp，一开始竟然想状态压缩去了，惭愧。。。

5.

## [HNOI2008]Cards

/************************************************************** Problem: 1004 User: ImSB Language: Pascal Result: Accepted Time:30 ms Memory:252 kb ****************************************************************/ program h84; var f:array[-20..20,-20..20] of longint; a:array[0..60] of longint; o:array[0..60] of boolean; n,i,j,t,m,mo,s1,s2,s3,ans:longint; procedure work;var i,j,k:longint; begin fillchar(o,sizeof(o),0); fillchar(f,sizeof(f),0); f[0,0]:=1; for i:=1 to n do if not o[i] then begin j:=i;t:=0; while not o[j] do begin o[j]:=true;j:=a[j];inc(t); end; if t>20 then exit; for j:=s1 downto 0 do for k:=s2 downto 0 do f[j,k]:=(f[j,k]+f[j-t,k]+f[j,k-t]) mod mo; end; ans:=(ans+f[s1,s2]) mod mo; end; begin readln(s1,s2,s3,m,mo); n:=s1+s2+s3; for i:=1 to m do begin for j:=1 to n do read(a[j]); work; end; for i:=1 to n do a[i]:=i; work; for i:=1 to mo-2 do ans:=ans*(m+1) mod mo; writeln(ans); end.

6.

7.

8.

## [HNOI2008]越狱

ans=m^n-m*(m-1)^(n-1).

9.

## [HNOI2008]GT考试

wa了一次，原因是因为转移的时候理解错了，无耻的让我过样例了。

10.

11.

## [HNOI2008]玩具装箱

/************************************************************** Problem: 1010 User: ImSB Language: Pascal Result: Accepted Time:250 ms Memory:2884 kb ****************************************************************/ program h810; type real=extended; var f,a,b,s,x:array[0..50000] of real; q:array[0..50000] of longint; n,i,l,r:longint; d,aa,bb:real; begin readln(n,d);d:=d+1; for i:=1 to n do readln(s[i]); for i:=1 to n do s[i]:=s[i]+s[i-1]; for i:=1 to n do s[i]:=s[i]+i; l:=1;r:=1;q[1]:=0; for i:=1 to n do begin while (l<r)and(s[i]>x[l+1]) do inc(l); f[i]:=a[l]*s[i]+b[l]+sqr(s[i]-d); aa:=-2*s[i];bb:=f[i]+s[i]*s[i]+2*s[i]*d; while (l<r)and(x[r]*aa+bb<x[r]*a[r]+b[r]) do dec(r); inc(r);a[r]:=aa;b[r]:=bb; x[r]:=(b[r]-b[r-1])/(a[r-1]-a[r]+1e-15); end; writeln(f[n]:0:0); end.

12.

## [Jsoi2011]括号序列

/************************************************************** Problem: 2209 User: ImSB Language: Pascal Result: Accepted Time:17780 ms Memory:3872 kb ****************************************************************/ program ex1; {\$inline+} var l,r,a,b,s,a1,b1,a2,b2:array[0..100002] of longint; n,q,i,t,ll,rr,ls,rs,tmp,root,tt:longint; function rd:char;begin read(rd) end; procedure swap(var a,b:longint);inline;begin tmp:=a;a:=b;b:=tmp end; procedure update(i:longint);inline; begin ls:=l[i];rs:=r[i]; s[i]:=s[ls]+s[rs]+1; if a[i]=0 then begin a1[i]:=a1[ls];b1[i]:=b1[ls]+1; a2[i]:=a2[ls]+ord(b2[ls]=0); b2[i]:=b2[ls]-ord(b2[ls]>0); end else begin a2[i]:=a2[ls];b2[i]:=b2[ls]+1; a1[i]:=a1[ls]+ord(b1[ls]=0); b1[i]:=b1[ls]-ord(b1[ls]>0); end; if b1[i]>a1[rs] then inc(b1[i],b1[rs]-a1[rs]) else begin inc(a1[i],a1[rs]-b1[i]);b1[i]:=b1[rs]; end; if b2[i]>a2[rs] then inc(b2[i],b2[rs]-a2[rs]) else begin inc(a2[i],a2[rs]-b2[i]);b2[i]:=b2[rs]; end; end; procedure left(var i:longint);inline;var j:longint; begin j:=r[i];r[i]:=l[j];l[j]:=i; update(i);update(j);i:=j; end; procedure right(var i:longint);inline;var j:longint; begin j:=l[i];l[i]:=r[j];r[j]:=i; update(i);update(j);i:=j; end; procedure put(i,j:longint);inline; begin if odd(j>>1) then begin swap(a1[i],a2[i]);swap(b1[i],b2[i]); a[i]:=1-a[i];b[i]:=b[i] xor 2; end; if odd(j>>2) then begin swap(a1[i],b2[i]);swap(a2[i],b1[i]); b[i]:=b[i] xor 4;swap(l[i],r[i]); end; end; procedure splay(var i:longint;j:longint);inline; begin if b[i]<>0 then begin put(l[i],b[i]);put(r[i],b[i]); b[i]:=0; end; if s[l[i]]>=j then begin splay(l[i],j);right(i); end else if j>s[l[i]]+1 then begin splay(r[i],j-s[l[i]]-1);left(i); end; end; procedure make(var i:longint;ll,rr:longint); begin if ll>rr then exit; i:=(ll+rr)>>1; make(l[i],ll,i-1); make(r[i],i+1,rr); update(i); end; begin readln(n,q); for i:=2 to n+1 do a[i]:=ord(rd=’)’); make(root,1,n+2); for q:=1 to q do begin readln(t,ll,rr); splay(root,ll); splay(root,rr+2); i:=r[l[root]]; if t=0 then writeln((a1[i]+b1[i])>>1+a1[i] and 1) else begin put(i,1<<t); update(l[root]); update(root); end; end; end.

13.

## [SDOI2011]打地鼠

N^2的验证需要一点小技巧，类似与点事件的东西。

/************************************************************** Problem: 2241 User: ImSB Language: Pascal Result: Accepted Time:30 ms Memory:564 kb ****************************************************************/ program ex2; var a,b:array[-100..100,-100..100] of longint; c:array[0..100] of longint; n,m,i,j,s,ans:longint; procedure ck(x,y:longint);var i,j,t:longint; begin fillchar(c,sizeof(c),0); for i:=1 to n do begin t:=0; for j:=1 to m do begin dec(t,b[i,j-y]+b[i-x,j]-b[i-x,j-y]); inc(c[j],t); b[i,j]:=a[i,j]-c[j]; if b[i,j]<0 then exit; inc(t,b[i,j]); inc(c[j],b[i,j]); end; end; ans:=s div (x*y); end; begin readln(n,m); for i:=1 to n do for j:=1 to m do begin read(a[i,j]);inc(s,a[i,j]); end; ans:=maxlongint; for i:=1 to n do if s mod i=0 then for j:=1 to n do if (s mod (i*j)=0)and(s div (i*j)<ans) then ck(i,j); writeln(ans); end.

14.

## [ZJOI2007]最大半连通子图

/************************************************************** Problem: 1093 User: cjld Language: Pascal Result: Accepted Time:2640 ms Memory:12920 kb ****************************************************************/ program ex1; {\$inline+} var d,f,g,z,a,fa,oo:array[0..100000] of longint; p,next:array[0..1000000] of longint; o:array[0..100000] of boolean; t,i,j,k,n,m,mo,t1,t2,t3,ans1,ans2,task:longint; procedure dfs(i:longint);inline;var j,k,tt:longint; begin k:=d[i];j:=p[k]; inc(t);tt:=t; a[i]:=t;z[t]:=i;o[i]:=true; while k<>0 do begin if a[j]=0 then dfs(j); if o[j]and(a[j]<a[i]) then a[i]:=a[j]; k:=next[k];j:=p[k]; end; if tt=a[i] then begin inc(task); t1:=t-tt+1;g[i]:=1; for t:=tt to t do begin fa[z[t]]:=i; k:=d[z[t]];j:=fa[p[k]]; while k<>0 do begin if not o[j]and(j<>0)and(oo[j]<>task)then if f[j]>f[i] then begin f[i]:=f[j];g[i]:=g[j]; end else if f[j]=f[i] then inc(g[i],g[j]); oo[j]:=task;k:=next[k];j:=fa[p[k]]; end; end; for t:=t downto tt do o[z[t]]:=false; inc(f[i],t1); if f[i]>ans1 then begin ans1:=f[i];ans2:=g[i] end else if f[i]=ans1 then inc(ans2,g[i]); dec(t);g[i]:=g[i] mod mo;ans2:=ans2 mod mo; end; end; begin readln(n,m,mo); for i:=1 to m do begin readln(j,k);inc(t); next[t]:=d[j];d[j]:=t;p[t]:=k; end; t:=0; for i:=1 to n do if a[i]=0 then dfs(i); writeln(ans1);writeln(ans2); end.