当前位置:首页 >> 学科竞赛 >>

Codevs.cv题库 分析及参考代码【天梯 白银级别】


【天梯 白银级别】 1075 明明的随机数
2006 年 NOIP 全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 查看运行结果 题目描述 Description 明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先 用计算机生成了 N 个 1 到 1000 之间的随机整数(N≤100),对于其中重复的

数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。 然后再把这些数从小到大排序, 按照排好的顺序去找同学做调查。请你协助明明 完成“去重”与“排序”的工作。 输入描述 Input Description 有 2 行,第 1 行为 1 个正整数,表示所生成的随机数的 N 个数:

第 2 行有 N 个用空格隔开的正整数,为所产生的随机数 输出描述 Output Description 第 1 行为 1 个正整数 M,表示不相同的随机数的个数。第 2 行为 M 个用空格 隔开的正整数,为从小 到大排好序的不相同的随机数。 样例输入 Sample Input 10 20 40 32 67 40 20 89 300 400 15 样例输出 Sample Output 8 15 20 32 40 67 89 300 400 数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开
排序 NOIP 全国联赛普及组 大陆地区 2006 年
【分析】可以考虑桶排序 【参考程序】 program aa; var n,i,ans,x:integer; f:array[1..1000]of integer; begin readln(n); fillchar(f,sizeof(f),0); for i:=1 to n do begin read(x); f[x]:=1; end; ans:=0; for i:=1 to 1000 do if f[i]>0 then ans:=ans+1; writeln(ans); for i:=1 to 1000 do if f[i]>0 then write(i,' '); end.

1083 Cantor 表
1999 年 NOIP 全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下 面这一张表来证明这一命题的: 1/1 1/2 1/3 1/4 1/5 ? 2/1 2/2 2/3 2/4 ? 3/1 3/2 3/3 ? 4/1 4/2 ? 5/1 ? ? 我们以 Z 字形给上表的每一项编号。第 一项是 1/1,然后是 1/2,2/1,3/1,2/2,?

输入描述 Input Description 整数 N(1≤N≤10000000) 输出描述 Output Description 表中的第 N 项 样例输入 Sample Input 7 样例输出 Sample Output 1/4 数据范围及提示 Data Size & Hint 见描述

分类标签 Tags 点此展开
【参考答案】 【分析】直接模拟 【源程序】 一、 Program cantor; Var n,i,j,a,b:longint; Begin readln(n); a:=1;b:=1;j:=1; for i:=2 to n do case j of 1: if a=1 then begin inc(b);j:=2;end else begin dec(a); inc(b);end; 2: if b=1 then begin inc(a);j:=1;end else begin inc(a); dec(b);end; end; writeln(a,'/',b); End. 二、 program long; var i,j,k,n:longint; begin

readln(n); k:=1; while n>k do begin n:=n-k; k:=k+1; end; if k mod 2=0 then writeln(n,'/',k-n+1) else writeln(k-n+1,'/',n); end.

1076 排序
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description

给出 n 和 n 个整数,希望你从小到大给他们排序
输入描述 Input Description

第一行一个正整数 n

第二行 n 个用空格隔开的整数
输出描述 Output Description 输出仅一行,从小到大输出 n 个用空格隔开的整数 样例输入 Sample Input 3 3 1 2 样例输出 Sample Output 1 2 3 数据范围及提示 Data Size & Hint 1<=n<=100000

分类标签 Tags 点此展开
【参考代码 快排】 program aa; const max=100000; type

ty=array[1..max]of longint; var a:ty; i,h,g,n:longint; procedure quicksort(var b:ty;var s,t:longint); var i,j,k,x,u,v:longint; begin if s<t then begin i:=s;j:=t;k:=b[s];x:=b[s]; repeat while (b[j]>k) and (i<j) do j:=j-1; if i<j then begin b[i]:=b[j]; i:=i+1; end; while (b[i]<k) and (i<j) do i:=i+1; if i<j then begin b[j]:=b[i]; j:=j-1; end; until i=j; b[i]:=x; u:=j-1; v:=j+1; quicksort(b,s,u); quicksort(b,v,t); end; end; begin readln(n); for i:=1 to n do read(a[i]); h:=1;g:=n; quicksort(a,h,g); for i:=1 to n-1 do write(a[i],' '); writeln(a[n]); end.

