NOIP2007提高组 解题报告

少说多做- -||

1.统计数字

nlogn排序+n统计，水过 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

var i,n,count:longint;
    a:array[1..200000]of longint;
procedure qsort(l,r:longint);
  var i,j,x,t:longint;
  begin
    i:=l;j:=r;x:=a[(l+r)shr 1];
    repeat
      while a[i]<x do inc(i);
      while a[j]>x do dec(j);
      if i<=j then begin
        t:=a[i];a[i]:=a[j];a[j]:=t;
        inc(i);dec(j);
      end;
    until i>=j;
    if i<r then qsort(i,r);
    if l<j then qsort(l,j);
  end;
begin
  readln(n);
  for i:=1 to n do readln(a[i]);
  qsort(1,n);
  count:=1;
  for i:=2 to n do if a[i]<>a[i-1] then begin
    writeln(a[i-1],' ',count);
    count:=1;
  end else inc(count);
  writeln(a[n],' ',count);
end.

2.字符串的展开

模拟题，没什么好说的，跟着题目做就是了。不一定越长的代码一次AC的几率越高，简短一点的说不定更容易一次AC，比如我这次就一次AC了。初中的时候每次做都交了n次才过。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

var q1,q2,q3,k,i,j,last:longint;
    c:char;
    s:string;
