NOIP2006提高组 解题报告

少说多做- -||

1.能量项链

典型的合并类动规。对于一条链来说，f[i,j]表示合并i到j的最大能量，易得f[i,j]=max{f[i,k]+f[k+1,j]+a[i]a[k+1]a[j+1]}，复杂度O(n3)。由于项链是一个环，要拆成链，有一个办法就是做n次，每次都把项链移动一位。但是这样复杂度就变成了O(n4)，对于n<=100难以承受。

由于有许多的公共部分，可以考虑拆成2n个点，动规时合并区间[1,n],[2,n+1]…[n,2n-1]，最后从这几个区间中选出一个最大的作为答案。公共部分没有被重复计算，因此效率大大提高，整体的复杂度仍然保持在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

var tmp,n,i,j,k,len:longint;
    a:array[0..200]of longint;
    f:array[0..200,0..200]of longint;
begin
  fillchar(f,sizeof(f),193);
  readln(n);
  for i:=1 to n do read(a[i]);
  for i:=1 to n do a[n+i]:=a[i];
  for i:=1 to 2*n-1 do f[i,i]:=0;

  for len:=1 to n-1 do
    for i:=1 to n*2-1-len do begin
      j:=i+len;
      for k:=i to j-1 do begin
        tmp:=f[i,k]+f[k+1,j]+a[i]*a[k+1]*a[j+1];
        if tmp>f[i,j] then f[i,j]:=tmp;
      end;
    end;
  tmp:=0;
  for i:=0 to n-1 do
    if f[i+1,i+n]>tmp then tmp:=f[i+1,i+n];
  writeln(tmp);
end.

2.金明的预算方案

经典的01背包。因为有附件，并且一个主件最多只有2个附件，且附件没有附件，因此转移的方法只有如下四种：1.只买主件；2.买主件和附件1；3.买主件和附件2；4.买主件和两个附件。带入01背包DP方程f[j]=max{f[j-a[i]]+b[i]}，轻松解决。

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

{$inline on}
var n,m,i,j:longint;
    a:array[0..60,1..2]of longint;
    f:array[0..32000]of longint;
    q,v,w,count:array[0..60]of longint;
procedure up(var tmp:longint;i,need,j,w:longint);inline;
  begin
    if (count[i]>=need)and(j>=0)and(tmp<f[j]+w) then tmp:=f[j]+w;
  end;
begin
  readln(n,m);
  for i:=1 to m do begin
    readln(v[i],w[i],q[i]);
    if q[i]<>0 then begin
      inc(count[q[i]]);
      a[q[i],count[q[i]]]:=i;
    end;
  end;
  for i:=1 to m do if q[i]=0 then
    for j:=n downto 0 do begin
      up(f[j],i,0,j-v[i],v[i]*w[i]);
      up(f[j],i,1,j-v[i]-v[a[i,1]],v[i]*w[i]+v[a[i,1]]*w[a[i,1]]);
      up(f[j],i,2,j-v[i]-v[a[i,2]],v[i]*w[i]+v[a[i,2]]*w[a[i,2]]);
      up(f[j],i,2,j-v[i]-v[a[i,1]]-v[a[i,2]],v[i]*w[i]+v[a[i,1]]*w[a[i,1]]+v[a[i,2]]*w[a[i,2]]);
    end;
  writeln(f[n]);
end.

3.作业调度方案

此题主要考验选手的语文阅读理解能力、做题态度以及心态。题目的意思是这样：有n个工件，每个工件有m道工序，还有m个机器，每个工件的不同工序在不同的机器上所需要的时间是不同的，题目要把每个工件的m道工序分别放到m个不同的机器上去处理，问最少的时间是多少。并且输入数据会告诉你这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
29
30
31

var n,m,i,j,k,t:longint;
    a:array[1..20,1..20]of record machine,time:longint; end;
    count,last:array[1..20]of longint;
    list:array[1..400]of longint;
    ma:array[1..20,0..400]of boolean;
begin
  readln(m,n);
  for i:=1 to n*m do read(list[i]);
  for i:=1 to n do
    for j:=1 to m do read(a[i,j].machine);
  for i:=1 to n do
    for j:=1 to m do read(a[i,j].time);
  for i:=1 to n do last[i]:=0;

  for i:=1 to n*m do with a[list[i],count[list[i]]+1] do begin
    j:=last[list[i]]+1;k:=j-1;
    while k-j+1<time do begin
      inc(k);
      if ma[machine,k] then j:=k+1;
    end;
    for t:=j to k do ma[machine,t]:=true;
    last[list[i]]:=k;
    inc(count[list[i]]);
  end;
  for i:=400 downto 0 do
    for j:=1 to m do if ma[j,i] then begin
      writeln(i);
      close(input);close(output);
      halt;
    end;
end.

4.2k进制数

我是用一个数学方法做的，貌似不是很快，比DP的慢……

考虑2k进制数除了最高位外的每一位，都可以转换成k位二进制数。假设一个数在2k进制下有x位，最高位为a1，那么由题目可以得到：(x-1)a1+t<=w。又因为a1>=1，所以：x<=(w-1)/k+1。又因为题目说相邻的两位中，左边的必须大于右边的，按照12345…这样的顺序排下去，最大的长度也只能为2^k-1。

在不考虑最高位，也就是有x-1位可以任取的时候，因为题目要求有序，所以可以将问题转成求组合数。我们一共有2k-1个数可以填在x-1个格子中，这样就有了C(2k-1,x-1)种方案。

然后我们考虑最高位，如果最高位取1，那么后面就只有2k-2个数可以放；如果最高位取2，那么后面就只有2k-3个数可以放……因此答案再把C(2^k-1-i,x-1)累加起来，其中i为最高位能够取到的最大的数。

注意答案需要高精。C(n,k)可以利用杨辉三角算出，C(n,k)=C(n-1,k)+C(n-1,k-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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

const MAXW=1 shl 9 - 1;
type bigint=array[0..50]of longint;
var x,n,k,w,t,i,j:longint;
    ans:bigint;
    com:array[0..MAXW,0..MAXW]of bigint;
operator :=(a:longint) c:bigint;
  begin
    fillchar(c,sizeof(c),0);
    c[0]:=0;
    while a<>0 do begin
      inc(c[0]);
      c[c[0]]:=a mod 10000;
      a:=a div 10000;
    end;
  end;
operator +(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:=x div 10000+a[i]+b[i];
      c[i]:=x mod 10000;
    end;
    if x>=10000 then begin
      inc(c[0]);
      c[c[0]]:=1;
    end;
  end;
begin
  for i:=0 to MAXW do begin
    com[i,0]:=1;
    for j:=1 to i do com[i,j]:=com[i-1,j]+com[i-1,j-1];
  end;
  readln(k,w);
  n:=1 shl k-1;
  x:=trunc((w-1)/k)+1;
  if x>n then x:=n;

  ans:=0;
  for i:=2 to x-1 do ans:=ans+com[n,i];
  t:=w mod k;
  if t=0 then begin
    ans:=ans+com[n,x];
  end else begin
    for i:=1 to 1 shl t-1 do ans:=ans+com[n-i,x-1];
  end;
  write(ans[ans[0]]);
  for i:=ans[0]-1 downto 1 do begin
    if ans[i]<10 then write('000') else
    if ans[i]<100 then write('00') else
    if ans[i]<1000 then write('0');
    write(ans[i]);
  end;
end.

Comments