1083 Cantor 表
1999 年 NOIP 全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下 面这一张表来证明这一命题的: 1/1 1/2 1/3 1/4 1/5 ? 2/1 2/2 2/3 2/4 ? 3/1 3/2 3/3 ? 4/1 4/2 ? 5/1 ? ? 我们以 Z 字形给上表的每一项编号。第 一项是 1/1,然后是 1/2,2/1,3/1,2/2,?

输入描述 Input Description 整数 N(1≤N≤10000000) 输出描述 Output Description 表中的第 N 项 样例输入 Sample Input 7 样例输出 Sample Output 1/4 数据范围及提示 Data Size & Hint 见描述

分类标签 Tags 点此展开
【参考代码 找规律,直接输出】 Program cantor; Var n,i,j,a,b:longint; Begin readln(n); a:=1;b:=1;j:=1; for i:=2 to n do case j of 1: if a=1 then begin inc(b);j:=2;end else begin dec(a); inc(b);end; 2: if b=1 then begin inc(a);j:=1;end else begin inc(a); dec(b);end; end; writeln(a,'/',b); End.

1842 递归第一次
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver

题目描述 Description 同学们在做题时常遇到这种函数 f(x)=5 (x>=0) f(x)=f(x+1)+f(x+2)+1 (x<0) 下面就以这个函数为题做一个递归程序吧 输入描述 Input Description 一个数表示 f(x)中 x 值 大家注意就一个数,前面代表样例编号 输出描述 Output Description 一个数表示值 大家注意就一个数,前面代表样例编号 样例输入 Sample Input 样例一:0 样例二:-5 样例输出 Sample Output 样例一:5 样例二:77 数据范围及提示 Data Size & Hint x>=-30
【参考代码】 program aa; var k,ans:longint; function han(x:integer):longint; begin if x>=0 then han:=5 else han:=han(x+1)+han(x+2)+1; end; begin readln(k); ans:=han(k); write(ans); end.

1160 蛇形矩阵
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description

小明玩一个数字游戏,取个 n 行 n 列数字矩阵(其中 n 为不超过 100 的奇数), 数字的填补方法为:在矩阵中心从 1 开始以逆时针方向绕行,逐圈扩大,直到 n 行 n 列填满数字,请输出该 n 行 n 列正方形矩阵以及其的对角线数字之和. 输入描述 Input Description n(即 n 行 n 列) 输出描述 Output Description n+1 行,n 行为组成的矩阵,最后一行为对角线数字之和 样例输入 Sample Input 3 样例输出 Sample Output 5 4 3 6 1 2 7 8 9 25 数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开
模拟
【参考代码 1 用坐标方式计算:1 的位置为原点,用逆时针的方式输出一直到 n*n,因为 n

为不超过 100 的奇数,故数据类型得用 longint;输出 ans 时只要 x 和 y 的绝对 值相等即可加进来】
program aa; var x,y,i,j,k,n,m,ans,nsq:longint; s:array[-100..100,-100..100]of longint; begin fillchar(s,sizeof(s),0); readln(n); nsq:=n*n; x:=0; y:=0; ans:=0; i:=1; k:=1; s[x,y]:=i; while i<=nsq do case k of 5: k:=1; 4: begin x:=x+1; inc(i); s[x,y]:=i; 1: begin y:=y+1; inc(i); s[x,y]:=i; 2: begin x:=x-1; inc(i); s[x,y]:=i; 3: begin y:=y-1; inc(i); s[x,y]:=i; end; for x:=-(n div 2) to (n div 2) do begin for y:=-(n div 2) to (n div 2) do

