实例介绍
【实例简介】
赵端阳的《ACM国际大学生程序设计竞赛题解（1）》很常见 但是（2）不好找 所以资源分稍微高了一点，望同好理解~
目录 第一章基础编程题 ZJU1086-Octal fractions-.--- ZJU1089-Lotto 3 Z3U1090-The Circumference of the Circle. 6 ZJU1095-Humble Numbers ZJU1099-HTML ZJU1105-FatMouse's Tour zJU11l5- Digital roots…… …17 zJU1122 Clock…… zJU139 Rectangles… zJU1151- Word reversa1…… …………25 ZJU1152-A Mathematical Curiosity. ZJU1154-Niven Numbers 第二章模拟算法题… 32 ZJU1088-System Overload ZU1098-Simple Computers 36 ZJU1121-Reserve Bookshelf 0 ZJU1143-Date Bugs …48 ZJU1144-Robber zJU1146 LC-Display…… 56 ZJUI153-Fournament Seeding 61 ZJUI160-Biorhythms 第三章字符串处理题 ZJU1109-Language of FatMouse 70 ZJU1ll1-Poker hands ZJUll16-A Well-Formed Problem 81 ZJU1126-Bio-Informatics ……88 zJU1159487-3279 ……93 第四章基本数据结构题 ZJU1094 Matrix Chain multiplication…………… …9 ZJU1097-Code the Tree 垂垂垂 ……104 ZJU1156-Unscrambling imag ·,..b宝 第五章搜索算法题 日··,,·.护垂‘ 116 ZJU1084-Channel Allocation ………………………116 ZJU1085- Alien Security…… 120 ZJUI09 1-Knight moves 126 ZJUI101-Gamblers …………132 ZJU1l103-Hike on a gi 135 ZJU1129-Erdos Numbers.. …………141 ZJU1136-Multiple 147 ZJU1l42-Maze 152 ZJUl148-The Game 158 第六章动态规划算法题 ………163 ZJU1093-Monkey and Banana …163 ZJU1100-Mondriaan's Dream ……169 ZJU1102-Phylogenetic Trees Inherited 174 ZJU1107-FatMouse and Cheese 180 ZJU1108-FatMouse's Speed zJU1132- Railroad… 188 ZJU1147-Formatting Text 195 ZJU1149-Dividing 201 第七章回溯算法题 207 ZJU1l45- Dreisam Equations…… …207 ZJUI157-A Plug for UNIX 第八章图论算法题 ……223 ZJU1082-Stockbroker Grapevine 223 ZJU1083 Frame Stacking…… 228 ZJU1092-Arbitrage zJU117- ntropy… 239 zJU118-N- Credible mazes……… ZJU1119-SPF…… 251 ZJU1127- Roman forts……………… 256 ZJU1130-Ouroboros Snake 262 ZJU1134 Strategic Game……… ZJU137- Girls and Boys……… 273 ZJU1140-Courses 278 ZJU1141-Closest Common Ancestors 281 zJU1150-S- Trees……… 285 第九章几何和数学题 291 zJU1081- Points within…… 291 ZJU1096-Subway ……………………296 zJU1104 Leaps Tall Buildings…… ……301 ZJUl110-Dick and Jane 306 AJUI12-Equidistance zJU114- Problem bee… 315 625 ZJUl123-Triangle Encapsulation 319 zJU1125- Floating Point Numbers………… 325 zJU1128- Atlantis…………………… 330 ZJU1l33-Smith Numbers 335 728 ZJU1158-Treasure hunt 339 索引 346 参考文献 物一P专 39403851774 8 6283815116169 第“章基础编程题 在本章的题目大部分都比较简单,作为刚刚开始参加竞赛的练习题。 ZJU1086-Octal Fractions [1、2、3] 四名 Time limit: 1 Seconds. Memory limit: 32768KB Fractions in octal(base 8)notation can be expressed exactly in decimal notation. For example, 0.75 in octal is 0.953125(7/8+5/64)in decimal. All octal numbers of n digits to the right of the octal point can be expressed in no more than 3n decimal digits to the right of the decimal point. Write a program to convert octal numerals between 0 and 1, inclusive, into equivalent decimal numerals. The input to your program will consist of octal numbers, one per line, to be converted Each input number has the form Od d2d3".dk, where the d; are octal digits(0.7). There is no limit on k. Your output will consist of a sequence of lines of the form 0.d1d2d3…dk[8]=0.DD2D3…Dm[10] where the left side is the input (in octal), and the right hand side the decimal (base 10) equivalent. There must be no trailing zeros, i.e. Dm is not equal to O SAMPLE INPUT 0.75 0.0001 0.01234567 SAMPLE OUTPUT 0.75[8]=0.953125[10 0,0001[8] 0.000244140625[10] 0.01234567[8]=0.020408093929290771484375[10 Problem Source South africa 2001 【题目大意】 八进制表示的小数可用十进制数精确地表示。例如,八进制数0.75等于进制数0953125 [i]httpacm.zju.edu.cn/onlinejudge/showproblem.do?problemcode-1086 [2]http://acm.pku.edu.cn/judgeonline/problem?id=1131 [3]http://acmicpc-live-archive.uvaes/nuevoportal/data/problem.php?p-2245 (7/8+5/64)。八进制小数点右边的n位数可表示成小数位数不多于3n位的十进制数 编程任务:将0~1之间的八进制小数,转换为等值的十进制数。程序的输入是八进制数, 每行一个,分别转换成十进制数。输入数据的格式为0d1d2d3…ck,其中d为八进制数值(0… 7),k值没有限制。程序输出格式: 0.d1d2d3…dk[8]=0.D1D2D3…·Dn[10] 左边是输入的八进制数,而右边是等值的十进制数。小数后面没有拖零,也就是Dn不为0 【算法分析】 本题需要将八进制表示的小数用十进制数精确地表示,由于位数很多,需要采用高精度的 方法计算。用数学公式表达这种转换关系 (0.75)8=(7×81+5×82)10=(0.93125) 被除数和除数都要使用高精度运算,编程是比较麻烦的。改变一下计算公式 (0375)8(7×8+5×82)0=((58+7)/8)0=(0.93125)1 也就是采用累除的方法,计算起来就很方便。从八进制小数的最低位开始,除以8后,与 其前一位相加,一直到小数点后的第一位小数。如上例数据,只有两个小数位,分两步运算 ①5/8=0615 ②(0.625+7)/8=0.93125 这样,我们只要实现除以8的高精度运算。 【程序代码 程序名称:du1086c 题目: Octal fractions 提交语言:C 运行时间:00:0000 运行内存:38KB #include <stdio. h #include <string. h> define MaxN 100 int main() char src [maxn]i //八进制的小数 It i while(scanf(os", src)! EOF char dest [MaxN]=[0i //进制的小数 int index =0; //十进制小数的长度 //从八进制小数的最后一位开始累除 for(i=strlen(src)-l: i>1; i--) int num srcli] 0 //八进制小数的当前位 //实现除以8的高精度运算 lnt tem //最后的余数num也必须除尽 2 for(1=0;:了 index num 十 tem lum*10+ (j<index? dest [j]-0: 0) dest[j] =temp/8+0; //商 num temp%8; //余数 index //进制小数的实际位数 dest[j]=\0 //字符串结束标志 printf("os [8]=0%s[101 src, dest)i eturn o ZJU1089-Lotto!1, 2,3 Time limit: I Seconds Memory limit: 32768KB n a Lotto i have ever played, one has to select 6 numbers from the set ( 1, 2, 49. A popular strategy to play Lotto although it doesn't increase your chance of winning- is to select a subset S containing k(k>)of these 49 numbers, and then play several games with choosing numbers only from S. For example, for k=8 and S-(1, 2, 3, 5, 8, 13, 21, 34 there are 28 possible games:[1,2,3,5,8,13],[12,3,5,8,21,[1,2,3,5,8,341,[12,3,5,13,21]l…,3,5,813,21,34] Your job is to write a program that reads in the number k and the set s and then prints all possible games choosing numbers only from S Input Specification The input file will contain one or more test cases. Each test case consists of one line containing several integers separated from each other by spaces. The first integer on the line will be the number k(6<k<13). Then k integers, specifying the set S, will follow in ascending order Input will be terminated by a value of zero(0) for k Output Specification For each test case, print all possible games, each game on one line. The numbers of each game have to be sorted in ascending order and separated from each other by exactly one space. The games themselves have to be sorted lexicographically that means sorted by the lowest number first, then by the second lowest and so on, as demonstrated in the sample output below The test cases have to be n]http://acm.zju.edu.cn/onlinejudge/showproblem.do?problemcode=1089 [2]http://acm.pku.edu.cn/judgeonline/pRoblem?id=2245 3]http://acm.uva.es/p/v4/441.html separated from each other by exactly one blank line Do not put a blank line after the last test case Sample Input 里 深 812358132134 Sample Output 12.3456 1235813 128132134 123457 235821 13581321 123467 1235834 135813·34 1.2.3.567 12351321 13582134 124567 12351334 135132134 134567 12352134 138132134 234567 12381321 158132134 12381334 23581321 12382134 23581334 号 123132134 23582134 125813.21 235132134 12581334 238132134 12582134 258132134 125132134 3581321.34 Problem source University of Ulm Local Contest 1996 【题目大意】 在我曾经玩过的一种对号码的纸牌游戏(乐透)里,玩家必须从{,2,…,49}中选6个数。 玩Ioto的一个流行的策略是(虽然它并不增加你赢的机会):就是从这49个数中,选出k(k> 6)个数组成一个子集S,然后只从S里拿出牌来玩几局游戏。例如,k=8,S={1,2,3,5,8,13, 21,34},那么有28场可能的游戏:[1,23,5,8,13][1,2,3,5,8,211,2,3,5,8,34,[1,2,3,5, 13,21],…[3,5,8,13,21,34] 编程任务 读取数字k和一组数S,输出由S中的数组成的所有可能的游戏。 输入格式 输入有一组或多组测试数据。每组测试数据一行,数与数之间用空格隔开。每行第一个整 数是k(6<k<13),然后是从小到大排列的k个整数,即子集S。当k为零时,输入结束。 输出格式 对于每组测试数据,输出所有可能的游戏,每个游戏占一行。游戏里的数字按升序排列, 数与数之间有一个空格。所有游戏也要按字典序排列,也就是,首先比较各局游戏的第一个数 的大小,然后是第二个数的大小,依次类推,如下面的输出样例所示。不同的测试例之间用 个空行隔开。最后一组测试例之后没有空行。 【实例截图】
【核心代码】
赵端阳的《ACM国际大学生程序设计竞赛题解（1）》很常见 但是（2）不好找 所以资源分稍微高了一点，望同好理解~
目录 第一章基础编程题 ZJU1086-Octal fractions-.--- ZJU1089-Lotto 3 Z3U1090-The Circumference of the Circle. 6 ZJU1095-Humble Numbers ZJU1099-HTML ZJU1105-FatMouse's Tour zJU11l5- Digital roots…… …17 zJU1122 Clock…… zJU139 Rectangles… zJU1151- Word reversa1…… …………25 ZJU1152-A Mathematical Curiosity. ZJU1154-Niven Numbers 第二章模拟算法题… 32 ZJU1088-System Overload ZU1098-Simple Computers 36 ZJU1121-Reserve Bookshelf 0 ZJU1143-Date Bugs …48 ZJU1144-Robber zJU1146 LC-Display…… 56 ZJUI153-Fournament Seeding 61 ZJUI160-Biorhythms 第三章字符串处理题 ZJU1109-Language of FatMouse 70 ZJU1ll1-Poker hands ZJUll16-A Well-Formed Problem 81 ZJU1126-Bio-Informatics ……88 zJU1159487-3279 ……93 第四章基本数据结构题 ZJU1094 Matrix Chain multiplication…………… …9 ZJU1097-Code the Tree 垂垂垂 ……104 ZJU1156-Unscrambling imag ·,..b宝 第五章搜索算法题 日··,,·.护垂‘ 116 ZJU1084-Channel Allocation ………………………116 ZJU1085- Alien Security…… 120 ZJUI09 1-Knight moves 126 ZJUI101-Gamblers …………132 ZJU1l103-Hike on a gi 135 ZJU1129-Erdos Numbers.. …………141 ZJU1136-Multiple 147 ZJU1l42-Maze 152 ZJUl148-The Game 158 第六章动态规划算法题 ………163 ZJU1093-Monkey and Banana …163 ZJU1100-Mondriaan's Dream ……169 ZJU1102-Phylogenetic Trees Inherited 174 ZJU1107-FatMouse and Cheese 180 ZJU1108-FatMouse's Speed zJU1132- Railroad… 188 ZJU1147-Formatting Text 195 ZJU1149-Dividing 201 第七章回溯算法题 207 ZJU1l45- Dreisam Equations…… …207 ZJUI157-A Plug for UNIX 第八章图论算法题 ……223 ZJU1082-Stockbroker Grapevine 223 ZJU1083 Frame Stacking…… 228 ZJU1092-Arbitrage zJU117- ntropy… 239 zJU118-N- Credible mazes……… ZJU1119-SPF…… 251 ZJU1127- Roman forts……………… 256 ZJU1130-Ouroboros Snake 262 ZJU1134 Strategic Game……… ZJU137- Girls and Boys……… 273 ZJU1140-Courses 278 ZJU1141-Closest Common Ancestors 281 zJU1150-S- Trees……… 285 第九章几何和数学题 291 zJU1081- Points within…… 291 ZJU1096-Subway ……………………296 zJU1104 Leaps Tall Buildings…… ……301 ZJUl110-Dick and Jane 306 AJUI12-Equidistance zJU114- Problem bee… 315 625 ZJUl123-Triangle Encapsulation 319 zJU1125- Floating Point Numbers………… 325 zJU1128- Atlantis…………………… 330 ZJU1l33-Smith Numbers 335 728 ZJU1158-Treasure hunt 339 索引 346 参考文献 物一P专 39403851774 8 6283815116169 第“章基础编程题 在本章的题目大部分都比较简单,作为刚刚开始参加竞赛的练习题。 ZJU1086-Octal Fractions [1、2、3] 四名 Time limit: 1 Seconds. Memory limit: 32768KB Fractions in octal(base 8)notation can be expressed exactly in decimal notation. For example, 0.75 in octal is 0.953125(7/8+5/64)in decimal. All octal numbers of n digits to the right of the octal point can be expressed in no more than 3n decimal digits to the right of the decimal point. Write a program to convert octal numerals between 0 and 1, inclusive, into equivalent decimal numerals. The input to your program will consist of octal numbers, one per line, to be converted Each input number has the form Od d2d3".dk, where the d; are octal digits(0.7). There is no limit on k. Your output will consist of a sequence of lines of the form 0.d1d2d3…dk[8]=0.DD2D3…Dm[10] where the left side is the input (in octal), and the right hand side the decimal (base 10) equivalent. There must be no trailing zeros, i.e. Dm is not equal to O SAMPLE INPUT 0.75 0.0001 0.01234567 SAMPLE OUTPUT 0.75[8]=0.953125[10 0,0001[8] 0.000244140625[10] 0.01234567[8]=0.020408093929290771484375[10 Problem Source South africa 2001 【题目大意】 八进制表示的小数可用十进制数精确地表示。例如,八进制数0.75等于进制数0953125 [i]httpacm.zju.edu.cn/onlinejudge/showproblem.do?problemcode-1086 [2]http://acm.pku.edu.cn/judgeonline/problem?id=1131 [3]http://acmicpc-live-archive.uvaes/nuevoportal/data/problem.php?p-2245 (7/8+5/64)。八进制小数点右边的n位数可表示成小数位数不多于3n位的十进制数 编程任务:将0~1之间的八进制小数,转换为等值的十进制数。程序的输入是八进制数, 每行一个,分别转换成十进制数。输入数据的格式为0d1d2d3…ck,其中d为八进制数值(0… 7),k值没有限制。程序输出格式: 0.d1d2d3…dk[8]=0.D1D2D3…·Dn[10] 左边是输入的八进制数,而右边是等值的十进制数。小数后面没有拖零,也就是Dn不为0 【算法分析】 本题需要将八进制表示的小数用十进制数精确地表示,由于位数很多,需要采用高精度的 方法计算。用数学公式表达这种转换关系 (0.75)8=(7×81+5×82)10=(0.93125) 被除数和除数都要使用高精度运算,编程是比较麻烦的。改变一下计算公式 (0375)8(7×8+5×82)0=((58+7)/8)0=(0.93125)1 也就是采用累除的方法,计算起来就很方便。从八进制小数的最低位开始,除以8后,与 其前一位相加,一直到小数点后的第一位小数。如上例数据,只有两个小数位,分两步运算 ①5/8=0615 ②(0.625+7)/8=0.93125 这样,我们只要实现除以8的高精度运算。 【程序代码 程序名称:du1086c 题目: Octal fractions 提交语言:C 运行时间:00:0000 运行内存:38KB #include <stdio. h #include <string. h> define MaxN 100 int main() char src [maxn]i //八进制的小数 It i while(scanf(os", src)! EOF char dest [MaxN]=[0i //进制的小数 int index =0; //十进制小数的长度 //从八进制小数的最后一位开始累除 for(i=strlen(src)-l: i>1; i--) int num srcli] 0 //八进制小数的当前位 //实现除以8的高精度运算 lnt tem //最后的余数num也必须除尽 2 for(1=0;:了 index num 十 tem lum*10+ (j<index? dest [j]-0: 0) dest[j] =temp/8+0; //商 num temp%8; //余数 index //进制小数的实际位数 dest[j]=\0 //字符串结束标志 printf("os [8]=0%s[101 src, dest)i eturn o ZJU1089-Lotto!1, 2,3 Time limit: I Seconds Memory limit: 32768KB n a Lotto i have ever played, one has to select 6 numbers from the set ( 1, 2, 49. A popular strategy to play Lotto although it doesn't increase your chance of winning- is to select a subset S containing k(k>)of these 49 numbers, and then play several games with choosing numbers only from S. For example, for k=8 and S-(1, 2, 3, 5, 8, 13, 21, 34 there are 28 possible games:[1,2,3,5,8,13],[12,3,5,8,21,[1,2,3,5,8,341,[12,3,5,13,21]l…,3,5,813,21,34] Your job is to write a program that reads in the number k and the set s and then prints all possible games choosing numbers only from S Input Specification The input file will contain one or more test cases. Each test case consists of one line containing several integers separated from each other by spaces. The first integer on the line will be the number k(6<k<13). Then k integers, specifying the set S, will follow in ascending order Input will be terminated by a value of zero(0) for k Output Specification For each test case, print all possible games, each game on one line. The numbers of each game have to be sorted in ascending order and separated from each other by exactly one space. The games themselves have to be sorted lexicographically that means sorted by the lowest number first, then by the second lowest and so on, as demonstrated in the sample output below The test cases have to be n]http://acm.zju.edu.cn/onlinejudge/showproblem.do?problemcode=1089 [2]http://acm.pku.edu.cn/judgeonline/pRoblem?id=2245 3]http://acm.uva.es/p/v4/441.html separated from each other by exactly one blank line Do not put a blank line after the last test case Sample Input 里 深 812358132134 Sample Output 12.3456 1235813 128132134 123457 235821 13581321 123467 1235834 135813·34 1.2.3.567 12351321 13582134 124567 12351334 135132134 134567 12352134 138132134 234567 12381321 158132134 12381334 23581321 12382134 23581334 号 123132134 23582134 125813.21 235132134 12581334 238132134 12582134 258132134 125132134 3581321.34 Problem source University of Ulm Local Contest 1996 【题目大意】 在我曾经玩过的一种对号码的纸牌游戏(乐透)里,玩家必须从{,2,…,49}中选6个数。 玩Ioto的一个流行的策略是(虽然它并不增加你赢的机会):就是从这49个数中,选出k(k> 6)个数组成一个子集S,然后只从S里拿出牌来玩几局游戏。例如,k=8,S={1,2,3,5,8,13, 21,34},那么有28场可能的游戏:[1,23,5,8,13][1,2,3,5,8,211,2,3,5,8,34,[1,2,3,5, 13,21],…[3,5,8,13,21,34] 编程任务 读取数字k和一组数S,输出由S中的数组成的所有可能的游戏。 输入格式 输入有一组或多组测试数据。每组测试数据一行,数与数之间用空格隔开。每行第一个整 数是k(6<k<13),然后是从小到大排列的k个整数,即子集S。当k为零时,输入结束。 输出格式 对于每组测试数据,输出所有可能的游戏,每个游戏占一行。游戏里的数字按升序排列, 数与数之间有一个空格。所有游戏也要按字典序排列,也就是,首先比较各局游戏的第一个数 的大小,然后是第二个数的大小,依次类推,如下面的输出样例所示。不同的测试例之间用 个空行隔开。最后一组测试例之后没有空行。 【实例截图】
【核心代码】
标签：
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论