9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

tyvj部分题解



主站题库

p1000 A+B Problem 【背景 】 为大家熟悉本系统创建本题! 【描述】 输入两个自然数,输出他们的和 【输入格式】 输出两个自然数 x,y 【输出格式】 一个数,即 x 和 y 的和 【样例输入】 125 300 【样例输出】 425 【时间限制】 各个测试点 1s 【题解】 这倒我就不讲了,没什么好注意。 【参考程序】 progra

m ghfjk; var a,b:longint; begin readln(a,b); writeln(a+b); end. p1001 第 K 极值 【描述】 给定一个长度为 N(0<n<=10000)的序列,保证每一个序列 中的数字 a[i]是小于 maxlongint 的非负整数,编程要求 求出整个序列中第 k 大的数字减去第 k 小的数字的值 m,并 判断 m 是否为质数。(0<k<=n) 【输入格式】 第一行为 2 个数 n,k(含义如上题) 第二行为 n 个数,表示这个序列 【输出格式】 : 如果 m 为质数则 第一行为'YES'(没有引号) 第二行为这个数 m 否则 第一行为'NO' 第二行为这个数 m 【样例输入】

52 12345 【样例输出】 YES 2 【时间限制】 各个测试点 1s 【数据范围】 20%数据满足 0<n<=10 50%数据满足 0<n<=5000 100%数据满足 0<n<=10000 a[i]<=maxlongint 【注释】 对于第 K 大的详细解释: 如果一个序列为 1 2 2 2 2 3 第1大 为3 第2大 为2 第3大 为2 第4大 为2 第5大 为1 第 K 小与上例相反 另外需要注意的是 最小的质数是 2,如果小于 2 的话,请直接输出 NO 【题解】 这道题很简单,先快排,在按要求判断该数是否为素数。 注释里的话一定要看!(有很多人吃亏) ! 【参考程序】 program dfj; var n,k,i:longint; a:array[1..10000]of longint;

procedure qs(l,r:longint); var i,j,m,t:longint; begin i:=l; j:=r; m:=a[(l+r) DIV 2]; repeat while a[i]<m do inc(i); while a[j]>m do dec(j); if i<=j then begin t:=a[i]; a[i]:=a[j];

a[j]:=t; inc(i); dec(j); end; until i>j; if i<r then qs(i,r); if l<j then qs(l,j); end;

function prime(x:longint):boolean; var i:longint; begin if x<=1 then exit(false); if x=2 then exit(true); for i:=2 to trunc(sqrt(x)) do if x mod i=0 then exit(false); exit(true); end;

begin readln(n,k); for i:=1 to n do read(a[i]); qs(1,n); if prime(a[n-k+1]-a[k])then writeln('YES') else writeln('NO'); writeln(a[n-k+1]-a[k]); end. p1002 谁拿了最多奖学金 【描述】 某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种,获取的条件各自不同: 1)院士奖学金,每人 8000 元,期末平均成绩高于 80 分(>80) ,并且在本学期内发表 1 篇或 1 篇以上论文 的学生均可获得; 2)五四奖学金,每人 4000 元,期末平均成绩高于 85 分(>85) ,并且班级评议成绩高于 80 分(>80)的学 生均可获得; 3)成绩优秀奖,每人 2000 元,期末平均成绩高于 90 分(>90)的学生均可获得; 4)西部奖学金,每人 1000 元,期末平均成绩高于 85 分(>85)的西部省份学生均可获得; 5)班级贡献奖,每人 850 元,班级评议成绩高于 80 分(>80)的学生干部均可获得; 只要符合条件就可以得奖,每项奖学金的获奖人数没有限制,每名学生也可以同时获得多项奖学金。例如 姚林的期末平均成绩是 87 分,班级评议成绩 82 分,同时他还是一位学生干部,那么他可以同时获得五四 奖学金和班级贡献奖,奖金总数是 4850 元。 现在给出若干学生的相关数据,请计算哪些同学获得的奖金总数最高(假设总有同学能满足获得奖学金的 条件) 。