if s[x,y+1]=0 then inc(k); if s[x-1,y]=0 then inc(k); if s[x,y-1]=0 then inc(k); if s[x+1,y]=0 then inc(k);

end; end; end; end;

begin if s[x,y]>0 then write(s[x,y],' '); if abs(x)=abs(y) then ans:=ans+s[x,y]; end; writeln; end; writeln(ans); end. 【参考代码二:用二维数组的存储方式,先计算出中心点的坐标,然后按逆时针输出数字序 列;注意最后输出的时候可以有两种情况的数据相加:一种是横纵下标相等的元素,还有一 种是横纵下标的和等于 n+1 这样的元素值,最终 1 被加了 2 遍,需要在结果中将 1 减掉】 program aa; var x,y,fx,ans,k,n:longint; yz:array[1..200,1..200] of longint; begin readln(n); for x:=1 to 200 do for y:=1 to 200 do yz[x,y]:=0; fx:=1; ans:=0; x:=(n div 2)+1; y:=(n+1) div 2; yz[x,y]:=1; for k:=2 to n*n do case (fx mod 4) of 1:begin y:=y+1; yz[x,y]:=k; if yz[x-1,y]=0 then fx:=fx+1; end; 2:begin x:=x-1; yz[x,y]:=k; if yz[x,y-1]=0 then fx:=fx+1; end; 3:begin y:=y-1; yz[x,y]:=k; if yz[x+1,y]=0 then fx:=fx+1; end; 0:begin x:=x+1; yz[x,y]:=k; if yz[x,y+1]=0 then fx:=fx+1; end; end; for x:=1 to n do begin for y:=1 to n do begin write(yz[x,y]:3); if x=y then ans:=ans+yz[x,y]; if x+y=n+1 then ans:=ans+yz[x,y]; end; writeln; end;

writeln(ans-1); end.

1012 最大公约数和最小公倍数问题
2001 年 NOIP 全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 输入二个正整数 x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的 P,Q 的个数 条件: 1.P,Q 是正整数

2.要求 P,Q 以 x0 为最大公约数,以 y0 为最小公倍数. 试求:满足条件的所有可能的两个正整数的个数. 输入描述 Input Description 二个正整数 x0,y0 输出描述 Output Description 满足条件的所有可能的两个正整数的个数 样例输入 Sample Input 3 60 样例输出 Sample Output 4 数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开
数论 NOIP 全国联赛普及组 大陆地区 2001 年
【网络搜集代码】 【样例输入】 3 60 【样例输出】 4

【说明】 http://zhurui250.blog.163.com/blog/static/137270520201162414616998/ 此时的 P Q 分别为: 3 60 15 12 12 15

60 3 所以:满足条件的所有可能的两个正整数的个数共 4 种. 【分析】 gcd(a,b)为数 a 与数 b 的最大公约数(Greatest Common Divisor),lcm(a,b) 为数 a 与数 b 的最小公倍数(least common multiple)。 题目给出了 gcd(p,q)和 lmc(p,q),让我们求解 p,q 的正整数解数。 设 s=lmc(p,q)/gcd(p,q),问题化为求解 xy=s 且 gcd(x,y)=1 的正整数解数。 因式分解就可以得到。 然后枚举 s 的因数 x,得到另一个因数 y,判断 gcd(x.y)是否等于 1 即可。详见 程序 1 这里讲一个更有数学味的算法,希望大家看完。 按照上面的分析, 无非就是把问题转化成为了求 S 的因数集合中,两两互质的数 对的个数。 设 s=a[1]^p[1]*a[2]^p[2]*a[3]^p[3]??*a[n]^p[n] 设 x 设 s 的一个因数,相对的因数是 y=s/x 一定不存在 a[i](s 的质因数),a[i]|x 且 a[i]|y 于是,如果 a[i]|x,因为 s=xy,所以 a[i]^p[i]|x 且,不存在 a[i]|y (符 号打不出来,这里表示不同余) 设 b[i]=a[i]^p[i] s 总共有 n 个质因数,那么答案一定是 2^n 这里用语言简单说明一下,通过刚才的证明,有 xy=s,所以 x 必为 b 数组中若 干不相同元素的乘积,那么不是 x 因数的 b 数组中的元素,一定是 y 的因数, 那么考虑会选择哪几个元素相乘得到 x,必然用二进制加以枚举。 也就是说 s 有 n 中质因数,则一定有 2^n 种答案。详见程序 2 【源程序 1】 Program noip01p2; Var x0,y0,s,p,q,k,ans:longint; function gcd(x,y:longint):longint; begin if x=0 then exit(y); exit(gcd(y mod x,x)); end; Begin read(x0,y0); if y0 mod x0<>0 then begin writeln(0); halt; end; s:=y0 div x0; for k:=1 to trunc(sqrt(s)) do if s mod k=0 then

