NOIP2005提高组 解题报告

少说多做- -||

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

var count,i,j,k,n:longint;
    s:string;
    a:array[0..100]of record name:string[20];no,finalScore,classScore,article,money:longint;staff,western:char; end;
begin
  assign(input,'scholar.in');reset(input);
  assign(output,'scholar.out');rewrite(output);

  readln(n);
  for i:=1 to n do with a[i] do begin
    no:=i;
    readln(s);
    k:=pos(' ',s);
    name:=copy(s,1,k-1);
    delete(s,1,k);
    k:=pos(' ',s);
    val(copy(s,1,k-1),finalScore);
    delete(s,1,k);
    k:=pos(' ',s);
    val(copy(s,1,k-1),classScore);
    staff:=s[k+1];
    western:=s[k+3];
    delete(s,1,k+4);
    val(s,article);

    if (finalScore>80)and(article>=1) then inc(money,8000);
    if (finalScore>85)and(classScore>80) then inc(money,4000);
    if (finalScore>90) then inc(money,2000);
    if (finalScore>85)and(western='Y') then inc(money,1000);
    if (classScore>80)and(staff='Y') then inc(money,850);
    inc(count,money);
  end;
  for i:=1 to n-1 do
    for j:=i+1 to n do if a[i].money      a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];
    end;
  k:=1;
  for i:=2 to n do if (a[i].money=a[1].money)and(a[i].no  writeln(a[k].name);
  writeln(a[1].money);
  writeln(count);

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

2.过河

可以考虑动归。f[i]表示跳到第i个位置需要踩到多少石子，f[i]=min{f[k]}+rock[i]  (s<=k<=t，当i处有石子的时候rock[i]=1，否则为0)。显然L<=10^9，O(n)会时间空间双爆，考虑压缩。

因为石子数量比较少<=100，所以中间一定会产生许多的空长条，如果我们能够压缩这些空长条，那么总的长度就会小得多了。可以证明，如果相邻两个石头的距离Q>=s*(s+1)，那么一定可以使用s,s+1两种步长跳过。可以参考noip2005 过河 解题报告 @ N_C_Derek

因此，对于所有相邻的两个石头距离b[i]-b[i-1]>=s(s+1)，则从第i个点开始，后面的每个点都向左移动b[i]-b[i-1]-s(s+1)个单位。这样一来，L被压缩到10010，m<=100，对于O(m^2)的预处理和O(n)的DP毫无压力。

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

var ans,l,i,j,s,t,n,tmp,p,k:longint;
    a:array[0..101]of longint;
    f:array[0..10010]of longint;
begin
  assign(input,'river.in');reset(input);
  assign(output,'river.out');rewrite(output);

  readln(l);
  readln(s,t,n);
  for i:=1 to n do read(a[i]);
  inc(n);a[n]:=l;
  for i:=1 to n-1 do
    for j:=i+1 to n do if a[i]>a[j] then begin
      tmp:=a[i];a[i]:=a[j];a[j]:=tmp;
    end;
  if s=t then begin
    ans:=0;
    for i:=1 to n-1 do if a[i] mod s=0 then inc(ans);
  end else begin
    p:=s*(s+1);
    for i:=1 to n do begin
      if a[i]-a[i-1]>=p then begin
        k:=a[i]-a[i-1]-p;
        for j:=i to n do dec(a[j],k);
      end;
      f[a[i]]:=1;
    end;
    f[a[n]]:=0;

    for i:=1 to a[n]+t-1 do begin
      k:=maxlongint;
      for j:=s to t do if (i-j>=0)and(k>f[i-j]) then k:=f[i-j];
      if k=maxlongint then f[i]:=maxlongint else inc(f[i],k);
    end;

    ans:=maxlongint;
    for i:=a[n] to a[n]+t-1 do if f[i]  end;
  writeln(ans);

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

3.等价表达式

这题大体的思路是：随机选取几个a，分别带入原式和目标式子，如果得到的答案都相等，那么就可以认为目标式子=原式。

这题的难点不再于算法，而在于编程的熟练度。大部分人都使用栈来操作，我没用栈而是用递归分治的思想来解决，代码长度和编程复杂度相对来说较低。具体做法如下：

对于每一个待机算的字符串s，我先对s进行处理，去除空格和括号，使其仅留下常数和运算符。比方说-3(x+1)-3^2，处理完后就变成了-3x+1-3^2。同时我又记录每一个字符串和常数的深度，所谓深度就是指它被几个括号包住。上面那个例子，处理完后的字符串中每个字符的深度分别为0001110000。

每一次函数work(l,r)处理字符串的区间[l,r]，并返回计算的值。分治的方法如下：找出取出[l,r]中深度最低的符号，如果有多个深度相同的符号那么取优先级最低的（优先级从大到小排列如下：^、*、+-、常数）。假设这个符号是-，位置是p，那么work(l,r)=work(l,p-1)-work(p+1,r)。有三个小细节需要注意：
  1. 如果当前取出的符号为-，那么所有[p+1,r]中和当前-号深度相同的+号都得变成-号，-号都得变成+号。
  2. 因为xyz=(xy)z != x(yz)，因此寻找深度最小并且记录位置的时候，位置要尽量靠后。
  3. 如果计算使用浮点数，x^y的时候千万不要使用exp(y*ln(x))，这样当x<=0时果断出错，正负性也难以解决。因为y为整数，所以for一遍吧。

显然对于题目给定的数据范围，int64也无法承受。不建议使用浮点数，因为其太容易出错了。可以发现题目中的操作只有+-*^，mod对这些运算符均无影响，因此可以考虑使用整型+取模。

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
84
85
86
87

{$inline on}
const TEST=10;
      LUCK=9973;
type arr=array[1..TEST]of longint;
var i,j,n:longint;
    a:longint;
    b:boolean;
    s2,s:string[50];
    ans,res,ran:arr;
    depth:array[1..50]of longint;
procedure get(var p,d:longint;const c:char;const st,ed:longint);inline;
  var i:longint;
  begin
    p:=-1;d:=maxlongint;
    for i:=st to ed do if (s[i]=c)and(depth[i]      p:=i;d:=depth[i];
    end;
  end;
function pow(const x,y:longint):longint;inline;
  var i:longint;
  begin
    pow:=1;
    for i:=1 to y do pow:=pow*x mod LUCK;
  end;
function work(const left,right:longint):longint;
  var o,i:longint;
      tmp1,tmp2:longint;
      p,d:array[1..4]of longint;
  begin
    get(p[1],d[1],'+',left,right);
    get(p[2],d[2],'-',left,right);
    get(p[3],d[3],'*',left,right);
    get(p[4],d[4],'^',left,right);
    o:=-1;
    if d[1]    if d[3]    if d[4]    if d[o]=maxlongint then begin
      if s[left]='a' then exit(a);
      val(copy(s,left,right-left+1),work);
    end else begin
      if o=2 then
        for i:=p[o]+1 to right do if ((s[i]='-')or(s[i]='+'))and(depth[i]=d[o]) then begin
          if s[i]='-' then s[i]:='+' else s[i]:='-';
        end;
      tmp1:=work(left,p[o]-1) mod LUCK;
      tmp2:=work(p[o]+1,right);
      case o of
        1:exit((tmp1+tmp2 mod LUCK)mod LUCK);
        2:exit((tmp1-tmp2 mod LUCK+LUCK)mod LUCK);
        3:exit(tmp1*tmp2 mod LUCK);
        4:exit(pow(tmp1,tmp2));
      end;
    end;
  end;
procedure solve(var ans:arr);
  var i,j:longint;
  begin
    readln(s2);s:='';
    j:=0;
    for i:=1 to length(s2) do if s2[i]<>' ' then begin
      if s2[i]='(' then inc(j) else if s2[i]=')' then dec(j) else begin
        s:=s+s2[i];
        depth[length(s)]:=j;
      end;
    end;
    s2:=s;
    for i:=1 to TEST do begin
      s:=s2;
      a:=ran[i];
      ans[i]:=work(1,length(s));
    end;
  end;
begin
  assign(input,'equal.in');reset(input);
  assign(output,'equal.out');rewrite(output);

  randomize;
  for i:=1 to TEST do ran[i]:=random(100)+1;

  solve(ans);
  readln(n);
  for i:=1 to n do begin
    solve(res);
    b:=true;
    for j:=1 to TEST do b:=b and (res[j]=ans[j]);
    if b then write(chr(64+i));
  end;

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

4.篝火晚会

这题是构造算法。 可以参考noip2005(提高组)讲解 @Des，讲得很详细。

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

var i,k,n,max:longint;
    a:array[1..50000,1..2]of longint;
    b:array[1..50000]of boolean;
    c,sol:array[0..50000]of longint;
begin
  assign(input,'fire.in');reset(input);
  assign(output,'fire.out');rewrite(output);

  readln(n);
  for i:=1 to n do readln(a[i,1],a[i,2]);
  sol[1]:=1;k:=1;
  b[1]:=true;
  repeat
    if (k>1)and(sol[k-1]<>a[sol[k],1])and(sol[k-1]<>a[sol[k],2]) then begin
      writeln(-1);
      close(input);close(output);
      halt;
    end;
    for i:=1 to 2 do if not b[a[sol[k],i]] then begin
      b[a[sol[k],i]]:=true;
      inc(k);
      sol[k]:=a[sol[k-1],i];
      break;
    end;
  until k=n;

  max:=0;
  for i:=1 to n do begin
    k:=(sol[i]-i+n)mod n;
    inc(c[k]);
    if c[k]>max then max:=c[k];
  end;
  fillchar(c,sizeof(c),0);
  for i:=1 to n do begin
    k:=(sol[n-i+1]-i+n)mod n;
    inc(c[k]);
    if c[k]>max then max:=c[k];
  end;
  writeln(n-max);

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

Comments