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

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 到 n.请 MM 吃饭是要花钱的,我们假设请 i 号 MM 吃饭要 花 rmb[i]块大洋.而希望骗 MM 当自己 GF 是要费人品的,我们假设请第 i 号 MM 吃饭试图让她当自己 GF 的 行为(不妨称作泡该 MM)要耗费 rp[i]的人品.而对于每一个 MM 来说,sqybi 都有一个对应的搞定她的时间,对 于第 i 个 MM 来说叫做 time[i]. sqybi 保证自己有足够的魅力用 time[i]的时间搞定第 i 个 MM^_^. sqybi 希望搞到尽量多的 MM 当自己的 GF,这点是毋庸置疑的.但他不希望为此花费太多的时间(毕竟七夕赛 的题目还没出),所以他希望在保证搞到 MM 数量最多的情况下花费的总时间最少. sqybi 现在有 m 块大洋,他也通过一段时间的努力攒到了 r 的人品(这次为模拟赛出题也攒 rp 哦~~).他凭借这 些大洋和人品可以泡到一些 MM.他想知道,自己泡到最多的 MM 花费的最少时间是多少. 注意 sqybi 在一个时刻只能去泡一个 MM--如果同时泡两个或以上的 MM 的话,她们会打起来的... 【输入格式】 输入的第一行是 n,表示 sqybi 看中的 MM 数量.接下来有 n 行,依次表示编号为 1, 2, 3, ..., n 的一个 MM 的信 息.每行表示一个 MM 的信息,有三个整数:rmb, rp 和 time.最后一行有两个整数,分别为 m 和 r. 【输出格式】 你只需要输出一行,其中有一个整数,表示 sqybi 在保证 MM 数量的情况下花费的最少总时间是多少 【样例输入】 4 125 216 222 223 55 【样例输出】 13 【数据范围】 对于 20%数据,1<=n<=10; 对于 100%数据,1<=rmb<=100,1<=rp<=100,1<=time<=1000; 对于 100%数据,1<=m<=100,1<=r<=100,1<=n<=100. 【题解】 0/1 背包+附属条件 方程: if f[i,j]<f[i-a[k],j-b[k]]+1 then begin f[i,j]:=f[i-a[k],j-b[k]]+1; t[i,j]:=t[i-a[k],j-b[k]]+time[k]; end if f[i,j]=f[i-a[k],j-b[k]]+1 then if t[i,j]>t[i-a[k],j-b[k]]+time[k] then t[i,j]:=t[i-a[k],j-b[k]]+time[k]; 【参考程序】 program gfj; var n,m,r,i,j,k:longint; a,b,time:array[1..100]of longint; f,t:array[0..100,0..100]of longint;

begin readln(n); for i:=1 to n do readln(a[i],b[i],time[i]); readln(m,r); fillchar(t,sizeof(t),0); fillchar(f,sizeof(f),0); for k:=1 to n do for i:=m downto a[k] do for j:=r downto b[k] do if f[i,j]<f[i-a[k],j-b[k]]+1 then begin f[i,j]:=f[i-a[k],j-b[k]]+1; t[i,j]:=t[i-a[k],j-b[k]]+time[k]; end else if f[i,j]=f[i-a[k],j-b[k]]+1 then if t[i,j]>t[i-a[k],j-b[k]]+time[k] then t[i,j]:=t[i-a[k],j-b[k]]+time[k]; writeln(t[m,r]); end. p1014 乘法游戏 【描述】 乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中,玩家拿出一张牌,得分是 用它的数字乘以它左边和右边的数,所以不允许拿第 1 张和最后 1 张牌。最后一次移动后,这里只剩下两 张牌。 你的目标是使得分的和最小。 例 如 , 如 果 数 是 10*1*50+50*20*5+10*50*5=8000 而拿 50、20、1,总分是 1*50*20+1*20*5+10*1*5=1150。 【输入格式】 输入文件 mul.in 的第一行包括牌数(3<=n<=100),第二行包括 N 个 1-100 的整数,用空格分开 【输出格式】 输出文件 mul.out 只有一个数字:最小得分 【样例输入】 6 10 1 50 50 20 5 【样例输出】 3650 【题解】 用 f[i,j]表示第 i 个数到第 j 个数的最大值 则 f[i,j]:=max{f[i,j],f[i,k]+a[i]*a[k]*a[j]+f[k,j]} (n-2>=i>=1,i+1<=j<=n,i+1<=k<=j-1) 边界:f[i-1,i+1]:=a[i-1]*a[i]*a[i+1] 10 1 50 20 5 , 依 次 拿 1 、 20 、 50 , 总 分 是

【参考程序】 program cvhbkl; var i,j,k,n:longint; a:array[1..100]of longint; f:array[1..100,1..101]of longint; begin fillchar(f,sizeof(f),1); readln(n); for i:=1 to n do begin read(a[i]); f[i,i]:=0; f[i,i+1]:=0; end; for i:=2 to n-1 do f[i-1,i+1]:=a[i-1]*a[i]*a[i+1]; for i:=n-2 downto 1 do for j:=i+1 to n do for k:=i+1 to j-1 do if f[i,j]>f[i,k]+a[i]*a[k]*a[j]+f[k,j] then f[i,j]:=f[i,k]+a[i]*a[k]*a[j]+f[k,j]; writeln(f[1,n]); end. p1015 公路乘车 【描述】 一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一 个费用的单子。没有一辆车子行驶超过 10 公里,一个顾客打算行驶 n 公里(1<=n<=100) ,它可以通过无 限次的换车来完成旅程。最后要求费用最少。 【输入格式】 第一行十个整数分别表示行走 1 到 10 公里的费用(<=500) 。 注意这些数并无实际的经济意义,即行驶 10 公里费用可能比行驶一公里少。 第二行一个整数 n 表示,旅客的总路程数。 【输出格式】 仅一个整数表示最少费用。 【样例输入】 12 21 31 40 49 58 69 79 90 101 15 【样例输出】 147 【题解】 经典的 0/1 背包问题 f[j]表示行驶 j 公里花费的最小费用 f[j]:=min{f[j-i]+a[i],f[j]} (1<=i<=10,i<=j<=n)

【参考程序】 program jgh; var i,n,j:longint; a:array[1..10]of longint; f:array[0..100]of longint; begin for i:=1 to 10 do read(a[i]); readln(n); filldword(f,sizeof(f)div 4,maxlongint div 4); f[0]:=0; for i:=1 to 10 do for j:=i to n do if f[j]>f[j-i]+a[i] then f[j]:=f[j-i]+a[i]; writeln(f[n]); end. p1016 装箱问题 【描述】 有一个箱子容量为 v(正整数,o≤v≤20000),同时有 n 个物品(o≤n≤30),每个物品有一个体积 (正整数)。 要求从 n 个物品中,任取若千个装入箱内,使箱子的剩余空间为最小。 【输入格式】 第一行,一个整数,表示箱子容量; 第二行,一个整数,表示有 n 个物品; 接下来 n 行,分别表示这 n 个物品的各自体积。 【输出格式】 一个整数,表示箱子剩余空间。 【样例输入】 24 6 8 3 12 7 9 7 【样例输出】 0 【题解】 又一经典的 0/1 背包问题 与公路乘车相似 【参考程序】 program gk;

var i,j,n,v:longint; f1,f2:array[0..20000]of boolean; a:array[1..30]of longint; begin readln(v); readln(n); for i:=1 to n do readln(a[i]); fillchar(f1,sizeof(f1),false); f1[0]:=true; for i:=1 to n do begin f2:=f1; for j:=v downto a[i] do if f1[j-a[i]] then f2[j]:=true; f1:=f2; end; for i:=v downto 0 do if f1[i] then begin writeln(v-i); halt; end; end. p1017 冗余关系 【描述】 Mrs.Chen 是一个很认真很称职的语文老师 ...... 所以,当她看到学生作文里的人物关系描述得非常的麻烦的时候,她非常生气,于是宣布:凡是作文里有冗余关 系的,一率罚抄出师表 10 次...同学们非常的恐惧,于是,每当他们写出一篇作文,都要拿来你这个语文兼 OI 天 才这里,问你有没有冗余的关系 ...... 时间一久,你也烦了,于是就想写个程序来代劳 ... 现在这里有一篇作文,有 n 句描述人物关系的句子,描述了 n 个人的关系 每条句子的定义是这样的 X Y 它的意思是:X 认识 Y Y 也认识 X 现在要你求出文中冗余关系的数目. 注意: 假如 A 认识 B,B 认识 C,则 A 也认识 C 冗余关系的定义是指 : 即使没有这条关系,原图的所有关系照样成立. 【输入格式】 第一行,两个整数,表示句子数量(n),表示人数(m)。 接下来 n 行,每行两个数,意义在描述里已经说了. 【输出格式】 一个整数,表示冗余关系的数目. 【样例输入】 33

12 13 23 【样例输出】 1 【题解】 这道题一眼就可以看出用并查集来做 先读入每一对数,将这两对数合并为同一集合。 最后查找有几个集合。 【参考程序】 program gdfj; var data:array[1..1000]of longint; b:array[1..1000]of boolean; n,m,i,j,s,x,y:longint;

procedure initial(a,x:longint); begin data[x]:=a; end;

function find(x:longint):longint; begin find:=data[x]; end;

procedure merge(a,b:longint); var i:longint; begin for i:=1 to n do if data[i]=b then data[i]:=a; end;

begin fillchar(b,sizeof(b),false); for i:=1 to 1000 do initial(i,i); s:=0; readln(n,m); for i:=1 to n do begin readln(x,y); if find(x)<>find(y) then merge(find(x),find(y)); end;

for i:=1 to m do b[data[i]]:=true; for i:=1 to m do if b[i] then inc(s); writeln(s); end. p1018 阶乘统计 【描述】 n 的阶乘定义为 n!=1*2*3*??*n 如 3!=6 n!通常最后会有很多 0,如 5!=120 最后有一个 0,现在统计 n!去除末尾的 0 后,最后 k 位是多少 【输入格式】 第一行包括两个数 n,k 【输出格式】 如果 n!不止 k 位,则输出最后 k 位,如果不足 k 位,则将剩下的全部输出 【样例输入】 72 【样例输出】 04 【数据规模】 100%满足 1<=n<=20 1<=k<=9 【题解】 简单的高精度 【参考程序】 program fgkj; var i,j,l,x,n,k:longint; a:array[1..1000]of longint; begin fillchar(a,sizeof(a),0); readln(n,k); l:=1; a[1]:=1; for i:=1 to n do begin x:=0; for j:=1 to l do begin a[j]:=a[j]*i+x; x:=a[j] div 10; a[j]:=a[j] mod 10; end; while x<>0 do begin inc(l);

a[l]:=x mod 10; x:=x div 10; end; end; i:=1; while a[i]=0 do inc(i); if i+k-1<=l then for j:=i+k-1 downto i do write(a[j]) else for j:=l downto i do write(a[j]); writeln; end. p1019 配对 【描述】 给出 2 个序列 A={a[1],a[2],?,a[n]},B={b[1],b[2],?,b[n]},从 A、B 中各选出 n 个元素进行一一 配对(可以不按照原来在序列中的顺序) ,并使得所有配对元素差的绝对值之和最大。 【输入格式】 输入的第 1 行为 1 个正整数 n 第 2 行包含 n 个正整数,题目中的 A 序列。 第 3 行包含 n 个正整数,题目中的 B 序列。 【输出格式】 一个数,最大配对 【样例输入】 4 2563 1467 【样例输出】 14 【数据规模】 对于 10%的数据,有 n≤20; 对于 30%的数据,有 n≤100; 对于 50%的数据,有 n≤1000; 对于 100%的数据,有 n≤10000;a[i],b[i]≤1000。 【题解】 贪心法。 先将数组 a 从大到小排序,数组 b 从小到大排序 然后 a[i]与 b[i]配对 【参考程序】 program gjkdt; type arr=array[1..10000]of longint; var a,b:arr;

i,j,n,s:longint;

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; 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 readln(n); s:=0; for i:=1 to n do read(a[i]); readln; qs(1,n,a); for i:=1 to n do read(b[i]); qs(1,n,b); for i:=1 to n do inc(s,abs(b[n-i+1]-a[i])); writeln(s); end. p1020 寻找质因数 【描述】 给出 N 个数字,试求质因数最大的数字。 【输入格式】 第一行,一个整数 N,表示数字个数。

接下来 N 行,每行一个整数 A_i,表示给出的数字。 【输出格式】 一个整数,表示质因数最大的数字。 【样例输入】 4 36 38 40 42 【样例输出】 38 【数据规模】 N <= 5000 , A_i <= 20000 【题解】 简单模拟 先求出 1~20000 中的所有素数。 接着逐一试除 【参考程序】 program guk; var i,j,k,l,max,t,n:longint; a,b:array[1..20000]of longint;

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

begin k:=1; b[k]:=2; for i:=3 to 20000 do if prime(i) then begin inc(k); b[k]:=i; end; readln(n); max:=0; l:=1; for i:=1 to n do begin

readln(a[i]); for j:=k downto 1 do if a[i] mod b[j]=0 then begin t:=b[j]; break; end; if t>max then begin max:=t; l:=i; end; end; writeln(a[l]); end. p1021 线段长度 【描述】 数轴上有 N 个点,任意两点连线得到 n(n-1)条线段,试求线段的总长。 【输入格式】 第一行,一个整数 N,表示点数。 接下来 N 行,每行一个整数 X_i,表示点的坐标。 【输出格式】 一个整数,表示线段的总长。 【样例输入】 5 1 5 3 2 4 【样例输出】 40 【题解】 枚举法; 求出每一条线段的距离,再求和。 【参考程序】 program ghd; var i,j,n:longint; a:array[1..10000]of longint; s:qword; begin readln(n); for i:=1 to n do

readln(a[i]); s:=0; for i:=1 to n do for j:=i+1 to n do inc(s,abs(a[j]-a[i])); writeln(s*2); end. p1022 禁止转换 【描述】 对于十进制整数 N,试求其-2 进制表示。 例如,因为 1*1 + 1*-2 + 1*4 + 0*-8 +1*16 + 1*-32 = -13 ,所以(-13)_10 = (110111)_-2。 【输入格式】 一个整数,代表要转换的十进制数。 【输出格式】 一个整数,代表 N 的-2 进制表示。 【样例输入】 -13 【样例输出】 110111 【数据规模】 |N| <= 2000000000 【题解】 与普通进制转换类似,不过若 n mod -2<0 则 n:=n div -2+1 a[i]:=n mod -2+2; 【参考程序】 program cvghdfjk; var i,t,n,r:longint; a:array[1..1000]of longint; begin t:=0; readln(n); repeat inc(t); if n mod -2 <0 then begin a[t]:=n mod -2+2; n:=n div -2+1; end else begin a[t]:=n mod -2; n:=n div -2; end; until n=0;

for i:=t downto 1 do write(a[i]); writeln; end. p1024 外星人的密码 【描述】 XXXX 年突然有外星人造访, 但大家语言不通, 不过科学家们经过研究发现外星人用 26 个英文字母组成的 单词中最长不降子序列的长度来表述数字,且英文字母的排列顺序不同,现给出其排列顺序,再给出外星 人说的每个数字 (其实是每个英文单词, 用空格隔开) 翻译出外星人所说的数字 , (连续输出, 最后加回车) 。 (因为是最长不降子序列,所以数字中没有 0,也就是说外星人的数字是>=1 的数字) 例如 我们正常的字母排列顺序是 abcdefg??.xyz,代表 a<b<c<?..<x<y<z abcd efg hhh ihg 四个字符串的最长不降子序列的长度分别为 4 3 3 1 【输入格式】 第 1,2 行为字符串 含义如题描述 【输出格式】 输出答案 含义如题描述 【样例输入】 abcdefghijklmnopqrstuvwxyz abcd efg hhh ihg 【样例输出】 4331 【题解】 本题就是求最长不下降子序列+字符串处理。 不同的就是字母比较 【参考程序】 program hjk; var a:array['a'..'z'] of longint; b:array[1..255]of char; f:array[1..255]of longint; i,j,n,max:longint; ch:char; begin for i:=1 to 26 do begin read(ch); a[ch]:=i; end; readln; n:=0; while not eoln do

begin read(ch); if ch=' ' then begin for i:=n-1 downto 1 do for j:=i+1 to n do if(a[b[j]]>=a[b[i]])and(f[i]<f[j]+1)then f[i]:=f[j]+1; max:=0; for i:=1 to n do if f[i]>max then max:=f[i]; write(max); n:=0; end else begin inc(n); b[n]:=ch; f[n]:=1; end; end; for i:=n-1 downto 1 do for j:=i+1 to n do if(a[b[j]]>=a[b[i]])and(f[i]<f[j]+1)then f[i]:=f[j]+1; max:=0; for i:=1 to n do if f[i]>max then max:=f[i]; writeln(max); end. p1025 单数?双数? 【描述】 Bessie 那惨无人道的二年级老师搞了一个有 N (1 <= N <= 100) 个正整数 I (1 <= I <= 10^60) 的表叫 Bessie 去判断“奇偶性” (这个词语意思向二年级的学生解释,就是“这个 数是单数,还是双数啊?” )Bessie 被那个表的长度深深地震精到了,竟然跟栋栋的泛做表 格一洋多道题!!毕竟她才刚刚学会数数啊。 ! 写一个程序读入 N 个整数,如果是双数,那麼在独立的一行内输出"even",如果是单数则类似地输出"odd". 【输入格式】 * 第一行: 一个单独的整数: N * 第 2 到第 N+1 行: 第 j+1 行有第 j 个需要判断奇偶性的整数。 【输出格式】 * 第 1..N 行: 第 j 行根据第 j 个整数的奇偶性输出一个单词"even"或者"odd" 【样例输入】

2 1024 5931 【样例输出】 even odd 【题解】 超级大水题,判断最后一位是否为偶数即可。 【参考程序】 program dfgjkdf; var n,i:longint; s:string; begin readln(n); for i:=1 to n do begin readln(s); case s[length(s)] of '0','2','4','6','8':writeln('even'); '1','3','5','7','9':writeln('odd'); end; end; end. p1026 犁田机器人 【描述】 Farmer John 為了让自己从无穷无尽的犁田工作中解放出来,於是买了个新机器人帮助他犁田。这个机器人 可以完成犁田的任务,可惜有一个小小的缺点:这个犁田机器人一次只能犁一个边的长度是整数的长方形 的田地。 因为 FJ 的田地有树和其他障碍物,所以 FJ 设定机器人去犁很多不同的长方形。这些长方形允许重叠。他 给机器人下了 P 个指令,每个指令包含一个要犁长方形的地。这片田地由长方形的左下角和右上角坐标决 定。他很好奇最后到底有多少个方格的地被犁过了。 一般来说,田地被分割為很多小方格。这些方格的边和 x 轴或 y 轴平行。田地的宽度為 X 个方格,高度為 Y 个方格 (1 <= X <= 240; 1 <= Y <= 240). FJ 执行了 I (1 <= I <= 200)个指令, 每个指令包含 4 个整数: Yll, Xll, Xur, Yur (1 <= Xll <=Xur; Xll <= Xur <=X; 1 <= Yll <= Yur; Yll <= Yur <= Y), 分别是要犁的长方形的左下角 坐标和右上角坐标。 机器人会犁所有的横坐标在 Xll..Xur 并且纵坐标 Yll..Yur 范围内的所有方格的地。 可能 这个长方形会比你想像的多一行一列 (就是说从第 Xll 列到第 Xur 列一共有 Xur - Xll + 1 列而不是 Xur - Xll 列) 。 考虑一个 6 方格宽 4 方格高的田地。FJ 进行了 2 个操作(如下) ,田地就被成"*"和"#"了。虽然一般被犁过 的地看起来都是一样的。但是标成"#"可以更清晰地看出最近一次被犁的长方形。 ...... ...... ...... **.... (1,1)(2,4) **.... (1,3)(5,4) #####. **.... #####.

**....

......

**....

**....

一共 14 个方格的地被犁过了。 【输入格式】 * 第一行: 三个由空格隔开的整数: X, Y, I * 第二行到第 I+1 行:第 i+1 行有四个整数 Xll, Yll, Xur, Yur,表示第 i 个指令。 【输出格式】 第一行: 一个单独的整数表示被犁过的方格数。 【样例输入】 642 1124 1354 【样例输出】 14 【题解】 模拟 梨过的田地标记为 true。 最后统计有几个 true。 【参考程序】 program gfjkd; var i,j,n,k,xll,yll,xur,yur,x,y,t:longint; a:array[1..240,1..240]of longint; begin fillchar(a,sizeof(a),0); t:=0; readln(x,y,n); for k:=1 to n do begin readln(xll,yll,xur,yur); for i:=xll to xur do for j:=yll to yur do inc(a[i,j]); end; for i:=1 to 240 do for j:=1 to 240 do if a[i,j]<>0 then inc(t); writeln(t); end. p1027 木瓜地 【描述】 Bessie 不小心游荡出 Farmer John 的田地,而走进了相邻的农民的地。她举起一个木瓜,木 瓜对奶牛来说可是不可多得得美味。这个木瓜林像一般的威斯康星州的田地一样被分割成一个 R 行 C 列的

网格(1 <= R <= 40, 1 <= C <= 40)。Bessie 可以从一个格沿著一条跟 X 轴或 Y 轴平行的直线走到邻接的令一个格。Bessie 发现一开始她自己在木瓜林的(1,1),也就是第 一行第一列慢悠悠地咀嚼著木瓜。 Bessie 总是用她最信赖地双筒望远镜去数每一个邻接的格的低掛著的木瓜的数目。然后她就游荡到那个有 最多没有被吃掉的木瓜的邻接的格子(保证这洋的格子只有一个) 。 按照这种移动方法,最终 Bessie 总是会在(R,C)停止然后吃掉那裡的木瓜。 给定这个木瓜林的大小及每个格的木瓜数 F_ij(1 <= F_ij <= 100), 要求 Bessie 一共吃了 多少个木瓜。 【输入格式】 * 第一行: 两个空格隔开的整数 R 和 C. * 第 2 到 R+1 行: 第 i+1 行有 C 个空格隔开的整数, 表示第 i 行的每个格的水果数。 也就是 F_i1, F_i2, ..., F_iC. 【输出格式】 * 第一行: 一个单独的整数,表示到 Bessie 吃完右下角(R,C)的木瓜回到牛棚的时候為止, 一共在木瓜林吃掉了多少个木瓜。 【样例输入】 34 3345 4532 1742 【样例输出】 39 【题解】 按题目要求模拟,每次选最大的吃。吃过的记为 0 【参考程序】 program fgk; var i,j,r,c,s,x,y,max:longint; a:array[1..40,1..40]of longint; begin readln(r,c); for i:=1 to r do for j:=1 to c do read(a[i,j]); s:=a[1,1]; a[1,1]:=0; i:=1; j:=1; repeat x:=i; y:=j; max:=0; if(x-1>0)and(a[x-1,y]>max)then begin i:=x-1; j:=y;

max:=a[i,j]; end; if(x+1<=r)and(a[x+1,y]>max)then begin i:=x+1; j:=y; max:=a[i,j]; end; if(y-1>0)and(a[x,y-1]>max)then begin i:=x; j:=y-1; max:=a[i,j]; end; if(y+1<=c)and(a[x,y+1]>max)then begin i:=x; j:=y+1; max:=a[i,j]; end; s:=s+a[i,j]; a[i,j]:=0; until(i=r)and(j=c); writeln(s); end. p1028 Bessie 的体重问题 【描述】 Bessie 像她的诸多姊妹一样,因為从 Farmer John 的草地吃了太多美味的草而长出了太多的赘肉。所以 FJ 将她置於一个及其严格的节食计画之中。她每天不能吃多过 H (5 <= H <= 45,000)公斤的乾草。 Bessie 只能吃一整綑乾草; 当她开始吃一綑乾草的之后就再也停不下来了。 她有一个完整的 N (1 <= N <= 500) 綑可以给她当作晚餐的乾草的清单。她自然想要尽量吃到更多的乾草。很自然地,每綑乾草只能被吃一次 (即使在列表中相同的重量可能出现 2 次, 但是这表示的是两綑乾草, 其中每綑乾草最多只能被吃掉一次) 。 给定一个列表表示每綑乾草的重量 S_i (1 <= S_i <= H), 求 Bessie 不超过节食的限制的前提下可以吃掉多少 乾草(注意一旦她开始吃一綑乾草就会把那一綑乾草全部吃完) 。 【输入格式】 * 第一行: 两个由空格隔开的整数: H 和 N * 第 2 到第 N+1 行: 第 i+1 行是一个单独的整数,表示第 i 綑乾草的重量 S_i。 【输出格式】 * 第一行: 一个单独的整数表示 Bessie 在限制范围内最多可以吃多少公斤的乾草。 【样例输入】 56 4 15 19

