NOIP2009普及组复赛解题报告

NFLS QMD

第一题 多项式输出

1、摘要

　　时间复杂度:O(n)

空间复杂度:O(n)

 

2、题目大意

输入一个n次多项式各项的系数，按要求输出多项式

 

3、算法分析

先将不为0的系数和对应的次数存入a数组和b数组，然后依次输出。要注意以下几点：

①系数绝对值为1的情况

②指数为1或0的情况

③首项加号不必输出

 

4、参考程序

program poly;

var

  n,i,g,xx:integer;

  a,b:array[0..200]of integer;

function x(n:integer):string;                  //处理项的x^n部分

  var

    st1:string;

  begin

    if n=0 then x:='';

    if n=1 then x:='x';

    if n>1 then

      begin

        str(n,st1);

        x:='x^'+st1;

      end;

  end;

procedure flag(t:integer);                  //处理每项的符号

  begin

    if t>0 then write('+')

           else write('-');

  end;

begin

  assign(input,'poly.in');reset(input);

  assign(output,'poly.out');rewrite(output);

  readln(n);

  g:=0;

  for i:=n downto 0 do                      //保存系数非零的项

    begin

      read(xx);

      if xx<>0 then

        begin

          g:=g+1;

          a[g]:=xx;

          b[g]:=i;

        end;

    end;

  for i:=1 to g do

    begin

      if i=1 then                        //处理首项的情况

        begin

          if abs(a[1])>1 then write(a[1]);

          if a[1]=-1 then write('-');

        end

      else

        begin

          flag(a[i]);

          if(b[i]=0)or(abs(a[i])<>1)then write(abs(a[i]));

        end;

      write(x(b[i]));

    end;

  writeln;

  close(input);close(output);

end.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

第二题 分数线划定

1、摘要

核心算法思想：排序

　　时间复杂度：O(Nlog₂N)

空间复杂度：O(N)

 

2、题目大意

给出n个分数和编号(编号互不相同)，按分数从大到小取前[m*150%]个(可能有重分情况)，输出实际数目，最低分数以及按顺序排列的分数、编号。

 

3、算法分析

显然，本题的算法是排序，但是选择哪一种排序至关重要。比较常用的排序算法按时间复杂度可大致分为三类：

①O(n^2)类：选择排序法、冒泡排序法、插入排序法等

②O(Nlog₂N)类：快速排序、堆排等

③O(n)类：桶排等

因为n≤5000，因此O(n^2)的算法在配置较好的评测机上应该是可以通过的，但是这题还是有一些需要注意的地方：

①对于选择排序等，为了实现双关键字，可以先排编号，再排分数，也可以把交换的条件写为(a[i]<a[j])or((a[i]=a[j])and(b[i]>b[j]))，其中a和b分别是分数和编号；

②对于快速排序，因为快排是不稳定的，因此只能在比较条件上做修改，不能使用二次排序的方法；

③对于桶排，因为会有重分，又因为报名号在1000与9999之间，成绩在1至100，所以可以用“分数*10000+编号”的方法存储布尔值。还有，在处理重分时可能比前两种麻烦一些。

 

4、参考程序(快排)

program score;

var

  n,m,i:integer;

  a,num:array[1..6000]of integer;

procedure swap(var a,b:integer);

  var

    t:integer;

  begin

    t:=a;

    a:=b;

    b:=t;

  end;

procedure sort(l,r:integer);                 //快排过程

  var

    i,j,mid_a,mid_num:integer;

  begin

    i:=l;j:=r;

    mid_a:=a[(i+j)div 2];

    mid_num:=num[(i+j)div 2];

    while i<=j do

      begin

        while(a[i]>mid_a)or((a[i]=mid_a)and(num[i]<mid_num))do i:=i+1;

        while(a[j]<mid_a)or((a[j]=mid_a)and(num[j]>mid_num))do j:=j-1;

        if i<=j then

          begin

            swap(a[i],a[j]);

            swap(num[i],num[j]);

            i:=i+1;j:=j-1;

          end;

      end;

    if l<j then sort(l,j);

    if i<r then sort(i,r);

  end;

begin

  assign(input,'score.in');reset(input);

  assign(output,'score.out');rewrite(output);

  readln(n,m);

  for i:=1 to n do

    readln(num[i],a[i]);

  sort(1,n);

  m:=trunc(m*1.5);

  while a[m+1]=a[m] do m:=m+1;         //处理重分

  writeln(a[m],' ',m);

  for i:=1 to m do

    writeln(num[i],' ',a[i]);

  close(input);close(output);

end.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

第三题 细胞分裂

1、摘要

　　核心算法思想：逐个比较

　　其它辅助知识：基本数论

　　时间复杂度：O(kn)(k不会很大)

空间复杂度：O(n)

 

2、题目大意

给定m1,m2及n个正整数S₁,S₂...S_n，令M=m1^m2。设Ai表示满足M|S_i^x的x最小值，求A₁~A_n中的最小值。

 

3、算法分析