begin if k*k=s then continue; p:=k; q:=s div k; if gcd(p,q)=1 then inc(ans); end; writeln(ans*2); End. 【源程序 2】 Program noip01p2; Var x0,y0,s,ans,k:longint; Begin read(x0,y0); if y0 mod x0<>0 then begin writeln(0); halt; end; s:=y0 div x0; k:=2; ans:=1; while k<=s do begin if s mod k=0 then begin while s mod k=0 do s:=s div k; ans:=ans*2; end; inc(k); end; writeln(ans); End. 【参考代码 1】 var x1,x2,i,j,s,y,r,a,b:longint; begin readln(x1,x2); repeat i:=i+x1; j:=0; repeat j:=j+x1; a:=j; b:=i;

repeat if a<b then begin r:=a; a:=b; b:=r; end; a:=a-b; until a=0; if (i*j div x1 =x2) and (b=x1 ) then s:=s+1; until j>=x2; until i>=x2 ; write(s); end. 【参考代码 2】 var x0,y0,n,divs:longint; begin read(x0,y0); if (y0 mod x0<>0) then begin writeln(0); exit; end; x0:=y0 div x0; if (x0=1) then begin writeln(1); exit; end; divs:=2; n:=0; if (x0>1) then begin if (x0 mod divs=0) then begin n:=n+1; while (x0 mod divs=0) do x0:=x0 div divs; end; end; divs:=3; while (x0>1) do begin if (x0 mod divs=0) then begin n:=n+1; while (x0 mod divs=0) do x0:=x0 div divs; end; divs:=divs+2; end;

x0:=1 shl n; writeln(x0); end.

1212 最大公约数
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 查看运行结果 题目描述 Description 求两个数 A 和 B 的最大公约数。 1<=A,B<=2^31-1 输入描述 Input Description 两个整数 A 和 B 输出描述 Output Description 最大公约数 gcd(A,B) 样例输入 Sample Input 8 12 样例输出 Sample Output 4
数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开
数论

【参考代码:辗转相减法会超时,用辗转相除法】 program aa; var a,b,t:longint; function gcd(x,y:longint):longint; var r:longint; begin if (x mod y=0) then gcd:=y else begin r:=x mod y; gcd:=gcd(y,r); end; end; begin read(a,b); if a<b then begin t:=a; a:=b; b:=t; end; write(gcd(a,b)); end.