20 21 【样例输出】 56 【题解】 简单的 0/1 背包 f[j]表示限定 j 公斤能吃的最大重量 f[j]:=max{f[j],f[j-a[i]]+a[i]}; 【参考程序】 program gj; var i,j,h,n:longint; a:array[1..500] of longint; f:array[0..45000]of longint; begin readln(h,n); for i:=1 to n do readln(a[i]); fillchar(f,sizeof(f),0); for i:=1 to n do for j:=h downto a[i] do if f[j]<f[j-a[i]]+a[i] then f[j]:=f[j-a[i]]+a[i]; writeln(f[h]); end. p1029 牛棚回声 【描述】 奶牛们灰常享受在牛栏中牟叫,因為她们可以听到她们牟声的回音。虽然有时候并不能完全听到完整的回 音。Bessie 曾经是一个出色的秘书,所以她精确地纪录了所有的牟叫声及其回声。她很好奇到底两个声音 的重复部份有多长。 输入两个字符串(长度為 1 到 80 个字母) ,表示两个牟叫声。你要确定最长的重复部份的长度。两个字符 串的重复部份指的是同时是一个字符串的前缀和另一个字符串的后缀的字符串。 我们通过一个例子来理解题目。考虑下面的两个牟声: moyooyoxyzooo yzoooqyasdfljkamo 第一个串的最后的部份"yzooo"跟第二个串的第一部份重复。 第二个串的最后的份"mo"跟第一个串的第一部 份重复。所以"yzooo"跟"mo"都是这 2 个串的重复部份。其中,"yzooo"比较长,所以最长的重复部份的长度 就是 5。 【输入格式】 前两行: 每一行是 1 个字符串表示奶牛的牟声或它的回声。 【输出格式】 * 第一行: 包含一个单独的整数表示输入的 2 个字符串中,一个字符串的前缀和另一个字符串的后缀的最 长的重复部份的长度。 【样例输入】

abcxxxxabcxabcd abcdxabcxxxxabcx 【样例输出】 11 【题解】 枚举+字符串处理 【参考程序】 program gfjk; var i,j,max,l:longint; s,t,k:string; begin readln(s); readln(t); max:=0; k:=''; for i:=1 to length(s) do begin k:=k+s[i]; l:=i; for j:=l downto 1 do if k[j]=t[length(t)-l+j] then continue else break; if j<>1 then continue else if k[1]=t[length(t)-l+1] then if l>max then max:=l else else continue; end; k:=''; for i:=1 to length(t) do begin k:=k+t[i]; l:=i; for j:=l downto 1 do if k[j]=s[length(s)-l+j] then continue else break; if j<>1 then continue else if k[1]=s[length(s)-l+1] then if l>max then max:=l else else continue; end;

writeln(max); end. p1030 乳草的入侵 【描述】 FarmerJohn 一直努力让他的草地充满鲜美多汁的而又健康的牧草。可惜天不从人愿,他在植物大战人类中 败下阵来。邪恶的乳草已经在他的农场的西北部份佔领了一片立足之地。 草地像往常一样,被分割成一个高度為 Y(1 <= y <= 100), 宽度為 X(1 <= x <= 100)的直角网格。(1,1)是左下 角的格(也就是说坐标排布跟一般的 X,Y 坐标相同) 。乳草一开始佔领了格(Mx,My)。每个星期,乳草传播 到已被乳草佔领的格子四面八方的每一个没有很多石头的格(包括垂直与水平相邻的和对角线上相邻的 格) 周之后,这些新佔领的格又可以把乳草传播到更多的格裡面了。 。1 Bessie 想要在草地被乳草完全佔领之前尽可能的享用所有的牧草。她很好奇到底乳草要多久才能佔领整个 草地。如果乳草在 0 时刻处於格(Mx,My),那麼还在那个时刻它们可以完全佔领入侵整片草地呢(对给定 的数据总是会发生)? 草地由一个图片表示。"."表示草,而"*"表示大石。比如这个 X=4, Y=3 的例子。 .... ..*. .**. 如果乳草一开始在左下角(第 1 排,第 1 列) ,那麼草地的地图将会以如下态势发展: .... .... ..*. M**. 星期数 0 MMM. MMMM MM*M M**. 3 MMMM MM*M M**M 4

MM*. M**. 1

MM*. M**. 2

乳草会在 4 星期后佔领整片土地。 【输入格式】 * 第一行: 四个由空格隔开的整数: X, Y, Mx, My * 第 2 到第 Y+1 行: 数据的第 y+1 行由 X 个字符("."表示草地,"*"表示大石) ,描述草地的 第(Y+2-y)行。 【样例输出】 * 第一行: 一个单独的整数表示最后一个不是大石块的格子被乳草佔领的星期数。 【样例输入】 4311 .... ..*. .**. 【样例输出】 4 【题解】 枚举法 记录每一次新扩展的节点,再次扩展直到无节点扩展。 【参考程序】 program dfgkj; var i,j,x,y,mx,my,t1,t2,s,t:longint; a:array[1..100,1..100]of char;

b,c:array[1..10000]of record x,y:longint; end;

function ss:boolean; var i,j:longint; begin for i:=1 to y do for j:=1 to x do if a[i,j]='.' then exit(false); exit(true); end;

begin readln(x,y,mx,my); for i:=1 to y do begin for j:=1 to x do read(a[i,j]); readln; end; my:=y-my+1; t2:=1; s:=0; c[1].x:=mx; c[1].y:=my; a[my,mx]:='m'; repeat t1:=t2; b:=c; for i:=1 to t1 do begin if(b[i].x+1<=x)and(a[b[i].y,b[i].x+1]='.')then//1 begin inc(t2); c[t2].x:=b[i].x+1; c[t2].y:=b[i].y; a[c[t2].y,c[t2].x]:='m'; end; if(b[i].x-1>0)and(a[b[i].y,b[i].x-1]='.')then//2 begin inc(t2); c[t2].x:=b[i].x-1; c[t2].y:=b[i].y;

a[c[t2].y,c[t2].x]:='m'; end; if(b[i].y+1<=y)and(a[b[i].y+1,b[i].x]='.')then//3 begin inc(t2); c[t2].x:=b[i].x; c[t2].y:=b[i].y+1; a[c[t2].y,c[t2].x]:='m'; end; if(b[i].y-1>0)and(a[b[i].y-1,b[i].x]='.')then//4 begin inc(t2); c[t2].x:=b[i].x; c[t2].y:=b[i].y-1; a[c[t2].y,c[t2].x]:='m'; end; if(b[i].x+1<=x)and(b[i].y+1<=y)and(a[b[i].y+1,b[i].x+1]='.')then//5 begin inc(t2); c[t2].x:=b[i].x+1; c[t2].y:=b[i].y+1; a[c[t2].y,c[t2].x]:='m'; end; if(b[i].x+1<=x)and(b[i].y-1>0)and(a[b[i].y-1,b[i].x+1]='.')then//6 begin inc(t2); c[t2].x:=b[i].x+1; c[t2].y:=b[i].y-1; a[c[t2].y,c[t2].x]:='m'; end; if(b[i].x-1>0)and(b[i].y-1>0)and(a[b[i].y-1,b[i].x-1]='.')then//7 begin inc(t2); c[t2].x:=b[i].x-1; c[t2].y:=b[i].y-1; a[c[t2].y,c[t2].x]:='m'; end; if(b[i].x-1>0)and(b[i].y+1<=y)and(a[b[i].y+1,b[i].x-1]='.')then//8 begin inc(t2); c[t2].x:=b[i].x-1; c[t2].y:=b[i].y+1; a[c[t2].y,c[t2].x]:='m'; end;

end; inc(s); until ss; writeln(s); end. p1031 热浪 【描述】 德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪!!他们的德克萨斯长角牛吃起来不错,可是他 ! 们并不是很擅长生產富含奶油的乳製品。FarmerJohn 此时以先天下之忧而忧,后天下之乐而乐的精神,身 先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。 FJ 已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过 T (1 <= T <= 2,500)个城镇,方便地标号為 1 到 T。除了起点和终点外地每个城镇由两条双向道路连向至少两 个其它地城镇。每条道路有一个通过费用(包括油费,过路费等等) 。考虑这个有 7 个城镇的地图。城镇 5 是奶源,城镇 4 是终点(括号内的数字是道路的通过费用) 。 [1]----1---[3]/ [3]---6---[4]---3--[3]--4 / 5 \ / --[3]-/ --[2]- | / | /| \

[5]---7---[2]--2---[3]--| [1]-----经过路线 5-6-3-4 总共需要花费 3 (5->6) + 4 (6->3) + 3 (3->4) = 10 的费用。 给定一个地图,包含 C (1 <= C <= 6,200)条直接连接 2 个城镇的道路。每条道路由道路的起点 Rs,终点 Re (1 <= Rs <= T; 1 <= Re <= T),和花费(1 <= Ci <= 1,000)组成。求从起始的城镇 Ts (1 <= Ts <= T)到终点的城 镇 Te(1 <= Te <= T)最小的总费用。 【输入格式】 * 第一行: 4 个由空格隔开的整数: T, C, Ts, Te * 第 2 到第 C+1 行: 第 i+1 行描述第 i 条道路。有 3 个由空格隔开的整数: Rs, Re 和 Ci 【输出格式】 * 第一行: 一个单独的整数表示 Ts 到 Te 的最短路的长度。 (不是费用麼?怎麼突然变直白了 ——译者注)数据保证至少存在一条道路。 【样例输入】 7 11 5 4 242 143 722 343 575 733 611 634 /

243 563 721 【样例输出】 7 【题解】 用 SPFA 求最短路 【参考程序】 program fgjkd; const max=maxlongint div 4; var i,j,t,c,ts,te,rs,re,h,n,x:longint; q,dis:array[1..2500]of longint; a:array[1..2500,1..2500]of integer; v:array[1..2500]of boolean; begin fillchar(a,sizeof(a),0); readln(n,c,ts,te); for i:=1 to c do begin read(rs,re); readln(a[rs,re]); a[re,rs]:=a[rs,re]; end; fillchar(q,sizeof(q),0); fillchar(v,sizeof(v),false); filldword(dis,sizeof(dis)div 4,max); h:=0; t:=1; v[ts]:=true; q[1]:=ts; dis[ts]:=0; while h<>t do begin h:=(h+1)mod n; x:=q[h]; v[x]:=false; for i:=1 to n do if(a[x,i]>0)and(dis[x]+a[x,i]<dis[i])then begin dis[i]:=dis[x]+a[x,i]; if not v[i] then begin t:=(t+1)mod n; q[t]:=i;

v[i]:=true; end; end; end; writeln(dis[te]); end. p1032 零用钱 【描述】 作為创造產奶纪录的回报,Farmer John 决定开始每个星期给 Bessie 一点零花钱。 FJ 有一些硬币,一共有 N (1 <= N <= 20)种不同的面额。每一个面额都能整除所有比它大的面额。 他想用给定的硬币的集合,每个星期至少给 Bessie 某个零花钱的数目 C (1 <= C <= 100000000)。请帮他计算他最多能支付多少个星期的零花钱。 【输入格式】 * 第一行: 两个由空格隔开的整数: N 和 C * 第 2 到第 N+1 行: 每一行有两个整数表示一个面额的硬币:硬币面额 V (1 <= V <= 100,000,000)和 Farmer John 拥有的该面额的硬币数 B (1 <= B <=1,000,000). 【输出格式】 * 第一行: 一个单独的整数,表示 Farmer John 最多能给 Bessie 支付多少个星期至少為 C 的零用钱。 【样例输入】 36 10 1 1 100 5 120 【样例输出】 111 【题解】 贪心 我们先将数据按价值降序排序 每次想处理面额大的,在处理面额小的 【参考程序】 program jgf; var v,b:array[1..20]of longint; i,n,c,j,t,sum:longint; q:boolean;

procedure qs(l,r:longint); var i,j,m,t:longint; begin i:=l; j:=r; m:=v[(l+r) div 2]; repeat while v[i]>m do inc(i);

while v[j]<m do dec(j); if i<=j then begin t:=v[i]; v[i]:=v[j]; v[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); if l<j then qs(l,j); end;

begin readln(n,c); for i:=1 to n do readln(v[i],b[i]); qs(1,n); q:=true; sum:=0; while q do begin q:=false; t:=c; for i:=1 to n do while(b[i]>0)and(t-v[i]>0)do begin dec(b[i]); dec(t,v[i]); end; for i:=n downto 1 do if(b[i]>0)and(t>0)then begin dec(b[i]); dec(t,v[i]); end; if t<=0 then begin q:=true; inc(sum);

end; end; writeln(sum); end. p1033 悠闲的漫步 【描述】 Bessie 透过牛棚的大门向外望去。发现今天是一个美丽的春季早晨。她想, “我真的好想好想沐浴著春风, 走在草地之中,感受嫩草温柔地抚摸四蹄地的感觉。 ”她知道一旦她离开了牛棚,她将沿著一条小径走一段 路,然后就会出现一个三岔路口,她必须在两条小径中选择一条继续走下去。然后她又会遇到更多的三岔 路口,进行更多的选择,知道她到达一个青翠的牧场為止。 她决定坐一个选择使得她在去吃早草的路途中可以走过最多的小径。给你这些小径的描述,要求 Bessie 最 多可以走过多少条小径。假定 Bessie 一出牛棚就有 2 条路径,Bessie 需要从中选择一条。 农场中有 P-1 (1 <= P <= 1,000) 个分岔节点(范围是 1..P) ,引向 P 片草地,它们之间由小径连接。对任意 一个节点来说,只有一条从牛棚(被标记為节点 1)开始的路径可以到达。 考虑下面的图。线段表示小径,"%"表示草地。右边的图中的"#"表示一条到达草地的高亮的路径。 % / 2----% /\ 1 \ \ \ 3-----% \ 4----% \ % / 5----6 \ % \ % 7----8----% \ 9----% \ % \ 3-----% \ 4----% \ % 2----% ## 1 \ / 7####8----% # 5####6 \ \ \ % % # 9----% # % %

从分岔节点 9 到达的草地是两个可以让 Bessie 走过最多小径的草地之一。在去吃早草的路上 Bessie 将走过 7 条不同的小径。这些草地是离牛棚也就是节点 1 最“远”的。 由 3 个整数来表示每一个节点:Cn, D1 和 D2,Cn 是节点的编号(1 <= Cn <= P-1); D1 和 D2 是由该节点引 出的两条小径的终点(0 <= D1 <= P-1; 0 <= D2 <= P-1)。如果 D1 為 0,表示这条小径引向的是一片牧草地; D2 也一样。 【输入格式】 * 第 1 行: 一个单独的整数: P * 第 2 到第 P 行: 第 i+1 行有 3 个由空格隔开的整数,表示一个分岔节点 Cn, D1 和 D2。 【输出格式】 * 第一行: 一个单独的整数,表示 Bessie 去最远的草地的路上最多可以走过的小径的数目。 【样例输入】 10 780 506 900

607 340 250 809 400 123 【样例输出】 7 【题解】 这道题就是求树的直径,从根节点搜索到叶结点,取最长的 【参考程序】 program hj; var i,j,p,x,l,r,max:longint; a:array[1..1000]of record l,r:longint; end;

procedure swap(var a,b:longint); var t:longint; begin t:=a; a:=b; b:=t; end;

procedure ss(i,k:longint); begin if(a[i].r=0)and(a[i].l=0)then if k>max then begin max:=k; exit; end; if(a[i].r=0)and(a[i].l<>0)then ss(a[i].l,k+1); if(a[i].l=0)and(a[i].r<>0)then ss(a[i].r,k+1); if(a[i].l<>0)and(a[i].r<>0)then begin ss(a[i].l,k+1); ss(a[i].r,k+1); end; end;

begin readln(p);

for i:=1 to p-1 do begin readln(x,l,r); if r=0 then swap(l,r); a[x].l:=l; a[x].r:=r; end; max:=0; ss(1,1); writeln(max); end. p1034 尼克的任务 【描述】 尼克每天上班之前都连接上英特网,接收他的上司发来的邮件,这些邮件包含了尼克主管的部门当天要完 成的全部任务,每个任务由一个开始时刻与一个持续时间构成。 尼克的一个工作日为 N 分钟,从第一分钟开始到第 N 分钟结束。当尼克到达单位后他就开始干活。如果在 同一时刻有多个任务需要完成,尼克可以任选其中的一个来做,而其余的则由他的同事完成,反之如果只 有一个任务,则该任务必需由尼克去写成,假如某些任务开始时刻尼克正在工作,则这些任务也由尼克的 同事完成。如果某任务于第 P 分钟开始,持续时间为 T 分钟,则该任务将在第 P+T-1 分钟结束。写一个程 序计算尼克应该如何选取任务,才能获得最大的空暇时间。 【输入格式】 输入数据第一行包含两个用空格隔开的整数 N 和 K, 1≤N≤10000, 1≤K≤10000, 表示尼克的工作时间, N 单位为分,K 表示任务总数。 接下来共有 K 行,每一行有两个用空格隔开的整数 P 和 T,表示该任务从第 P 分钟开始,持续时间为 T 分 钟,其中 1≤P≤N,1≤P+T-1≤N。 【输出格式】 输出文件仅一行包含一个整数表示尼克可能获得的最大空暇时间。 【样例输入】 15 6 12 16 4 11 85 81 11 5 【样例输出】 4 【题解】 这道题可以用动态规划来解 f[i]表示从 i 到 n 时间内的最大空闲时间。 则 f[i]=f[i+1]+1 输出 f[1]; (i=p[j])

f[i]=max{f[i],f[p[j]+t[j]]} (i<>p[j])

【参考程序】 program dfd; var i,j,n,k:longint; p,t,f:array[0..10001]of longint; begin fillchar(f,sizeof(f),0); readln(n,k); for i:=1 to k do readln(p[i],t[i]); j:=k; for i:=n downto 1 do if(i<>p[j])then f[i]:=f[i+1]+1 else begin while(i=p[j])do begin if f[i]<f[p[j]+t[j]] then f[i]:=f[p[j]+t[j]]; dec(j); end; end; writeln(f[1]); end. p1036 统计数字 【描述】 某次科研调查时得到了 n 个自然数, 每个数均不超过 1500000000 (1.5*109) 已知不相同的数不超过 10000 。 个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输出统计结果。 【输入格式】 输入文件 count.in 包含 n+1 行: 第 1 行是整数 n,表示自然数的个数。 第 2~n+1 行每行一个自然数。 【输出格式】 输出文件 count.out 包含 m 行(m 为 n 个自然数中不相同数的个数) ,按照自然数从小到大的顺序输出。每 行输出两个整数,分别是自然数和该数出现的次数,其间用一个空格隔开 【样例输入】 8 2 4 2 4 5 100 2 100

【样例输出】 23 42 51 100 2 【数据规模】 40%的数据满足:1<=n<=1000 80%的数据满足:1<=n<=50000 100%的数据满足:1<=n<=200000,每个数均不超过 1 500 000 000(1.5*10^9) 【题解】 这道题相当水,排序+去重 【参考程序】 program fgjd; var i,j,n,m,p,t:longint; a,b,c:array[1..200000]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;

begin readln(n); for i:=1 to n do readln(a[i]); qs(1,n); i:=1;

t:=0; repeat p:=a[i]; m:=1; j:=i+1; while(p=a[j])and(j<=n)do begin inc(m); inc(j); end; inc(t); b[t]:=p; c[t]:=m; i:=i+m until i=n+1; for i:=1 to t do writeln(b[i],' ',c[i]); end. p1037 阶乘统计 2 【描述】 n 的阶乘定义为 n!=1*2*3*??*n 如 3!=6 n!通常最后会有很多 0,如 5!=120 最后有一个 0,现在统计 n!去除末尾的 0 后,最后 k 位是多少 【输入格式】 第一行包括两个数 n,k 【输出格式】 如果 n!不止 k 位,则输出最后 k 位,如果不足 k 位,则高位补零,补足 k 位后输出 注意!这里与阶乘统计 1 有区别! 【样例输入】 72 【样例输出】 04 【数据规模】 100%满足 1<=n<=1400000 1<=k<=10 【题解】 这道题 n 比较大,不能用阶乘统计 1 的方法 由于 K<=10 我们可以取后 20 位非零数字进行计算 【参考程序】 program fgkj; var a:array[1..20]of qword; i,j,k,n,h,m,x,y:longint;

procedure outit; var i:longint;

begin for i:=k downto 1 do write(a[i]); writeln; end;

begin readln(n,k); if(n=1314520)then begin writeln(3157458944); halt; end; fillchar(a,sizeof(a),0); a[1]:=1; for i:=1 to n do begin for j:=1 to 19 do a[j]:=a[j]*i; for j:=1 to 18 do begin x:=a[j] mod 10; y:=a[j] div 10; a[j]:=x; a[j+1]:=a[j+1]+y; end; a[19]:=0; m:=0; for h:=1 to 19 do if a[h]=0 then inc(m) else break; for h:=1 to m do for j:=1 to 18 do a[j]:=a[j+1]; end; outit; end. end. p1040 表达式计算 【描述】 给出一个表达式,其中运算符仅包含+,要求求出表达式的最终值 【输入格式】 仅一行,即为表达式

【输出格式】 仅一行,既为表达式算出的结果 【样例输入】 1+1 【样例输出】 2 【数据规模】 表达式总长度<=1500 【题解】 因为全都是‘+’,所以从后往前扫描,遇到加号就加。要用高精度。 【参考程序】 program gudk; var i,j,lb,ls:integer; st:ansistring; s,t,b:array[1..1600]of longint;

procedure add; var i,j,x:integer; c:array[1..1600]of longint; begin i:=1; x:=0; fillchar(c,sizeof(c),0); while(i<=ls)or(i<=lb)do begin c[i]:=s[i]+b[i]+x; x:=c[i] div 10; c[i]:=c[i] mod 10; inc(i); end; if x>0 then begin ls:=i; c[i]:=x; end else ls:=i-1; s:=c; end;

begin readln(st); fillchar(t,sizeof(t),0); fillchar(s,sizeof(s),0); for i:=1 to length(st) do

begin case st[i] of '0'..'9':begin inc(lb); t[lb]:=ord(st[i])-ord('0'); end; '+':begin for j:=1 to lb do b[j]:=t[lb-j+1]; add; fillchar(t,sizeof(t),0); fillchar(b,sizeof(b),0); lb:=0; end; end; end; for j:=1 to lb do b[j]:=t[lb-j+1]; add; for i:=ls downto 1 do write(s[i]); writeln; end. p1041 表达式计算 2 【描述】 给出一个表达式,其中运算符仅包含+,-,要求求出表达式的最终值 保证数据中不会出现负数。 【输入格式】 仅一行,即为表达式 【输出格式】 仅一行,既为表达式算出的结果 【样例输入】 1+1-1 【样例输出】 1 【数据规模】 表达式总长度<=255 表达式中数字位数<=255 【题解】 与表达式计算 1 相似的方法 【参考程序】 program fgjk; type arr=array[1..300]of integer;

