《信息学竞赛OJ代码.doc》由会员分享，可在线阅读，更多相关《信息学竞赛OJ代码.doc（35页珍藏版）》请在三一办公上搜索。
1、101:鸡兔同笼描述一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物输入第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，每行一个正整数a (a 32768)输出输出包含n行，每行对应一个输入,包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开如果没有满足要求的答案，则输出两个0。样例输入2320样例输出0 05 10代码#include#includeint main() int m;int n; int min,max; scanf(%d,&m); fo
2、r(int i=0;im;i+) scanf(%d,&n); if(n%2!=0) printf(0 0n); else min=n/4+(n%4)/2; max=n/2; printf(%d %dn,min,max); /system(pause);104:Distance on Chessboard描述国际象棋的棋盘是黑白相间的8 * 8的方格，棋子放在格子中间。如下图所示：王、后、车、象的走子规则如下： 王：横、直、斜都可以走，但每步限走一格。 后：横、直、斜都可以走，每步格数不受限制。车：横、竖均可以走，不能斜走，格数不限。 象：只能斜走，格数不限。写一个程序，给定起始位置和目标位置，
3、计算王、后、车、象从起始位置走到目标位置所需的最少步数。输入第一行是测试数据的组数t（0 = t = 20）。以下每行是一组测试数据，每组包括棋盘上的两个位置，第一个是起始位置，第二个是目标位置。位置用字母-数字的形式表示，字母从a到h，数字从1到8。输出对输入的每组测试数据，输出王、后、车、象所需的最少步数。如果无法到达,就输出Inf.样例输入2a1 c3f5 f8样例输出2 1 2 13 1 1 Inf代码#include #include #include int main() int nCases, i; scanf(%d, & nCases); for(i = 0; i nCases
4、; i+) char begin5, end5; scanf(%s %s,begin,end); int x,y; x = abs (begin0 - end0); y = abs (begin1 - end1); if(x = 0 & y = 0) printf(0 0 0 0n); else if(x y) printf(%d, y); else printf(%d, x); if(x = y | x = 0 | y = 0) printf( 1); else printf( 2); if(x = 0 | y = 0)printf( 1); else printf( 2); if(abs(
5、x - y) % 2 !=0)printf( Infn); else if(x = y) printf( 1n); else printf( 2n); return 0;105:校门外的树描述 某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，L，都种有一棵树。马路上有一些区域要用来建地铁，这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算
6、将这些树都移走后，马路上还有多少棵树。输入输入的第一行有两个整数L（1 = L = 10000）和 M（1 = M = 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。输出输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。样例输入500 3150 300100 200470 471样例输出298代码#includeint main() int L,M;int i; int x,y; int count=0; int a10001; scanf(%d %d,&L,&M);
7、for(i=0;i=L;i+) ai=1; for(i=0;iM;i+) scanf(%d %d,&x,&y); for(int j=x;j=y;j+) if(aj=1) aj=0; for(i=0;i=L;i+) if(ai=1) count+; printf(%dn,count); return 0; 106:放苹果描述把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。输入第一行是测试数据的数目t（0 = t = 20）。以下每行均包含二个整数M和N，以空格分开。1=M，N=10。输出对输入的每组数据M和N
8、，用一行输出相应的K。样例输入17 3样例输出8代码#include#includeint apple(int m,int n);int main() int k; int m,n; scanf(%d,&k); while(k-) scanf(%d %d,&m,&n); printf(%dn,apple(m,n); int apple(int m,int n) if(m=0|n=1) return 1; if(nm) return apple(m,m); else return apple(m,n-1)+apple(m-n,n);107:迷宫描述一天Extense在森林里探险的时候不小心走入了
9、一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。输入第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 = n = 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha
10、行, 第la列，B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。输出k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。样例输入23.#.#.0 0 2 25.#.#.#.#.#.0 0 4 0样例输出YESNO代码#include#include#includechar migong110110;int la,lb,ha,hb;int n;int k;int f(int a,int b) if(a=la&b=lb) return 1; if(a=n|b=n) return 0; if(migongab=#) return 0; if(mi
11、gongab=.) migongab=#; return f(a-1,b)|f(a+1,b)|f(a,b-1)|f(a,b+1); int main() int i,j; scanf(%d,&k); while(k-) scanf(%d,&n); getchar(); for(i=0;in;i+) scanf(%s,migongi); scanf(%d %d %d %d,&ha,&hb,&la,&lb); int b=f(ha,hb); if(migonglalb=#) printf(NOn); else if(b=1) printf(YESn); if(b=0) printf(NOn); 3
12、01:统计字符数描述判断一个由a-z这26个字符组成的字符串中哪个字符出现的次数最多输入第1行是测试数据的组数n，每组测试数据占1行，是一个由a-z这26个字符组成的字符串每组测试数据之间有一个空行，每行数据不超过1000个字符且非空输出n行，每行输出对应一个输入。一行输出包括出现次数最多的字符和该字符出现的次数，中间是一个空格。如果有多个字符出现的次数相同且最多，那么输出ascii码最小的那一个字符样例输入2abbcccadfadffasdf样例输出c 3f 4代码#include#includeint main()int a26;int c26;int n,i,j,k,len,t,m;ch
13、ar str1000;scanf(%d,&n);for(i=0;in;i+)int a26=0,c26=0;scanf(%s,str);len=strlen(str);for(j=0;jlen;j+)a(int)(strj-a)+;for(m=0;m26;m+)cm=am;for(j=0;j25;j+)for(k=0;k25-j;k+)if(ak=ak+1)t=ak;ak=ak+1;ak+1=t;for(j=0;j26;j+)if(a0=cj)printf(%c %d,j+97,a0);printf(n);break;return 0;302:487-3279描述企业喜欢用容易被记住的电话号码
14、。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或者短语。例如，你需要给滑铁卢大学打电话时，可以拨打TUT-GLOP。有时，只将电话号码中部分数字拼写成单词。当你晚上回到酒店，可以通过拨打310-GINO来向Ginos订一份pizza。让电话号码容易被记住的另一个办法是以一种好记的方式对号码的数字进行分组。通过拨打必胜客的“三个十”号码3-10-10-10，你可以从他们那里订pizza。电话号码的标准格式是七位十进制数，并在第三、第四位数字之间有一个连接符。电话拨号盘提供了从字母到数字的映射，映射关系如下：A, B, 和C 映射到 2 D, E, 和F 映射到 3 G, H, 和I
15、 映射到 4 J, K, 和L 映射到 5 M, N, 和O 映射到 6 P, R, 和S 映射到 7 T, U, 和V 映射到 8 W, X, 和Y 映射到 9 Q和Z没有映射到任何数字，连字符不需要拨号，可以任意添加和删除。 TUT-GLOP的标准格式是888-4567，310-GINO的标准格式是310-4466，3-10-10-10的标准格式是310-1010。 如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号） 你的公司正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相同的电话号码。输入输入的格式是，第一行是一个正整数，指定电话
16、号码薄中号码的数量（最多100000）。余下的每行是一个电话号码。每个电话号码由数字，大写字母（除了Q和Z）以及连接符组成。每个电话号码中只会刚好有7个数字或者字母。输出对于每个出现重复的号码产生一行输出，输出是号码的标准格式紧跟一个空格然后是它的重复次数。如果存在多个重复的号码，则按照号码的字典升序输出。如果输入数据中没有重复的号码，输出一行： No duplicates.样例输入124873279ITS-EASY888-45673-10-10-10888-GLOPTUT-GLOP967-11-11310-GINOF101010888-1200-4-8-7-3-2-7-9-487-3279样
17、例输出310-1010 2487-3279 4888-4567 3代码#include#include#includecharmap=22233344455566677778889999;charstr80,telNumbers1000009;intcompare(constvoid*elem1,constvoid*elem2)return(strcmp(char*)elem1,(char*)elem2);voidstandardizeTel(intn)intj,k;j=k=-1;while(k=A&strj=Z)telNumbersnk=mapstrj-A;continue;telNumbe
18、rsnk=strj;telNumbersnk=0;return;intmain()intn,i,j;boolnoduplicate;scanf(%d,&n);for(i=0;in;i+)scanf(%s,str);standardizeTel(i);qsort(telNumbers,n,9,compare);noduplicate=true;i=0;while(in)j=i;i+;while(i1)printf(%s%dn,telNumbersj,i-j);noduplicate=false;if(noduplicate)printf(Noduplicates.n);return0;303:子
19、串描述现在有一些由英文字符组成的大小写敏感的字符串，你的任务是找到一个最长的字符串x，使得对于已经给出的字符串中的任意一个y，x或者是y的子串，或者x中的字符反序之后得到的新字符串是y的子串。输入输入的第一行是一个整数t (1 = t = 10)，t表示测试数据的数目。对于每一组测试数据，第一行是一个整数n (1 = n = 100)，表示已经给出n个字符串。接下来n行，每行给出一个长度在1和100之间的字符串。输出对于每一组测试数据，输出一行，给出题目中要求的字符串x的长度。样例输入23ABCDBCDFFBRCD2roseorchid样例输出22代码304:Caesar 密码描述Julius
20、 Caesar 生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递。假设你是Caesar 军团中的一名军官，需要把Caesar 发送的消息破译出来、并提供给你的将军。消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如：消息原文中的每个字母A都分别替换成字母F），其他字符不 变，并且消息原文的所有字母都是大写的。 密码字母：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z原文字母：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U输入最多
21、不超过100个数据集组成。每个数据集由3部分组成：起始行：START 密码消息：由1到200个字符组成一行，表示Caesar发出的一条消息结束行：END 在最后一个数据集之后，是另一行：ENDOFINPUT输出每个数据集对应一行，是Caesar 的原始消息。样例输入STARTNS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJXENDSTARTN BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJENDSTARTIFSLJW PSTBX K
22、ZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJENDENDOFINPUT样例输出IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSESI WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROMEDANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE代码#include#include#includechar mima210;char s
23、tr110;char str210;int main() A=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; B=V,W,X,Y,Z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U; char A=ABCDEFGHIJKLMNOPQRSTUVWXYZ; char B=VWXYZABCDEFGHIJKLMNOPQRSTU; while(scanf(%s,str1) char mingwen210=; getchar(); if(strcmp(str1,ENDOFINPUT)=0) break; if(s
24、trcmp(str1,START)!=0) continue; gets(mima); int len=strlen(mima); for(int i=0;i=F&mimai=A&mimai=E) mingweni=mimai+21; else mingweni=mimai; scanf(%s,str2); getchar(); printf(%sn,mingwen); 306:All in All问题描述：给定两个字符串s和t，判断s是否是t的子序列。即从t中删除一些字符，将剩余的字符连接起来，即可获得s。输入：输入文件包括多组测试数据，每组测试数据占一行，包括两个由ASCII码组成的字符串
25、s和t，它们的长度都不超过100000。输出：对于每个测试数据输出一行，如果s是t的子序列，则输出“Yes”，否则输出“No”。样例输入：sequence subsequenceperson compressionVERDI vivaVittorioEmanueleReDiItaliacaseDoesMatter CaseDoesMatter样例输出：YesNoYesNo代码#include#include#include int main() int i,j;int len1,len2; char str1100010; char str2100010; while(scanf(%s %s,
26、str1,str2)!=EOF) int k=-1;int b=0; len1=strlen(str1); len2=strlen(str2); for(int i=0;ilen1;i+) for(int j=k+1;jlen2;j+) if(str1i=str2j) k=j; b+; break; if(b=len1) printf(Yesn); else printf(Non); 307:WERTYU问题描述：一种常见的打字键入错误是将键盘上的键位错按成它右侧相邻的按键，如图3.1所示图3.1 键盘比如，想键入“Q”却误按成“W”，想键入“J”却被误按成“K”，要求编程对上述错误的打字方式
27、进行更正。输入：输入文件包含若干行，每行可以包含数字、空格和除“A”、“Z”、“Q”外的大写字母，还有除单引号“”外的标点符号。并且也不会错按到Tab、BackSpace、Control等标记了单词的按键。输出：将每个字母或标点符号用它左边的符号替换，输入中的空格按原样输出（即空格不会键入错误）。样例输入：O S,GOMR YPFSU/234567890-=WERTYYUIOP样例输出：I AM FINE TODAY.1234567890-QWERTYUIOP代码#include#include#includechar str100;char key410=1,2,3,4,5,6,7,8,9,
28、0,Q,W,E,R,T,Y,U,I,O,P,A,S,D,F,G,H,J,K,L,;,Z,X,C,V,B,N,M,.,/;int main() while(gets(str) char str1100=; int i; int len=strlen(str); for(i=0;ilen;i+) if(stri=-)str1i=0; if(stri=)str1i=-; if(stri=)str1i=P; if(stri=)str1i=; if(stri=)str1i=; if(stri=)str1i=; if(stri= )str1i= ; if(stri=1)str1i=; else for(i
29、nt j=0;j4;j+) for(int k=1;k10;k+) if(stri=keyjk) str1i=keyjk-1; for(i=0;ilen;i+) printf(%c,str1i); printf(n); 501:约瑟夫问题描述约瑟夫问题：有只猴子，按顺时针方向围成一圈选大王（编号从到），从第号开始报数，一直数到，数到的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入，后，输出最后猴王的编号。输入每行是用空格分开的两个整数，第一个是 n, 第二个是 m ( 0 m,n =300)。最后一行是：0 0输出对于每行输入数据（最
30、后一行除外)，输出数据也是一行，即最后猴王的编号样例输入6 212 48 30 0样例输出517代码#includeint main()int a301;int i,n,m,count,j;while(scanf(%d %d,&n,&m)&n!=0&m!=0)for(i=0;in;i+)ai=i+1; j=0;for(i=0;in;i+)count=0;while(countm)while(aj=0)j=(j+1)%n;count+;j=(j+1)%n;j-;if(j0)j=n-1;if(i=n-1)printf(%dn,aj);aj=0;return 0;getchar();502:摘花生鲁
31、宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！熊字”。鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”我们假定多多在每个单位时间内，可以做下列四件事情中的一件：1) 从路边跳到最靠近路边（即第一行）的某棵
32、花生植株；2) 从一棵植株跳到前后左右与之相邻的另一棵植株；3) 采摘一棵植株下的花生；4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。例如在图2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。输入输入的第一行包括一个整数T，表示数据组数每组输入的第一行包括三个整数，M, N和K，用空格
33、隔开；表示花生田的大小为M * N（1 = M, N = 50），多多采花生的限定时间为K（0 = K = 1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i + 1行的第j个整数Pij（0 = Pij = 500）表示花生田里植株(i, j)下花生的数目，0表示该植株下没有花生。输出输出包括T行，每一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。样例输入6 7 210 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 0样例输出37代码#inclu
34、de#includeint main()int hf5555;int n,N,k,M,K,max,total,time=0;int i,j,maxi,maxj,nowi,nowj;scanf(%d,&n); for( k=0;kn;k+) total=0;time=0;scanf(%d %d %d,&N,&M,&K);for(i=1;i=N;i+)for(j=1;j=M;j+)scanf(%d,&hfij); nowi=0;nowj=0;while(timeK) max=0; for(i=1;i=N;i+) for(j=1;jmax) max=hfij; maxi=i;maxj=j; if(m
35、ax=0) break; if(nowi=0) nowj=maxj; if(time+1+maxi+fabs(nowi-maxi)+fabs(maxj-nowj)=K) time+=fabs(nowi-maxi)+fabs(maxj-nowj)+1; nowi=maxi; nowj=maxj; total+=hfmaximaxj; hfmaximaxj=0; else break;printf(%dn,total);return 0;503:THE DRUNK JAILER问题描述：某个监狱有一排、共n间牢房，一间挨一间。每间牢房关着一名囚犯，每间牢房的门刚开始时都是关着的。有一天晚上，狱卒厌
36、烦了看守工作，决定玩一个游戏。游戏的第1轮，他喝了一杯酒，然后沿着监狱，把所有的牢房的门挨个挨个打开；第2轮，他又喝了一杯酒，然后沿着监狱，把编号为偶数的牢房的门关上；第3轮，他又喝了一杯酒，然后沿着监狱，对编号为3的倍数的牢房，如果牢房的门开着，则关上，否则打开；，狱卒重复游戏n轮。游戏结束后，他喝下最后一杯酒，醉倒了。这时，囚犯才意识到他们牢房的门可能是开着的，而且狱卒醉倒了，所以他们越狱了。给定牢房的数目，求越狱囚犯的人数。输入：输入文件的第1行为一个正整数，表示测试数据的个数。每个测试数据占一行，为一个整数n，5=n=100，表示牢房的数目。输出：对每个测试数据所表示的牢房数目n，输出越狱的囚犯人数。样例输入：25100样例输出：210代码#include#includeint a200;int main() int n; scanf(%d,&n); while(n-) int m; int i; int count=0; int j,k; /int a200=0; scanf(%d,&m);