1430 素数判定
时间限制: 1 s 空间限制: 1000 KB 题目等级 : 青铜 Bronze 题目描述 Description 质数又称素数。指在一个大于 1 的自然数中,除了 1 和此整数自身外,不能被其 他自然数整除的数。 素数在数论中有着很重要的地位。比 1 大但不是素数的数称为合数。1 和 0 既非 素数也非合数。 质数是与合数相对立的两个概念,二者构成了数论当中最基础的 定义之一。 基于质数定义的基础之上而建立的问题有很多世界级的难题,如哥德 巴赫猜想等。 算术基本定理证明每个大于 1 的正整数都可以写成素数的乘积,并 且这种乘积的形式是唯一的。 这个定理的重要一点是, 将 1 排斥在素数集合以外。 如果 1 被认为是素数,那么这些严格的阐述就不得不加上一些限制条件。 概念 只有 1 和它本身两个约数的自然数,叫质数(Prime Number)。(如:由 2÷1=2, 2÷2=1,可知 2 的约数只有 1 和它本身 2 这两个约数,所以 2 就是质数。与之相 对立的是合数:“除了 1 和它本身两个约数外,还有其它约数的数,叫合数。” 如:4÷1=4,4÷2=2,4÷4=1,很显然,4 的约数除了 1 和它本身 4 这两个约数 以外,还有约数 2,所以 4 是合数。) 100 以内的质数有 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47, 53,59,61,67,71,73,79,83,89,97,在 100 内共有 25 个质数。 注:(1)1 既不是质数也不是合数。因为它的约数有且只有 1 这一个约数。 (2)2 和 3 是所有素数中唯一两个连着的数 . 输入描述 Input Description 第一行输入一个正整数 n,n<=30000 输出描述 Output Description 如果该数是质数,则输出\t 否则输出\n 样例输入 Sample Input 输入样例1 13 输入样例2 8 样例输出 Sample Output 样例输出1

\t 样例输出2 \n 数据范围及提示 Data Size & Hint c 或 c++的初学者注意,"\"的意思

分类标签 Tags 点此展开
素数判定 数论 【参考代码】 program aa; var n,i,f:longint; begin readln(n); f:=0; for i:=2 to trunc(sqrt(n)) do begin if n mod i=0 then f:=1; if f=1 then begin write('\n');halt; end; end; if f=0 then writeln('\t'); end.

1474 十进制转 m 进制
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 查看运行结果 题目描述 Description 将十进制数 n 转换成 m 进制数 m<=16 n<=100 输入描述 Input Description 共一行 n和m 输出描述 Output Description 共一个数 表示 n 的 m 进制 样例输入 Sample Input 样例 1:10 2

样例 2:100 15 样例输出 Sample Output 样例 1:1010 样例 2:6A 数据范围及提示 Data Size & Hint 用反向取余法

分类标签 Tags 点此展开
进制转换
【参考代码】 program aa; var x,i,n,m,r:integer; a:array[1..10]of integer; begin read(n,m); for i:=1 to 10 do a[i]:=-1; r:=n mod m; n:=n div m; a[1]:=r; i:=1; repeat r:=n mod m; n:=n div m; i:=i+1; a[i]:=r; until n=0; for x:=i downto 1 do begin if a[x]<=9 then write(a[x]); if a[x]>9 then case a[x] of 10: write('A'); 11: write('B'); 12: write('C'); 13: write('D'); 14: write('E'); 15: write('F'); END; end; end.

1475 m 进制转十进制
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 查看运行结果 题目描述 Description 将 m 进制数 n 转化成一个十进制数 m<=16 题目保证转换后的十进制数<=100 输入描述 Input Description 共一行 n和m 输出描述 Output Description 共一个数 表示 m 进制的 n 化成十进制的数 样例输入 Sample Input 1010 2 样例输出 Sample Output 10 数据范围及提示 Data Size & Hint 乘权累加法

分类标签 Tags
进制转化 【参考代码:初始读入时可以按照字符串的方式读入,用 pos 找出空格的位置从而将 n 和 m 区分开来】 program aa; var m,i,len,ans,l,code:integer; n,s,x:string; a:array[1..10]of integer; function fang(x,y:integer):integer; var p,i:integer; begin IF y=0 then begin fang:=1;exit;end; p:=1; for i:=1 to y do p:=p*x; fang:=p; end;

begin read(s); l:=pos(' ',s); n:=copy(s,1,l-1); x:=copy(s,l+1,length(s)); val(x,m,code); len:=length(n); ans:=0; for i:=len downto 1 do case n[i] of '0','1','2','3','4','5','6','7','8','9' : ans:=ans+(ord(n[i])-48)*fang(m,len-i); 'A' : ans:=ans+10*fang(m,len-i); 'B' : ans:=ans+11*fang(m,len-i); 'C' : ans:=ans+12*fang(m,len-i); 'D' : ans:=ans+13*fang(m,len-i); 'E' : ans:=ans+14*fang(m,len-i); 'F' : ans:=ans+15*fang(m,len-i); end; write(ans); end.