begin
  assign(input,'expand.in');reset(input);
  assign(output,'expand.out');rewrite(output);

  readln(q1,q2,q3);
  readln(s);
  s:=s+' ';
  last:=0;

  while last<>length(s) do begin
    k:=pos('-',s);
    for i:=last+1 to k-1 do write(s[i]);
    if (k>1)and((s[k-1]in['a'..'z'])and(s[k+1]in['a'..'z']) or (s[k-1]in['0'..'9'])and(s[k+1]in['0'..'9'])and(s[k-1]<s[k+1]) then begin
      if p3=1 then
        for c:=succ(s[k-1]) to pred(s[k+1]) do writech(p3)
      else
        for c:=pred(s[k+1]) to succ(s[k-1]) do writech(p3);
    end else begin
      write(s[k],s[k+1]);
      last:=k+1;
    end;
  end;

  close(input);close(output);
end.

3.矩阵取数游戏

题目可以这么考虑：针对每一行单独处理，每一次只能取走行头或者行尾；如此分别处理这n行即可。 考虑第i行，f[l,r]表示取走区间[l,r]的最大值。那么显然f[l,r]只能够从f[l+1,r]+a[i,l]和f[l,r-1]+a[i,r]中去一个最大值。做一次复杂度为m^2，因此总的复杂度为O(n m^2)。 注意答案需要用高精。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

type bigint=array[0..40]of longint;
var n,m,i,j,x:longint;
    tmp,ans:bigint;
    pow:array[1..80]of bigint;
    f,a:array[1..80,1..80]of bigint;
operator +(const a,b:bigint) c:bigint;
  var i,x:longint;
  begin
    fillchar(c,sizeof(c),0);
    if a[0]>b[0] then c[0]:=a[0] else c[0]:=b[0];
    x:=0;
    for i:=1 to c[0] do begin
      x:=a[i]+b[i]+x div 10;
      c[i]:=x mod 10;
    end;
    if x>9 then begin
      inc(c[0]);
      c[c[0]]:=1;
    end;
  end;
operator *(const a,b:bigint) c:bigint;
  var i,j,x:longint;
  begin
    fillchar(c,sizeof(c),0);
    for i:=1 to a[0] do begin
      x:=0;
      for j:=1 to b[0] do begin
        x:=a[i]*b[j]+x+c[i+j-1];
        c[i+j-1]:=x mod 10;
        x:=x div 10;
      end;
      c[i+j]:=x;
    end;
    c[0]:=a[0]+b[0];
    while (c[0]>0)and(c[c[0]]=0) do dec(c[0]);
  end;
operator <(const a,b:bigint) ans:boolean;
  var i:longint;
  begin
    if a[0]<>b[0] then exit(a[0]<b[0]);
    for i:=a[0] downto 1 do if a[i]<>b[i] then exit(a[i]<b[i]);
    exit(false);
  end;
procedure calc(left,right:longint);
  var tmp1,tmp2:bigint;
  begin
    if f[left,right][0]>0 then exit;
    if left<right then begin
      calc(left+1,right);
      tmp1:=f[left+1,right]+pow[m-right+left]*a[i,left];

      calc(left,right-1);
      tmp2:=f[left,right-1]+pow[m-right+left]*a[i,right];
      if tmp1<tmp2 then f[left,right]:=tmp2 else f[left,right]:=tmp1;
    end else f[left,right]:=pow[m]*a[i,left];
  end;
begin
  assign(input,'game.in');reset(input);
  assign(output,'game.out');rewrite(output);

  pow[1][0]:=1;pow[1][1]:=2;
  for i:=2 to 80 do pow[i]:=pow[i-1]*pow[1];
  readln(n,m);
  for i:=1 to n do
    for j:=1 to m do begin
      read(x);
      while x>0 do begin
        inc(a[i,j][0]);
        a[i,j][a[i,j][0]]:=x mod 10;
        x:=x div 10;
      end;
    end;

  ans[0]:=1;
  for i:=1 to n do begin
    fillchar(f,sizeof(f),0);
    calc(1,m);
    ans:=ans+f[1,m];
  end;
  for i:=ans[0] downto 1 do write(ans[i]);

  close(input);close(output);
end.

4.树网的核

介绍一个简单的方法： 可以用n3的时间，用floyd求出任两点间的距离d[i,j]（或者使用SPFA，这样复杂度大约可以降到n2）。此时可以用n2的时间遍历d[st,ed]，找出树的直径长度（或者两遍DFS找直径，复杂度2n）。然后枚举直径st->ed上的路径i->j，也就是枚举核（时间n2），之后求Ecc(i->j)（复杂度1）。 对于直径st->ed上的核i->j（注意，前提是核），Ecc(i->j)=max(min(dist[st,i],dist[st,j]),min(dist[i,ed],dist[j,ed]))。之所以只考虑四个数，是因为i(j)到st(ed)的距离大于其他任何点，如果不是这样的话那么st->ed就不是直径了。 另外，可以证明只需要考虑一条直径上的最优核偏心距（至于怎么证明真的不知道），因此考虑一条直径即可。 总的复杂度=O(n3+n2+n2)=O(n3)。如果使用SPFA，那么大约可以降到O(n^2)。对于n<=300轻松过。

进一步研究可以参照： http://tieba.baidu.com/f?kz=842504583 O(n)算法：http://www.cnblogs.com/yymore/archive/2011/07/01/2095962.html 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

{$inline on}
var top,ecc,ans,st,ed,i,j,w,n,m,dia:longint;
    s:array[1..300]of boolean;
    q:array[1..300*300]of longint;
    dist:array[1..300,1..300]of longint;
    g:array[1..300+300*300]of record v,w,next:longint;end;
function min(a,b:longint):longint;inline;begin if(a<b)then exit(a)else exit(b)end;
function max(a,b:longint):longint;inline;begin if(a>b)then exit(a)else exit(b)end;
procedure join(x,y,w:longint);inline;
  begin
    inc(top);
    g[top].v:=y;
    g[top].w:=w;
    g[top].next:=g[x].next;
    g[x].next:=top;
  end;
procedure SPFA(source:longint);
  var u,v,head,tail:longint;
  begin
    fillchar(dist[source],sizeof(dist[source]),63);
    fillchar(s,sizeof(s),0);
    head:=0;tail:=1;
    q[tail]:=source;
    dist[source,source]:=0;
    s[source]:=true;
    repeat
      inc(head);
      u:=q[head];
      v:=g[u].next;
      while v<>-1 do begin
        if dist[source,g[v].v]>dist[source,u]+g[v].w then begin
          dist[source,g[v].v]:=dist[source,u]+g[v].w;
          if not s[g[v].v] then begin
            s[g[v].v]:=true;
            inc(tail);
            q[tail]:=g[v].v;
          end;
        end;
        v:=g[v].next;
      end;
      s[u]:=false;
    until head>=tail;
  end;
begin
  assign(input,'core.in');reset(input);
  assign(output,'core.out');rewrite(output);

  readln(n,m);
  for i:=1 to n do g[i].next:=-1;
  top:=n;
  for i:=1 to n-1 do begin
    readln(st,ed,w);
    join(st,ed,w);
    join(ed,st,w);
  end;
  for i:=1 to n do SPFA(i);
  dia:=0;
  for i:=1 to n-1 do
    for j:=i+1 to n do if dist[i,j]>dia then dia:=dist[i,j];

  for st:=1 to n-1 do
    for ed:=st+1 to n do if dist[st,ed]=dia then begin
      ans:=maxlongint;
      for i:=1 to n do if dist[st,i]+dist[i,ed]=dia then
        for j:=1 to n do if (dist[st,j]+dist[j,ed]=dia)and(dist[i,j]<=m) then begin
          ecc:=max(min(dist[st,i],dist[st,j]),min(dist[i,ed],dist[j,ed]));
          ans:=min(ans,ecc);
        end;
      writeln(ans);
      close(input);close(output);
      halt;
    end;

  close(input);close(output);
end.

Comments