【输入格式】 输入的第一行是一个整数 N(1<=N<=100) ,表示学生的总数。接下来的 N 行每行是一位学生的数据,从 左向右依次是姓名,期末平均成绩,班级评议成绩,是否是学生干部,是否是西部省份学生,以及发表的 论文数。姓名是由大小写英文字母组成的长度不超过 20 的字符串(不含空格) ;期末平均成绩和班级评议 成绩都是 0 到 100 之间的整数(包括 0 和 100) ;是否是学生干部和是否是西部省份学生分别用一个字符表 示,Y 表示是,N 表示不是;发表的论文数是 0 到 10 的整数(包括 0 和 10) 。每两个相邻数据项之间用一 个空格分隔。 【输出格式】 输出包括三行,第一行是获得最多奖金的学生的姓名,第二行是这名学生获得的奖金总数。如果有两位或 两位以上的学生获得的奖金最多,输出他们之中在输入文件中出现最早的学生的姓名。第三行是这 N 个学 生获得的奖学金的总数。 【样例输入】 4 YaoLin 87 82 Y N 0 ChenRuiyi 88 78 N Y 1 LiXin 92 88 N N 0 ZhangQin 83 87 Y N 1 【样例输出】 ChenRuiyi 9000 28700 【题解】 快排+字符串处理,仔细一点就可以 AC。 【参考程序】 program jk; var n,i,j,k,l,max:longint; b,c,f,g:array[1..100]of longint; a,d,e:array[1..100]of string; st:string;

procedure init; var i,l:longint; s,t:string; begin readln(n); for i:=1 to n do begin readln(s); l:=pos(' ',s); a[i]:=copy(s,1,l-1); delete(s,1,l); l:=pos(' ',s); t:=copy(s,1,l-1); val(t,b[i]);

delete(s,1,l); l:=pos(' ',s); t:=copy(s,1,l-1); val(t,c[i]); delete(s,1,l); l:=pos(' ',s); d[i]:=copy(s,1,l-1); delete(s,1,l); l:=pos(' ',s); e[i]:=copy(s,1,l-1); delete(s,1,l); val(s,f[i]); end; end;

begin init; fillchar(g,sizeof(g),0); for i:=1 to n do begin if (b[i]>80)and(f[i]>=1)then inc(g[i],8000); if (b[i]>85)and(c[i]>80)then inc(g[i],4000); if b[i]>90 then inc(g[i],2000); if (b[i]>85)and(e[i]='Y')then inc(g[i],1000); if (c[i]>80)and(d[i]='Y')then inc(g[i],850); end; max:=0; l:=0; for i:=1 to n do begin l:=l+g[i]; if g[i]>max then begin max:=g[i]; st:=a[i]; end; end; writeln(st); writeln(max); writeln(l); end. P1003 越野跑 【描述】

为了能在下一次跑步比赛中有好的发挥,贝茜在一条山路上开始了她的训练。贝茜希望能在每次训练中 跑得尽可能远,不过她也知道农场中的一条规定: 奶牛独自进山的时间不得超过 M 秒(1 <=M<=10,000,000)。 整条山路被贝茜划分成 T 个长度相同的小段(1 <= T <= 100,000),并且,贝茜用 S_i 表示第 i 个小段的路况。 S_i 为 u,f,d 这 3 个字母之一,它们分别表示 第 i 个小段是上坡、平地,或是下坡。 贝茜要花 U 秒(1<=U<=100)才能跑完一段上坡路,跑完一段平地的耗时是 F 秒(1<=F<=100),跑完一段 下坡路要花 D 秒(1<=D<=100)。注意,沿山路原路返回的时候,原本是上坡路的路段变成了下坡路,原本 是下坡路的路段变成 了上坡路。 贝茜想知道,在能按时返回农场的前提下,她最多能在这条山路上跑多远。 【输入格式】 * 第 1 行: 5 个用空格隔开的整数:M,T,U,F,以及 D *第 2..T+1 行:第 i+1 行为 1 个字母 S_i,描述了第 i 段山路的路况 【输出格式】 *第 1 行:输出 1 个整数,为贝茜在按时回到农场的前提下,最多能跑到多远 【样例输入】 13 5 3 2 1 u f u d f 【样例输出】 3 【题解】 模拟一下跑步的过程。用 s 记录跑到第 i 段路并返回的时间 若 s=m 则输出 i 并退出,若 s>m 则输出 I-1 并退出。 【参考程序】 program dfjk; var i,s,m,t,u,f,d:longint; a:array[1..100000]of char; begin readln(m,t,u,f,d); for i:=1 to t do readln(a[i]); s:=0; for i:=1 to t do begin case a[i] of 'u':s:=s+u+d; 'f':s:=s+2*f; 'd':s:=s+u+d; end;