1011 数的计算
2001 年 NOIP 全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 我们要求找出具有下列性质数的个数(包含输入的自然数 n): 先输入一个自然数 n(n<=1000),然后对此自然数按照如下方法进行处理: 1. 2. 不作任何处理; 在它的左边加上一个自然数,但该自然数不能超过原数的一半;

3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止. 输入描述 Input Description 一个数 n 输出描述 Output Description 满足条件的数的个数 样例输入 Sample Input 6 样例输出 Sample Output

6 数据范围及提示 Data Size & Hint 6 个数分别是: 6 16 26 126 36 136

分类标签 Tags 点此展开
递推 数论 NOIP 全国联赛普及组 大陆地区 2001 年
【参考代码 1:用递归实现】 program aa; var ans,n:longint; procedure f(y:longint); var i,s:longint; begin ans:=ans+1; s:=y div 2; for i:=1 to s do if i>1 then f(i) else ans:=ans+1; end; begin read(n); ans:=0; f(n); writeln(ans); end. 【参考代码 2:找规律,偶数和其后的一个数字(如 6 和 7)的方案数是一样的;用递推公 式】 program aa; var i,h,j,m:longint; a:array[1..10000]of longint; begin readln(m); a[1]:=1; a[2]:=2;

a[3]:=2; i:=2; while i<=m do begin i:=i+2; a[i]:=a[i div 2]+a[i-1]; a[i+1]:=a[i]; end; writeln(a[m]); end.

1978 Fibonacci 数列 3
时间限制: 1 s 空间限制: 64000 KB 题目等级 : 青铜 Bronze 查看运行结果 题目描述 Description 斐波纳契数列是这样的数列: f = 1
1

f = 1
2

f = 2
3

f = 3
4

.... f = f
n n-1

+ f

n-2

输入一个整数 n 求f 输入描述 Input Description 一个整数 n, n<= 40 输出描述 Output Description 一个整数 f 样例输入 Sample Input 3 样例输出 Sample Output 2 数据范围及提示 Data Size & Hint n<=40
n n

分类标签 Tags 点此展开
递归 递推 搜索 数论
【参考代码】 program aa; var n:longint; f:array[1..50]of longint; procedure ji; var i:longint; begin f[1]:=1; f[2]:=1; for i:=3 to n do f[i]:=f[i-1]+f[i-2]; end; begin read(n); ji; writeln(f[n]); end.

1501 二叉树最大宽度和高度
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 给出一个二叉树,输出它的最大宽度和高度。 输入描述 Input Description 第一行一个整数 n。 下面 n 行每行有两个数, 对于第 i 行的两个数,代表编号为 i 的节点所连接的两 个左右儿子的编号。如果没有某个儿子为空,则为 0。 输出描述 Output Description 输出共一行,输出二叉树的最大宽度和高度,用一个空格隔开。 样例输入 Sample Input 5 2 3 4 5 0 0

0 0 0 0 样例输出 Sample Output 2 3 数据范围及提示 Data Size & Hint n<16 默认第一个是根节点 以输入的次序为编号 2-N+1 行指的是这个节点的左孩子和右孩子 注意:第二题有极端数据! 1 0 0 这题你们别想投机取巧了,给我老老实实搜索!

分类标签 Tags 点此展开
深度优先搜索 递归 搜索 【参考代码】
program eee; var n,i,maxw,maxd:longint; lc,rc:array[1..10000]of longint; wid:array[1..10000]of longint; procedure go(dep,i:integer); begin if lc[i]>0 then begin inc(wid[dep]); go(dep+1,lc[i]); end; if rc[i]>0 then begin inc(wid[dep]);

go(dep+1,rc[i]); end; if dep>maxd then maxd:=dep; end;

begin readln(n);if n=1 then begin writeln(1,' ',1);exit;end;