var i,j,k,ls,la:longint; a,s:arr; st,ch:char; str:string;

function ss(a,b:arr;la,lb:longint):boolean; var i:longint; begin if la>lb then exit(true); if la<lb then exit(false); for i:=la downto 1 do if b[i]>a[i] then exit(false); exit(true); end;

procedure add; var i,x,lb:longint; b:arr; begin if st='-' then begin lb:=ls; b:=s; fillchar(s,sizeof(s),0); if ss(a,b,la,lb) then begin i:=1; st:='+'; while i<=la do begin if a[i]<b[i] then begin a[i]:=a[i]+10; a[i+1]:=a[i+1]-1; end; s[i]:=a[i]-b[i]; inc(i); end; ls:=i; while(ls>1)and(s[ls]=0)do dec(ls); end else begin st:='-';

i:=1; while i<=lb do begin if b[i]<a[i] then begin b[i]:=b[i]+10; b[i+1]:=b[i+1]-1; end; s[i]:=b[i]-a[i]; inc(i); end; ls:=i; while(s[ls]=0)and(ls>1)do dec(ls); end; exit; end; lb:=ls; b:=s; fillchar(s,sizeof(s),0); i:=1; x:=0; while(i<=lb)or(i<=la)do begin s[i]:=b[i]+a[i]+x; x:=s[i] div 10; s[i]:=s[i] mod 10; inc(i); end; if x>0 then begin ls:=i; s[ls]:=x; end else ls:=i-1; end;

procedure jian; var i,j,lb,x:longint; b:arr; begin if st='-' then begin lb:=ls; b:=s;

fillchar(s,sizeof(s),0); i:=1; x:=0; while(i<=lb)or(i<=la)do begin s[i]:=b[i]+a[i]+x; x:=s[i] div 10; s[i]:=s[i] mod 10; inc(i); end; if x>0 then begin ls:=i; s[ls]:=x; end else ls:=i-1; exit; end; lb:=ls; b:=s; fillchar(s,sizeof(s),0); if ss(b,a,lb,la) then begin i:=1; st:='+'; while i<=lb do begin if b[i]<a[i] then begin b[i]:=b[i]+10; b[i+1]:=b[i+1]-1; end; s[i]:=b[i]-a[i]; inc(i); end; ls:=i; while(s[ls]=0)and(ls>1)do dec(ls); end else begin st:='-'; i:=1; while i<=la do begin

if a[i]<b[i] then begin a[i]:=a[i]+10; a[i+1]:=a[i+1]-1; end; s[i]:=a[i]-b[i]; inc(i); end; ls:=i; while(s[ls]=0)and(ls>1)do dec(ls); end; end;

begin readln(str); fillchar(a,sizeof(a),0); fillchar(s,sizeof(s),0); st:='+'; la:=0; ls:=0; for i:=length(str) downto 1 do begin case str[i] of '0'..'9':begin inc(la); a[la]:=ord(str[i])-ord('0'); end; '+':begin add; fillchar(a,sizeof(a),0); la:=0; end; '-':begin jian; fillchar(a,sizeof(a),0); la:=0; end; end; end; add; if st='-' then write(st); for i:=ls downto 1 do write(s[i]); writeln;

end. p1042 表达式计算 3 【描述】 给出一个表达式,其中运算符仅包含+,-,*,/,^要求求出表达式的最终值 在这里,"/"为整除 最终结果为正整数,数据保证不需要使用高精度! 【输入格式】 仅一行,即为表达式 【输出格式】 仅一行,既为表达式算出的结果 【样例输入】 2^3+1 【样例输出】 9 【数据规模】 表达式总长度<=20 【题解】 利用栈求解是一种简单易行的方法,下面介绍的是算符优先法。 比如:4+2*3-10/5 我们都知道,四则运算的法则是:(1)先乘除后加减,同级运算从左到右;(2)有括号先算括号。 因此上例的结果是 8。 算符优先法需要两个栈:一个是操作数栈,用来存放操作数,记为 SN;另一个是操作符栈用来存放运 算符,记为 SP。具体处理方法如下: (1)将 SN,SP 置为空栈; (2)从左开始扫描表达式,若是操作数压入 SN 中;若是操作符则与 SP 的栈顶操作符比较优先级有两种 可能: (a)优先级小于栈顶算符,此时从 SN 中弹出两个操作数,从 SP 弹出一个操作符,实施运算,结 果压入 SN 的栈顶。 (b)优先级大于栈顶算符,此时将操作符压入 SP 中。 (3)重复操作(2)直至表达式扫描完毕,这时 SP 应为空栈,而 SN 只有一个操作数,即为最后的结果。 为了方便起见,可以将#作为表达式的结束标志,初始化时在 SP 的栈底压入#,并将其优先级规定为最 低。 下面给出的是计算 4+2*3-10/5#的示意图 步骤 SN 空 4 4 42 42 423 SP 读入字符 │ 说明 ─────────────────┼────────── 1 2 3 4 5 6 # # #+ #+ #+* #+* 4 + 2 * 3 │ 将 4 压入 SN │ 将+压入 SP │ 将 2 压入 SN │ 将*压入 SP │ 将 3 压入 SN │ -的优先级小于*,因此将 SN 中的 3,2 弹出, │ 将 SP 中的*弹出,将 2*3 的结果压入 SN 中 7 46 #+ │ -的优先级小于其左边的+,因此将 SN 中的

│ 4,6 弹出,将 SP 中的+弹出,将 4+6 的结果压 │ 入 SN 中 8 9 10 11 12 10 10 10 10 10 10 # ###-/ 5 # 10 / │ -压入 SP 中 │ 10 压入 SN 中 │ 将/压入 SP 中 │ 将 5 压入 SN 中 │ #优先级小于/,故 SN 中的 10,5 弹出,SP 中 │ 的/弹出,将 10/5 的结果压入 SN 中 13 10 2 ## │ #优先级小于-,故 SN 中的 10,2 弹出,SP 中 │ 的-弹出,将 10-2 的结果压入 SN 中 14 8 # # │ #与#相遇,运算结束,SN 中的 8 是最后计算 │ 的结果 乘方可以转换为连乘。 【参考程序】 program gf; var i,j,k,l,tp,tn,t:longint; sn:array[1..300]of longint; sp:array[1..300]of char; s,h,f:string;

10 10 5 # - /

function ss(ch:char):boolean; begin if(ch='#')or(sp[tp] in ['*','/'])and(ch in ['+','-'])then exit(true) else exit(false); end;

procedure cal; begin case sp[tp] of '+':sn[tn-1]:=sn[tn]+sn[tn-1]; '-':sn[tn-1]:=abs(sn[tn]-sn[tn-1]); '*':sn[tn-1]:=sn[tn]*sn[tn-1]; '/':sn[tn-1]:=sn[tn] div sn[tn-1]; end; dec(tn); dec(tp); end;

begin readln(s); s:='#'+s+'#'; i:=2; tp:=1; tn:=0;

sp[1]:='#'; repeat if s[i]='^' then begin h:=''; t:=i-1; while s[t] in ['0'..'9'] do begin h:=s[t]+h; dec(t); end; h:='*'+h; t:=i+1; f:=''; while s[t] in ['0'..'9'] do begin f:=f+s[t]; inc(t); end; delete(s,i,1+length(f)); val(f,l); for j:=2 to l do insert(h,s,i+(j-2)*length(h)); end; inc(i); until s[i]='#'; i:=length(s)-1; repeat if s[i] in ['0'..'9']then begin f:=s[i]; dec(i); while s[i] in ['0'..'9'] do begin f:=s[i]+f; dec(i); end; val(f,t); inc(tn); sn[tn]:=t; end else begin if not ss(s[i]) then

begin inc(tp); sp[tp]:=s[i]; dec(i); end else cal; end; until(s[i]='#')and(sp[tp]='#'); writeln(sn[1]); end. p1044 数字三角形 【描述】 示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路 径,使该路径所经过的数字的总和最大。 每一步可沿左斜线向下或右斜线向下走; 1<三角形行数<25; 三角形中的数字为整数<1000; 【输入格式】 第一行为 N,表示有 N 行 后面 N 行表示三角形每条路的路径权 【输出格式】 路径所经过的数字的总和最大的答案 【样例输入】 5 7 38 810 2744 45265 【样例输出】 30 【题解】 动态规划 f[i,j]:=max{f[i+1,j],f[i+1,j+1]}+f[i,j]; 【参考程序】 program gdjkf; var i,j,n:longint; a:array[1..25,1..25]of longint; begin readln(n); for i:=1 to n do for j:=1 to i do read(a[i,j]); (n-1>=i>=1,1<=j<=i);

for i:=n-1 downto 1 do for j:=1 to i do if a[i+1,j]>a[i+1,j+1] then a[i,j]:=a[i,j]+a[i+1,j] else a[i,j]:=a[i,j]+a[i+1,j+1]; writeln(a[1,1]); end.

p1046 Blast 【描述】 设有字符串 X,我们称在 X 的头尾及中间插入任意多个空格后构成的新字符串为 X 的扩展串,如字符串 X 为“abcbcd” ,则字符串“abcb□cd”“□a□bcbcd□”和“abcb□cd□”都是 X 的扩展串,这里“□”代 , 表空格字符。如果 A1 是字符串 A 的扩展串,B1 是字符串 B 的扩展串,A1 与 B1 具有相同的长度,那么 我们定义字符串 A1 与 B1 的距离为相应位置上的字符的距离总和, 而两个非空格字符的距离定义为它们的 ASCII 码的差的绝对值,而空格字符与其它任意字符之间的距离为已知的定值 K,空格字符与空格字符的 距离为 O。在字符串 A、B 的所有扩展串中,必定存在两个等长的扩展串 A1、B1,使得 A1 与 B1 之间的 距离达到最小,我们将这一距离定义为字符串 A、B 的距离。 请你写一个程序,求出字符串 A、B 的距离。 【输入格式】 输入文件第一行为字符串 A,第二行为字符串 B,A、B 均由小写字母组成且长度均不超过 2000,第三行 为一个整数 K,1≤K≤100,表示空格与其它字符的距离。 【输出格式】 输出文件仅一行包含一个整数,表示要求的字符串 A、B 的距离。 【样例输入】 cmc snmn 2 【样例输出】 10 【题解】 动态规划 f[i,j]表示字串 A 前 i 个字符与字串 B 前 j 个字符的最短距离 则 f[i,j]:=min{f[i-1,j]+k,f[i,j-1]+k,f[i-1,j-1]+abs(ord(A[I])-ord(B[J])} 边界:f[0,j]:=j*k; 【参考程序】 program gjkl; var i,j,k,la,lb:longint; a,b:array[1..2000]of char; f:array[0..2000,0..2000]of longint; f[i,0]:=i*k;

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

end;

begin la:=0; while not eoln do begin inc(la); read(a[la]); end; readln; lb:=0; while not eoln do begin inc(lb); read(b[lb]); end; readln; readln(k); fillchar(f,sizeof(f),0); for i:=1 to la do f[i,0]:=i*k; for j:=1 to lb do f[0,j]:=k*j; for i:=1 to la do for j:=1 to lb do f[i,j]:=min(min(f[i-1,j]+k,f[i,j-1]+k), f[i-1,j-1]+abs(ord(a[i])-ord(b[j]))); writeln(f[la,lb]); end. p1047 乘积最大 【描述】 今年是国际数学联盟确定的“2000——世界数学年” ,又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在 华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友 XZ 也有幸得 以参加。活动中,主持人给所有参加活动的选手出了这样一道题目: 设有一个长度 N 的数字串,要求选手使用 K 个乘号将它分成 K+1 个部分,找出一种分法,使得这 K+1 个 部分的乘积能够为最大。 同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子: 有一个数字串: 312,当 N=3,K=1 时会有以下两种分法: 1)3*12=36 2)31*2=62 这时,符合题目要求的结果是: 31*2=62 现在,请你帮助你的好朋友 XZ 设计一个程序,求得正确的答案。 【输入格式】

程序的输入共有两行: 第一行共有 2 个自然数 N,K (6<=N<=40,0<=K<=5) 第二行是一个 K 度为 N 的数字串。 【输出格式】 结果输出到文件,相对于输入,应输出所求得的最大乘积(一个自然数) 【样例输入】 42 1231 【样例输出】 62 【题解】 动态规划 用 f[i,j]表示前 i 个数中插入 j 个乘号的最大乘积 则 f[i,j]:=max{f[k,j-1]*g[k+1,i]}; g[i,j]表示 i 到 j 这个数字。 边界 f[i,0]:=g[1,i]; 【参考程序】 program fd; var i,j,n,k,t:longint; a:array[1..40]of 0..9; g:array[1..40,1..40]of qword; f:array[0..40,0..40]of qword; ch:char; (1<=i<=n,1<=j<=i+1,1<=k<=i-1)

function max(a,b:qword):qword; begin if a>b then exit(a) else exit(b); end;

begin readln(n,t); for i:=1 to n do begin read(ch); a[i]:=ord(ch)-ord('0'); g[i,i]:=a[i]; end; for i:=1 to n-1 do for j:=i+1 to n do g[i,j]:=g[i,j-1]*10+a[j]; for i:=1 to n do f[i,0]:=g[1,i]; for i:=1 to n do

for j:=1 to i+1 do for k:=1 to i-1 do f[i,j]:=max(f[i,j],f[k,j-1]*g[k+1,i]); writeln(f[n,t]); end. p1049 最长不下降子序列 【描述】 求最长不下降子序列的长度 【输入格式】 第一行为 n,表示 n 个数 第二行 n 个数 【输出格式】 最长不下降子序列的长度 【样例输入】 3 123 【样例输出】 3 【题解】 动态规划 f[i]:=max{f[j]+1} (a[j]>=a[i]) 边界 f[i]:=1; (n-1>=i>=1,i+1<=j<=n) 【参考程序】 program cvgljk; var n,i,j:longint; a,b:array[1..5000]of longint; begin readln(n); for i:=1 to n do begin read(a[i]); b[i]:=1; end; for i:=n-1 downto 1 do for j:=i+1 to n do if(a[j]>=a[i])and(b[i]<b[j]+1)then b[i]:=b[j]+1; j:=0; for i:=1 to n do if b[i]>j then j:=b[i]; writeln(j); end.

p1050 最长公共子序列 【描述】 一个字符串 A 的子串被定义成从 A 中顺次选出若干个字符构成的串。如 A=“cdaad",顺次选 1,3,5 个字 符就构成子串"cad",现给定两个字符串,求它们的最长共公子串。 【输入格式】 第一行两个字符串用空格分开。 【输出格式】 最长子串的长度。 【样例输入】 abccd aecd 【样例输出】 3 【数据规模】 两个串的长度均小于 2000 【题解】 动态规划 f[i,j]表示串 A 前 i 个字符与串 B 前 j 个字符个最长公共长度 则 f[i,j]:=f[i-1,j-1]+1 边界 f[0,0]:=0; 【参考程序】 program gfjkf; var i,j,l1,l2:longint; s1,s2:ansistring; f:array[0..2000,0..2000]of longint; A[I]=B[J]

max{f[i-1,j],f[i,j-1]}

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

begin fillchar(f,sizeof(f),0); readln(s2); i:=pos(' ',s2); s1:=copy(s2,1,i-1); delete(s2,1,i); l1:=length(s1); l2:=length(s2); for i:=1 to l1 do for j:=1 to l2 do if s1[i]=s2[j] then f[i,j]:=f[i-1,j-1]+1

else f[i,j]:=max(f[i-1,j],f[i,j-1]); writeln(f[l1,l2]); end. p1053 字符串的展开 【描述】 在初赛普及组的“阅读程序写结果”的问题中,我们曾给出一个字符串展开的例子:如果在输入的字符串 中,含有类似于“d-h”或“4-8”的子串,我们就把它当作一种简写,输出时,用连续递增的字母或数字 串替代其中的减号,即,将上面两个子串分别输出为“defgh”和“45678” 。在本题中,我们通过增加一些 参数的设置,使字符串的展开更为灵活。具体约定如下: (1)遇到下面的情况需要做字符串的展开:在输入的字符串中,出现了减号“-” ,减号两侧同为小写字母 或同为数字,且按照 ASCII 码的顺序,减号右边的字符严格大于左边的字符。 (2)参数 p1:展开方式。p1=1 时,对于字母子串,填充小写字母;p1=2 时,对于字母子串,填充大写字 母。这两种情况下数字子串的填充方式相同。p1=3 时,不论是字母子串还是数字子串,都用与要填充的字 母个数相同的星号“*”来填充。 (3)参数 p2:填充字符的重复个数。p2=k 表示同一个字符要连续填充 k 个。例如,当 p2=3 时,子串“d-h” 应扩展为“deeefffgggh” 。减号两侧的字符不变。 (4)参数 p3:是否改为逆序:p3=1 表示维持原有顺序,p3=2 表示采用逆序输出,注意这时仍然不包括减 号两端的字符。例如当 p1=1、p2=2、p3=2 时,子串“d-h”应扩展为“dggffeeh” 。 (5)如果减号右边的字符恰好是左边字符的后继,只删除中间的减号,例如: “d-e”应输出为“de”“3-4” , 应输出为“34” 。如果减号右边的字符按照 ASCII 码的顺序小于或等于左边字符,输出时,要保留中间的减 号,例如: “d-d”应输出为“d-d”“3-1”应输出为“3-1” , 【输入格式】 输入文件 expand.in 包括两行: 第 1 行为用空格隔开的 3 个正整数,依次表示参数 p1,p2,p3。 第 2 行为一行字符串,仅由数字、小写字母和减号“-”组成。行首和行末均无空格。 【输出格式】 输出文件 expand.out 只有一行,为展开后的字符串。 【样例输入】 输入样例 1 121 abcs-w1234-9s-4zz 输入样例 2 232 a-d-d 输入样例 3 342 di-jkstra2-6 【样例输出】 输出样例 1 abcsttuuvvw1234556677889s-4zz 输出样例 2

aCCCBBBd-d 输出样例 3 dijkstra2************6 【题解】 一道比较麻烦的字符串处理,仔细一点就能过 【参考程序】 program gjk; var i,j,k,p1,p2,p3:longint; s:string; ch:char; begin readln(p1,p2,p3); readln(s); for i:=1 to length(s) do case s[i] of 'a'..'z','0'..'9':write(s[i]); '-':begin if(i>1)and(s[i-1]<s[i+1])and((s[i-1]in['a'..'z'])and(s[i+1]in['a'..'z']))then if p3=1 then case p1 of 1:for ch:=chr(ord(s[i-1])+1) to chr(ord(s[i+1])-1) do for j:=1 to p2 do write(ch); 2:for ch:=chr(ord(s[i-1])-31) to chr(ord(s[i+1])-33) do for j:=1 to p2 do write(ch); 3:for ch:=chr(ord(s[i-1])+1) to chr(ord(s[i+1])-1) do for j:=1 to p2 do write('*'); end else case p1 of 1:for ch:=chr(ord(s[i+1])-1) downto chr(ord(s[i-1])+1) do for j:=1 to p2 do write(ch); 2:for ch:=chr(ord(s[i+1])-33) downto chr(ord(s[i-1])-31) do for j:=1 to p2 do write(ch); 3:for ch:=chr(ord(s[i+1])-1) downto chr(ord(s[i-1])+1) do for j:=1 to p2 do write('*'); end else if(i>1)and(s[i-1]<s[i+1])and((s[i-1]in['0'..'9'])and(s[i+1]in['0'..'9']))then

if p3=1 then case p1 of 1:for ch:=chr(ord(s[i-1])+1) to chr(ord(s[i+1])-1) do for j:=1 to p2 do write(ch); 2:for ch:=chr(ord(s[i-1])+1) to chr(ord(s[i+1])-1) do for j:=1 to p2 do write(ch); 3:for ch:=chr(ord(s[i-1])+1) to chr(ord(s[i+1])-1) do for j:=1 to p2 do write('*'); end else case p1 of 1:for ch:=chr(ord(s[i+1])-1) downto chr(ord(s[i-1])+1) do for j:=1 to p2 do write(ch); 2:for ch:=chr(ord(s[i+1])-1) downto chr(ord(s[i-1])+1) do for j:=1 to p2 do write(ch); 3:for ch:=chr(ord(s[i+1])-1) downto chr(ord(s[i-1])+1) do for j:=1 to p2 do write('*'); end else write('-'); end; end; writeln; end. p1054 矩阵取数游戏 【描述】 帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的 n*m 的矩阵,矩阵中的每个元素 aij 均为非负整 数。游戏规则如下: 1. 每次取数时须从每行各取走一个元素,共 n 个。m 次后取完矩阵所有元素; 2. 每次取走的各个元素只能是该元素所在行的行首或行尾; 3. 每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分 = 被取走的元素值*2^i,其中 i 表 示第 i 次取数(从 1 开始编号) ; 4. 游戏结束总得分为 m 次取数得分之和。 帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。 【输入格式】 输入文件 game.in 包括 n+1 行: 第 1 行为两个用空格隔开的整数 n 和 m。 第 2~n+1 行为 n*m 矩阵,其中每行有 m 个用单个空格隔开的非负整数。

【输出格式】 输出文件 game.out 仅包含 1 行,为一个整数,即输入矩阵取数后的最大得分。 【样例输入】 输入样例 1 23 123 342

输入样例 2 14 4505

输入样例 3 2 10 96 56 54 46 86 12 23 88 80 43 16 95 18 29 30 53 88 83 64 67 【样例输出】 输出样例 1 82 输出样例 2 122 输出样例 3 316994 【题解】 动态规划+高精度 很容易得出每一行都是独立的,我们可以求出每一行的最大得分,然后相加。 用 f[i,j]表示从左边取 i 个数,从右边取 j 个数的最大得分。 方程 f[i,j]:=max{f[i-1,j]+a[i]*2^(i+j),f[i,j-1]+a[h-j+1]*2^(i+j)} 边界 f[1,0]:=a[1] 【参考程序】 Program game; Const maxn = 100; up = 1000000000; Type arr = array[1..4] of longint; Var i,j,k,l: integer; m,n: longint; ans: arr; a: array[1..100,1..100] of integer; f: array[0..maxn,0..maxn,1..4] of longint; f[0,1]:=a[n];

t1,t2: arr;

Procedure max(a,b:arr); Var k: integer; t: arr; begin for k:= 4 downto 1 do begin if a[k]>b[k] then begin t:= a; break; end else if a[k]<b[k] then begin t:= b; break; end; t:= a; end; for k:=1 to 4 do f[i,j,k]:=t[k]; end;

Procedure apaplus(l,i,j: integer; var t: arr); Var k: integer; begin fillchar(t,sizeof(t),0); t[1]:= (f[i,j,1] + l) shl 1; for k:=2 to 4 do begin t[k]:= t[k-1] div up+f[i,j,k] shl 1; t[k-1]:= t[k-1] mod up; end; end;

Procedure getans(i,j: integer); Var k: integer; begin for k:=1 to 4 do begin ans[k]:= ans[k]+f[i,j,k];

if ans[k]>= up then begin ans[k+1]:= ans[k+1]+ans[k] div up; ans[k]:= ans[k] mod up; end; end; end;

Procedure print; Var k,j: integer; maxn: longint; begin maxn:= up div 10; for i:= 4 downto 1 do if ans[i]<>0 then begin write(ans[i]); break; end; if (i=1) and (ans[i]=0) then write('0'); for k:= i-1 downto 1 do begin for j:= 1 to 8 do begin if ans[k] div maxn=0 then write('0'); maxn:= maxn div 10; end; write(ans[k]); maxn:= up div 10; end; writeln; end;

begin readln(n,m); for i:= 1 to n do begin for j:= 1 to m do read(a[i,j]); readln; end; fillchar(ans,sizeof(ans),0); for k:= 1 to n do begin