因为m1^m2可能会很大，因此对于每个S_i尝试求出x的值的算法是不可行的。如何才能缩小数据的大小，并在1s内出解呢？这时想到了两种大致的思路：一是利用整除的性质或类似同余定理的方法，二是通过分解将数据规模减小。

再思考一番就能发现方法二可能更可行，因为m1^m2的质因数分解可以由m1得到，再将S_i分解并比较就能求出x的值。

因此程序第一步是将m1分解质因数，指数乘m2再和质因数存储在数组中；然后依次读入S₁，S₂...对于每个S_i分解质因数，再将它的分解与m1^m2做比较，进而求出x的值。

此外还有一些重要的优化技巧：

①因为S_i^x能否被M整除仅仅和其中M含有的质因数有关，也就是说，如果M=2^8*3^6，那么分解S_i时只要关注2、3两个质因数；

②如果上例中S_i中不含有2或3这个质因子，那么x一定为-1；

 

4、参考程序

program cell;

var

  n,m1,m2,i,j,g,best,x,max:longint;

  s:array[1..10010]of longint;

  a,b,c:array[1..100]of longint;

begin

  assign(input,'cell.in');reset(input);

  assign(output,'cell.out');rewrite(output);

  readln(n);

  readln(m1,m2);

  for i:=1 to n do

    read(s[i]);

  g:=0;

  for i:=2 to m1 do                   //分解m1

    if m1 mod i=0 then

      begin

        g:=g+1;

        a[g]:=i;b[g]:=0;

        while m1 mod i=0 do

          begin

            m1:=m1 div i;

            b[g]:=b[g]+1;

          end;

        b[g]:=b[g]*m2;

      end;

  best:=-1;

  for i:=1 to n do

    begin

      x:=s[i];                          //分解S_i

      for j:=1 to g do

        begin

          c[j]:=0;

          while x mod a[j]=0 do

            begin

              x:=x div a[j];

              c[j]:=c[j]+1;

            end;

        end;

      max:=0;

      for j:=1 to g do

        if(c[j]<>0)and(max<>-1)then        //若c[j]=0则必定x=-1

          begin

            x:=(b[j]-1)div c[j]+1;

            if x>max then max:=x;

          end

        else

          max:=-1;

      if max<>-1 then

        if(max<best)or(best=-1)then

          best:=max;

    end;

  writeln(best);

  close(input);close(output);

end.

 

 

 

 

 

 

 

 

 

 

 

第四题 道路游戏

1、摘要

　　核心算法思想：动态规划

　　时间复杂度：O(m·n·p)

空间复杂度：O(mn)

 

2、题目大意

有n段路，在m个单位时间内，每个单位时间每段路上都有一定的金币。从任意一段路开始最多可以走p段，每走一次都会花费不同数目的金币。求在m个单位时间内的最大收益。

 

3、算法分析

这题一开始可能让人有些困惑。搜索？数据规模显然太大。贪心？似乎找不到贪心策略。于是便想到了一种可能正确的算法——动态规划。

首先，这道题满足最优子结构，可以以时间划分阶段；其次，这道题应该也没有后效性。那么问题就在与动态转移方程了。

我们用f(i)表示从还剩下i个单位时间时开始的最大收益，那么它一定是由以前的某个时刻最大收益f(j)(j>i)加上一次行走得到的。因此动态转移方程为：

f(i)=max{f(j)+sum(k,j-i)-cost(k)}(i<j<=p+i,1<=k<=n)

其中j表示以前的某个时刻，k表示行走的起点，sum(k,j-i)为从k出发走(j-i)步的金币数，cost(k)为在工厂k买机器人的支出。

在实现时有所不同，我们可以外循环枚举时间，第二重循枚举起点，第三重枚举走的长度。这样在计算sum时可以通过累加得到。

由于我们要枚举i，j，k，因此时间复杂度应为O(m·n·p)，本来计算sum也需要O(p)的时间，因此只有优化才能过90%的数据，这样比最原始的算法能多得50分。

 

4、参考程序(10%最大数据分别为2.1s和2.5s)

program game;

var

  n,m,p,i,j,k,x,sum:longint;

  a:array[0..1000,0..1000]of integer;

  b,f:array[0..1000]of longint;

function fac(x:integer):integer;

  begin

    fac:=(x-1)mod n+1;

  end;

begin

  assign(input,'game.in');reset(input);

  assign(output,'game.out');rewrite(output);

  readln(n,m,p);

  for i:=1 to n do

    begin

      for j:=1 to m do

        read(a[i,j]);

      readln;

    end;

  for i:=1 to n do

    read(b[i]);

  f[0]:=0;

  for i:=1 to m do

    begin

      f[i]:=0;

      for j:=1 to n do

        begin

          sum:=0;

          for k:=1 to p do

            if i>=k then

              begin

                sum:=sum+a[fac(j+k-1),m-i+k];

                x:=f[i-k]-b[j]+sum;

                if x>f[i] then f[i]:=x;

              end;

        end;

    end;

  writeln(f[m]);

  close(input);close(output);

end.