for i:=1to n do readln(lc[i],rc[i]); go(1,1); maxw:=wid[1]; wid[1]:=1; for i:=2 to n do if wid[i]>maxw then maxw:=wid[i]; writeln(maxw,' ',maxd); end.

1842 递归第一次
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 同学们在做题时常遇到这种函数 f(x)=5 (x>=0) f(x)=f(x+1)+f(x+2)+1 (x<0) 下面就以这个函数为题做一个递归程序吧 输入描述 Input Description 一个数表示 f(x)中 x 值 大家注意就一个数,前面代表样例编号 输出描述 Output Description 一个数表示值 大家注意就一个数,前面代表样例编号 样例输入 Sample Input 样例一:0 样例二:-5

样例输出 Sample Output 样例一:5 样例二:77 数据范围及提示 Data Size & Hint x>=-30

分类标签 Tags 点此展开
递归 搜索
【参考代码】 program aa; var k,ans:longint; function han(x:integer):longint; begin if x>=0 then han:=5 else han:=han(x+1)+han(x+2)+1; end; begin readln(k); ans:=han(k); write(ans); end.

3038 3n+1 问题
时间限制: 1 s 空间限制: 32000 KB 题目等级 : 白银 Silver 查看运行结果 题目描述 Description 3n+1 问题是一个简单有趣而又没有解决的数学问题。这个问题是由 L. Collatz 在 1937 年提出的。克拉兹问题(Collatz problem)也被叫做 hailstone 问题、 3n+1 问题、 Hasse 算法问题、 Kakutani 算法问题、 Thwaites 猜想或者 Ulam 问题。 问题如下: (1)输入一个正整数 n; (2)如果 n=1 则结束; (3)如果 n 是奇数,则 n 变为 3n+1,否则 n 变为 n/2; (4)转入第(2)步。 克拉兹问题的特殊之处在于: 尽管很容易将这个问题讲清楚,但直到今天仍不能 保证这个问题的算法对所有可能的输入都有效——即至今没有人证明对所有的 正整数该过程都终止。

输入描述 Input Description 第一行是一个整数 T.表示输入数据的组数. 第二行是 T 个正整数 n. 输出描述 Output Description 对于每个正整数 n,每行输出一个数 s,表示 n 通过多少步变换会变成 1,如果 n 无法变成 1,则输出-1. 样例输入 Sample Input 3 1 2 3 样例输出 Sample Output 0 1 7 数据范围及提示 Data Size & Hint 1 <= T <= 100 1 <= n <= 10000

分类标签 Tags 点此展开
暂无标签
【参考代码】 program aa; const max=1000000; var i,t,n,f,m,step:longint; procedure ji(x:longint); begin if x=1 then begin f:=1;exit; end else if odd(x) then begin n:=3*n+1;step:=step+1;f:=0;ji(n);if step>max then step:=-1; exit;end else begin n:=n div 2; step:=step+1;f:=0;ji(n);if step>max then step:=-1;exit;end; end; begin readln(t); for i:=1 to t do begin step:=0; read(n); ji(n); writeln(step);

end; end.

3143 二叉树的序遍历
时间限制: 1 s 空间限制: 32000 KB 题目等级 : 白银 Silver 题目描述 Description 求一棵二叉树的前序遍历,中序遍历和后序遍历 输入描述 Input Description 第一行一个整数 n,表示这棵树的节点个数。 接下来 n 行每行 2 个整数 L 和 R。第 i 行的两个整数 Li 和 Ri 代表编号为 i 的节 点的左儿子编号和右儿子编号。 输出描述 Output Description 输出一共三行,分别为前序遍历,中序遍历和后序遍历。编号之间用空格隔开。 样例输入 Sample Input 5 2 3 4 5 0 0 0 0 0 0 样例输出 Sample Output 1 2 4 5 3 4 2 5 1 3 4 5 2 3 1 数据范围及提示 Data Size & Hint n <= 16

分类标签 Tags 点此展开
递归 搜索
【参考代码】 program aa; type ttp=record data,li,ri:integer; end;

