NOIP2008提高组 解题报告

少说多做- -||

1.笨小猴

送分，略…… 
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

var i,maxn,minn:longint;
    s:string;
    c:char;
    a:array['a'..'z']of longint;
begin
  readln(s);
  for i:=1 to length(s) do inc(a[s[i]]);
  minn:=maxlongint;
  maxn:=0;
  for c:='a' to 'z' do if a[c]<>0 then begin
    if a[c]>maxn then maxn:=a[c];
    if a[c]<minn then minn:=a[c];
  end;
  dec(maxn,minn);
  for i:=2 to trunc(sqrt(maxn)) do if maxn mod i=0 then begin
    c:=#32;
    break;
  end;
  if (c=#32)or(maxn<2) then begin
    writeln('No Answer');
    writeln(0);
  end else begin
    writeln('Lucky Word');
    writeln(maxn);
  end;
end.

2.火柴棒等式

题目火柴棒的数量n最大等于24，扣掉加号、等号只剩下20根。20根显然不可能有五位数（最好情况都是1，但即使如此组成的等式不成立，11111+1=1111）。而如果组成了一个四位数加数，则另一个加数必定<=11。其他情况最多A,B都是3位数。 因此可以先预处理算出组成x（x<10000）需要多少根火柴棒，然后枚举加数A和B。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

const MAT:array[0..9]of integer=(6,2,5,5,4,5,6,3,7,6);
var i,ans,a,b,n:longint;
    need:array[0..9999]of longint;
begin
  for i:=0 to 9 do need[i]:=MAT[i];
  for i:=10 to 99 do need[i]:=need[i mod 10]+need[i div 10];
  for i:=100 to 999 do need[i]:=need[i mod 10]+need[i div 10];
  for i:=1000 to 9999 do need[i]:=need[i mod 10]+need[i div 10];
  readln(n);
  dec(n,4);
  ans:=0;
  for a:=0 to 999 do
    for b:=0 to 999 do if need[a]+need[b]+need[a+b]=n then inc(ans);
  for a:=1000 to 9999 do
    for b:=0 to 11 do if (a+b<=9999)and(need[a]+need[b]+need[a+b]=n) then inc(ans);
  writeln(ans);
end.

3.传纸条

题目相当于，找两条从(1,1)到(n,m)的不相交的线路，使得这两条线路经过的个子上的数值之和最大。 朴素做法：四维动归，f[x1,y1,x2,y2]表示第一条线路走到(x1,y1)，第二条线路走到(x2,y2)，显然转移只能从f[x1-1,y1,x2-1,y2],f[x1-1,y1,x2,y2-1],f[x1,y1-1,x2-1,y2],f[x1,y1-1,x2,y2-1]里面寻找最大值。 为了避免两条线路相交，因此特殊处理交点的情况，也就是(x1=x2)and(y1=y2)and(x1<>n)and(y1<>m)的情况，此时f[x1,y1,x1,y1]=-∞。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

{$inline on}
var i,j,x,y,n,m:longint;
    a:array[1..50,1..50]of longint;
    f:array[0..51,0..51,0..51,0..51]of longint;
procedure max(var a:longint;b:longint);inline;begin if(a<b)then a:=b;end;
begin
  fillchar(f,sizeof(f),193);
  readln(n,m);
  for i:=1 to n do
    for j:=1 to m do read(a[i,j]);
  f[1,1,1,1]:=0;
  for i:=1 to n do
  for j:=1 to m do
    for x:=1 to n do
    for y:=1 to m do if (i<>x)and(j<>y) or (i=n)and(j=m) then begin
      max(f[i,j,x,y],f[i-1,j,x-1,y]);
      max(f[i,j,x,y],f[i-1,j,x,y-1]);
      max(f[i,j,x,y],f[i,j-1,x,y-1]);
      max(f[i,j,x,y],f[i,j-1,x-1,y]);
      inc(f[i,j,x,y],a[i,j]+a[x,y]);
    end;
  writeln(f[n,m,n,m]);
end.
稍加优化：我们可以考虑使得第一条线路和第二条线路走的步数相同，这样就可以减少一维。由于x+y=step+2，因此如果记录了第一条线路的行坐标x1，和第二条线路的x2，则第一条线路的列坐标就为step+2-x1，第二条的为step+2-x2，转移同理还是从那四个位置过来。空间和时间都降到O(n^3)。 
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

{$inline on}
var i,j,x1,x2,step,n,m:longint;
    a,sum:array[1..50,0..50]of longint;
    f:array[0..98,0..50,0..50]of longint;
procedure max(var a:longint;b:longint);inline;begin if(a<b)then a:=b;end;
begin
  fillchar(f,sizeof(f),193);
  readln(n,m);
  for i:=1 to n do begin
    sum[i,0]:=0;
    for j:=1 to m do begin
      read(a[i,j]);
      sum[i,j]:=sum[i,j-1]+a[i,j];
    end;
  end;
  f[0,1,1]:=0;
  for step:=1 to m+n-2 do
    for x1:=1 to n do
      for x2:=1 to n do if (x1<>x2) or (x1=n)and(step-x2+2=m) then begin
        if x1>1 then max(f[step,x1,x2],f[step-1,x1-1,x2]);
        if x2>1 then max(f[step,x1,x2],f[step-1,x1,x2-1]);
        if (x1>1)and(x2>1) then max(f[step,x1,x2],f[step-1,x1-1,x2-1]);
        max(f[step,x1,x2],f[step-1,x1,x2]);
        inc(f[step,x1,x2],a[x1,step-x1+2]+a[x2,step-x2+2]);
      end;

  writeln(f[m+n-2,n,n]);
end.

4.双栈排序

可以发现，如果存在k满足a[k] 
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

type stack=array[0..1000]of longint;
var n,i,j,k,top:longint;
    can:boolean;
    s1,s2,color,a,min:stack;
    g:array[1..1000+1000*1000]of record v,next:longint;end;
procedure join(x,y:longint);
  begin
    inc(top);
    g[top].v:=y;
    g[top].next:=g[x].next;
    g[x].next:=top;
  end;
function go(u,C:longint):boolean;
  var v:longint;
  begin
    color[u]:=C;
    v:=g[u].next;
    while v<>-1 do begin
      if (color[g[v].v]=-1)and not go(g[v].v,1-C) then exit(false);
      if color[g[v].v]+C<>1 then exit(false);
      v:=g[v].next;
    end;
    exit(true);
  end;
function pop(var s:stack;c:char):boolean;
  begin
    if (s[0]>0)and(s[s[0]]=k) then begin
      write(c,' ');
      dec(s[0]);
      inc(k);
      exit(true);
    end;
    exit(false);
  end;
procedure push(var s:stack;x:longint;c:char);
  begin
    write(c,' ');
    inc(s[0]);
    s[s[0]]:=x;
    inc(i);
  end;
begin
  fillchar(color,sizeof(color),255);
  readln(n);
  for i:=1 to n do begin
    read(a[i]);
    g[i].next:=-1;
  end;
  top:=n;
  min[n]:=a[n];
  for i:=n-1 downto 1 do if a[i]<min[i+1] then min[i]:=a[i] else min[i]:=min[i+1];
  for i:=1 to n-2 do
    for j:=i+1 to n-1 do
      if (min[j+1]<a[i])and(a[i]<a[j]) then begin
        join(i,j);
        join(j,i);
      end;
  can:=true;
  for i:=1 to n do if color[i]=-1 then can:=can and go(i,0);

  if not can then begin
    write(0);
  end else begin
    s1[0]:=0;s2[0]:=0;
    k:=1;
    i:=1;
    while k<=n do begin
      if pop(s1,'b') or pop(s2,'d') then continue;
      if color[i]=0 then push(s1,a[i],'a') else push(s2,a[i],'c');
    end;
  end;
end.

Comments