if s>=m then break; end; if s=m then writeln(i); if s>m then writeln(i-1); end. p1004 滑雪 【描述】 trs 喜欢滑雪。他来到了一个滑雪场,这个滑雪场是一个矩形,为了简便,我们用 r 行 c 列的矩阵来表示 每块地形。为了得到更快的速度,滑行的路线必须向下倾斜。 例如样例中的那个矩形,可以从某个点滑向上下左右四个相邻的点之一。例如 24-17-16-1,其实 25-24-23?3-2-1 更长,事实上这是最长的一条。 【输入】 第 1 行: 两个数字 r,c(1<=r,c<=100),表示矩阵的行列。 第 2..r+1 行:每行 c 个数,表示这个矩阵。 【输出】 仅一行: 输出 1 个整数,表示可以滑行的最大长度。 【样例输入】 55 12345 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 【样例输出】 25 【题解】 这道题用动态规划+记忆化搜索求解 【参考程序】 program gj; const dx:array[1..4]of -1..1=(-1,0,1,0); dy:array[1..4]of -1..1=(0,-1,0,1); var i,j,r,c,max,t:longint; a:array[1..100,1..100]of longint; f:array[1..100,1..100]of longint;

function dfs(x,y:longint):longint; var i,nx,ny,t,temp:longint; begin if f[x,y]>0 then begin dfs:=f[x,y]; exit; end;

t:=1; for i:=1 to 4 do begin nx:=x+dx[i]; ny:=y+dy[i]; if(nx>0)and(nx<=r)and(ny>0)and(ny<=c)then if a[x,y]<a[nx,ny] then begin temp:=dfs(nx,ny)+1; if temp>t then t:=temp; end; end; f[x,y]:=t; dfs:=t; end;

begin readln(r,c); for i:=1 to r do for j:=1 to c do read(a[i,j]); max:=0; fillchar(f,sizeof(f),0); for i:=1 to r do for j:=1 to c do begin t:=dfs(i,j); f[i,j]:=t; if t>max then max:=t; end; writeln(max); end. p1005 采药 【描述】 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。 医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说: “孩子,这 个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间, 在这段时间里, 你可以采到一些草药。 如果你是一个聪明的孩子, 你应该可以让采到的草药的总价值最大。 ” 如果你是辰辰,你能完成这个任务吗? 【输入格式】 输入文件 medic.in 的第一行有两个整数 T(1 <= T <= 1000)和 M(1 <= M <= 100) ,用一个空格隔开, T 代表总共能够用来采药的时间,M 代表山洞里的草药的数目。接下来的 M 行每行包括两个在 1 到 100 之 间(包括 1 和 100)的整数,分别表示采摘某株草药的时间和这株草药的价值。