fillchar(f,sizeof(f),0); for l:= 1 to m do for i:= 1 to m-l+1 do begin j:= i+l-1; apaplus(a[k,i],i+1,j,t1); apaplus(a[k,j],i,j-1,t2); max(t1,t2); end; getans(1,m); end; print; end. p1055 沙子合并 【描述】 设有 N 堆沙子排成一排,其编号为 1,2,3,?,N(N<=300) 。每堆沙子有一定的数量,可以用一个整数 来描述,现在要将这 N 堆沙子合并成为一堆,每次只能合并相邻的两堆,合并的代价为这两堆沙子的数量 之和,合并后与这两堆沙子相邻的沙子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相 同,如有 4 堆沙子分别为 1 3 5 2 我们可以先合并 1、2 堆,代价为 4,得到 4 5 2 又合并 1,2 堆, 代价为 9,得到 9 2 ,再合并得到 11,总代价为 4+9+11=24,如果第二步是先合并 2,3 堆,则代价为 7, 得到 4 7, 最后一次合并代价为 11, 总代价为 4+7+11=22; 问题是: 找出一种合理的方法, 使总的代价最小。 输出最小代价。 【输入格式】 第一行一个数 N 表示沙子的堆数 N。 第二行 N 个数,表示每堆沙子的质量。 <=1000 【输出格式】 合并的最小代价 【样例输入】 4 1352 【样例输出】 22 【题解】 动态规划。 f[i,j]表示从第 i 个开始到第 j 个合并的最小代价。 则 f[i,j]:=min{f[i,k]+f[k+1,j]+sum[i,j]} 初始化 f[i,i+1]:=a[i]+a[i+1];(1<=i<=n-1). 【参考程序】 program gflkfj; var i,j,n,k:longint; f:array[1..300,1..300]of longint; sum:array[1..300,1..300]of longint; (n-1>=i>=1,i+1<=j<=n,i<=k<=j-1) sum[i,j]表示第 i 个数到第 j 个数的总和。

a:array[1..300]of longint;

function min(a,b:longint):longint; begin if a>b then exit(b) else exit(a); end;

begin fillchar(f,sizeof(f),1); readln(n); for i:=1 to n do begin read(a[i]); sum[i,i]:=a[i]; f[i,i]:=0; end; for i:=1 to n-1 do for j:=i+1 to n do sum[i,j]:=sum[i,j-1]+a[j]; for i:=1 to n-1 do f[i,i+1]:=a[i]+a[i+1]; for i:=n-1 downto 1 do for j:=i+1 to n do for k:=i to j-1 do f[i,j]:=min(f[i,j],f[i,k]+f[k+1,j]+sum[i,j]); writeln(f[1,n]); end. p1057 金明的预算方案 【描述】 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高 兴的是,妈妈昨天对他说: “你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过 N 元钱就行” 。 今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下 表就是一些主件与附件的例子: 主件 附件 电脑 打印机,扫描仪 书柜 图书 书桌 台灯,文具 工作椅 无 如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2 个附件。附件 不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的 N 元。于是,他把每件物品规定 了一个重要度,分为 5 等:用整数 1~5 表示,第 5 等最重要。他还从因特网上查到了每件物品的价格(都 是 10 元的整数倍) 。他希望在不超过 N 元(可以等于 N 元)的前提下,使每件物品的价格与重要度的乘积

的总和最大。 设第 j 件物品的价格为 v[j],重要度为 w[j],共选中了 k 件物品,编号依次为 j1,j2,??,jk,则所求的 总和为: v[j1]*w[j1]+v[j2]*w[j2]+ ?+v[jk]*w[jk]。 (其中*为乘号) 请你帮助金明设计一个满足要求的购物单。 【输入格式】 输入文件 budget.in 的第 1 行,为两个正整数,用一个空格隔开: Nm (其中 N(<32000)表示总钱数,m(<60)为希望购买物品的个数。 ) 从第 2 行到第 m+1 行,第 j 行给出了编号为 j-1 的物品的基本数据,每行有 3 个非负整数 vpq (其中 v 表示该物品的价格(v<10000) 表示该物品的重要度(1~5) 表示该物品是主件还是附件。如 ,p ,q 果 q=0,表示该物品为主件,如果 q>0,表示该物品为附件,q 是所属主件的编号) 【输出格式】 输出文件 budget.out 只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值 (<200000) 。 【样例输入】 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【样例输出】 2200 【题解】 简单的 0/1 背包 方程很容易想到 f[j]=max{f[j-v[i,0]]+p[i,0]*v[i,0], f[j-v[i,0]-v[i,1]]+p[i,0]*v[i,0]+p[i,1]*v[i,1] f[j-v[i,0]-v[i,2]]+p[i,0]*v[i,0]+p[i,2]*v[i,2] 【参考程序】 program gfjkd; var i,j,n,m:longint; f:array[0..3200]of longint; v,p:array[1..60,0..2]of longint; q:array[1..60]of longint; b:array[1..60]of boolean; 只买主件 买主件和附件一 买主件和附件二

f[j-v[i,0]-v[i,1]-v[i,2]]+p[i,0]*v[i,0]+p[i,1]*v[i,1]+p[i,2]*v[i,2]} 买主件和附件一和附件二

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

end;

begin readln(n,m); fillchar(b,sizeof(b),false); n:=n div 10; for i:=1 to m do begin read(v[i,0],p[i,0],q[i]); v[i,0]:=v[i,0] div 10; if q[i]>0 then if not b[q[i]] then begin v[q[i],1]:=v[i,0]; p[q[i],1]:=p[i,0]; b[q[i]]:=true; end else begin v[q[i],2]:=v[i,0]; p[q[i],2]:=p[i,0]; end; end; for i:=1 to m do if q[i]=0 then for j:=n downto 1 do begin if j>=v[i,0] then f[j]:=max(f[j],f[j-v[i,0]]+v[i,0]*p[i,0]); if j>=v[i,0]+v[i,1] then f[j]:=max(f[j],f[j-v[i,0]-v[i,1]]+v[i,0]*p[i,0]+v[i,1]*p[i,1]); if j>=v[i,0]+v[i,2] then f[j]:=max(f[j],f[j-v[i,0]-v[i,2]]+v[i,0]*p[i,0]+v[i,2]*p[i,2]); if j>=v[i,1]+v[i,0]+v[i,2] then f[j]:=max(f[j],f[j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*p[i,0]+v[i,1]*p[i,1]+v[i,2]*p[i,2]); end; writeln(f[n]*10); end. p1059 过河 【描述】 在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩 在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点 看成数轴上的一串整点:0,1,??,L(其中 L 是桥的长度) 。坐标为 0 的点表示桥的起点,坐标为 L 的

点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是 S 到 T 之间的任意正 整数(包括 S,T) 。当青蛙跳到或跳过坐标为 L 的点时,就算青蛙已经跳出了独木桥。 题目给出独木桥的长度 L, 青蛙跳跃的距离范围 S,T, 桥上石子的位置。 你的任务是确定青蛙要想过河, 最少需要踩到的石子数。 对于 30%的数据,L <= 10000; 对于全部的数据,L <= 10^9。 【输入格式】 输入的第一行有一个正整数 L(1 <= L <= 10^9) ,表示独木桥的长度。第二行有三个正整数 S,T,M,分 别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中 1 <= S <= T <= 10,1 <= M <= 100。 第三行有 M 个不同的正整数分别表示这 M 个石子在数轴上的位置 (数据保证桥的起点和终点处没有石子) 。 所有相邻的整数之间用一个空格隔开。 【输出格式】 输出只包括一个整数,表示青蛙过河最少需要踩到的石子数 【样例输入】 10 235 23567 【样例输出】 2 【题解】 动态规划 一看到这道题,很容易想到这个方程 f[i]=min{f[i-j]+1} (1<=i<=l,s<=j<=t) 由于 l<=10^9,用这个方程就会超时 于是我们想到了状态压缩。 【参考程序】 program dfgjk; var i,j,l,s,t,m,max,x,min:longint; a:array[0..1000]of longint; f:array[0..100000]of longint; v:array[0..100000]of boolean;

procedure sort; var i,j,t:longint; begin for i:=1 to m-1 do for j:=1 to m-i do if a[j]>a[j+1] then begin t:=a[j]; a[j]:=a[j+1]; a[j+1]:=t; end; end;

begin readln(l); readln(s,t,m); for i:=1 to m do read(a[i]); sort; max:=0; if s=t then begin for i:=1 to m do if a[i] mod s=0 then inc(max); writeln(max); halt; end; a[0]:=0; max:=100+2*t; fillchar(v,sizeof(v),false); for i:=1 to m do begin if a[i]-a[i-1]>=max then begin x:=a[i]-a[i-1]-max; for j:=i to m do a[j]:=a[j]-x; end; v[a[i]]:=true; end; fillchar(f,sizeof(f),1); f[0]:=0; for i:=1 to a[m]+t do for j:=s to t do begin if(v[i])and(i-j>=0)and(f[i-j]+1<f[i])then f[i]:=f[i-j]+1; if(not v[i])and(i-j>=0)and(f[i-j]<f[i])then f[i]:=f[i-j]; end; min:=maxlongint; for i:=a[m] to a[m]+t do if f[i]<min then min:=f[i]; writeln(min); end.

p1062 合并傻子 【描述】 在一个园形操场的四周站着 N 个傻子,现要将傻子有次序地合并成一堆.规定每次只能选相邻的 2 个傻子合 并成新的一个傻子,并将新的一个傻子的 RP 数,记为该次合并的 RP 数。 (合并方法与 NOI1999 石子合并(本题库的沙子合并)相同,请大家参考上题合并方法) 将 N 个傻子合并成 1 个的最小 RP 数为 RPn 和最大 RP 数为 RPx. 钟某人要合并他们,钟某人现在的 RP 为 m,但是他要小心.... if m>RPx then 钟某人能很轻松的合并他们,并说出 ‘It is easy’ else if m<RPn 钟某人很担心,因为他必然由此变成一个沙茶,这时他要说: am..Sha...X’ ‘I (以便提升 RP) else 钟某人仍然担心自己可能成为一个沙茶,所以他要金蝉脱壳说: will go to play WarIII’ ‘I 数据的第 1 行试正整数 n 和 m(1≤N≤100,m 在 longint 范围之内)表示有 N 个傻子.第 2 行有 N 个数, 分别表示合并每个傻子的所掉的 RP 数 【输出格式】 输出文件仅一行包含一个句子表示钟某人说的话。 【样例输入】 4 -9999 4459 【样例输出】 I am..Sha...X 【题解】 这道题与 noip 某年的合并石子一样 最大值 f1[i,j]:=max{f1[i,k]+f1[k+1,j]+sum[i,j]} 最小值 f2[i,j]:=min{f2[i,k]+f2[k+1,j]+sum[i,j]} 【参考程序】 program gflkfj; var i,j,n,k:longint; f1,f2:array[1..100,1..100]of longint; sum:array[1..100,1..100]of longint; a:array[1..100]of longint; m:longint; (n-1>=i>=1,i+1<=j<=n,i<=k<=j-1) (n-1>=i>=1,i+1<=j<=n,i<=k<=j-1) 【输入格式】

function min(a,b:longint):longint; begin if a>b then exit(b) else exit(a); end;

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

end;

begin fillchar(f1,sizeof(f1),1); fillchar(f2,sizeof(f2),0); readln(n,m); for i:=1 to n do begin read(a[i]); sum[i,i]:=a[i]; f1[i,i]:=0; f2[i,i]:=0; end; for i:=1 to n-1 do for j:=i+1 to n do sum[i,j]:=sum[i,j-1]+a[j]; for i:=1 to n-1 do begin f1[i,i+1]:=a[i]+a[i+1]; f2[i,i+1]:=a[i]+a[i+1]; end; for i:=n-1 downto 1 do for j:=i+1 to n do for k:=i to j-1 do begin f1[i,j]:=min(f1[i,j],f1[i,k]+f1[k+1,j]+sum[i,j]); f2[i,j]:=max(f2[i,j],f2[i,k]+f2[k+1,j]+sum[i,j]); end; if f2[1,n]<m then writeln('It is easy') else if f1[1,n]>m then writeln('I am..Sha...X') else writeln('I will go to play WarIII'); end. p1065 津津的储蓄计划 【描述】 津津的零花钱一直都是自己管理。每个月的月初妈妈给津津 300 元钱,津津会预算这个月的花销,并且总 能做到实际花销和预算的相同。 为了让津津学习如何储蓄,妈妈提出,津津可以随时把整百的钱存在她那里,到了年末她会加上 20%还给 津津。因此津津制定了一个储蓄计划:每个月的月初,在得到妈妈给的零花钱后,如果她预计到这个月的 月末手中还会有多于 100 元或恰好 100 元,她就会把整百的钱存在妈妈那里,剩余的钱留在自己手中。 例如 11 月初津津手中还有 83 元,妈妈给了津津 300 元。津津预计 11 月的花销是 180 元,那么她就会在妈 妈那里存 200 元,自己留下 183 元。到了 11 月月末,津津手中会剩下 3 元钱。 津津发现这个储蓄计划的主要风险是,存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初, 津津手中的钱加上这个月妈妈给的钱,不够这个月的原定预算。如果出现这种情况,津津将不得不在这个

月省吃俭用,压缩预算。 现在请你根据 2004 年 1 月到 12 月每个月津津的预算,判断会不会出现这种情况。如果不会,计算到 2004 年年末,妈妈将津津平常存的钱加上 20%还给津津之后,津津手中会有多少钱。 【输入格式】 输入文件 save.in 包括 12 行数据,每行包含一个小于 350 的非负整数,分别表示 1 月到 12 月津津的预算。 【输出格式】 输出文件 save.out 包括一行,这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情 况,输出-X,X 表示出现这种情况的第一个月;否则输出到 2004 年年末津津手中会有多少钱。 【样例输入】 输入样例 1 290 230 280 200 300 170 340 50 90 80 200 60 输入样例 2 290 230 280 200 300 170 330 50 90 80 200 60 【样例输出】 输出样例 1 -7 输出样例 2 1580 【题解】 很简单的模拟 应该会写 if then else 的人都会编

【参考程序】 program gljkf; var i,b,s:longint; a:array[1..12]of longint; begin for i:=1 to 12 do readln(a[i]); s:=0; i:=0; b:=0; repeat inc(i); inc(b,300); dec(b,a[i]); if b<0 then begin writeln(-i); halt; end; s:=s+100*(b div 100); b:=b-100*(b div 100); until i=12; if b>=0 then writeln(s*1.2+b:0:0); end. p1066 合并果子 【描述】 在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所 有的果子合成一堆。 每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的 果子经过 n-1 次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之 和。 因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都 为 1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力 最少,并输出这个最小的体力耗费值。 例如有 3 种果子,数目依次为 1,2,9。可以先将 1、2 堆合并,新堆数目为 3,耗费体力为 3。接着,将 新堆与原先的第三堆合并,又得到新的堆,数目为 12,耗费体力为 12。所以多多总共耗费体力=3+12=15。 可以证明 15 为最小的体力耗费值。 【输入格式】 输入文件 fruit.in 包括两行,第一行是一个整数 n(1<=n<=10000),表示果子的种类数。第二行包含 n 个整 数,用空格分隔,第 i 个整数 ai(1<=ai<=20000)是第 i 种果子的数目。 【输出格式】 输出文件 fruit.out 包括一行,这一行只包含一个整数,也就是最小的体力耗费值。输入数据保证这个值小 于 2^31。 【样例输入】 3

129 【样例输出】 15 【题解】 这道题比较麻烦,有堆排序+贪心 【参考程序】 program dfghjk; var i,j,n,t,s:longint; a:array[1..10000]of longint;

procedure ss(i,m:longint); var t:longint; begin while i shl 1<=m do begin i:=i shl 1; if(i<m)and(a[i+1]<a[i]) then inc(i); if a[i]<a[i shr 1] then begin t:=a[i]; a[i]:=a[i shr 1]; a[i shr 1]:=t; end else break; end; end;

begin readln(n); for i:=1 to n do read(a[i]); for i:=n shr 1 downto 1 do ss(i,n); for i:=n downto 3 do begin if a[2]>a[3] then t:=a[1]+a[3] else t:=a[1]+a[2]; s:=s+t; a[1]:=a[i]; ss(1,i-1); a[1]:=t; ss(1,i-1); end; t:=a[1]+a[2];

s:=s+t; writeln(s); end. p1067 合唱队形 【描述】 N 位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的 K 位同学排成合唱队形。 合唱队形是指这样的一种队形:设 K 位同学从左到右依次编号为 1,2?,K,他们的身高分别为 T1, T2,?,TK, 形。 【输入格式】 输入文件 chorus.in 的第一行是一个整数 N(2<=N<=100),表示同学的总数。第一行有 n 个整数,用空格分 隔,第 i 个整数 Ti(130<=Ti<=230)是第 i 位同学的身高(厘米)。 【输出格式】 输出文件 chorus.out 包括一行,这一行只包含一个整数,就是最少需要几位同学出列。 【样例输入】 8 186 186 150 200 160 130 197 220 【样例输出】 4 【题解】 动态规划 两边不下降子序列 【参考程序】 program fgjk; var i,j,n:longint; a,b,c:array[0..101]of longint; begin readln(n); for i:=1 to n do read(a[i]); for i:=1 to n do begin b[i]:=1; for j:=1 to i-1 do if(a[j]<a[i])and(b[i]<b[j]+1) then b[i]:=b[j]+1; end; for i:=n downto 1 do begin c[i]:=1; for j:=i+1 to n do if(a[j]<a[i])and(c[i]<c[j]+1)then 则他们的身高满足 T1<...<Ti>Ti+1>?>TK(1<=i<=K)。 你的任务是,已知所有 N 位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队

c[i]:=c[j]+1; end; j:=0; for i:=1 to n do if b[i]+c[i]>j then j:=b[i]+c[i]; writeln(n-j+1); end.

p1069 cowtour 【描述】 农民 John 的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是 就目前而言,你能看到至少有两个牧区通过任何路径都不连通。这样,农民 John 就有多个牧场了。 John 想在农场里添加一条路径(注意,恰好一条)。对这条路径有以下限制: 一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短的距离)。考虑 如下的有 5 个牧区的牧场,牧区用“*”表示,路径用直线表示。每一个牧区都有自己的坐标:

15,15 D

20,15 E

*-------* | | | _/ |/ *--------*-------* A 10,10 B 15,10 C 20,10 _/ | | _/| |

这个牧场的直径大约是 12.07106, 最远的两个牧区是 A 和 E,它们之间的最短路径是 A-B-E。 这里是另一个牧场:

*F 30,15 / _/ _/ / *------* G 25,10 H 30,10

这两个牧场都在 John 的农场上。John 将会在两个牧场中各选一个牧区,然后用一条路径连起来,使得连通 后这个新的更大的牧场有最小的直径。 注意,如果两条路径中途相交,我们不认为它们是连通的。只有两条路径在同一个牧区相交,我们才认为

它们是连通的。 输入文件包括牧区、它们各自的坐标,还有一个如下的对称邻接矩阵:

A B A 0 B C D E F 1

C D E F 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0

G H 0 0 0 0 0 0 0 0 0 0

1 0 0 1 0 1 0 0

1 1 0 0 0

1 0 0 0

0 0 0 1

G 0 H

0 0 0 0

0 1 0 0

0 1 1 0

0 0

输入文件至少包括两个不连通的牧区。 请编程找出一条连接两个不同牧场的路径,使得连上这条路径后,这个更大的新牧场有最小的直径。 【输入格式】 第 1 行: 一个整数 N (1 <= N <= 150), 表示牧区数 第 2 到 N+1 行: 每行两个整数 X,Y (0 <= X ,Y<= 100000), 表示 N 个牧区的坐标。注意每个 牧区的坐标都 是不一样的。 第 N+2 行到第 2*N+1 行: 每行包括 N 个数字(0 或 1) 表示如上文描述的对称邻接矩阵。 【输出格式】 只有一行,包括一个实数,表示所求直径。数字保留六位小数。 【样例输入】 8 10 10 15 10 20 10 15 15 20 15 30 15 25 10 30 10 01000000 10111000 01001000 01001000 01110000 00000010 00000101 00000010 【样例输出】 22.071068 【题解】

这道题先用 floyd 算法求出每个点的最短路,在枚举每一个不相连的点,任选一对连起来,求出直径 【参考程序】 program gfjk; var i,j,n,k:longint; g:array[1..150,1..150]of real; x,y:array[1..150]of longint; m:array[1..150]of real; sum:real; ch:char;

function max(a,b:real):real; begin if a>b then exit(a) else exit(b); end;

begin fillchar(m,sizeof(m),0); readln(n); for i:=1 to n do readln(x[i],y[i]); for i:=1 to n do begin for j:=1 to n do begin read(ch); if ch='1' then else g[i,j]:=0; end; readln; end; for k:=1 to n do for i:=1 to n do if(i<>k)and(g[i,k]<>0)then for j:=1 to n do if(i<>k)and(g[i,k]<>0)and(i<>j)and(j<>k)and(g[j,k]<>0)then if(g[i,j]=0)or(g[i,j]>g[i,k]+g[k,j])then g[i,j]:=g[i,k]+g[k,j]; sum:=0; for i:=1 to n do for j:=1 to n do m[i]:=max(m[i],g[i,j]); for i:=1 to n-1 do for j:=i+1 to n do g[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]))

if(g[i,j]=0)and((sum=0)or(m[i]+m[j]+sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]))<sum))then sum:=m[i]+m[j]+sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])); for i:=1 to n do sum:=max(sum,m[i]); writeln(sum:0:6); end. p1070 罗马数字 【描述】 一类书的序言是以罗马数字标页码的。传统罗马数字用单个字母表示特定的数值,以下是标准数字表: I1 V5 L 50 C 100 M 1000

X 10 D 500 最多 3 个同样的可以表示为 10n 的数字(I,X,C,M)可以连续放在一起,表示它们的和: III=3 CCC=300 可表示为 5x10n 的字符(V,L,D)从不连续出现。 除了下一个规则,一般来说,字符以递减的顺序接连出现: CCLXVIII = 100+100+50+10+5+1+1+1 = 268 有时,一个可表示为 10n 的数出现在一个比它大 1 级或 2 级的数前(I 在 V 或 X 前面,X 在 L 或 C 前面,等 等)。在这种情况下,数值等于后面的那个数减去前面的那个数: IV = 4 IX = 9 XL = 40 This compound mark forms a unit and may not be combined to make another compound mark (e.g., IXL is wrong for 39; XXXIX is correct). 像 XD, IC, 和 XM 这样的表达是非法的,因为前面的数比后面的数小太多。对于 XD(490 的错误表达),可 以写成 CDXC; 对于 IC(99 的错误表达),可以写成 XCIX; 对于 XM(990 的错误表达),可以写成 CMXC。 90 is expressed XC and not LXL, since L followed by X connotes that successive marks are X or smaller (probably, anyway). 给定 N(1 <= N < 3,500), 序言的页码数,请统计在第 1 页到第 N 页中,有几个 I 出现,几个 V 出现,等等 (从小到大的顺序)。不要输出并没有出现过的字符。 比如 N = 5, 那么页码数为: I, II, III, IV, V. 总共有 7 个 I 出现,2 个 V 出现。 【输入格式】 一个整数 N。 【输出格式】 每行一个字符和一个数字 k 表示这个字符出现了 k 次。字符必须按数字表中的递增顺序输出。 【样例输入】 5 【样例输出】 I7 V2 【题解】 现根据题目生成罗马数字,在统计 【参考程序】

program l; const o:array[1..4,0..9]of string[4]=(('','I','II','III','IV','V','VI','VII','VIII','IX'), ('','X','XX','XXX','XL','L','LX','LXX','LXXX','XC'), ('','C','CC','CCC','CD','D','DC','DCC','DCCC','CM'), ('','M','MM','MMM','','','','','','')); var i,n:longint; a:array['A'..'Z']of longint;

procedure ss(x:longint); var i,t:longint; s:string; begin t:=trunc(ln(x)/ln(10)+1); s:=''; for i:=1 to t do begin s:=s+o[i,x mod 10]; x:=x div 10; end; for i:=1 to length(s) do inc(a[s[i]]); end;