var t:array[1..20] of ttp; n,i:integer; procedure xian(x:integer); begin if x=0 then exit; write(t[x].data,' '); if t[x].li<>0 then xian(t[x].li); if t[x].ri<>0 then xian(t[x].ri); end; procedure hou(x:integer) ; begin if x=0 then exit; if t[x].li<>0 then hou(t[x].li); if t[x].ri<>0 then hou(t[x].ri); write(t[x].data,' '); end; procedure zhong(x:integer); begin if x=0 then exit; if t[x].li<>0 then zhong(t[x].li); write(t[x].data,' '); if t[x].ri<>0 then zhong(t[x].ri); end; begin readln(n); for i:=1 to n do begin t[i].data:=i; readln(t[i].li,t[i].ri); end; xian(1); writeln; zhong(1);writeln; hou(1); end.

3145 汉诺塔游戏
时间限制: 1 s 空间限制: 32000 KB

题目等级 : 白银 Silver 题目描述 Description 汉诺塔问题(又称为河内塔问题),是一个大家熟知的问题。在 A,B,C 三根柱 子上,有 n 个不同大小的圆盘(假设半径分别为 1-n 吧),一开始他们都叠在我 A 上(如图所示),你的目标是在最少的合法移动步数内将所有盘子从 A 塔移动 到 C 塔。 游戏中的每一步规则如下: 1. 每一步只允许移动一个盘子(从一根柱子最上方到另一个柱子的最上方) 2. 移动的过程中,你必须保证大的盘子不能在小的盘子上方(小的可以放在大 的上面,最大盘子下面不能有任何其他大小的盘子)

如对于 n=3 的情况,一个合法的移动序列式: 1 from A to C 2 from A to B 1 from C to B 3 from A to C 1 from B to A 2 from B to C 1 from A to C

给出一个数 n,求出最少步数的移动序列 输入描述 Input Description 一个整数 n 输出描述 Output Description 第一行一个整数 k,代表是最少的移动步数。 接下来 k 行,每行一句话,N from X to Y,表示把 N 号盘从 X 柱移动到 Y 柱。 X,Y 属于{A,B,C} 样例输入 Sample Input 3 样例输出 Sample Output 7 1 from A to C 2 from A to B 1 from C to B 3 from A to C

1 from B to A 2 from B to C 1 from A to C 数据范围及提示 Data Size & Hint n<=10

分类标签 Tags 点此展开
递归 搜索
【参考代码 搬动次数因为要在输出步骤之前输出,因此要先算出来,可以使用公式 step=2n-1】 program aa; var n,step:longint; a,b,c:char; function num(n:longint):longint; var i:integer; begin if n=1 then begin step:=1;num:=step end else begin for i:=1 to n do step:=step*2; num:=step-1; end; end; procedure yi(x:longint;ch1,ch2,ch3:char); begin if x=1 then begin writeln(x,' from ',ch1,' to ',ch3); end else begin yi(x-1,ch1,ch3,ch2); step:=step+1; writeln(x,' from ',ch1,' to ',ch3); yi(x-1,ch2,ch1,ch3); end; end; begin read(n); step:=1; a:='A'; b:='B'; c:='C';

writeln(num(n)); yi(n,a,b,c); end.


相关文章:
Codevs.cv题库 分析及参考代码【天梯 白银级别】
Codevs.cv题库 分析及参考代码【天梯 白银级别】_学科竞赛_高中教育_教育专区。...1212 最大公约数时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 ...
Codevs.cv题库 分析及参考代码【天梯 青铜级别】
Codevs.cv题库 分析及参考代码【天梯 青铜级别】_学科竞赛_高中教育_教育专区。原维基oi,现在改名叫codevs.cn了。这是其中天梯部分的青铜级别题目及代码和部分题解...
更多相关标签:
codevs题库 | codevs天梯 | codevs题库答案 | codevs天梯答案 | codevs | codevs.cn | codevs怎么样 | codevs被攻击 |