【输出格式】 输出文件 medic.out 包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价 值。 【样例输入】 70 3 71 100 69 1 12 【样例输出】 3 【题解】 这道题一眼就看出来是 0/1 背包。 用 f[j]表示在时间 j 内的最大采集价值。 则 f[j]:=max{f[j],f[j-t[i]+v[i]} (1<=i<=m,T<=j<=a[i]); 【参考程序】 program uijg; var t,m,i,j:longint; a,b:array[1..100]of longint; f:array[0..1000]of longint; begin fillchar(f,sizeof(f),0); readln(t,m); for i:=1 to m do readln(a[i],b[i]); for i:=1 to m do for j:=t downto a[i] do if f[j-a[i]]+b[i]>f[j] then f[j]:=f[j-a[i]]+b[i]; writeln(f[t]); end.

p1006 isbn 【描述】 每一本正式出版的图书都有一个 ISBN 号码与之对应,ISBN 码包括 9 位数字、1 位识别码和 3 位分隔符, 其规定格式如“x-xxx-xxxxx-x” ,其中符号“-”就是分隔符(键盘上的减号) ,最后一位是识别码,例如 0-670-82162-4 就是一个标准的 ISBN 码。ISBN 码的首位数字表示书籍的出版语言,例如 0 代表英语;第一 个分隔符“-”之后的三位数字代表出版社,例如 670 代表维京出版社;第二个分隔符后的五位数字代表该 书在该出版社的编号;最后一位为识别码。 识别码的计算方法如下: 首位数字乘以 1 加上次位数字乘以 2??以此类推,用所得的结果 mod11,所 得的余数即为识别码,如果余数为 10,则识别码为大写字母 X。例如 ISBN 号码 0-670-82162-4 中的识别码 4 是这样得到的:对 067082162 这 9 个数字,从左至右,分别乘以 1,2,...,9,再求和,即 0×1+6×2+?? +2×9=158,然后取 158 mod 11 的结果 4 作为识别码。 你的任务是编写程序判断输入的 ISBN 号码中识别码是否正确,如果正确,则仅输出“Right” ;如果错误,

则输出你认为是正确的 ISBN 号码。 【输入格式】 输入文件 isbn.in 只有一行,是一个字符序列,表示一本书的 ISBN 号码(保证输入符合 ISBN 号码的格式 要求) 。 【输出格式】 输出文件 isbn.out 共一行,假如输入的 ISBN 号码的识别码正确,那么输出“Right” ,否则,按照规定的格 式,输出正确的 ISBN 号码(包括分隔符“-”。 ) 【样例输入】 【样例 1】 0-670-82162-4 【样例 2】 0-670-82162-0 【样例输出】 【样例 1】 Right 【样例 2】 0-670-82162-4 【题解】 这道题模拟一下就可以。noip 总有一些送分题。 【参考程序】 program dhj; const a:array['0'..'9']of longint=(0,1,2,3,4,5,6,7,8,9); var t,i,j,k:longint; s:string; begin readln(s); k:=0; for i:=1 to length(s)-2 do if s[i] in ['0'..'9'] then begin inc(k); t:=t+k*a[s[i]]; end; t:=t mod 11; if(t=10)and(s[length(s)]='X')then begin writeln('Right'); halt; end; if t=a[s[length(s)]] then begin writeln('Right'); halt; end;

for i:=1 to length(s)-1 do write(s[i]); if t<10 then writeln(t) else writeln('X'); end. p1007 排座椅 【描述】 上课的时候总有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主 任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的 D 对同学上课时会交头接耳。 同学们在教室中坐成了 M 行 N 列,坐在第 i 行第 j 列的同学的位置是(i,j) ,为了方便同学们进出,在教 室中设置了 K 条横向的通道,L 条纵向的通道。于是,聪明的小雪想到了一个办法,或许可以减少上课时 学生交头接耳的问题:她打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条通道隔开了两 个会交头接耳的同学,那么他们就不会交头接耳了。请你帮忙给小雪编写一个程序,给出最好的通道划分 方案。在该方案下,上课时交头接耳的学生对数最少。 【输入格式】 输入的第一行, 5 各用空格隔开的整数, 有 分别是 M, N,K, D(2<=N, L, M<=1000, 0<=K<M,0<=L<N, D<=2000) 。接下来 D 行,每行有 4 个用空格隔开的整数,第 i 行的 4 个整数 Xi,Yi,Pi,Qi,表示坐在位 置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳(输入保证他们前后相邻或者左右相邻) 。输入数据保证最优方案 的唯一性。 【输出格式】 第一行包含 K 个整数,a1a2??aK,表示第 a1 行和 a1+1 行之间、第 a2 行和第 a2+1 行之间、?、第 aK 行和第 aK+1 行之间要开辟通道,其中 ai< ai+1,每两个整数之间用空格隔开(行尾没有空格) 。 第二行包含 L 个整数,b1b2??bk,表示第 b1 列和 b1+1 列之间、第 b2 列和第 b2+1 列之间、?、第 bL 列和第 bL+1 列之间要开辟通道,其中 bi<bi+1,每两个整数之间用空格隔开(行尾没有空格) 。 【样例输入】 45123 4243 2333 2524 【样例输出】 2 24 【题解】 快排+贪心,每次选能隔开最多人数的排和列。最后快排一下就可以了。 【参考程序】 program gfjh; type arr=array[1..1000]of longint; var n,m,k,l,d,i,j:longint; x,y,p,q:array[1..2000]of longint; hang,lie,b,c:arr;

procedure qs(l,r:longint;var a:arr); var i,j,m,t:longint;

begin i:=l; j:=r; m:=a[(l+r) div 2]; repeat while a[i]>m do inc(i); while a[j]<m do dec(j); if i<=j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; t:=b[i]; b[i]:=b[j]; b[j]:=t; inc(i); dec(j); end; until i>j; if i<r then qs(i,r,a); if l<j then qs(l,j,a); end;

begin fillchar(hang,sizeof(hang),0); fillchar(lie,sizeof(lie),0); readln(m,n,k,l,d); for i:=1 to d do read(x[i],y[i],p[i],q[i]); for i:=1 to m-1 do for j:=1 to d do if y[j]=q[j] then if (x[j]+p[j])div 2=i then inc(hang[i]); for i:=1 to n-1 do for j:=1 to d do if x[j]=p[j] then if (y[j]+q[j])div 2=i then inc(lie[i]); for i:=1 to m do b[i]:=i; qs(1,m,hang); for i:=k downto 1 do c[i]:=b[i];

qs(1,k,c); for i:=k downto 2 do write(c[i],' '); writeln(c[1]); for i:=1 to n do b[i]:=i; qs(1,n,lie); for i:=l downto 1 do c[i]:=b[i]; qs(1,l,c); for i:=l downto 2 do write(c[i],' '); writeln(c[1]); end. p1008 传球游戏 【描述】 上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。 游戏规则是这样的:n 个同学站成一个圆圈,其中的一个同学手里拿着一个球,当老师吹哨子时开始传球, 每个同学可以把球传给自己左右的两个同学中的一个 (左右任意) 当老师再次吹哨子时, , 传球停止, 此时, 拿着球没传出去的那个同学就是败者,要给大家表演一个节目。 聪明的小蛮提出一个有趣的问题:有多少种不同的传球方法可以使得从小蛮手里开始传的球,传了 m 次以 后,又回到小蛮手里。两种传球的方法被视作不同的方法,当且仅当这两种方法中,接到球的同学按接球 顺序组成的序列是不同的。比如有 3 个同学 1 号、2 号、3 号,并假设小蛮为 1 号,球传了 3 次回到小蛮手 里的方式有 1->2->3->1 和 1->3->2->1,共 2 种。 【输入格式】 输入文件 ball.in 共一行,有两个用空格隔开的整数 n,m(3<=n<=30,1<=m<=30) 。 【输出格式】 输出文件 ball.out 共一行,有一个整数,表示符合题意的方法数。 【样例输入】 33 【样例输出】 2 【题解】 动态规划 f[i,k]表示球在人 i 手中,传 k 此的方案 s 数 每次球总是从 i-1 人或 i+1 人手中传过来,所以 f[i,k]:=f[i-1,k-1+f[i+1,k-1]; (1<=i<=n,1<=k<=m) 输出[f1,m]。 边界:f[1,0]:=1;(传 0 次,方案数为 1). 注意处理 i=1 和 i=n 的情况。 【参考程序】 program gf;

var i,k,n,m:longint; f:array[1..30,0..30]of longint; begin readln(n,m); fillchar(f,sizeof(f),0); f[1,0]:=1; for k:=1 to m do begin f[1,k]:=f[n,k-1]+f[2,k-1]; for i:=2 to n-1 do f[i,k]:=f[i-1,k-1]+f[i+1,k-1]; f[n,k]:=f[1,k-1]+f[n-1,k-1]; end; writeln(f[1,m]); end. p1010 笨小猴 【描述】 笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用 这种方法去选择选项的时候选对的几率非常大! 这种方法的具体描述如下:假设 maxn 是单词中出现次数最多的字母的出现次数,minn 是单词中出现次数最 少的字母的出现次数,如果 maxn-minn 是一个质数,那么笨小猴就认为这是个 Lucky word 这样的单词很可 能就是正确的答 案。 【输入格式】 输入只有一行,是一个单词,其中只可能出现小写字母,并且长度小于 100。 【输出格式】 输出共两行,第一行是一个字符串,假设输入的的单词是 Lucky Word,那么输出“Lucky Word” ,否则输 出“No Answer” ; 第二行是一个整数,如果输入单词是 Lucky Word,输出 maxn-minn 的值,否则输出 0。 【样例输入】 输入样例 1 error 输入样例 2 olympic 【样例输出】 输出样例 1 Lucky Word 2 输出样例 2 No Answer 0 【题解】 简单的字符串处理+素数判断

【参考程序】 program gdfk; var max,min,j:longint; a:array['a'..'z']of longint; s:string; i:char;

function prime(x:longint):boolean; var i:longint; begin if x<=1 then exit(false); if x=2 then exit(true); for i:=2 to trunc(sqrt(x)) do if x mod i=0 then exit(false); exit(true); end;

begin fillchar(a,sizeof(a),0); readln(s); for j:=1 to length(s) do inc(a[s[j]]); max:=0; min:=100; for i:='a' to 'z' do if a[i]<>0 then begin if a[i]>max then max:=a[i]; if a[i]<min then min:=a[i]; end; if prime(max-min) then begin writeln('Lucky Word'); writeln(max-min); end else begin writeln('No Answer'); writeln(0); end; end. p1011 传纸条 【描述】

小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排 做成一个 m 行 n 列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸 运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,小渊坐在矩阵的左上角, 坐标(1,1),小轩坐在矩阵的右下角,坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递,从小轩 传给小渊的纸条只可以向上或者向左传递。在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩 给他回复。班里每个同学都可以帮他们传递,但只会帮他们一次,也就是说如果此人在小渊递给小轩纸条 的时候帮忙,那么在小轩递给小渊的时候就不会再帮忙。反之亦然。还有一件事情需要注意,全班每个同 学愿意帮忙的好感度有高有低(注意:小渊和小轩的好心程度没有定义,输入时用 0 表示) ,可以用一个 0-100 的自然数来表示,数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条,即 找到来回两条传递路径,使得这两条路径上同学的好心程度只和最大。现在,请你帮助小渊和小轩找到这 样的两条路径。 【输入格式】 输入文件 message.in 的第一行有 2 个用空格隔开的整数 m 和 n,表示班里有 m 行 n 列(1<=m,n<=50) 。 接下来的 m 行是一个 m*n 的矩阵,矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度。每行 的 n 个整数之间用空格隔开。 【输出格式】 输出文件 message.out 共一行,包含一个整数,表示来回两条路上参与传递纸条的学生的好心程度之和的最 大值。 【样例输入】 33 039 285 570 【样例输出】 34 【题解】 这题与二取方格数类似,用暴力枚举+dp 可以过 用 f[i1,j1,i2,j2]表示到达点(i1,j1),(i2,j2)的最大好心程度。则: 令 t=max(f[i1-1,j1,i2-1,j2], f[i1-1,j1,i2,j2-1], f[i1,j1-1,i2,j2-1], f[i1,j1-1,i2-1,j2]); 若(i1=i2)and(j1=j2)则 f[i1,j1,i2,j2]:=t+a[i1,j1]; 否则 f[i1,j1,i2,j2]:=t+a[i1,j1]+a[i2,j2]; 最后输出 f[m,n,m,n]。 【参考程序】 program gjkdr; var m,n,i1,j1,i2,j2,t:longint; a:array[1..51,1..51]of longint; f:array[0..51,0..51,0..51,0..51]of longint;

function max(a,b:longint):longint; begin if a>b then exit(a)

else exit(b); end;

begin readln(m,n); for i1:=1 to m do for j1:=1 to n do read(a[i1,j1]); fillchar(f,sizeof(f),0); for i1:=1 to m do for j1:=1 to n do for i2:=1 to m do for j2:=1 to n do begin t:=max(max(f[i1-1,j1,i2-1,j2], f[i1-1,j1,i2,j2-1]), max(f[i1,j1-1,i2,j2-1], f[i1,j1-1,i2-1,j2])); if(i1=i2)and(j1=j2)then f[i1,j1,i2,j2]:=t+a[i1,j1] else f[i1,j1,i2,j2]:=t+a[i1,j1]+a[i2,j2]; end; writeln(f[m,n,m,n]); end. p1012 火柴棒 【描述】 给你 n 根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的 A、B、C 是用火柴棍拼出的整数 (若该数非零,则最高位不能是 0) 。用火柴棍拼数字 0-9 的拼法如图所示:0:=6;1:=2;2:=5;3:=5; 4:=4; 5:=5;6:=6;7:=3;8:=7;9:=6 注意: 1. 加号与等号各自需要两根火柴棍 2.如果 A≠B,则 A+B=C 与 B+A=C 视为不同的等式(A、B、C>=0) 3. n 根火柴棍必须全部用上 【输入格式】 输入文件 matches.in 共一行,又一个整数 n(n<=24) 。 【输出格式】 输出文件 matches.out 共一行,表示能拼成的不同等式的数目。 【样例输入】 【输入样例 1】 14 【输入样例 2】 18 【样例输出】

【输出样例 1】 2 【输出样例 2】 9 【题解】 先生成 0~1000(可以更少)所需的火柴棒数。 再枚举每个数。 【参考程序】 program ghkl; const o:array[0..9]of longint=(6,2,5,5,4,5,6,3,7,6); var n,i,j,s:longint; a:array[0..2000]of longint;

function ss(x:longint):longint; var t:longint; begin t:=0; repeat inc(t,o[x mod 10]); x:=x div 10; until x=0; exit(t); end;

begin s:=0; for i:=0 to 2000 do a[i]:=ss(i); readln(n); n:=n-4; for i:=0 to 1000 do for j:=0 to 1000 do if a[i]+a[j]+a[i+j]=n then inc(s); writeln(s); end. p1013 找啊找啊找 GF 【描述】 "找啊找啊找 GF,找到一个好 GF,吃顿饭啊拉拉手,你是我的好 GF.再见.""诶,别再见啊..." 七夕...七夕...七夕这个日子,对于 sqybi 这种单身的菜鸟来说是多么的痛苦...虽然他听着这首叫做"找啊找啊 找 GF"的歌,他还是很痛苦.为了避免这种痛苦,sqybi 决定要给自己找点事情干.他去找到了七夕模拟赛的负责 人 zmc MM,让她给自己一个出题的任务.经过几天的死缠烂打,zmc MM 终于同意了. 但是,拿到这个任务的 sqybi 发现,原来出题比单身更让人感到无聊-_-....所以,他决定了,要在出题的同时去办

另一件能够使自己不无聊的事情--给自己找 GF. sqybi 现在看中了 n 个 MM,我们不妨把她们编号 1