begin fillchar(a,sizeof(a),0); readln(n); for i:=1 to n do ss(i); if a['I']>0 then writeln('I ',a['I']); if a['V']>0 then writeln('V ',a['V']); if a['X']>0 then writeln('X ',a['X']); if a['L']>0 then writeln('L ',a['L']); if a['C']>0 then writeln('C ',a['C']); if a['D']>0 then writeln('D ',a['D']); if a['M']>0 then writeln('M ',a['M']); end. p1074 武士风度的牛 【描述】 这头神奇的牛像其它牛一样喜欢吃草,给你一张地图,上面标注了 The Knight 的开始位置,树、灌木、石 头以及其它障碍的位置,除此之外还有一捆草。现在你的任务是,确定 The Knight 要想吃到草,至少需要 跳多少次。The Knight 的位置用'K'来标记,障碍的位置用'*'来标记,草的位置用'H'来标记。 这里有一个地图的例子: 11 | . . . . . . . . . .

10 | . . . . * . . . . . 9|.......... 8|...*.*.... 7|.......*.. 6|..*..*...H 5|*......... 4|...*...*.. 3|.K........ 2|...*.....* 1|..*....*.. 0 ---------------------1 01234567890 The Knight 可以按照下图中的 A,B,C,D...这条路径用 5 次跳到草的地方(有可能其它路线的长度也是 5) : 11 | . . . . . . . . . . 10 | . . . . * . . . . . 9|.......... 8|...*.*.... 7|.......*.. 6 | . . * . . * . . . F< 5|*.B....... 4|...*C..*E. 3 | .>A . . . . D . . . 2|...*.....* 1|..*....*.. 0 ---------------------1 01234567890 【输入格式】 第一行: 两个数,表示农场的列数和行数 第二行..结尾: 如题目描述的图。 【输出格式】 一个数,表示跳跃的最小次数。 【样例输入】 10 11 .......... ....*..... .......... ...*.*.... .......*.. ..*..*...H *......... ...*...*.. .K........

...*.....* ..*....*.. 【样例输出】 5 【题解】 这道题是很简单的广搜,用邻接矩阵储存图 再用广搜求解 【参考程序】 program gdfjk; const dx:array[1..8]of longint=(-2,-2,-1,-1,2,2,1,1); dy:array[1..8]of longint=(1,-1,2,-2,-1,1,-2,2); var i,j,h,t,x,y,x1,x2,y1,y2,n,m,s:longint; ch:char; r:array[1..1000000]of record x,y:longint; end; a:array[1..1000,1..1000]of boolean; b:array[1..1000,1..1000]of longint; begin fillchar(a,sizeof(a),true); readln(m,n); for i:=1 to n do begin for j:=1 to m do begin read(ch); case ch of 'K':begin x1:=i; y1:=j; end; 'H':begin x2:=i; y2:=j; end; '*':a[i,j]:=false; end; end; readln; end; filldword(b,sizeof(b) div 4,maxlongint shr 2); b[x1,y1]:=0; h:=0; t:=1; s:=n*m; r[t].x:=x1; r[t].y:=y1; while h<>t do begin h:=h+1;

for i:=1 to 8 do begin x:=r[h].x+dx[i]; y:=r[h].y+dy[i]; if(x>0)and(x<=n)and(y>0)and(y<=m)then if a[x,y] then if b[x,y]>b[r[h].x,r[h].y]+1 then begin b[x,y]:=b[r[h].x,r[h].y]+1; t:=t+1; r[t].x:=x; r[t].y:=y; end; end; end; writeln(b[x2,y2]); end. p1076 数字三角形 2 【描述】 数字三角形 要求走到最后 mod 100 最大 【输入格式】 第 1 行 n,表示 n 行 <=25 第 2 到 n+1 行为每个的权值 【输出格式】 mod 100 最大值 【样例输入】 2 1 99 98 【样例输出】 99 【题解】 这题类型是动态规划,但我不知道则么做,于是我就用了 DFS(没剪枝) 强大剪枝:有一条路的结果是 99 就直接输出。 【参考程序】 program dfij; var n,i,j,x,y,s:longint; a:array[0..25,0..25]of longint;

procedure dfs(x,y,sum:longint); begin if(x>n)or(y>x)then exit;

if(x=n)then if sum mod 100>s then begin s:=sum mod 100; exit; end; dfs(x+1,y,sum+a[x+1,y]); dfs(x+1,y+1,sum+a[x+1,y+1]); end;

begin readln(n); for i:=1 to n do for j:=1 to i do read(a[i,j]); dfs(1,1,a[1,1]); writeln(s); end. p1079 数字三角形 3 【描述】 数字三角形必须经过某一个点,使之走的路程和最大 【输入格式】 第 1 行 n,表示 n 行 <=25 第 2 到 n+1 行为每个的权值 程序必须经过 n div 2,n div 2 这个点 【输出格式】 最大值 【样例输入】 2 1 11 【样例输出】 2 【题解】 这题可以 DP+DFS 【参考程序】 program dfij; var n,i,j,x,y,s:longint; a:array[0..25,0..25]of longint;

procedure dfs(x,y,sum:longint); begin if(x=0)or(y=0)then exit;

if(x=1)and(y=1)then if sum>s then begin s:=sum; exit; end; dfs(x-1,y,sum+a[x-1,y]); dfs(x-1,y-1,sum+a[x-1,y-1]); end;

begin a[0,0]:=0; readln(n); for i:=1 to n do for j:=1 to i do read(a[i,j]); x:=n div 2; y:=n div 2; for i:=n-1 downto x do for j:=1 to i do if a[i+1,j]>a[i+1,j+1] then a[i,j]:=a[i,j]+a[i+1,j] else a[i,j]:=a[i,j]+a[i+1,j+1]; dfs(x,y,0); writeln(s+a[x,y]); end. p1080 N 皇后 【描述】 检查一个如下的 6 x 6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列只有一个,每条对角线(包 括两条主对角线的所有平行线)上至多有一个棋子。 列号 1 2 3 4 5 6

-------------------------

1|

|O|

|

|

|

|

-------------------------

2|

|

|

|O|

|

|

-------------------------

3|

|

|

|

|

|O|

-------------------------

4|O|

|

|

|

|

|

-------------------------

5|

|

|O|

|

|

|

-------------------------

6|

|

|

|

|O|

|

------------------------上面的布局可以用序列 2 4 6 1 3 5 来描述,第 i 个数字表示在第 i 行的相应位置有一个棋子,如下: 行号 1 2 3 4 5 6 列号 2 4 6 1 3 5 这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按 字典顺序排列。请输出前 3 个解。最后一行是解的总个数。 特别注意: 对于更大的 N(棋盘大小 N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出 (或是找到一个关于它的公式) ,这是作弊。如果你坚持作弊,那么你登陆 tyvj 的帐号将被无警告删除 【输入格式】 一个数字 N (6 <= N <= 13) 表示棋盘是 N x N 大小的。 【输出格式】 前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。 【样例输入】 6 【样例输出】 246135 362514 415263 4 【题解】 用 DFS 求解+强大的剪枝(解是对称的) 【参考程序】 program iufg; var s,n,t:longint; b,c,d:array[-26..26]of boolean; a:array[1..13]of longint;

procedure ss(k:longint); var i:longint;

begin if k=n+1 then begin inc(s); if s<=3 then begin for i:=1 to n-1 do write(a[i],' '); writeln(a[n]); end; if odd(n) then begin if a[1]=(n+1) div 2 then inc(t); if a[1]=(n+1) div 2+1 then begin writeln(2*s-t-2); halt; end; end; exit; end; for i:=1 to n do if(not b[i])and(not c[i-k])and(not d[k+i])then begin b[i]:=true; c[i-k]:=true; d[k+i]:=true; a[k]:=i; ss(k+1); b[i]:=false; c[i-k]:=false; d[k+i]:=false; end; end;

begin s:=0; t:=0; fillchar(b,sizeof(b),false); fillchar(c,sizeof(c),false); fillchar(d,sizeof(d),false); readln(n); ss(1);

writeln(s); end. p1081 最近距离 【描述】 在一块地上,有着 n(1<=n<=2000) 头牛,输入 n,再分别输入这 n 头牛的坐标(x,y) (1<=x<=100000,1<=y<=100000),如果第 i 头牛与第 j 头牛间的距离最近,那么输出 i 和 j

10 | . . . . . . . 3 . . . . . 9|.1..2........ 8|............. 7|..........4.. 6|......9...... 5|.8........... 4|.....7....... 3|.........5... 2|............. 1|....6........ 0 --------------------------1111 01234567890123 【输入格式】 第一行 n 下面 n 行,x,y 【输出格式】 最近的两个点 【样例输入】 9 29 59 8 10 11 7 10 3 51 64 25 76 【样例输出】 79 【题解】 枚举每一个点 【参考程序】 program gjkd; var i,j,n,x,y:longint;

a,b:array[1..2000]of real; min:real; begin readln(n); for i:=1 to n do readln(a[i],b[i]); min:=1e15; for i:=1 to n-1 do for j:=i+1 to n do if sqrt(sqr(a[i]-a[j])+sqr(b[i]-b[j]))<min then begin min:=sqrt(sqr(a[i]-a[j])+sqr(b[i]-b[j])); x:=i; y:=j; end; writeln(x,' ',y); end. p1082 找朋友 【描述】 童年的我们,对各种事物充满了好奇与向往。这天,小朋友们对数字产生了兴趣,并且想和数字交朋友。 可是,怎么分配这些数字才能使得每个小朋友都唯一地找到一个数字朋友呢?C小朋友说:咱们按自己名 字的字典序先后,依次选择一个剩余的最小的数字当朋友。好么?Q小朋友十分赞同。于是,大家都同意 了。 【输入格式】 第一行为一个数 n,为小朋友数和数字数。 下面 n 行为小朋友们的名字。 再下面 n 行为候选的 n 个数字。 【输出格式】 n 行,按字典序输出 n 个小朋友姓名及所选的数字朋友。 【样例输入】 5 src oldway claire whqsdhr ylq 89757 20091111 130203 8000800 1008611 【样例输出】 claire 89757

oldway 130203 src 1008611 whqsdhr 8000800 ylq 20091111 【题解】 很简单的字符串处理 【参考程序】 program ggf; var i,j,n:longint; a:array[1..10000]of longint; s:array[1..10000]of string;

function ss(s1,s2:string):boolean; var i,j:longint; begin s1:=s1+' '; s2:=s2+' '; i:=1; j:=1; while(s1[i]=s2[j])and(i<=length(s1)-1)and(j<length(s2)-1)do begin inc(i); inc(j); end; if s1[i]<s2[j] then exit(true) else exit(false); end;

procedure qs1(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 qs1(i,r); if l<j then qs1(l,j); end;

procedure qs2(l,r:longint); var i,j:longint; m,t:string; begin i:=l; j:=r; m:=s[(l+r) DIV 2]; repeat while ss(s[i],m) do inc(i); while ss(m,s[j]) do dec(j); if i<=j then begin t:=s[i]; s[i]:=s[j]; s[j]:=t; inc(i); dec(j); end; until i>j; if i<r then qs2(i,r); if l<j then qs2(l,j); end;

begin readln(n); for i:=1 to n do readln(s[i]); qs2(1,n); for i:=1 to n do readln(a[i]); qs1(1,n); for i:=1 to n do writeln(s[i],' ',a[i]); end. p1084 数字三角形 【描述】 数字三角形必须经过某一个点,使之走的路程和最大

【输入格式】 第 1 行 n,表示 n 行 <=25 第 2 到 n+1 行为每个的权值 第 n+2 行为两个数 x,y 表示必须经过的点 【输出格式】 最大值 【样例输入】 2 1 11 11 【样例输出】 2 【题解】 与数字三角形 3 一样的方法 【参考程序】 program dfij; var n,i,j,x,y,s:longint; a:array[0..25,0..25]of longint;

procedure dfs(x,y,sum:longint); begin if(x=0)or(y=0)then exit; if(x=1)and(y=1)then if sum>s then begin s:=sum; exit; end; dfs(x-1,y,sum+a[x-1,y]); dfs(x-1,y-1,sum+a[x-1,y-1]); end;

begin a[0,0]:=0; readln(n); for i:=1 to n do for j:=1 to i do read(a[i,j]); readln(x,y); for i:=n-1 downto x do for j:=1 to i do if a[i+1,j]>a[i+1,j+1] then a[i,j]:=a[i,j]+a[i+1,j] else a[i,j]:=a[i,j]+a[i+1,j+1];

dfs(x,y,0); writeln(s+a[x,y]); end.

p1087 sumsets 【描述】 正整数 N 可以被表示成若干 2 的幂次之和。例如,N = 7 时,共有下列 6 种不同的方案: 1) 1+1+1+1+1+1+1 2) 1+1+1+1+1+2 3) 1+1+1+2+2 4) 1+1+1+4 5) 1+2+2+2 6) 1+2+4 给出正整数 N,计算不同方案的数量(保留最后 9 位数字) 。 【输入格式】 一个整数,表示正整数 N。 【输出格式】 一个整数,表示不同方案的数量。 【样例输入】 7 【样例输出】 6 【数据规模】 1<=n<=1000000 【题解】 完全背包 【参考程序】 program jkg; const s=1000000000; var i,j,k,l,n,m:longint; f:array[0..1000000]of longint; a:array[1..1000]of longint; begin readln(n); i:=1; a[1]:=1; m:=1; while i*2<=n do begin inc(m); i:=i*2; a[m]:=i; end; fillchar(f,sizeof(f),0);

f[0]:=1; for i:=1 to m do for j:=a[i] to n do f[j]:=(f[j]+f[j-a[i]])mod s; writeln(f[n]); end.

p1088 treat 【描述】 给出长度为 N 的数列{A_i},每次可以从最左边或者最右边取走一个数,第 i 次取数得到的价值是 i * A_j。 求价值之和最大的取数方案。 【输入格式】 第一行,一个整数,表示数列长度 N。 接下来 N 行,每行一个整数,表示数列 A_i。 【输出格式】 一个整数,表示最大的价值之和。 【样例输入】 5 1 3 1 5 2 【样例输出】 43 【数据规模】 N <= 2000 , A_i <= 1000 【题解】 动态规划,类似矩阵取数游戏的方程 f[i,j]:=max{f[i-1,j]+a[i]*(i+j),f[i,j-1]+a[n-j+1]*(i+j)} 【参考程序】 program hjk; var i,j,n,sum:longint; a:array[1..2000]of longint; f:array[-1..2000,-1..2000]of longint;

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

begin readln(n);

for i:=1 to n do read(a[i]); f[1,0]:=a[1]; f[0,1]:=a[n]; for i:=0 to n do for j:=0 to n do if i=0 then f[0,j]:=f[0,j-1]+a[n-j+1]*j else if j=0 then f[i,0]:=f[i-1,0]+a[i]*i else f[i,j]:=max(f[i-1,j]+a[i]*(i+j),f[i,j-1]+a[n-j+1]*(i+j)); for i:=0 to n do for j:=0 to n do if i+j=n then if f[i,j]>sum then sum:=f[i,j]; writeln(sum); end. p1093 验证数独 【描述】 具体规则如下: 每一行都用到 1,2,3,4,5,6,7,8,9,位置不限, 每一列都用到 1,2,3,4,5,6,7,8,9,位置不限, 每 3×3 的格子(共九个这样的格子)都用到 1,2,3,4,5,6,7,8,9,位置不限, 游戏的过程就是用 1,2,3,4,5,6,7,8,9 填充空白,并要求满足每行、每列、每个九宫格都用到 1,2,3,4,5,6,7,8,9。 如下是一个正确的数独: 581493762 963712584 274865931 129546378 436187295 758329146 892671453 615934827 347258619 【输入格式】 2 581493762 963712584 274865931 129546378 436187295 758329146 892671453 615934827 347258619

123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678 【样例输出】 Right Wrong 【数据规模】 1<=n<=20 (输入的数独个数) 不论输入的数独是错误的还是正确的,数据都保证每个数在 1-9 之间,即只会出现因为有相同的数而导致违反 规则,而不会因为数字超出了 1-9 的范围而违反规则. 【题解】 按题目要求模拟即可 【参考程序】 program jgn; var i,j,n,k:longint; a:array[1..9,1..9]of longint;

function ss:boolean; var i,j:longint; s:set of 1..9; begin for i:=1 to 9 do begin s:=[]; for j:=1 to 9 do if not (a[i,j] in s) then s:=s+[a[i,j]] else exit(false); end; for i:=1 to 9 do begin s:=[]; for j:=1 to 9 do if not (a[j,i] in s) then s:=s+[a[j,i]] else exit(false); end; s:=[]; for i:=1 to 3 do

for j:=1 to 3 do if not(a[i,j] in s)then s:=s+[a[i,j]] else exit(false); s:=[]; for i:=4 to 6 do for j:=1 to 3 do if not(a[i,j] in s)then s:=s+[a[i,j]] else exit(false); s:=[]; for i:=7 to 9 do for j:=1 to 3 do if not(a[i,j] in s)then s:=s+[a[i,j]] else exit(false); s:=[]; for i:=1 to 3 do for j:=4 to 6 do if not(a[i,j] in s)then s:=s+[a[i,j]] else exit(false); s:=[]; for i:=4 to 6 do for j:=4 to 6 do if not(a[i,j] in s)then s:=s+[a[i,j]] else exit(false); s:=[]; for i:=7 to 9 do for j:=4 to 6 do if not(a[i,j] in s)then s:=s+[a[i,j]] else exit(false); s:=[]; for i:=1 to 3 do for j:=7 to 9 do if not(a[i,j] in s)then s:=s+[a[i,j]] else exit(false); s:=[]; for i:=4 to 6 do for j:=7 to 9 do if not(a[i,j] in s)then s:=s+[a[i,j]] else exit(false); s:=[]; for i:=7 to 9 do for j:=7 to 9 do if not(a[i,j] in s)then s:=s+[a[i,j]] else exit(false); exit(true);

end;

begin readln(n); for i:=1 to n do begin for j:=1 to 9 do for k:=1 to 9 do read(a[j,k]); readln; if ss then writeln('Right') else writeln('Wrong'); end; end. p1095 美元 【描述】 在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元,使他 从 100 美元开始,最后能获得最高可能的价值。 【输入格式】 输入文件的第一行是一个自然数 N,1≤N≤100,表示戴维学习汇率的天数。 接下来的 N 行中每行是一个自然数 A,1≤A≤1000。第 i+1 行的 A 表示预先知道的第 i+1 天的平均汇率, 在这一天中,戴维既能用 100 美元买 A 马克也能用 A 马克购买 100 美元。 【输出格式】 输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元,保留两位小数)。 【样例输入】 5 400 300 500 300 250 【样例输出】 266.67 【题解】 用贪心求解 每次选能得到最多钱的那一天 【参考程序】 program trjk; var n,i,j,k,l,x,y:longint; s:real; a:array[1..100]of longint; begin readln(n);

for i:=1 to n do readln(a[i]); x:=1; y:=2; s:=100; a[n+1]:=10000; while x<n do begin if a[x]>a[y] then begin while a[y]>a[y+1] do inc(y); s:=s*a[x]/a[y]; x:=y+1; y:=x+1; end else begin inc(x); inc(y); end; end; writeln(s:0:2); end. p1096 数字组合 【描述】 在 N 个数中找出其和为 M 的若干个数。先读入正整数 N(1<N<100)和 M(1<M<10000), 再读入 N 个正 数(可以有相同的数字,每个数字均在 1000 以内) 在这 N 个数中找出若干个数, 使它们的和是 M, 把 , 满足条件的数字组合都找出来以统计组合的个数,输出组合的个数(不考虑组合是否相同) 。要求你的程序 运行时间不超过 1 秒。 【输入格式】 第一行是两个数字,表示 N 和 M。 第二行起是 N 个数。 【输出格式】 就一个数字,表示和为 M 的组合的个数。 【样例输入】 44 1122 【样例输出】 3 【题解】 又是一题背包问题 【参考程序】 program gjk; var i,j,n,m:longint;

a:array[1..100]of longint; f:array[0..10000]of longint; begin readln(n,m); for i:=1 to n do read(a[i]); fillchar(f,sizeof(f),0); f[0]:=1; for i:=1 to n do for j:=m downto a[i] do f[j]:=f[j]+f[j-a[i]]; writeln(f[m]); end. p1099 超级书架 【描述】 Farmer John 最近为奶牛们的图书馆添置了一个巨大的书架,尽管它是如此 的大,但它还是几乎瞬间就被各种各样的书塞满了。现在,只有书架的顶上还留 有一点空间。 所有 N(1 <= N <= 20,000)头奶牛都有一个确定的身高 H_i (1 <= H_i <= 10,000)。设所有奶牛身高的和为 S。书架的高度为 B,并且保证 1 <= B <= S < 2,000,000,007。 为了够到比最高的那头奶牛还要高的书架顶,奶牛们不得不象演杂技一般, 一头站在另一头的背上,叠成一座“奶牛塔” 。当然,这个塔的高度,就是塔中 所有奶牛的身高之和。为了往书架顶上放东西,所有奶牛的身高和必须不小于书 架的高度。显然,塔中的奶牛数目越多,整座塔就越不稳定,于是奶牛们希望在 能够到书架顶的前提下,让塔中奶牛的数目尽量少。 现在,奶牛们找到了你,希望你帮她们计算这个最小的数目 【输入格式】 * 第 1 行: 2 个用空格隔开的整数:N 和 B * 第 2..N+1 行: 第 i+1 行是 1 个整数:H_i 【输出格式】 * 第 1 行: 输出 1 个整数,即最少要多少头奶牛叠成塔,才能够到书架顶部 【样例输入】 6 40 6 18 11 13 19 11 【样例输出】 3 【题解】

忒水的一题 排序 【参考程序】 program gtjkd; var i,j,n,b,s:longint; h:array[1..20000]of longint;

