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;

functionx(n:integer):string;//處理項的x^n部分

var

st1:string;

begin

if n=0then x:="";

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

ifn>1 then

begin

str(n,st1);

x:="x^"+st1;

end;

end;

procedureflag(t:integer);//處理每項的符號

begin

ift>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 0do//保存係數非零的項

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=1then//處理首項的情況

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)thenwrite(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];

whilei<=j do

begin

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

while(a[j]<mid_a)or((a[j]=mid_a)and(num[j]>mid_num))doj:=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;

ifl<j then sort(l,j);

ifi<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] dom:=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 m1do//分解m1

if m1 modi=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.

推薦閱讀：

相关文章