2014noip复赛模拟练习11（答案）

新学年就要开始了，爸爸把N元钱给了小青，让他购买一批文具，并作了以下要求：只能买圆珠笔、铅笔和铅笔芯，并且每样至少买一支，总数要超过30支，而且钱要全部花完。当小青去到文具店时，发现圆珠笔8角钱一支、铅笔2角钱一支、铅笔芯1角钱一支。小青怎么买才能符合爸爸的要求呢？请你编个程序帮他算出符合购买要求的所有方案总数。 Input

一个整数N，表示购买文具一共的元数。（1 <= N <= 50） Output

一个整数，即符合购买要求的所有方案总数。 Sample Input 8 Sample Output 135 Source

program ex1294;

var n,i,j,k,sum:integer; begin

readln(n); n:=n*10; sum:=0;

for i:=1 to n div 8 do for j:=1 to n div 2 do begin

k:=n-i*8-j*2;

if (i+j+k>30) and (k>1) then inc(sum); end;

writeln(sum); end.

任意一个数都可以由1、2、3三个数组合而成。如4有以下7种组合方案： 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 2 + 1 + 1 2 + 2 1 + 3 3 + 1

你的问题来了，对于给定的一个数，请你计算出这个整数可以有多少个组合方案，其和由1、2、3组合而成。

数据输入

输入包含多组数据，每一组数据中，输入数据的第一行为一个整数n（1<=n<=20），要分解的数。

数据输出

这个整数的分解的组合数。

样例输入 4 样例输出 7

分析

用f(n)表示将n按照1、2、3分解的方法数 当n=1时,

f(1)=1; {1} 当n=2时，

f(2)=2; {1+1},{2} 当n=3时，

f(3)=3; {1+1+1},{1+2},{2+1},{3} 当 n=k时 (k>=4)

考虑最后添加的一个数字可能是1、2、3。 所以很容易推出递推公式

f(k)=f(k-1)+f(k-2)+f(k-3). var

f:array[1..20] of longint; i,n:longint;

procedure init; begin

assign(input,'divide.in'); assign(output,'divide.out'); reset(input); rewrite(output); end;

procedure endit; begin

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

begin init;

readln(n); f[1]:=1; f[2]:=2;

f[3]:=4;

for i:=4 to n do

f[i]:=f[i-1]+f[i-2]+f[i-3]; writeln(f[n]); endit; end.

聪明的小地鼠

Description 在学校里的试验田里面，种了n个大萝卜，小地鼠又非常的喜欢吃萝卜。它呢，就会出来偷偷的从试验田中偷萝卜。大萝卜都是种在一排地里面，认真的管理员，按照萝卜的位置早早的给萝卜编了号。希望能增加管理，保证产量。谁知道，小地鼠也有了自己的偷萝卜策略。

同样，在这个地里呢，正好也有n只小地鼠，这些小地鼠，他们都是按照顺序出来偷萝卜。小地鼠们根据自己的出场顺序编好号，然后开始根据自己的编号开始偷萝卜。因为，小地鼠的老大（即1号老鼠），很胖，所以他决定多偷萝卜了，而只是拿了1号萝卜，把剩余的萝卜交给他的小弟们。当然，他为了让管理员还能够有点收入，好以后继续种萝卜，就给小弟们，下达了一个命令。即每个地鼠只能拿自己编号倍数的大萝卜，但是不能拿与自己编号相同的萝卜。这样就能稍微给管理员留下一些萝卜了。可怜的管理员，你能告诉他，他最后能够剩下的大萝卜编号。 Input

有一个正整数n，代表大萝卜的个数（即地鼠的个数），(5 < n < 5000) Output 有若干个，代表侥幸存活下来的萝卜的编号。由小到大输出且两个编号间用两个空格隔开。

Sample Input 10 Sample Output 2 3 5 7

Source 海淀区2008年模拟试题（FATSHIP） program ex1131;

var i,j,n,b,t:integer;

a:array[0..5000] of integer; begin

readln(n);

fillchar(a,sizeof(a),0); a[1]:=1;

for i:=2 to n div 2 do begin t:=2; b:=t*i;

while b<=n do begin

a[b]:=1; inc(t);

b:=t*i; end; end;

for i:=1 to n do

if a[i]=0 then write(i,' ':2) ; end.

学生排队

【试题描述】 某班有n个学生（１＜n≤100），编号为１,２,…，n，同时给出k个关系，关系为一对整数〈x,y〉，表示x学生比y学生高。例如： n=4 即４个学生，同时给出５个关系：〈２,１〉 〈２,３〉 〈３,４〉 〈１,３〉 〈１,４〉

此时可以根据关系将学生由高到低排队，上例排队的结果为： ２ １ ３ ４ 数据保证不会出现矛盾，也不会出现不确定的关系。 给出n, k后，按要求求出他们由高到低排队的结果。 【输入描述】

n k（即n个学生数，k个关系）

接下来k行，每行二个整数（表示关系）。 【输出描述】 排队的结果

若n≤6则全部输出，否则输出排队结果的前3个与最后3个（均以一个空格分开）。

【输入样例】 4 5 2 1 2 3 3 4 1 3 1 4

【输出样例】 2 1 3 4

【试题来源】 2009年江苏省小学生信息学（计算机）奥赛

拓扑排序

program ex1766;

var n,i,j,k,x,y,t,l,s,sc:integer; a:array[1..6] of integer;

m:array[1..100,1..100] of integer; p:set of 1..100; begin

readln(n,k); for i:=1 to k do begin

readln(x,y); m[x,y]:=1;

end;

p:=[];s:=0;sc:=0; repeat

for i:=1 to n do begin t:=0;

for j:=1 to n do t:=t+m[j,i]; if (t=0) and not (i in p) then begin

p:=p+[i]; inc(s);

if (s<=3) or (s>n-3) then begin inc(sc);a[sc]:=i; end; for l:=1 to n do m[i,l]:=0; end;

end; until s>=n;

if n<=6 then t:=n else t:=6;

for i:=1 to t-1 do write(a[i],' '); write(a[t]); end.

你将要在元旦演奏一场吉他专场。但你不希望声音平淡，所以你希望每个曲之间都有变化。现在你已经确定了每个曲可以与上一个曲之间的音量的变化量，即每首曲开始，你可以对音量选择增加或减少一个指定的变化值。当然音量不可能为负数，也不能太高，因此必需保证每首曲音量在0和maxLevel之间（包含）。 你的任务是，根据已有的开始音量beginLevel 和每首曲之间的变化量，求出最后一首曲的最大可能音量。如果没有方案，输出 -1。

［输入文件：song.in］

文件第一行有三个整数，n, beginLevel, maxLevel，分别表示曲目数，开始量，最大限制音量。

下面有n-1行整数，第i行整数表示第i首曲与第i+1首曲之间的变化量。 ［输入文件：song.in］ 文件只一行一个数，答案。 [样例：] 4 5 10 5 8 20

本文来源：https://www.bwwdw.com/article/45zd.html