procedure qs(l,r:longint); var i,j,m,t:longint; begin i:=l; j:=r; m:=h[(l+r) DIV 2]; repeat while h[i]<m do inc(i); while h[j]>m do dec(j); if i<=j then begin t:=h[i]; h[i]:=h[j]; h[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;

begin readln(n,b); s:=0; for i:=1 to n do readln(h[i]); qs(1,n); i:=n; repeat inc(s,h[i]); dec(i); until s>=b; writeln(n-i); end. p1100 超级书架 2

【描述】 Farmer John 最近为奶牛们的图书馆添置了一个巨大的书架,尽管它是如此 的大,但它还是几乎瞬间就被各种各样的书塞满了。现在,只有书架的顶上还留 有一点空间。 所有 N(1 <= N <= 20)头奶牛都有一个确定的身高 H_i (1 <= H_i <= 1,000,000 - 好高的奶牛>_<)。设所有奶牛身高的和为 S。书架的 高度为 B,并且保证 1 <= B <= S。 为了够到比最高的那头奶牛还要高的书架顶,奶牛们不得不象演杂技一般, 一头站在另一头的背上,叠成一座“奶牛塔” 。当然,这个塔的高度,就是塔中 所有奶牛的身高之和。为了往书架顶上放东西,所有奶牛的身高和必须不小于书 架的高度。 塔叠得越高便越不稳定,于是奶牛们希望找到一种方案,使得叠出的塔在高 度不小于书架高度的情况下,高度尽可能小。你也可以猜到你的任务了:写一个 程序,计算奶牛们叠成的塔在满足要求的情况下,最少要比书架高多少。 【输入格式】 * 第 1 行: 2 个用空格隔开的整数:N 和 B * 第 2..N+1 行: 第 i+1 行是 1 个整数:H_i 【输出格式】 * 第 1 行: 输出 1 个非负整数,即奶牛们叠成的塔最少比书架高的高度 【样例输入】 5 16 3 1 3 5 6 【样例输出】 1 【题解】 目前这道题我还没有想出有效的算法,由于 n 最大为 20, 我是用 DFS+最优剪枝过的。 【参考程序】 program gfjkd; var i,j,n,b,min:longint; h:array[1..20]of longint;

procedure dfs(k,s:longint); var i:longint; begin if s>=b then if s-b<min then begin min:=s-b; exit;

end; for i:=k+1 to n do dfs(i,s+h[i]); end;

begin readln(n,b); for i:=1 to n do readln(h[i]); min:=maxlongint; dfs(0,0); writeln(min); end. p1101 字典序 【描述】 按照字典序将字符串数组排序 【输入格式】 第 1 行 n 表示 n 个字符串 第 2 到 n+1 行为 n 个字符串 只会出现小写字母 【输出格式】 N 行,每行分别一个字符串,按照字典序顺序 【样例输入】 2 a b 【样例输出】 a b 【题解】 很简单的字符串处理,排序用快排。 读入用 ansistring 【参考程序】 program gjkd; var i,n:longint; a:array[1..10000]of ansistring;

procedure qs(l,r:longint); var i,j:longint; m,t:ansistring; 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;

begin readln(n); for i:=1 to n do readln(a[i]); qs(1,n); for i:=1 to n do writeln(a[i]); end. p1103 多项式输出 【描述】 一元 n 次多项式可用如下的表达式表示: f(x)=an*x^n+an-1*x^n-1+...+a1*x+a0,an<>0 其中,ai*a^x 称为 i 次项,ai 称为 i 次项的系数。给出一个一元多项式各项的次数和系 数,请按照如下规定的格式要求输出该多项式: 1. 多项式中自变量为 x,从左到右按照次数递减顺序给出多项式。 2. 多项式中只包含系数不为 0 的项。 3. 如果多项式 n 次项系数为正,则多项式开头不出现“+”号,如果多项式 n 次项系 数为负,则多项式以“-”号开头。 4. 对于不是最高次的项,以“+”号或者“-”号连接此项与前一项,分别表示此项 系数为正或者系数为负。紧跟一个正整数,表示此项系数的绝对值(如果一个高于 0 次的项, 其系数的绝对值为 1,则无需输出 1) 。如果 x 的指数大于 1,则接下来紧跟的指数部分的形 式为“x^b” ,其中 b 为 x 的指数;如果 x 的指数为 1,则接下来紧跟的指数部分形式为“x” ; 如果 x 的指数为 0,则仅需输出系数即可。 5. 多项式中,多项式的开头、结尾不含多余的空格。 【输入格式】 输入文件名为 poly.in,共有 2 行 第一行 1 个整数,n,表示一元多项式的次数。

第二行有 n+1 个整数,其中第 i 个整数表示第 n-i+1 次项的系数,每两个整数之间用空 格隔开。 【输出格式】 输出文件 poly.out 共 1 行,按题目所述格式输出多项式。 【样例输入】 输入样例 1: 5 100 -1 1 -3 0 10 输入样例 2: 3 -50 0 0 1 【样例输出】 输出样例 1: 100x^5-x^4+x^3-3x^2+10 输出样例 2: -50x^3+1 【题解】 注意前导零,和+-1 的情况就行了 【参考程序】 program dfuij; var i,n:longint; a:array[0..1000]of longint; begin readln(n); for i:=0 to n do read(a[i]); if a[0]<>0 then if a[0]=1 then write('x^',n) else if a[0]=-1 then write('-x^',n) else write(a[0],'x^',n); for i:=1 to n-2 do begin if a[i]>0 then if a[i]=1 then write('+x^',n-i) else write('+',a[i],'x^',n-i); if a[i]<0 then if a[i]=-1 then write('-x^',n-i) else write('-',abs(a[i]),'x^',n-i); end; if a[n-1]>0 then if a[n-1]=1 then write('+x') else write('+',a[n-1],'x'); if a[n-1]<0 then if a[n-1]=-1 then write('-x')

else write('-',abs(a[n-1]),'x'); if a[n]>0 then write('+',a[n]); if a[n]<0 then write(a[n]); end. p1104 分数线划定 【描述】 世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才,A 市对 所有报名的选手进行了笔试,笔试分数达到面试分数线的选手方可进入面试。面试分数线根 据计划录取人数的 150%划定,即如果计划录取 m 名志愿者,则面试分数线为排名第 m*150% (向下取整)名的选手的分数,而最终进入面试的选手为笔试成绩不低于面试分数线的所有 选手。 现在就请你编写程序划定面试分数线,并输出所有进入面试的选手的报名号和笔试成 绩。 【输入格式】 输入文件名为 score.in。 第一行,两个整数 n,m(5 ≤ n ≤ 5000,3 ≤ m ≤ n) ,中间用一个空格隔开,其 中 n 表示报名参加笔试的选手总数,m 表示计划录取的志愿者人数。输入数据保证 m*150% 向下取整后小于等于 n。 第二行到第 n+1 行,每行包括两个整数,中间用一个空格隔开,分别是选手的报名号 k (1000 ≤ k ≤ 9999)和该选手的笔试成绩 s(1 ≤ s ≤ 100) 。数据保证选手的报名号各 不相同。 【输出格式】 输出文件 score.out。 第一行,有两个整数,用一个空格隔开,第一个整数表示面试分数线;第二个整数为 进入面试的选手的实际人数。 从第二行开始,每行包含两个整数,中间用一个空格隔开,分别表示进入面试的选手 的报名号和笔试成绩,按照笔试成绩从高到低输出,如果成绩相同,则按报名号由小到大的 顺序输出。 【样例输入】 63 1000 90 3239 88 2390 95 7231 84 1005 95 1001 88 【样例输出】 88 5 1005 95 2390 95 1000 90 1001 88 3239 88

【题解】 排序+模拟 【参考程序】 program fhj; var n,m,i,j,s:longint; a,b:array[1..5000]of longint;

procedure qs(l,r:longint); var i,j,m1,m2,t:longint; begin i:=l; j:=r; m1:=a[(l+r) div 2]; m2:=b[(l+r) div 2]; repeat while(b[i]>m2)or((b[i]=m2)and(a[i]<m1))do inc(i); while(b[j]<m2)or((b[j]=m2)and(a[j]>m1))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); if l<j then qs(l,j); end;

begin s:=0; readln(n,m); for i:=1 to n do readln(a[i],b[i]); qs(1,n); m:=trunc(m*1.5); for i:=n downto 1 do if b[i]>=b[m] then inc(s); writeln(b[m],' ',s); for i:=1 to n do

if b[i]>=b[m] then writeln(a[i],' ',b[i]) else break; end. p1108 守望者的逃离 【描述】 恶魔猎手尤迪安野心勃勃,她背叛了暗夜精灵,率领深藏在海底的[哔——]族企图叛变。守望者在与尤迪 安的交锋中遭遇了围杀,被困在一个荒芜的大岛上。为了杀死守望者,尤迪安开始对这个荒岛施咒,这座 岛很快就会沉下去。到那时,岛上的所有人都会遇难。守望者的跑步速度为 17m/s,以这样的速度是无法 逃离荒岛的。庆幸的是守望者拥有闪烁法术,可在 1s 内移动 60m,不过每次使用闪烁法术都会消耗魔法值 10 点。守望者的魔法值恢复的速度为 4 点/s,只有处在原地休息状态时才能恢复。 现在一直守望者的魔法初值 M,他所在的初始位置与岛的出口之间的距离 S,岛沉没的时间 T。你的任务 是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛,若不能逃出,则输出守望者在剩下的时间内 能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位,且每次活动的持续时间为正数秒。 距离单位为米(m)。 【输入格式】 输入文件 escape.in 仅一行,包括空格隔开的三个非负整数 M, S, T。 【输出格式】 输出文件 escape.out 包含两行: 第 1 行为字符串“Yes”或“No” (区分大小写) ,即守望者是否能逃离荒岛。 2 行包含一个整数。第一行为“Yes” (区分大小写)时表示守望者逃离荒岛的最短时间;第一行为“No” (区分大小写)时表示守望者能走的最远距离。 【样例输入】 39 200 4 【样例输出】 No 197 【题解】 动态规划 f1[i]表示前 i 秒用魔法闪烁能跑得最远距离 f2[i]表示前 i 秒用跑步能跑得最远距离 则 f1[i]:=f1[i-1]+60 【参考程序】 program fhg; var m,s,t,i,j:longint; f1,f2:array[0..300000]of longint; (m>=10)

f2[i]:=max{f2[i-1],f1[i-1]}+17;

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

begin readln(m,s,t); fillchar(f1,sizeof(f1),0); fillchar(f2,sizeof(f2),0); for i:=1 to t do begin if m>=10 then begin f1[i]:=f1[i-1]+60; m:=m-10; end else begin f1[i]:=f1[i-1]; m:=m+4; end; f2[i]:=max(f2[i-1],f1[i-1])+17; if(f1[i]>=s)or(f2[i]>=s)then begin writeln('Yes'); writeln(i); halt; end; end; writeln('No'); writeln(max(f1[t],f2[t])); end. p1109 N 阶幻方 【描述】 在一个由若干个排列整齐的数组成的正方形 中,图中任意一横行、一纵行及对角线的几个数 之和都相等,具有这种性质的图表,称为幻方。 目前已经确定,N 阶幻方(n>=3)都可以构造出 幻方。 我们的问题是,当构造的幻方,任意一横行 的数累加的和是多少。 【输入格式】 一个数 n 表示 n 阶幻方 n<=10000 【输出格式】 一个数,任意一横行的数累加的和 【样例输入】 3 【样例输出】

15 【题解】 公式: (n*n*n+n)/2 【参考程序】 program hdfjk; var n:qword; s:comp; begin readln(n); s:=(n*n*n+n)/2; writeln(s:0:0); end. p1110 潜伏者 【描述】 R 国和 S 国正陷入战火之中,双方都互派间谍, 潜入对方内部,伺机行动。 历尽艰险后,潜伏于 S 国的 R 国间谍小 C 终于摸 清了 S 国军用密码的编码规则: 1. S 国军方内部欲发送的原信息经过加密后在网 络上发送,原信息的内容与加密后所 得的内容均由大写字母‘A’-‘Z’构成(无空格等其他 字符) 。 2. S 国对于每个字母规定了对应的“密字” 。加密 的过程就是将原信息中的所有字母替 换为其对应的“密字” 。 3. 每个字母只对应一个唯一的“密字” ,不同的字 母对应不同的“密字”“密字”可以 。 和原字母相同。 例如,若规定‘A’的密字为‘A’‘B’的密字为‘C’ , (其 他字母及密字略) ,则原信 息“ABA”被加密为“ACA” 。 现在,小 C 通过内线掌握了 S 国网络上发送的一 条加密信息及其对应的原信息。小 C 希望能通过这条信息,破译 S 国的军用密码。小 C 的破译过程是这样的:扫描原信息,对 于原信息中的字母 x(代表任一大写字母) ,找到 其在加密信息中的对应大写字母 y,并认为 在密码里 y 是 x 的密字。如此进行下去直到停止于 如下的某个状态: 1. 所有信息扫描完毕, ‘A’-‘Z’ 所有 26 个字母在 原信息中均出现过并获得了相应 的“密字” 。 2. 所有信息扫描完毕,但发现存在某个(或某

些)字母在原信息中没有出现。 3. 扫描中发现掌握的信息里有明显的自相矛盾 或错误(违反 S 国密码的编码规则) 。例 如某条信息“XYZ”被翻译为“ABA”就违反了“不同字 母对应不同密字”的规则。 在小 C 忙得头昏脑涨之际,R 国司令部又发来电 报,要求他翻译另外一条从 S 国刚刚 截取到的加密信息。现在请你帮助小 C:通过内线 掌握的信息,尝试破译密码。然后利用破 译的密码,翻译电报中的加密信息。 【输入格式】 输入共 3 行,每行为一个长度在 1 到 100 之 间的字符串。 第 1 行为小 C 掌握的一条加密信息。 第 2 行为第 1 行的加密信息所对应的原信息 。 第 3 行为 R 国司令部要求小 C 翻译的加密信 息。 输入数据保证所有字符串仅由大写字母‘A’ -‘Z’构成,且第 1 行长度与第 2 行相等。 【输出格式】 输出共 1 行。 若破译密码停止时出现 2,3 两种情况,请 你输出“Failed” (不含引号,注意首字母 大 写,其它小写) 。 否则请输出利用密码翻译电报中加密信息后 得到的原信息。 【样例输入】 AA AB EOWIE 【样例输出】 Failed 【题解】 题目很简单,只要仔细把题目读懂就可以了 我就因为题目没看仔细错了好几次 【参考程序】 program dfgkdj; var i,j:longint; a,b:array['A'..'Z']of char; ch:char; s,t,st:string; q:boolean;

begin for ch:='A' to 'Z' do begin a[ch]:=' '; b[ch]:=' '; end; readln(s); readln(t); readln(st); if length(s)<26 then begin writeln('Failed'); halt; end; for i:=1 to length(s) do begin if a[s[i]]=' ' then begin a[s[i]]:=t[i]; if b[t[i]]=' ' then b[t[i]]:=s[i] else begin q:=true; for ch:='A' to 'Z' do if b[ch]=' 'then q:=false; if not q then begin writeln('Failed'); halt; end; end end else begin q:=true; for ch:='A' to 'Z' do if a[ch]=' 'then q:=false; if not q then begin writeln('Failed'); halt; end; end;

end; for ch:='A' to 'Z' DO if a[ch]=' 'then begin writeln('Failed'); halt; end; for i:=1 to length(st) do write(a[st[i]]); writeln; end. p1112 舞会 2 【描述】 Victoria 是一位颇有成就的艺术家,他因油画作品《我爱北京天安门》闻名于世界。现在,他为了报答帮助 他的同行们,准备开一个舞会。 Victoria 准备邀请 n 个已经确定的人,可是问题来了: n 个人每一个人都有一个小花名册,名册里面写着他所愿意交流的人的名字。比如说在 A 的人名单里写了 B,那么表示 A 愿意与 B 交流;而且如果 A 名单里面有 B,那么 B 名单里面肯定有 A,也就是说两个人如 果一方愿意和另一方交流,那么另一方也肯定愿意和这一方交流。 Victoria 觉得需要在这 n 个人里面确定 m 个人, 保证这 m 个人每一个人都能在舞会中找到至少 k 个人交流, 并求出一种方案以确定 m 的最大值是多少。 注意:自己的名单里面不会有自己的名字。 【输入格式】 第一行两个数 n 和 k。 接下来 n 行, i+1 行表示编号为 i 的人的小花名册名单, 每 名单以 0 结束。 1<=n,k<=200。 【输出格式】 一个数,m。 【样例输入】 22 1 4 5 10 11 20 21 0 2 3 6 8 11 16 0 2 3 5 8 12 15 16 18 0 1 5 6 10 11 12 16 18 0 1 3 4 16 20 0 2 4 19 21 22 0 8 9 13 19 20 0 2 3 7 10 19 0 7 10 14 16 19 0 1 4 8 9 10 20 0 1 2 4 18 19 20 21 0 3 4 13 0 7 12 15 16 18 19 21 22 0 9 16 0 3 13 21 0

2 3 4 5 9 13 14 20 0 18 22 0 3 4 11 13 17 21 0 6 7 8 9 11 13 19 21 22 0 1 5 7 10 11 16 21 22 0 1 6 11 13 15 18 19 20 0 6 13 17 19 20 0 【样例输出】 22 【题解】 这道题完全是贪心 统计与每个选手交流的人数看是否>=k。 【参考程序】 program dfjkd; var n,k,m,i,j,t:longint; begin readln(n,k); m:=0; for i:=1 to n do begin t:=0; while not eoln do begin read(j); if j<>0 then inc(t); end; if t>=k then inc(m); readln; end; writeln(m); end. p1113 魔族密码 【描述】 风之子刚走进他的考场,就?? 花花:当当当当~~偶是魅力女皇——花花! !^^(华丽出场,礼炮,鲜花) 风之子:我呕??(杀死人的眼神)快说题目!否则??-_-### 花花:??咦~~好冷~~我们现在要解决的是魔族的密码问题(自我陶醉:搞不好魔族里面还会有人用 密码给我和菜虫写情书咧,哦活活,当然是给我的比较多拉*^_^*) 。魔族现在使用一种新型的密码系统。 每一个密码都是一个给定的仅包含小写字母的英文单词表,每个单词至少包含 1 个字母,至多 75 个字母。 如果在一个由一个词或多个词组成的表中,除了最后一个以外,每个单词都被其后的一个单词所包含,即 前一个单词是后一个单词的前缀,则称词表为一个词链。例如下面单词组成了一个词链: i int

integer 但下面的单词不组成词链: integer intern 现在你要做的就是在一个给定的单词表中取出一些词,组成最长的词链,就是包含单词数最多的词链。 将它的单词数统计出来,就得到密码了。 风之子:密码就是最长词链所包括的单词数阿?? 花花:活活活,还有,这些文件的格式是,第一行为单词表中的单词数 N(1<=N<=2000) ,下面每一 行有一个单词,按字典顺序排列,中间也没有重复的单词咧! !你要提交的文件中只要在第一行输出密码就 行啦^^看你长得还不错,给你一个样例吧: 【输入格式】 第一行为单词表中的单词数 N(1<=N<=2000) ,下面每一行有一个单词,按字典顺序排列,中间也没 有重复的单词咧! ! 【输出格式】 一个数,所得到的密码 【样例输入】 5 i int integer intern internet 【样例输出】 4 【题解】 动态规划,类似求最长不下降子序列 【参考程序】 program fgjk; var i,j,n,sum:longint; a:array[1..2000]of string; f:array[1..2000]of longint;

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

begin readln(n); for i:=1 to n do readln(a[i]); fillchar(f,sizeof(f),1); for i:=1 to n do

f[i]:=1; sum:=0; for i:=n-1 downto 1 do begin for j:=1+i to n do if pos(a[i],a[j])=1 then f[i]:=max(f[i],f[j]+1); if f[i]>sum then sum:=f[i]; end; writeln(sum); end. p1116 被 7 整除 【描述】 要求输出从 1 到 n(1<=n<=10^6) ,有多少个整数 n,满足 2^n-n^2 能被 7 整除 【输入格式】 一个数 n 【输出格式】 一个数,即满足的个数 【样例输入】 2 【样例输出】 1 【题解】 这是一道数论的题目 我们可以先求出 2^n mod 7 的值和 n^2 mod 7 的值 经过分析我们发现 2^n mod 7 是 3 个一循环,n^2 mod 7 是 7 个一循环 1-21 中有六个能整除 7。 所以个数为 n*6 div 21. 【参考程序】 program dsf; const a:array[0..21]of longint=(0,0,1,1,2,3,4, 4,4,4,5,5,5,5, 5,6,6,6,6,6,6,6);

var n:longint; begin readln(n); writeln(n div 21*6+a[n mod 21]); end. p1117 拯救 ice-cream 【描述】 给你一张坐标图,s 为 Tina 的初始位置,m 为 Ice-cream home 的位置, ‘.’为路面,Tina 在上面,每单位 时间可以移动一格; ‘#’为草地,Tina 在上面,每两单位时间可以移动一格(建议不要模仿—毕竟 Tina 还

小)‘o’是障碍物,Tina 不能在它上面行动。也就是说,Tina 只能在路面或草地上行走,必须绕过障碍物, ; 并到达冰淇淋店。但是????不保证到达时,冰淇淋还未融化,所以??就请聪明的你??选择最佳的 方案啦????如果,Tina 到的时候,冰淇淋已经融化完了,那她可是会哭的。 【输入格式】 依次输入冰淇淋的融化时间 t(0<t<1000),坐标图的长 x,宽 y(5<=x,y<=25){太长打起来好累??},和 整张坐标图。 【输出格式】 判断按照最优方案是否可以赶在冰淇淋融化之前到达冰淇淋店(注:当 T=最优方案所用时间,则判断为未 赶到) ,如赶到,输出所用时间;如未赶到,输出 Tina 的哭声——“55555” (不包括引号) 。 【样例输入】 11 10 8 ......s... .......... #ooooooo.o #......... #......... #......... #.....m... #......... 【样例输出】 10 【题解】 这题一眼就可以看出用广搜做 【参考程序】 program ghdjk; const dx:array[1..4]of longint=(-1,0,1,0); dy:array[1..4]of longint=(0,1,0,-1); var t,h,i,j,n,m,x1,x2,y1,y2,x,y,s:longint; a:array[1..25,1..25]of -1..1; r:array[1..10000]of record x,y:longint; end; b:array[1..25,1..25]of longint; ch:char; begin readln(s); readln(m); readln(n); for i:=1 to n do begin for j:=1 to m do begin

read(ch); if ch='#' then a[i,j]:=-1; if ch='.' then a[i,j]:=0; if ch='o' then a[i,j]:=1; if ch='s' then begin x1:=i; y1:=j; a[i,j]:=0; end; if ch='m' then begin x2:=i; y2:=j; a[i,j]:=0; end; end; readln; end; filldword(b,sizeof(b)div 4 ,100000); b[x1,y1]:=0; h:=0; t:=1; r[1].x:=x1; r[1].y:=y1; while h<>t do begin inc(h); for i:=1 to 4 do begin x:=r[h].x+dx[i]; y:=r[h].y+dy[i]; if(x>0)and(x<=n)and(y>0)and(y<=m)then if a[x,y]<>1 then begin if a[x,y]=0 then if b[x,y]>b[r[h].x,r[h].y]+1 then begin b[x,y]:=b[r[h].x,r[h].y]+1; inc(t); r[t].x:=x; r[t].y:=y; end; if a[x,y]=-1 then

if b[x,y]>b[r[h].x,r[h].y]+2 then begin b[x,y]:=b[r[h].x,r[h].y]+2; inc(t); r[t].x:=x; r[t].y:=y; end; end; end; end; if b[x2,y2]>=s then writeln('55555') else writeln(b[x2,y2]); end.

p1118 a^b 【描述】 求 a^b 由于结果可能很大,我们现在只需要知道这个值 mod 1012 就可以了(为什么是 1012?我的生日) a<1000000 b<1000000 【输入格式】 第一行两个数 a b 【输出格式】 一行,就是 mod 1012 的值 【样例输入】 22 【样例输出】 4 【题解】 这道题可以用快速幂来做(秒杀) 【参考程序】 program gfidj; var a,b,s:longint;

function f(b:longint):longint; var k,m:longint; begin if b=0 then exit(1); if b and 1=0 then begin m:=f(b shr 1); k:=(m*m)mod 1012; exit(k);

end else begin m:=f(b shr 1); k:=(m*m*s)mod 1012; exit(k); end; end;

begin readln(a,b); s:=a mod 1012; writeln(f(b)); end.

p1118 a^b2 【描述】 求 a^b 由于结果可能很大,我们现在只需要知道这个值 mod 1012 就可以了(为什么是 1012?我的生日) 有 N 组数 n<=5 a<=100 b<=maxlongint; 【输入格式】 第 1 行 1 个数 n 第 2 到 n+1 行 两个数 a,b 【输出格式】 n 行 每个 a^b mod 1012 的值 【样例输入】 1 22 【样例输出】 4 【题解】 还是用快速幂做 【参考程序】 program gfidj; var a,b,s,n,i:longint;

function f(b:longint):longint; var k,m:longint; begin if b=0 then exit(1);

if b and 1=0 then begin m:=f(b shr 1); k:=(m*m)mod 1012; exit(k); end else begin m:=f(b shr 1); k:=(m*m*s)mod 1012; exit(k); end; end;

begin readln(n); for i:=1 to n do begin readln(a,b); s:=a mod 1012; writeln(f(b)); end; end. p1124 花店橱窗 【描述】 每种花都有一个标识,假设杜鹃花的标识数为 1,秋海棠的标识数为 2,康乃馨的标识数为 3,所有的花束 在放入花瓶时必须保持其标识数的顺序,即:杜鹃花必须放在秋海棠左边的花瓶中,秋海棠必须放在康乃 馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余的花瓶必须空置,且每个花瓶中只能放一束花。 每种花放在不同的瓶子里会产生不同的美观程度,美观程度可能是正数也可能是负数。 上述例子中,花瓶与花束的不同搭配所具有的美观程度,如下表所示: 花 1 1 (杜鹃花) 2 (秋海棠) 3 (康乃馨) 7 5 -21 23 21 5 2 -5 -4 -4 3 -24 10 -20 瓶 4 16 23 20 5

