「Clover 10」杯HE两校联赛(第二轮Day1)

应该说的确是NOIp难度。200分就有不错的名字。240分就是第三名，现在想想240并不难，应该注意状态。A题还是比较容易，很快想到正解。但是B题有个地方不等号写反了，导致0分，静态查错真的很重要。C题zzm神犇的O(N^N)暴力有40分。

A 掷骰子

考虑每个掷出骰子式独立事件，把答案用每个面表示就是sigma(i=1..M)=pi*i,显然要为大的数字选择大的概率。

  1: program tyvj1125a;
  2: var ai,i,n,m:longint;
  3:     count:array[0..100] of longint;
  4:     ans:extended;
  5: begin
  6: readln(n);m:=0;
  7: for i:=1 to n do
  8:   begin
  9:   read(ai);
 10:   inc(m,ai);
 11:   inc(count[ai])
 12:   end;
 13: for i:=1 to 100 do
 14:   while count[i]>0 do
 15:     begin
 16:     n:=i;
 17:     ans:=ans+m+(1-n)/2;
 18:     dec(m,n);
 19:     dec(count[i]);
 20:     if m<=0 then break;
 21:     end;
 22: writeln(ans:3:3);
 23: end.

B 环岛

细节题啊，多写注释。

  1: program tyvj1125b;
  2: uses math;
  3: const FileName='tyvj1125b';maxn=400;
  4:       next:array[0..3] of integer=(1,2,3,0);
  5:       pre :array[0..3] of integer=(3,0,1,2);
  6: type  Queue=record
  7:         h,t:longint;
  8:         data:array[0..maxn] of longint;
  9:       end;
 10: var order:array['A'..'Z'] of integer;
 11:     a:array[0..4] of longint;
 12:     ready,aim,pos:array[0..maxn] of longint;
 13:     Q:array[0..3] of Queue;
 14:     s:array[0..3] of string[100];
 15:     tot,n,i,j,time,k:longint;
 16:     finish,fall:boolean;
 17:     canin:array[0..3] of boolean;
 18: procedure init(var Q:Queue);
 19:           begin
 20:           with Q do begin
 21:             h:=0;t:=0;end;
 22:           end;
 23: procedure add(var Q:Queue;x:longint);
 24:           begin
 25:           with Q do begin
 26:             inc(t);data[t]:=x;end;
 27:           end;
 28: function  del(var Q:Queue):longint;
 29:           begin
 30:           with Q do begin
 31:             inc(h);del:=data[h];end;
 32:           end;
 33: begin
 34: order['N']:=0;order['W']:=1;order['S']:=2;order['E']:=3;
 35: readln(s[0]);readln(s[3]);readln(s[2]);readln(s[1]);
 36: n:=max(max(length(s[0]),length(s[1])),
 37:        max(length(s[2]),length(s[3])));
 38: for i:=1 to n do
 39:   for j:=0 to 3 do
 40:     if (i<=length(s[j]))
 41:        and(s[j][i]<>'-')
 42:         then begin
 43:              inc(tot);
 44:              ready[tot]:=i-1;
 45:              aim[tot]:=order[s[j][i]];
 46:              pos[tot]:=j;
 47:              end;
 48: time:=0;k:=1;
 49: init(Q[1]);init(Q[2]);
 50: init(Q[3]);init(Q[0]);
 51: fillchar(a,sizeof(a),0);finish:=false;
 52: fillchar(canin,sizeof(canin),true);
 53: while(not finish)do begin
 54:   //--inqueue--
 55:   while(ready[k]<=time)and(k<=tot)do
 56:     begin
 57:     add(Q[pos[k]],k);
 58:     inc(k);end;
 59:   //--can i get in?--
 60:   fillchar(canin,sizeof(canin),false);
 61:   fall:=true;
 62:   for i:=0 to 3 do begin
 63:     if Q[i].h=Q[i].t then fall:=false;
 64:     if(A[pre[i]]=0)and(Q[i].h<Q[i].t)
 65:        and(Q[pre[i]].h=Q[pre[i]].t)
 66:          then canin[i]:=true;
 67:     end;
 68:   if(fall)and(A[pre[0]]=0)then canin[0]:=true;
 69:   //==leave--
 70:   for i:=0 to 3 do
 71:     if(A[i]<>0)and(aim[A[i]]=i)
 72:       then A[i]:=0;
 73:   //--move--
 74:   for i:=3 downto 0 do A[i+1]:=A[i];A[0]:=A[4];
 75:   //--get in
 76:   for i:=0 to 3 do
 77:     if canin[i]
 78:       then A[i]:=del(Q[i]);
 79:   //check is it finish
 80:   if k<=tot
 81:     then finish:=false
 82:     else begin
 83:          finish:=true;
 84:          for i:=0 to 3 do
 85:           if(Q[i].h<>Q[i].t)or(A[i]<>0)
 86:            then begin
 87:                 finish:=false;
 88:                 break;
 89:                 end;
 90:          end;
 91:   inc(time);end;
 92: writeln(time);
 93: end.

C 铁路历险

为什么当时不写暴力？为什么不打表？

参考了zzm神犇的代码。该练练DP了，初始值总是很糊涂。

program tyvj1125c;
const maxn=5000;
      p=1000000007;
var   f,g,fsum,gsum:array[0..maxn] of int64;
      i,j,n:longint;
begin
readln(n);
fillQword(g,sizeof(g)>>3,1);
for i:=1 to n do Gsum[i]:=Gsum[i-1]+G[i];
for i:=2 to n do
  begin
  F[1]:=G[1];Fsum[0]:=0;
  for j:=i to n do
    begin
    F[j]:=(G[j]*j+Gsum[j-1]-Gsum[i-1]+p)mod p;
    Fsum[j]:=(Fsum[j-1]+F[j])mod p;
    end;
  G:=F;Gsum:=Fsum;
  end;
writeln(G[n]);
end.