NFLS QMD

第一題 多項式輸出

1、摘要

　　時間復雜度:O(n)

空間復雜度:O(n)

2、題目大意

輸入一個n次多項式各項的系數(shù)，按要求輸出多項式

3、算法分析

先將不為0的系數(shù)和對應的次數(shù)存入a數(shù)組和b數(shù)組，然后依次輸出。要注意以下幾點：

①系數(shù)絕對值為1的情況

②指數(shù)為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                      //保存系數(shù)非零的項

    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.

第二題 分數(shù)線劃定

1、摘要

核心算法思想：排序

　　時間復雜度：O(Nlog₂N)

空間復雜度：O(N)

2、題目大意

給出n個分數(shù)和編號(編號互不相同)，按分數(shù)從大到小取前[m*150%]個(可能有重分情況)，輸出實際數(shù)目，最低分數(shù)以及按順序排列的分數(shù)、編號。

3、算法分析

顯然，本題的算法是排序，但是選擇哪一種排序至關重要。比較常用的排序算法按時間復雜度可大致分為三類：

①O(n^2)類：選擇排序法、冒泡排序法、插入排序法等

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

③O(n)類：桶排等

因為n≤5000，因此O(n^2)的算法在配置較好的評測機上應該是可以通過的，但是這題還是有一些需要注意的地方：

①對于選擇排序等，為了實現(xiàn)雙關鍵字，可以先排編號，再排分數(shù)，也可以把交換的條件寫為(a[i]<a[j])or((a[i]=a[j])and(b[i]>b[j]))，其中a和b分別是分數(shù)和編號；

②對于快速排序，因為快排是不穩(wěn)定的，因此只能在比較條件上做修改，不能使用二次排序的方法；

③對于桶排，因為會有重分，又因為報名號在1000與9999之間，成績在1至100，所以可以用“分數(shù)*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、摘要

　　核心算法思想：逐個比較

　　其它輔助知識：基本數(shù)論

　　時間復雜度：O(kn)(k不會很大)

空間復雜度：O(n)

2、題目大意

給定m1,m2及n個正整數(shù)S₁,S₂...S_n，令M=m1^m2。設Ai表示滿足M|S_i^x的x最小值，求A₁~A_n中的最小值。

3、算法分析

因為m1^m2可能會很大，因此對于每個S_i嘗試求出x的值的算法是不可行的。如何才能縮小數(shù)據(jù)的大小，并在1s內(nèi)出解呢？這時想到了兩種大致的思路：一是利用整除的性質(zhì)或類似同余定理的方法，二是通過分解將數(shù)據(jù)規(guī)模減小。

再思考一番就能發(fā)現(xiàn)方法二可能更可行，因為m1^m2的質(zhì)因數(shù)分解可以由m1得到，再將S_i分解并比較就能求出x的值。

因此程序第一步是將m1分解質(zhì)因數(shù)，指數(shù)乘m2再和質(zhì)因數(shù)存儲在數(shù)組中；然后依次讀入S₁，S₂...對于每個S_i分解質(zhì)因數(shù)，再將它的分解與m1^m2做比較，進而求出x的值。

此外還有一些重要的優(yōu)化技巧：

①因為S_i^x能否被M整除僅僅和其中M含有的質(zhì)因數(shù)有關，也就是說，如果M=2^8*3^6，那么分解S_i時只要關注2、3兩個質(zhì)因數(shù)；

②如果上例中S_i中不含有2或3這個質(zhì)因子，那么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、摘要

　　核心算法思想：動態(tài)規(guī)劃

　　時間復雜度：O(m·n·p)

空間復雜度：O(mn)

2、題目大意

有n段路，在m個單位時間內(nèi)，每個單位時間每段路上都有一定的金幣。從任意一段路開始最多可以走p段，每走一次都會花費不同數(shù)目的金幣。求在m個單位時間內(nèi)的最大收益。

3、算法分析

這題一開始可能讓人有些困惑。搜索？數(shù)據(jù)規(guī)模顯然太大。貪心？似乎找不到貪心策略。于是便想到了一種可能正確的算法——動態(tài)規(guī)劃。

首先，這道題滿足最優(yōu)子結(jié)構，可以以時間劃分階段；其次，這道題應該也沒有后效性。那么問題就在與動態(tài)轉(zhuǎn)移方程了。

我們用f(i)表示從還剩下i個單位時間時開始的最大收益，那么它一定是由以前的某個時刻最大收益f(j)(j>i)加上一次行走得到的。因此動態(tài)轉(zhuǎn)移方程為：

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出發(fā)走(j-i)步的金幣數(shù)，cost(k)為在工廠k買機器人的支出。

在實現(xiàn)時有所不同，我們可以外循環(huán)枚舉時間，第二重循枚舉起點，第三重枚舉走的長度。這樣在計算sum時可以通過累加得到。

由于我們要枚舉i，j，k，因此時間復雜度應為O(m·n·p)，本來計算sum也需要O(p)的時間，因此只有優(yōu)化才能過90%的數(shù)據(jù)，這樣比最原始的算法能多得50分。

4、參考程序(10%最大數(shù)據(jù)分別為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.