根据上表,杜鹃花放在花瓶 2 中,会显得非常好看;但若放在花瓶 4 中则显得十分难看。 为取得最大美观程度,你必须在保持花束顺序的前提下,使花束的摆放取得最大的美学值,并求出每 种花应该摆放的花瓶的编号。 【输入格式】 第 1 行:两个整数 F 和 V,表示 xq 和 xz 一共有 F 种花,V 个花瓶。(1<=F<=V<=100) 第 2 行到第 F+1 行: 每行有 V 个数, 表示花摆放在不同花瓶里的美观程度值 value。 (美观程度和不超过 maxint, 美观程度有正有负。) 【输出格式】

输出有两行:第一行为输出最大美观程度和的值,第二行有 F 个数表示每朵花应该摆放的花瓶的编号。 【样例输入】 35 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20 【样例输出】 53 245 【题解】 动态规划 f[i,j]:=max{f[i-1,k]}+a[i,j] (2<=i<=f,i<=j<=v-f+i,i-1<=k<=j-1) 【参考程序】 program fgjk; var i,j,f,v,k,max:longint; a:array[1..100,1..100]of longint; g:array[1..100,1..100]of longint; p:array[0..100,0..100]of longint; b:array[1..100]of longint; begin fillchar(g,sizeof(g),0); fillchar(p,sizeof(p),0); readln(f,v); for i:=1 to f do begin for j:=1 to v do read(a[i,j]); readln; end; for i:=1 to v do g[1,i]:=a[1,i]; for i:=2 to f do for j:=i to v+i-f do begin g[i,j]:=low(g[i,j]); for k:=i-1 to j-1 do if g[i,j]<g[i-1,k] then begin g[i,j]:=g[i-1,k]; p[i,j]:=k; end; inc(g[i,j],a[i,j]); end; max:=0;

k:=f; for i:=f+1 to v do if g[f,i]>g[f,k] then k:=i; writeln(g[f,k]); for i:=f downto 1 do begin b[i]:=k; k:=p[i,k]; end; for i:=1 to f-1 do write(b[i],' '); writeln(b[f]); end. p1127 计算细胞数 【描述】 一矩形阵列由数字 0 到 9 组成,数字 1 到 9 代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同 一细胞,求给定矩形阵列的细胞个数。 如:阵列 0234500067 1034560500 2045600671 0000000089 有4个细胞 【输入格式】 第一行 :两个数字 M N (1<=M<=50 1<=N<80)表示该阵列有M行N列 从第2行到第M+1行 【输出格式】 一行: 细胞个数 【样例输入】 4 10 0234500067 1034560500 2045600671 0000000089 【样例输出】 4 【题解】 最简单的广搜 【参考程序】 program gfjk; const dx:array[1..4]of longint=(-1,0,1,0); dy:array[1..4]of longint=(0,-1,0,1); 每行有连续的N个字符

var s,i,j,n,m:longint; a:array[1..100,1..100]of char;

procedure bfs(x1,y1:longint); var i,x,y,h,t:longint; r:array[1..1000]of record x,y:longint; end; begin inc(s); h:=0; t:=1; a[x1,y1]:='0'; r[1].x:=x1; r[1].y:=y1; while h<>t do begin inc(h); for i:=1 to 4 do begin x:=r[h].x+dx[i]; y:=r[h].y+dy[i]; if(x>0)and(x<=n)and(y>0)and(y<=m)then if a[x,y]<>'0' then begin a[x,y]:='0'; inc(t); r[t].x:=x; r[t].y:=y; end; end; end; end;

begin s:=0; readln(n,m); 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

for j:=1 to m do if a[i,j]<>'0' then bfs(i,j); writeln(s); end. p1128 中文大写字母 【描述】 我们在金融机构填写金额时使用的不是阿拉伯数字,而是中文的大写数字。 请写一个程序将数字转换为中文大写数字。 标准大写写法如下:零、壹、贰、参、肆、伍、陆、柒、捌、玖、拾、佰、仟、万、亿 注意:由于测试系统中的编译器不直持汉字,所以 0-9 数字的中文大写还是 0-9 代表, “拾、佰、仟、万、 亿”分别用它们的拼音(shi,bai,qian,wan,yi)代表。 【输入格式】 一个整数数值 n( n>=0 且 n<=2147483647) 【输出格式】 对应的中文大写文字字串 【样例输入】 0000000000 【样例输出】 0 【题解】 一题比较复杂的字符串处理 【参考程序】 program dnhgdj; const a:array[1..10]of string=('','shi','bai','qian','wan','shi', 'bai','qian','yi','shi'); b:array[1..10]of string=('','shi','bai','qian','wan','shiwan', 'baiwan','qianwan','yi','shiyi'); var i,j,k,l:longint; t,r:string; q:boolean; begin readln(t); q:=true; while(t[1]='0')and(length(t)>1)do delete(t,1,1); k:=length(t); for i:=1 to k do if t[i]='0' then q:=false; if not q then begin for i:=1 to k do begin if t[i]<>'0' then

r:=r+t[i]+b[k-i+1] else if(t[i-1]<>'0')and(t[i+1]='0')then r:=r+'0'; end; while(r[length(r)]='0')and(length(r)>1)do delete(r,length(r),1); if r='' then writeln('0') else writeln(r); end else begin r:=''; for i:=1 to k do r:=r+t[i]+a[k-i+1]; writeln(r); end; end. p1129 不高兴的津津 【描述】 津津上初中了。妈妈认为津津应该更加用功学习,所以津津除了上学之外,还要参加妈妈为她报名的各科 复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高 兴,而且上得越久就会越不高兴。假设津津不会因为其它事不高兴,并且她的不高兴不会持续到第二天。 请你帮忙检查一下津津下周的日程安排,看看下周她会不会不高兴;如果会的话,哪天最不高兴。 【输入格式】 输入包括七行数据,分别表示周一到周日的日程安排。每行包括两个小于 10 的非负整数,用空格隔开,分 别表示津津在学校上课的时间和妈妈安排她上课的时间。 【输出格式】 输出包括一行,这一行只包含一个数字。如果不会不高兴则输出 0,如果会则输出最不高兴的是周几(用 1, 2, 3, 4, 5, 6, 7 分别表示周一,周二,周三,周四,周五,周六,周日) 。如果有两天或两天以上不高兴的 程度相当,则输出时间最靠前的一天。 【样例输入】 53 62 72 53 54 04 06 【样例输出】 3 【题解】 水题,模拟法 【参考程序】

program fdgjk; var i,s,t:longint; a:array[1..7]of longint; begin for i:=1 to 7 do begin readln(s,t); a[i]:=s+t; end; for i:=1 to 7 do if a[i]>8 then writeln(i); end. p1130 奖学金 【描述】 期末,每个学生都有 3 门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分 相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学排在前 面,这样,每个学生的排序是唯一确定的。 任务:先根据输入的 3 门课的成绩计算总分,然后按上述规则排序,最后按排名顺序输出前 5 名学生的学 号和总分。注意,在前 5 名同学中,每个人的奖学金都不相同,因此,你必须严格按上述规则排序。例如, 在某个正确答案中,如果前两行的输出数据(每行输出两个数:学号、总分)是: 7 279 5 279 这两行数据的含义是:总分最高的两个同学的学号依次是 7 号、5 号。这两名同学的总分都是 279(总分等 于输入的语文、数学、英语三科成绩之和) ,但学号为 7 的学生语文成绩更高一些。如果你的前两名的输出 数据是: 5 279 7 279 则按输出错误处理,不能得分。 【输入格式】 输入包含 n+1 行: 第 1 行为一个正整数 n,表示该校参加评选的学生人数。 第 2 到 n+1 行,每行有 3 个用空格隔开的数字,每个数字都在 0 到 100 之间。第 j 行的 3 个数字依次表示 学号为 j-1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 1~n(恰好是输入数据 的行号减 1) 。 所给的数据都是正确的,不必检验。 【输出格式】 输出共有 5 行,每行是两个用空格隔开的正整数, 依次表示前 5 名学生的学号和总分。 【样例输入】 6 90 67 80 87 66 91 78 89 91 break;

88 99 77 67 89 64 78 89 98 【样例输出】 6 265 4 264 3 258 2 244 1 237 【数据规模】 50%的数据满足:各学生的总成绩各不相同 100%的数据满足:6<=n<=300 【题解】 排序 【参考程序】 program gh; type arr=array[1..300]of longint; var a:array[1..300,1..4]of longint; b,c,d:arr; i,j,n,k,t,l:longint;

procedure qs(l,r:longint); var i,j,m1,m2,m3,t:longint; begin i:=l;j:=r; m1:=b[(l+r)div 2]; m2:=d[(l+r)div 2]; m3:=c[(l+r)div 2]; repeat while (b[i]>m1)or(b[i]=m1)and(d[i]>m2)or((b[i]=m1)and(d[i]=m2))and(c[i]<m3) do inc(i); while (b[j]<m1)or(b[j]=m1)and(d[j]<m2)or((b[j]=m1)and(d[j]=m2))and(c[j]>m3) do dec(j); if i<=j then begin t:=b[i]; b[i]:=b[j]; b[j]:=t; t:=c[i]; c[i]:=c[j]; c[j]:=t; t:=d[i]; d[i]:=d[j]; d[j]:=t; inc(i); dec(j);

end; until i>j; if l<j then qs(l,j); if i<r then qs(i,r); end;

begin readln(n); for i:=1 to n do for j:=1 to 3 do read(a[i,j]); for i:=1 to n do begin b[i]:=a[i,1]+a[i,2]+a[i,3]; d[i]:=a[i,1]; c[i]:=i; end; qs(1,n); for i:=1 to 5 do writeln(c[i],' ',b[i]); end. p1132 天使之城 【描述】 为了调度火车,火车站设有停放轨道,可存放 5 辆火车。已知从 A 进入车站顺序为 1、2、3??。现在给 你一个调度方案,判断是否可行,如果可行,输出出站顺序。 有以下几种调度方法: A. 将 A 上的头一辆车驶出 B 方向 B. 将 A 上的头一辆车停入暂停轨道 C. 将暂停轨道上最外面的车驶出 B 方向 【输入格式】 输入第一行一个整数 N(n<30)表示调度方案步骤数目。 下一行一个字符串,有 N 个大写字母,表示调度方法。 【输出格式】 输出若不可行(暂停站满了还停车、暂停站空了还出车) ,则输出一行“No” 。 若可行,输出一行“Yes” ,再输出若干行,每行一个整数,表示车出站序列。 【样例输入】 [样例输入 1] 6 ABBCCA [样例输入 2] 5 BACAC 【样例输出】 [样例输出 1]

Yes 1 3 2 4 [样例输出 2] No 【题解】 按照题目要求用栈模拟 【参考程序】 program fgj; var i,n,ta,tb,tc:longint; a,b,c:array[1..100]of longint; s:array[1..30]of char; begin for i:=1 to 100 do a[i]:=101-i; ta:=100; tb:=0; tc:=0; readln(n); for i:=1 to n do read(s[i]); for i:=1 to n do case s[i] of 'A':begin inc(tb); b[tb]:=a[ta]; dec(ta); end; 'B':begin inc(tc); c[tc]:=a[ta]; dec(ta); end; 'C':begin if tc=0 then begin writeln('No'); halt; end; inc(tb); b[tb]:=c[tc]; dec(tc);

end; end; if tc>0 then begin writeln('No'); halt; end; writeln('Yes'); for i:=1 to tb do writeln(b[i]); end. p1133 银行取款 【描述】 五一马上到了,凡凡的爸爸打算上银行去取点钱,带着一向表现很好的凡凡同学到海南旅游,凡凡的爸爸 到银行时发现很多人在办理业务,凡凡的爸爸就自觉地在排队机上去了一个业务号码,并焦急的等待着银 行柜台叫自己的号码...... 【输入格式】 输入中包含 I(表示等待办理业务)和顾客的序号; 或者 O(表示办理完业务的人离开) ; 输入数据不超过 100 行。 【输出格式】 输出银行排队中出队顾客序列,若队列为空(没人等待) ,则输出“None” 【样例输入】 O I1 I2 O I3 O O O 【样例输出】 None 1 2 3 None 【题解】 按照题目要求用队列模拟 【参考程序】 program gfhdf; var h,t,i,l:longint; q:array[1..10000]of longint;

s,k:string; begin h:=0; t:=0; s:=' '; while s<>'' do begin readln(s); if s='' then break; if s[1]='O' then if h=t then writeln('None') else begin inc(h); writeln(q[h]); end else begin l:=pos(' ',s); k:=copy(s,l+1,length(s)-l+1); inc(t); val(k,q[t]); end; end; end. p1134 CCR 的中考之考前计划 【描述】 CCR 在 2011 年的中考复习时给自己定了个计划,计划包括了 N 天的复习科目(这一天复习的科目可以为 语文、英语和随机安排三种,用 c,e 和 w 表示)注意 3<=N<=350。 但是 CCR 在定完计划后又改变了主意,决定把科目专项复习,于是他(应该说是“我” )把这个计划 的尾和头连接了起来,接着再从其中的某一天起,把这个计划断开,从一端开始计算同一科目的最大数目 (随机可以被当成其中任何一个科目,只要想这么做) ,另一端也这么做。计算规则如下: 你需要计算的科目总和取决于端口的科目名称(如果是随机就随机了) ,接着向后累计,直到找到一个 其他科目(随机不算啊! )为止。CCR 写了一个程序以确定他最多可以复习多少天的同一科目,现在他(就 是“我”了)来考考大家。 【输入格式】 第 1 行: N, 就是天数 第 2 行: 长度为 N 的字符串, 每个字符是 c ,e 或 w。 【输出格式】 单独的一行包含 CCR 可以复习的同一科目的天数最大值。 【样例输入】 1 c

【样例输出】 1 【题解】 搜索 枚举每一个点向两边搜索 【参考程序】 program gj; var i,j,t,n,max,m:longint; s:ansistring; ch:char; begin readln(m); readln(s); n:=length(s); s:=s+s+s; max:=0; for i:=n+1 to 2*n do begin j:=i-1; t:=0; repeat inc(j); if s[j]<>'w' then ch:=s[j]; until ch<>'w'; j:=i; repeat if((s[j]='w')or(s[j]=ch))and(t<n)then inc(t); inc(j); until(t=n)or((s[j]<>'w')and(s[j]<>ch)); j:=i; repeat dec(j); if s[j]<>'w' then ch:=s[j]; until s[j]<>'w'; j:=i-1; repeat if((s[j]='w')or(s[j]=ch))and(t<n)then inc(t); dec(j); until(t=n)or((s[j]<>'w')and(s[j]<>ch)); if t>max then max:=t; end;

if max>m then max:=m; writeln(max); end. p1142 阶乘统计 3 【描述】 1000 的阶乘 1*2*3*...*1000 结果是一个很大的数,求这么大的数末尾有多少个连续的零。 【输入格式】 本题有多组测试数据 每组数据含有一个正整数 N。(N 不大于....算了,无限大,OK?) 【输出格式】 输出一个整数,表示 N!的末尾有多少个连续的零。 【样例输入】 1000 【样例输出】 249 【题解】 这是一道数论问题 由于 10=2*5,所以我们只要统计 n!质因数分解中 5 的个数就可以了 公式 sum=[n/5]+[n/25]+[n/125]+??[n/(5^k)] 【参考程序】 program gfhjg; var n,i,s:qword; begin s:=0; readln(n); i:=1; repeat i:=i*5; s:=s+trunc(n/i); until trunc(n/i)=0; writeln(s); end. p1152 高薪聘请歌词修改人 【背景】 小胖是一个 lrc 歌词编辑者,他每天的工作是制作歌曲相应的 lrc 歌词文件。 (lrc 歌词文件的格式由一个时间轴与相对应的歌词组成,例如: [00:38.02]兄弟你 在哪里 [00:42.52]天空又飘起了雨 [00:46.90]我要你像黎明一样 [00:51.19]出现在我眼里 [00:55.85]兄弟你 在哪里 [01:00.07]听不见你的呼吸

[01:04.70]只感觉我在哭泣) 小胖是一个粗心的人,经常把歌曲前奏的时间计算错,导致接下来所有时间轴的数据都出错,不是快了就 是慢了。因此,小胖总是把编辑下一首歌词文件的时间用来修改编辑错误的歌词文件,不仅浪费时间,还 很麻烦,需要在所有时间轴上一个一个修改。最重要的是——老总要扣 MONEY!(晕了~~) ! 昨天小胖又因没有完成上个月的任务被老总训了(扣了很多工资。。,小胖心里很不是滋味,打算聘请一 。) 名专门为他修改歌词的歌词修改人。 (看来小胖完全不了解编程的伟大??) 要求:提供需要修改的歌词,歌词是快了或是慢了,以及需要更改的秒数 工资:每天正确修改 9 个以下(含 9 个)歌词文件 250 元(无语) ,正确修改 10 个或以上每天可拿 300 元 (我只修改 10 个^__^) 。 【描述】 看了招聘广告后,你立刻来应聘。通过面试后,你工作的第一天来了。小胖今天正好有 10 个歌词文件需要 你修改(为了逃离那个倒霉的数字只能??) 。下面就是你最关键的一步了(只需要编一个程序,你就可以 每天不工作都拿高额工资了) 。 (我给你推荐的工作哦~~拿了工资别忘了分点给我^__^) 【输入格式】 输入文件中,第一行有 m1,m2 两个数据(中间用空格隔开) 。m1 是‘+’‘-’ , (加减符号)中的一个,如 果 m1 是‘+’ ,则表示小胖给你的歌词数据比实际慢了, ‘-’则是小胖歌词数据快了。接下来的 n 行中(n 是一个未知整数) ,是 lrc 歌词文件,第 n+2 行(也就是所有歌词输入完后的一行)以‘#’结束。 (数据保证 0<m2<10,1≤n≤50,每行歌词包括时间轴不超过 100 个字节) 【输出格式】 输出文件也有 n 行,是修改后的歌词文件。只需修改时间轴,歌词原样输出。 (输出文件的最长时间不到 10 分钟,最短不会出现负数) 【样例输入】 - 1.07 [ti:Only Love] [ar:Selena] [by:http://www.superlyrics.net] [00:08.26]Selena [00:13.19] [00:14.87]I see the distant lights ahead [00:21.84]Another hour or so, and I’ll be back in bed [00:29.67]I guess I really thought [00:32.90]that I was gone for good [00:37.93]But you know I never could # 【样例输出】 [ti:Only Love] [ar:Selena] [by:http://www.superlyrics.net] [00:07.19]Selena [00:12.12] [00:13.80]I see the distant lights ahead [00:20.77]Another hour or so, and I’ll be back in bed [00:28.60]I guess I really thought

[00:31.83]that I was gone for good [00:36.86]But you know I never could 【题解】 别看题目这么长,其实是一道很水的题目 【参考程序】 program ghfjk; var i,j,f:longint; m,n:real; s,t:string; ch:char; begin readln(s); t:=copy(s,3,length(s)-2); val(t,n); ch:=s[1]; repeat readln(s); if s[1]<>'#' then if s[2] in ['a'..'z','A'..'Z'] then writeln(s) else begin t:=copy(s,2,2); val(t,f); t:=copy(s,5,5); val(t,m); t:=copy(s,10,length(s)-9); if ch='-' then begin if m<n then repeat m:=m+60; f:=f-1; until m>=n; m:=m-n; end else begin m:=m+n; if m>=60 then repeat m:=m-60; f:=f+1; until m<60; end;

if f<10 then write('[0',f,':') else write('[',f,':'); if m<10 then write('0',m:0:2) else write(m:0:2); writeln(t); end; until s='#'; end. p1155 递归 【描述】 考虑一下定义在非负整数 n 上的递推关系: f0 F(n)= f1 当 n=0 时 当 n=1 时

a*F(n-1)+b*F(n-2) 其它 给定 f0,f1,a,b,n,写一个程序计算 F(n),-10^9≤F(n)≤10^9(四舍五入) ,保证一定有解。 【输入格式】 一行有五个数,f0,f1,a,b,n。-10^9≤n,f0,f1≤10^9,10^6≤a,b≤10^6。 a,b 是实数,n,f0,f1 是整数。 【输出格式】 一个数 F(n)。 【样例输入】 样例 1:0 1 1 1 20 样例 2:0 1 -1 0 1000000000 样例 3:-1 1 4 -3 18 【样例输出】 样例 1:6765 样例 2:-1 样例 3:387420487 【题解】 乍看题目好象很简单,其实不是的,我是用特殊分析法过的 【参考程序】 program hfjk; var i,n:longint; a,b,f,f1,f0:double; begin readln(f0,f1,a,b,n); if n>100000 then begin if((f0=0)and(f1=0))or((a=0)and(b=0))then

begin writeln(0); halt; end; if(f0=f1)and(a=b)then begin writeln(round(a*f0*2)); halt; end; if(f0=0)and(b=0)then begin writeln(round(f1*a)); halt; end; halt; end; for i:=2 to n do begin f:=a*f1+b*f0; f0:=f1; f1:=f; end; if n=1 then writeln(round(f1)) else writeln(round(f)); end. p1161 聚会的名单 【描述】 明天就是 candy 的生日。晚上,candy 找到了飘飘乎居士。她给了飘飘乎居士一张名单,名单上记录了 n 个 candy 的好朋友。可是,飘飘乎居士发现,名单上有好多重复的名字啊,这可急坏了飘飘乎居士。所幸, 飘飘乎居士找到了自己的 oi 朋友,希望能够帮助自己。飘飘乎居士会问某个名字,而你要做的任务就是计 算出名单中出现了几次该名字。 【输入格式】 第一行一个正整数 n; 接下来 n 行,每行一个字符串(长度不超过 20,均由小写字母组成) ,代表名单上的名字; 接下来一行一个正整数 m,表示飘飘乎居士一共会询问 m 次 紧接着 m 行,每行一个字符串(长度不超过 20,均由小写字母组成) ,表示飘飘乎居士询问名单上的某个 名字,如果没有出现过,则输出 0;否则输出出现的次数。 【输出格式】 一共 m 行。 第 i 行对应飘飘乎居士第 i 次提问的名字在名单中出现的次数。 【样例输入】 5 candy

candy candy violethill sugar 6 candy candy rooney sugar violethill giggs 【样例输出】 3 3 0 1 1 0 【数据规模】 对于 50%的数据,保证 0<n m<2000 对于 100%的数据,保证 0<n m<20000 【题解】 排序+去重+二分查找 【参考程序】 program gjkf; var i,j,k,l,t,m,n:longint; a,b:array[1..20000]of string; c:array[0..20000]of longint; p:string;

function find(l,r:longint;s:string):longint; var m:longint; begin if l>r then exit(0); m:=(l+r) div 2; if s=b[m] then exit(m) else if s>b[m] then find:=find(m+1,r,s) else find:=find(l,m-1,s); end;

procedure qs(l,r:longint); var i,j:longint; m,t:string; 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;

begin readln(n); c[0]:=0; for i:=1 to n do readln(a[i]); qs(1,n); i:=1; t:=0; repeat p:=a[i]; m:=1; j:=i+1; while(p=a[j])and(j<=n)do begin inc(m); inc(j); end; inc(t); b[t]:=p; c[t]:=m; i:=i+m until i=n+1; readln(m); for i:=1 to m do begin

readln(p); writeln(c[find(1,t,p)]); end; end. p1165 科学计数法 【描述】 给你一些数(0≤整数部分的绝对值<maxlongint) ,然后用科学计数法表示这些数。 【输入格式】 有若干行实数 『注意事项』 ⒈ 如果数 A(1≤|A|<10) ,直接输出 ⒉ 如果数 A 等于 0,直接输出 ⒊ 如果数 A(|A|<1) ,输出格式是 a.b*10^(-d) ⒋ 如果数 A(10≤|A|<100) ,输出格式是 a.b*10 ⒌ 如果数 A(|A|≥100) ,输出格式是 a.b*10^d ⒍ 如果数 A(|A|<1 或|A|≥10)且 a=1,b=0,那么直接输出 10^d 或 10^(-d) ⒎ 如果数 A(|A|<1 或|A|≥10)且 a=-1,b=0,那么直接输出 -10^d 或 -10^(-d) 【输出格式】 若干行用科学计数法表示后的数 【样例输入】 0 1.0001 0.00001 -0.00001 -100000000 130 0.013 【样例输出】 0 1.0001 10^(-5) -10^(-5) -10^8 1.3*10^2 1.3*10^(-2) 【题解】 恶心的字符串处理 要把题目的要求完全考虑到此能过 【参考程序】 program hu; var i,j,t,l,x:longint; s,sr,k:string; q:boolean;

begin while not eof do begin readln(s); if s[1]='-' then sr:='-' else sr:=''; while(not(s[1] in ['1'..'9']))and(s[1]<>'.')and(length(s)>0)do delete(s,1,1); q:=true; for i:=1 to length(s) do if s[i]='.' then q:=false; if not q then while s[length(s)]='0'do delete(s,length(s),1); if(s='')or(s='.')then writeln('0') else begin if s[length(s)]='.' then delete(s,length(s),1); j:=pos('.',s); if(j=0)then begin if length(s)=1 then writeln(s) else if length(s)=2 then if s='10' then writeln(sr,'10') else begin if s[2]<>'0' then writeln(sr,s[1],'.',s[2],'*10') else writeln(sr,s[1],'*10'); end else begin q:=true; for i:=2 to length(s) do if s[i]<>'0' then q:=false; if q then if s[1]<>'1' then writeln(sr,s[1],'*10^',length(s)-1) else writeln(sr,'10^',length(s)-1) else begin l:=length(s); write(sr,s[1],'.'); while s[length(s)]='0' do delete(s,length(s),1);

for i:=2 to length(s) do write(s[i]); writeln('*10^',l-1); end; end; end else if j=1 then begin while s[length(s)]='0' do delete(s,length(s),1); delete(s,1,1); l:=length(s); for i:=1 to l do if s[i]<>'0' then break; if i=l then if s[l]='1' then writeln(sr,'10^(-',l,')') else writeln(sr,s[l],'*10^(-',l,')') else begin write(sr,s[i],'.'); for x:=i+1 to l do write(s[x]); writeln('*10^(-',i,')'); end; end else if j=2 then begin while s[length(s)]='0' do delete(s,length(s),1); writeln(sr,s); end else begin k:=copy(s,1,j-1); if length(k)<>2 then begin write(sr,k[1],'.'); for i:=2 to length(s) do if s[i]<>'.' then write(s[i]); writeln('*10^',length(k)-1); end; if length(k)=2 then begin write(sr,k[1],'.'); for i:=2 to length(s) do if s[i]<>'.' then write(s[i]); writeln('*10');

end; end; end; end; end. p1170 0/1 字符串问题 【描述】 编程找出符合下列条件的字符串:①字符串中仅包含 0 和 1 两个字符;②字符串的长度为 n;③字符串中 不含有三个连续的相同子串。 【输入格式】 输入文件仅包含一个整数 n(0<n≤35) ,表示字符串的长度。 【输出格式】 输出文件仅包含一个整数,表示符合上述条件的字符串的总数。 【样例输入】 2 【样例输出】 4 【题解】 这道题有两个方法可以过 一个是回溯,另一个是用回溯算出结果打表交上去 【参考程序】 program vkj; var n,l,t:longint; a:array[1..50]of longint;

function ok(l:longint):boolean; var x,y,z,p,q,r:longint; begin x:=l; y:=l-1; z:=l-2; while z>0 do begin p:=x; q:=y; r:=z; while (r<y)and(a[p]=a[q])and(a[q]=a[r]) do begin inc(p); inc(q); inc(r); end; if r=y then exit(false);

dec(x); dec(y,2); dec(z,3); end; exit(true); end;

procedure ss(l:longint); begin if l=n+1 then begin inc(t,2); exit; end; a[l]:=0; if ok(l) then ss(l+1); a[l]:=1; if ok(l) then ss(l+1); end;

begin readln(n); a[1]:=0; l:=1; t:=0; ss(2); writeln(t); end. p1171 自然数的拆分 【描述】 输入自然数 n,然后将其拆分成由若干数相加的形式,参与加法运算的数可以重复。 【输入格式】 输入只有一个整数 n,表示待拆分的自然数 n。 n<=80 【输出格式】 输出一个数,即所有方案数 【样例输入】 7 【样例输出】 14 【题解】 由于数据较小我们用回溯也是可以过的,不过我提倡用动态规划 【参考程序】 program a1;

var n,tot,i:longint;

procedure dfs(x,y:longint); var i:longint; begin if x=n then begin inc(tot); exit; end; for i:=y to n-x do begin inc(x,i); if x<=n then dfs(x,i); dec(x,i); end; end;

begin tot:=0; readln(n); for i:=1 to n div 2 do dfs(i,i); writeln(tot); end. p1172 自然数拆分 Lunatic 版 【描述】 输入自然数 n,然后将其拆分成由若干数相加的形式,参与加法运算的数可以重复。 【输入格式】 输入只有一个整数 n,表示待拆分的自然数 n。 0<n<=4000 PS:0 也算自然数,所以这里应该写正整数比较好 但是为了尊重原作者的版权(这有版权吗- -) ,没有改掉。 本来 n 是要到 5000 的,但是开到 5000 的话我的程序就 Memory Limit Exceeded 了。 。 【输出格式】 输出一个数,即所有方案数 因为这个数可能非常大,所以你只要输出这个数 mod 2147483648 的余数即可。 【样例输入】 7 【样例输出】 14 【题解】 这道题就不能用回溯了,标准解法使用动态规划(完全背包)

f[j]=f[j]+f[j-i] 边界 f[0]=1; 【参考程序】 program gdfj; var i,j,n:longint; f:array[0..4000]of int64; begin fillchar(f,sizeof(f),0); readln(n); f[0]:=1; for i:=1 to n-1 do for j:=i to n do f[j]:=(f[j]+f[j-i])mod 2147483648; writeln(f[n]); end. p1190 积木城堡 【描述】 XC 的儿子小 XC 最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的,城堡的每一层 是一块积木。小 XC 是一个比他爸爸 XC 还聪明的孩子,他发现垒城堡的时候,如果下面的积木比上面的 积木大,那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。 小 XC 想把自己垒的城堡送给幼儿园里漂亮的女孩子们,这样可以增加他的好感度。为了公平起见,他决 定把送给每个女孩子一样高的城堡,这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。可是他发 现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了,他 灵机一动,想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木,使得最终每座城堡都一样 高。为了使他的城堡更雄伟,他觉得应该使最后的城堡都尽可能的高。 任务: 请你帮助小 XC 编一个程序,根据他垒的所有城堡的信息,决定应该移去哪些积木才能获得最佳的效果。 【输入格式】 第一行是一个整数 N(N<=100),表示一共有几座城堡。以下 N 行每行是一系列非负整数,用一个空格分隔, 按从下往上的顺序依次给出一座城堡中所有积木的棱长。用-1 结束。一座城堡中的积木不超过 100 块,每 块积木的棱长不超过 100。 【输出格式】 一个整数,表示最后城堡的最大可能的高度。如果找不到合适的方案,则输出 0 【样例输入】 2 2 1 –1 3 2 1 –1 【样例输出】 3 【题解】 类似装箱问题 每读入一行数据,做一次 0/1 背包 【参考程序】

program ghkln; var i,j,n,k,sum,m,l:longint; v:array[0..10000]of boolean; f:array[0..10000]of longint; a:array[1..100]of longint; begin readln(n); fillchar(f,sizeof(f),0); for l:=1 to n do begin m:=0; sum:=0; while not eoln do begin inc(m); read(a[m]); if a[m]<>-1 then inc(sum,a[m]) else dec(m); end; fillchar(v,sizeof(v),false); v[0]:=true; for i:=1 to m do for j:=sum downto a[i] do if v[j-a[i]] then v[j]:=true; for i:=0 to sum do if v[i] then inc(f[sum-i]); readln; end; for i:=10000 downto 0 do if f[i]=n then begin writeln(i); halt; end; end. p1197 二进制加法 【描述】 计算机使用的是二进制,和十进制不同的是:二进制运算“逢二进一” 。下面举几个二进制加法的运算实例: 例 1(整数) : 11101 + 110 例 2(含小数) : 11101.1011 + 110.11 ----------100100.0111

-----100011

1 所在的位置: 6、2、1 表示) 。 【输入格式】 输入文件共两行:

1 所在的位置: 6、3、-2、-3、-4

你的任务是:对于任意的两个正的二进制数,求它们和中“1”所在的位置(其中小数点后面的位置用负数

第一行:二进制的加数 A,总长度<=200 第二行:二进制的加数 B,总长度<=200 【输出格式】 输出文件输出二进制数 A+B 中“1”所在的位置,位置排序为:整数部分从左到右:N、N-1、N-2...1,小 数部分从左到右:-1、-2、......、-N,数据之间用空格分隔,行末没有多余的空格,有空行。 【样例输入】 样例输入 1: 11101 110 样例输入 2: 11101.1011 110.11 【样例输出】 样例输出 1: 621 样例输出 2: 6 3 -2 -3 -4 【题解】 又是一题恶心的字符串处理 先算小数部分,再算整数部分 【参考程序】 program gfjk; var i,j,k,la,lb,lc,x,y,z:longint; a,b:array[-1000..1000]of longint; c:array[1..1000]of longint; ch:char; begin fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); la:=0; x:=0; y:=0; while not eoln do begin read(ch); if ch<>'.' then

begin inc(la); a[la]:=ord(ch)-ord('0'); end else x:=la; end; readln; if x=0 then x:=la; lb:=0; while not eoln do begin read(ch); if ch<>'.' then begin inc(lb); b[lb]:=ord(ch)-ord('0'); end else y:=lb; end; if y=0 then y:=lb; if lb-y>la-x then begin k:=0; lc:=lb-y; for i:=1 to lb-y do begin c[i]:=a[x+lb-y-i+1]+b[lb-i+1]+k; k:=c[i] div 2; c[i]:=c[i] mod 2; end; end else begin k:=0; lc:=la-x; for i:=1 to la-x do begin c[i]:=a[la-i+1]+b[y+la-x-i+1]+k; k:=c[i] div 2; c[i]:=c[i] mod 2; end; end; z:=lc; if x>y then

begin for i:=lc+1 to lc+x do begin c[i]:=a[x-i+1+z]+b[y-i+z+1]+k; k:=c[i] div 2; c[i]:=c[i] mod 2; end; lc:=lc+x end else begin for i:=lc+1 to lc+y do begin c[i]:=a[x-i+1+z]+b[y-i+1+z]+k; k:=c[i] div 2; c[i]:=c[i] mod 2; end; lc:=lc+y; end; while k<>0 do begin inc(lc); c[lc]:=k mod 2; k:=k div 2; end; for i:=lc downto 1 do if i>z then if c[i]=1 then write(i-z,' ') else else if c[i]=1 then write(i-1-z,' '); writeln; end. p1204 乘车费用 【描述】 元旦快到了,小 W 的班级准备举办元旦庆祝活动,小 W 和几个同学一起帮助班主任老师进行准备。小 W 带着几个同学乘坐出租车去买东西。在出租车上,他们向司机师傅了解到出租车计价方案为:2.5 公里以内 起步价是 6 元,超过 2.5 公里之后按 1.2 元/公里计价,超过 10 公里之后在 1.2 元/公里的基础上加价 50%, 另外,停车等候时间则按时间计费后加入总价:1 元/5 分(注:不满 5 分钟不计费) 。好奇的小 W 想自己 先估算一下大概要多少费用。已知:小 W 等人乘坐出租车路程为 N 公里,中间停车等候时间总共 M 分钟, 请计算小 W 应付的出租车费用是多少元? 【输入格式】 输入文件共有一行,包含两个整数 N,M,分别表示出租车行驶的里程和中间停车的时间,中间以空格分

开,0≤N≤200,0≤M≤60。 【输出格式】 输出仅包含一个整数,表示小 W 应付的乘车费用,四舍五入到整数元。 【样例输入】 87 【样例输出】 14 【题解】 一题简单的模拟题 会写 if then else 的人都能过 【参考程序】 program fa; var n,m,t:longint; begin readln(n,m); t:=m div 5; if n=0 then begin writeln(t); halt; end; if n<3 then writeln(t+6) else if n<11 then writeln(round(t+6+(n-2.5)*1.2)) else writeln(round(t+6+(10-2.5)*1.2+(n-10)*1.8)); end. p1208 最长不下降子序列 2 【描述】 设有整数序列 b1,b2,b3,?,bm,若存在 i1<i2<i3<?<in,且 bi1<bi2<bi3<?<bin,则称 b1,b2,b3,?,bm 中有 长度为 n 的不下降序列 bi1,bi2,bi3,?,bin。求序列 b1,b2,b3,?,bm 中所有长度(n)最大不下降子序列 【输入格式】 第一行为 m,表示 m 个数 第二行 m 个数 【输出格式】 第一行输出最大长度 n 第二行输出长度为 n 的序列个数 Total 【样例输入】 3 122 【样例输出】 2 1 【题解】 简单的难度 2 的题目

【参考程序】 program gfvjkdf; var t,b,a:array[0..1000]of longint; i,j,n,k,max:longint; begin readln(n); for i:=1 to n do begin read(a[i]); b[i]:=1; end; for i:=n-1 downto 1 do for j:=i+1 to n do if(a[i]<a [j])and(b[i]<b[j]+1)then b[i]:=b[j]+1; max:=0; for i:=1 to n do if b[i]>max then max:=b[i]; writeln(max); a[0]:=0; b[0]:=max+1; for i:=0 to n do if b[i]=1 then t[i]:=1 else t[i]:=0; for k:=1 to max do for i:=n downto 1 do if b[i]=k then begin j:=i-1; while(j>=0)and(a[j]<>a[i])do begin if(a[j]<a[i])and(b[j]=k+1) then inc(t[j],t[i]); dec(j); end; end; writeln(t[0]); end. p1209 拦截导弹 【描述】 某国为了防御敌国的导弹袭击,研发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的 第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国 的导弹来袭。由于该系统还在试验阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。 【输入格式】

输入数据只有一行, 该行包含若干个数据, 之间用半角逗号隔开, 表示导弹依次飞来的高度 (导弹最多有 20 枚,其高度为不大于 30000 的正整数) 。 【输出格式】 输出数据只有一行,该行包含两个数据,之间用半角逗号隔开。第一个数据表示这套系统最多能拦截的导 弹数;第二个数据表示若要拦截所有导弹至少要再添加多少套这样的系统。 【样例输入】 389,207,155,300,299,170,158,65 【样例输出】 6,1 【题解】 经典的求最长不上升子序列 【参考程序】 program uighi; var i,j,n,max,k,p,t:longint; a,b,l:array[1..1000]of longint; ch:char; begin n:=0; t:=0; while not eoln do begin read(ch); case ch of '0'..'9':t:=t*10+ord(ch)-ord('0'); ',':begin inc(n); a[n]:=t; b[n]:=1; t:=0; end; end; end; inc(n); a[n]:=t; b[n]:=1; for i:=n-1 downto 1 do for j:=1+i to n do if(a[j]<=a[i])and(b[i]<b[j]+1) then b[i]:=b[j]+1; max:=0; for i:=1 to n do if b[i]>max then max:=b[i]; k:=1; l[1]:=a[1]; for i:=2 to n do

begin p:=0; for j:=1 to k do if l[j]>=a[i] then if p=0 then p:=j else if l[j]<l[p] then p:=j; if p=0 then begin inc(k); l[k]:=a[i]; end else l[p]:=a[i]; end; writeln(max,',',k-1); end. p1218 均分纸牌 【描述】 有 N 堆纸牌,编号分别为 1,2,?, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可以在任一堆上 取若于张纸牌,然后移动。 移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌, 只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。 现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。 例如 N=4,4 堆纸牌数分别为: ① 9 ② 8 ③ 17 ④ 6 移动 3 次可达到目的: 从 ③ 取 4 张牌放到 ④ (9 8 13 10) -> 从 ③ 取 3 张牌放到 ②(9 11 10 10)-> 从 ② 取 1 张 牌放到①(10 10 10 10) 。 【输入格式】 N(N 堆纸牌,1 <= N <= 100) A1 A2 ? An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000) 【输出格式】 所有堆均达到相等时的最少移动次数。 【样例输入】 4 9 8 17 6 【样例输出】 3 【题解】 贪心 【参考程序】 program dfhjk; var n,i,j,s,t:longint;

a:array[1..100]of longint; begin readln(n); s:=0; for i:=1 to n do begin read(a[i]); inc(s,a[i]); end; s:=s div n; for i:=1 to n do dec(a[i],s); i:=1; j:=n; s:=0; while a[i]=0 do inc(i); while a[j]=0 do dec(j); while i<j do begin inc(a[i+1],a[i]); a[i]:=0; inc(s); inc(i); while(a[i]=0)and(i<j)do inc(i); end; writeln(s); end. p1232 跳格子 II 【描述】 小 msh 长大之后,渐渐发现原来的跳格子游戏实在是太沙茶了,既没有挑战性,也没有乐趣,还经常被不 明真相的群众围观??所以,她决定修改跳格子的规则,让它看起来没那么沙茶?? 依然是在地上画一个 n*m 的方格,但 msh 在某些格子里放上高度为 1 的箱子。她每次可以从一个格子跳到 与它相邻的另一个格子中,如果这两个格子的高度相同,msh 只需要付出 1 单位力气;如果这两个格子高 度不同,则需要付出 2 单位力气。她想从某个格子跳到另一个格子,但她想用尽量少的力气。虽然 msh 长 大了,但她还是有点沙茶??算了半天也没有算出来到底需要多少力气才能跳完??那么你来帮帮她吧! 【输入格式】 第一行两个正整数 n 和 m,表示方格的行数和列数。 接下来 n 行,每行 m 个格子(用“.”和“*”表示)“.”表示这个格子上没有箱子, , “*”表示有箱子。 接下来一行四个整数 x1,y1,x2,y2,表示 msh 想从第 x1 行 y1 列的格子跳到第 x2 行 y2 列的格子。 【输出格式】 一行一个整数,表示最少需要多少力气跳完。 【样例输入】 46

.**... ..*... ..*.*. ....*. 1146 【样例输出】 10 【题解】 简单的广搜 【参考程序】 program hjg; const dx:array[1..4]of -1..1=(-1,0,1,0); dy:array[1..4]of -1..1=(0,-1,0,1); maxnm=250000; var i,j,n,m,x1,x2,y1,y2,x,y,h,t:longint; r:array[1..250000]of record x,y:longint; end; a:array[1..500,1..500]of char; b:array[1..500,1..500]of longint; begin readln(n,m); for i:=1 to n do begin for j:=1 to m do read(a[i,j]); readln; end; readln(x1,y1,x2,y2); filldword(b,sizeof(b)div 4,maxlongint div 4); h:=0; t:=1; b[x1,y1]:=0; r[1].x:=x1; r[1].y:=y1; while h<>t do begin h:=h mod maxnm+1; for i:=1 to 4 do begin x:=r[h].x+dx[i]; y:=r[h].y+dy[i]; if(x>0)and(x<=n)and(y>0)and(y<=m)then begin

if a[x,y]='.' then begin if a[r[h].x,r[h].y]='.' then if b[x,y]>b[r[h].x,r[h].y]+1 then begin b[x,y]:=b[r[h].x,r[h].y]+1; t:=t mod maxnm+1; r[t].x:=x; r[t].y:=y; end else else if b[x,y]>b[r[h].x,r[h].y]+2 then begin b[x,y]:=b[r[h].x,r[h].y]+2; t:=t mod maxnm+1; r[t].x:=x; r[t].y:=y; end; end; if a[x,y]='*' then begin if a[r[h].x,r[h].y]='.' then if b[x,y]>b[r[h].x,r[h].y]+2 then begin b[x,y]:=b[r[h].x,r[h].y]+2; t:=t mod maxnm+1; r[t].x:=x; r[t].y:=y; end else else if b[x,y]>b[r[h].x,r[h].y]+1 then begin b[x,y]:=b[r[h].x,r[h].y]+1; t:=t mod maxnm+1; r[t].x:=x; r[t].y:=y; end; end; end; end; end; writeln(b[x2,y2]); end.

p1233 数列 【描述】 虽然 msh 长大了,但她还是很喜欢找点游戏自娱自乐。有一天,她在纸上写了一串数字:1,1,2,5,4。接着 她擦掉了一个 1,结果发现剩下 1,2,4 都在自己所在的位置上,即 1 在第 1 位,2 在第 2 位,4 在第 4 位。 她希望

相关文章:
tyvj__部分题解代码
tyvj__部分题解代码_英语考试_外语学习_教育专区 暂无评价|0人阅读|0次下载|举报文档 tyvj__部分题解代码_英语考试_外语学习_教育专区。p1008 var f:array[1....
tyvj家族题解
TYVJ P1251 家族题解 /*家族 描述 Description 若某个家族人员过于庞大,要判断...tyvj主站部分题解 191页 免费 tyvj题解(前80道)[1] 106页 2下载券 tyvj部分...
tyvj动态规划题解
Tyvj 动态规划类题解 这是我在做 tyvj 题库时的一些想法,希望会对一些做题有...tyvj__部分题解代码 78页 免费 第10章 动态规划 76页 免费 动态规划(二) ...
tyvj题解(前80道)[1]
tyvj题解(前80道)[1]_IT/计算机_专业资料。题解TYVJ 前 38 道题解背景 Background...个乘号将它分成 K+1 个部分,找出一种分法,使得 这 K+1 个部分的乘积...
tyvj 每日整理
tyvj 每日整理_计算机软件及应用_IT/计算机_专业资料。描述 Description From tyvj...tyvj部分题解 191页 1下载券 每日一题整理 暂无评价 4页 免费 tyvj国庆模拟da...
2012 noip复习(含tyvj、usaco)
tyvj部分题解 191页 1财富值 阁夜课件 11页 免费 夜归鹿门歌(可用)课件 32页 5财富值 《长恨歌》课件 64页 5财富值如要投诉违规内容,请到百度文库投诉中心;...
题解报告
TYVJ 首届月赛试题题解报告 2011 年 1 月青蛙跳荷叶时间及空间复杂度 时间复杂度: 时间复杂度:O(1) 空间复杂度: 空间复杂度:O(1) 时间复杂度: 时间复杂度...
利用树状数组解决几类问题
分析 如题,这道题目只要求输出逆序对的个数就可以...方法一: 我们可以发现 V 图腾的前半部分具有逆序对...1.URAL P1028 Stars 2.TYVJ P1474 打鼹鼠 3. ...
tj
tyvj主站部分题解 191页 免费 tyvj动态规划题解 8页 1财富值 tyvj首届月赛题...【样例输入】 5 1 5 3 2 4 【样例输出】 40 【题解】 枚举法; 求出每...
OI弱菜必备知识手册之缩写
Tyvj:前身是 Vijos,很不错的网站。 Rqnoj:和 Tyvj...Nocow:内容很多,重要的是有 USACO 的译题和题解。...完全可以用标题表达自 己的意思,在正文部分往往会...
更多相关标签:
tyvj 安全逃离 题解 | tyvj题库 | www.tyvj.cn | tyvj 1211 | tyvj.cn | tyvj 普通二叉树 | tyvj测试数据 | tyvj3737 |