ACM竞赛题

1、软件设计与开发的实践过程是令人反感的。ZLC正面临一个严重的问题。在k维空间多点了一点。ZLC需要找到最近的m个点。欧氏距离作为两点之间的距离度量。P和Q的点之间的欧几里德距离的线段连接起来的长度。在笛卡尔坐标系中，如果P＝（P 1，P 2，…，p n）和Q＝（Q 1，Q 2，…，q N）在n维欧氏空间的两点，然后从P到Q的距离，或从Q到P了：

输入描述:

输出描述:

输入例子:

3 2

1 1

1 3

3 4

2

2 3

2

2 3

1

输出例子:

2、英雄地精工程师在守卫遗迹有两个技能：远程矿山厂强大的煤矿，只有当触发引爆，引爆-引爆同时所有远程矿山。矿井电源会破坏敌人远离它1000 * /（R R）。当所有的地雷引爆的同时，损害的敌人是所有矿山的最大值，即1000 * A[i] / (r[i] * r[i])的最大值

地精工程师在地图植物许多矿山，和熊猫想通过危险区域。

该区域为正方形，每边长度为100。的西南角的坐标（x = 0，Y = 0）和东北角的坐标是（X = 100，Y = 100）。

熊猫将进入（50，0），并在（50，100），并不会以任何其他方式走出该地区。鉴于该地区的所有矿山的坐标和威力，什么应该熊猫的HP如果熊猫想在他死前所经过的地区的至少？假设熊猫会选择最好的路径

输入描述：

每一种情况有四条线。第一行是n个整数x [ I ]，第二行是n个整数Y [我]，第三行是n个整数A [我]，最后一行是一个空的行。1 < = 55。

输出描述：

最小的HP。小数点后保持三位。

输入例子:

50

2

20 50 70

50 70 80

42 42 42

10 10 10 20 30 40 50 60 40 50 60 70 80 80 80 90 90 90

40 50 60 60 60 60 60 70 30 30 30 30 40 30 20 50 40 10

90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90

输出例子:

21750.000

105.000

400.000

3、鲍伯是在西安旅行。他在这座城市找到了许多秘密的隧道。在他的眼里，城市是一个网格。他不能进入一个有障碍的格子。在一分钟内，他可以移动到一个相邻的网格，没有障碍。鲍伯充满了好奇，他想参观所有的秘密隧道下方的城市。在隧道里旅行，他必须走到隧道的入口，并从退出后，一个神话般的访问。他可以选择在他开始的地方，他将旅行每一个隧道一次，只有一次。现在他想知道，他参观所有的隧道会花费多长时间（不包括他在隧道里的时间）。

输入描述：

输入包含多个测试用例。请过程直到EOF。

对于每个测试用例，第一行包含两个整数n（1≤N≤15），广场的地图和M的边的长度（1≤M≤15），隧道的数量。

城市的地图是在下一个n行中给出的。每行包含确切的n个字符。障碍是由“#”和空格为代表的“代表”。

然后M线跟随。每一行包含四个整数x 1，y 1 x 2，y 2，说明有一个洞口隧道（x 1，y 1）和出口（x 2，y 2）。它保证（x 1，Y 1）和（X 2，Y 2）在地图都是空的网格。

输出描述：

对于每一种情况下，输出一个整数，表示鲍伯在隧道之间所花费的最小时间。

如果鲍伯访问所有的隧道是不可能的，输出-1。

输入例子:

....# ...#. ..... ..... .....

2 3 1 4

1 2 3 5

2 3 3 1 5 4 2 1

输出例子: 7

ACM竞赛试题集锦

取石子游戏 Time Limit:1S Memory Limit:1000K Total Submit:505 Accepted:90 Description 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。 Input 输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。 Output 输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。 Sample Input

2 1 8 4 4 7 Sample Output 1 跳蚤 Time Limit:1S Memory Limit:1000K Total Submit:198 Accepted:44 Description Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许

有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。 比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。 当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。 Input 两个整数N和M(N <= 15 , M <= 100000000)。 Output 可以完成任务的卡片数。 Sample Input

acm程序设计大赛题目

The Mailboxes Manufacturers Problem Time Limit:1000MS Memory Limit:65536K Total Submit:299 Accepted:227 Description In the good old days when Swedish children were still allowed to blowup their fingers with fire-crackers, gangs of excited kids would plague certain smaller cities during Easter time, with only one thing in mind: To blow things up. Small boxes were easy to blow up, and thus mailboxes became a popular target. Now, a small mailbox manufacturer is interested in how many fire-crackers his new mailbox prototype can withstand without exploding and has hired you to help him. He will provide you with k(1 ≤ k≤ 10) identical mailbox prototypes each fitting up to m(1 ≤ m≤ 100) crackers. However, he is not sure of how many firecrackers he needs to provide you with in order for you to be able to solve his problem, so he asks you. You think for a while and then say, “Well,if I blow up a mailbox I can’t use it again, so if you would provide me with only k = 1 mailboxes, I would have to start testing with 1 cracker, then 2 crackers, and so on until it finally exploded. In the worst case, that is if it does not blow up ev en when filled with m crackers, I would need 1 + 2 + 3 + … + m = m ×(m+ 1) ? 2 crackers. If m = 100 that would mean more than 5000 fire-crackers!” “That’s too many,” he replies. “What if I give you more than k = 1 mailboxes? Can you find a strategy that requires less crackers?” Can you? And what is the minimum number of crackers that you should ask him to provide you with? You may assume the following: 1.If a mailbox can withstand x fire-crackers, it can also withstand x? 1 fire-crackers. 2.Upon an explosion, a mailbox is either totally destroyed (blown up) or unharmed, which means that it can be reused in another test explosion.

acm竞赛位运算简介及实用技巧~

位运算简介及实用技巧 转载者注：最近在论坛上看到些十分空虚、空大的帖子。觉得编程还是要讲点实践，实践出真知。 众所周知，人和电脑处理的方式究竟还是不同的，否则人人都是计算机程序员了。有些东西对人说很容易，而对计算机来说很难，反之亦然。 位操作就是人和电脑处理方式不同的体现，有些人认为这个东西有些BT，但其实非常高效的程序大多都是用位操作优化，因为它十分底层，速度极快。其实位操作也有他自己独特的性质，只要我们能熟练得掌握，就可以更好得驾驭我们的程序，这也是我转此帖的目的。 PS：不要把注意力集中在语言上，所有语言都是一样的，只是工具而已。 去年年底写的关于位运算的日志是这个Blog里少数大受欢迎的文章之一，很多人都希望我能不断完善那篇文章。后来我看到了不少其它的资料，学习到了更多关于位运算的知识，有了重新整理位运算技巧的想法。从今天起我就开始写这一系列位运算讲解文章，与其说是原来那篇文章的follow-up，不如说是一个remake。当然首先我还是从最基础的东西说起。 什么是位运算？

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and 运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）： 110 AND 1011 ---------- 0010 --> 2 由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。当然有人会说，这个快了有什么用，计算6 and 11没有什么实际意义啊。这一系列的文章就将告诉你，位运算到底可以干什么，有些什么经典应用，以及如何用位运算优化你的程序。 Pascal和C中的位运算符号 下面的a和b都是整数类型，则： C语言 | Pascal语言 -------+------------- a & b | a and b a | b | a or b

ACM-ICPC简介和参赛规则

ACM/ICPC(ACM International Collegiate Programming Contest, 国际大学生程序设计竞赛)是由国际计算机界历史悠久、颇具权威性的组织ACM（Association for Computing Machinery，国际计算机协会）主办的，世界上公认的规模最大、水平最高的国际大学生程序设计竞赛。 1.ACM-ICPC的历史及其影响ACM/ICPC从1970年开始，已经举办了30多届，其目的旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。该竞赛一直受到国际各知名大学的重视，并受到全世界各著名计算机公司的高度关注。可以说，ACM国际大学生程序设计竞赛已成为世界各国大学生最具影响力的国际级计算机类的赛事。 2.ACM-ICPC的比赛形式和内容ACM/ICPC采用组队参赛的形式，由三名队员组成一支队伍参赛。比赛时三名队员只使用一台电脑，整个比赛时间为5个小时。比赛题目为6~10道不等，全英文。标准的程序数据输入和输出解答要求。选手们必须根据题目内容设计算法，并完成相应的功能要求。该队程序如果能在规定时间内得出正确的答案视为通过。队伍通过的题目数量多的在比赛中排名越高，题目数相同的则用时越少的排名越高。 3.竞赛内容竞赛涵盖的范围很广，大致划分如下：Direct（简单题），Computational Geometry（计算几何），Number Theory（数论），Combinatorics （组合数学），Search Techniques（搜索技术），Dynamic Programming（动态规划），Graph Theory（图论），Other（其他）可使用的计算机语言：C语言、C++，JAVA

2017ACM比赛试题

2017年计算机ACM编程竞赛 主办：计算机科学与技术学院 时间：2017-11-22 18:00---20:00 地点：计算机学院奋进楼4楼5机房

竞赛规则 1、比赛时间为120分钟，从18:00开始，20:00结束。 2、比赛形式为上机编程，每个小组使用三台电脑，可任选语言，同一小组不同题目可使用不同语言； 3、比赛期间可以使用自己电脑，不可查阅书籍、但禁止查阅个人U盘，禁止使用手机、电脑进行上网查询，禁止使用现有代码，违者取消比赛资格；（正式ACM中是可以携带纸质材料的，但由于本次比赛，有大量题目参考书上例题，所以就不让携带了） 4、比赛期间，如遇到设备问题，可举手示意工作人员； 5、由于机房电脑系统有重启还原功能，比赛期间请勿轻易重启电脑； 6、【重要】比赛结束后，请确认将所要提交文件拷至工作人员U盘，否则成绩无效概不负责。 提交方式 1、创建文件夹，文件夹命名格式为小组号-小组队长-组员1-组员2 2、将每一题的源程序文件夹以题目编号命名，拷贝至上述创建的文件夹中 3、在本文档中每题相应位置附上源码及截图（windows截图键:Alt+Prt sc sysrq）,拷贝至上述创建的文件夹中 4、比赛结束后将上述文件夹拷贝至工作人员U盘中，提交方算完成，提交 完成前请勿重启电脑。 注：本次比赛共14题，满分120分。没有完成题目，但有部分解题步骤者按完成度给分。每道题要有注释。

竞赛题目 1. 青年歌手大奖赛中，评委会给参赛选手打分。选手得分规则为去掉一个最高分和一个最低分，然后计算平均得分，请编程输出某选手的得分。输入数据有多组，每组占一行，每行的第一个数是n(2

ACM竞赛规则与常见

ACM/ICPC竞赛常见问题解答参赛对象 1、凡广州大学在校本专科生均可报名参加。 年级、专业不限。 鼓励低年级同学及女同学参加。 2、本次比赛学生以个人身份参加，每人独立参赛。 3、参赛同学应保证自己身份等资料的真实性。 竞赛细则 1、选手在参赛时携带个人证件。 2、竞赛以上机为比赛方式。 3、竞赛中至少命题6题，至多命题9题，上机比赛时间为4个小时，中间不休息。 4、参赛选手可以携带诸如书籍、字典、手册、程序清单等文字性参考资料。 5、参赛选手不能携带任何可用计算机处理的软件或数据（不允许任何私人携带的磁盘或计算器）。 6、参赛选手不能携带任何类型的通讯工具，包括无线电接收器、移动电话等。 7、选手未解决全部题目不得提前离场 &竞赛的预定时间为4小时，但当竞赛进行一定时间后，竞赛裁判可以因为出现不可预见的事件而调整比赛时间长度，一旦比赛时间长度发生改变，将会以及时并且统一的方式通告所有参赛选手。 9、当参赛选手出现妨碍比赛正常进行的行为时，诸如擅自移动赛场中的设备，未经授权修改比赛软硬件，干扰他人比赛等，都将会被竞赛裁判剥夺参赛资格。 竞赛评分

1、正确解答中等数量以上试题的队伍会根据解题数目进行排名，解题数在中等数量以下的队伍只发布解题数量，不进行排名。 2、在进行排名时，如果多人解题数量相同，贝卩根据总用时加上惩罚时间进行排名。 总用时和惩罚时间由每道解答正确的试题的用时之和加上惩罚时间之和而成。 每道试题用时将从竞赛开始到试题解答被判定为正确为止，期间每一次错误的运行将被加罚20分钟时间。 未正确解答的试题不记时，对应的错误运行也不计入惩罚时间。 3、选手在比赛期间能看到排名表和他人的成绩、解决的问题。 4、比赛中每一道题目对应一种颜色的气球（颜色的对应在试题中注明）。 在选手正确解答出某道题目后，工作人员将会把对应颜色的气球插到此同学的位置旁。 5、比赛结束前一个小时内，将不再为正确的解答摆放气球。 6、请注意竞赛裁判决定解答提交是否正确需要一定的时间。 竞赛评奖 1、为鼓励优秀同学，本次比赛设立若干奖项，获奖者将获得奖品及证书。 2、比赛设一等奖，人数四人；二等奖，人数六人，三等奖，人数十人。 同时设优胜奖20人。 3、所有获奖者自动成为新一届广州大学ACM竞赛代表队的预备队员，参加学校组织的进一步培训。 比赛组织Q(Question)： 我能否携带字典、书籍和程序清单？A(An swer): 可以，建议至少携带一本英文字典。

如何备战acm竞赛

一：知识点 数据结构： 1，单，双链表及循环链表 2，树的表示与存储，二叉树（概念，遍历）二叉树的 应用（二叉排序树，判定树，博弈树，解答树等） 3，文件操作（从文本文件中读入数据并输出到文本文件中） 4，图（基本概念，存储结构，图的运算） 数学知识 1，离散数学知识的应用（如排列组合、简单的图论，数理逻辑） 2，数论知识 3，线性代数 4，组合代数 5，计算几何 二：算法 1，排序算法（冒泡法，插入排序，合并排序，快速排序，堆排序） 2，查找（顺序查找，二分发） 3，回溯算法 4，递归算法 5，分治算法 6，模拟法 7，贪心法 8，简单搜索算法（深度优先，广度优先），搜索中的剪枝，A*算法 9，动态规划的思想及基本算法 10，高精度运算 三、ACM竞赛的题型分析 竞赛的程序设计一般只有16种类型，它们分别是： Dynamic Programming （动态规划） Greedy （贪心算法） Complete Search （穷举搜索） Flood Fill （不知该如何翻译） Shortest Path （最短路径） Recursive Search Techniques （回溯搜索技术） Minimum Spanning Tree （最小生成树） Knapsack （背包问题） Computational Geometry (计算几何学) Network Flow （网络流） Eulerian Path （欧拉回路） Two-Dimensional Convex Hull （不知如何翻译） BigNums （大数问题） Heuristic Search （启发式搜索） Approximate Search （近似搜索） Ad Hoc Problems （杂题） 四 ACM竞赛参考书

关于ACM-ICPC竞赛

ACM/ICPC简介 ACM/ICPC(ACM International Collegiate Programming Contest, 国际大学生程序设计竞 赛)是由国际计算机界历史悠久、颇具权威性的组织ACM（Association for Computing Machinery，国际计算机协会）主办的，世界上公认的规模最大、水平最高的国际大学生程 序设计竞赛。 Why to be an ACMer? 不功利地说： 1. 大学生程序设计的世界级顶级赛事，不参加终身抱憾。 2. 提升思维与实践动手能力，做名副其实的Trouble-shooter。 3. 起点低，有C/C++、JAVA等语言基础知识和一台计算机即可参与学习；周期长，乐趣多，学生互相探讨，有助于营造良好的学术氛围。 功利地说： 1. 业界知名的IT公司不约而同地认为有ACM参赛经历的学生（无论有无获奖），优先雇佣。 2. 计算机科学研究生复试上机有相关试题。 3. 赛事多，奖金高，含金量高，可以获得许多荣誉。如：Google杯、阿里巴巴杯ACM的区域性竞赛；百度之星；各种赛区的选拔赛。 参赛参考资料和网站 算法竞赛入门经典 UVa OJ, POJ, ZOJ, HOJ, HDOJ 等在线测评系统

某北京高校参加程序设计类比赛的年度安排 ●4月：校内大赛（暨选拔赛）如：阿里巴巴集团杯ACM-ICPC程序设计精英赛 ●5~7月：百度之星程序设计大赛 ●暑期：夏令营集中培训 ●11月：参加ACM/ICPC亚洲区比赛（至少参加4～5个赛区的比赛） ●另外：每学期至少有三次月赛以及适当的练习赛 2010ACM-ICPC亚洲区预选赛中国大陆5赛区比赛安排 2010-09-11 哈尔滨赛区（哈尔滨工程大学）网络预赛(哈工程oj：https://www.sodocs.net/doc/05774173.html,） 赛区官网：https://www.sodocs.net/doc/05774173.html,/icpc/ 2010-09-12 天津赛区（天津大学）网络预赛 (杭电oj：https://www.sodocs.net/doc/05774173.html,) 赛区官网：https://www.sodocs.net/doc/05774173.html,/tj2010/ 2010-09-18 成都赛区（四川大学）网络预赛 (川大oj：http://125.64.92.19/) 赛区官网：https://www.sodocs.net/doc/05774173.html,/icpc/ 2010-09-19 杭州赛区（浙江理工大学）网络预赛(杭电oj：https://www.sodocs.net/doc/05774173.html,) 赛区官网：https://www.sodocs.net/doc/05774173.html,/ 2010-10-10 福州赛区（福州大学）网络预赛 (福大oj：https://www.sodocs.net/doc/05774173.html,) 赛区官网： https://www.sodocs.net/doc/05774173.html,/acmicpc-2010-fuzhou/Default.aspx 2010年9月25-26日 哈尔滨赛区现场比赛（哈工程命题） 2010年10月16日到17日 天津赛区现场比赛（复旦命题） 2010年10月23日到24日 杭州赛区现场比赛（北大命题） 2010年11月6日到7日 成都赛区现场比赛（浙大命题） 2010年11月19日到21日 福州赛区现场比赛（北大命题） 一个人网络预赛最多官网注册3次（同一年度） 报名方式 登录https://https://www.sodocs.net/doc/05774173.html,/ 教师注册教练账号，创建队伍参加相应赛区的比赛今年的比赛（36届）尚未开启注册

感受ACM-ICPC竞赛的教育意义

感受ＡＣＭ－ＩＣＰＣ竞赛的教育意义 ACM-ICPC竞赛和培训模式在一定程度上将基础学科很好地运用于程序设计当中，帮助学生加强学习和理解；其竞赛题目需要融入很多相关学科知识；选手通过培训和学习，能够更好地掌握更多的基础学科知识，提高思维能力。 我是从高中开始接触程序设计类竞赛的，当时程序设计竞赛叫做信息学奥林匹克竞赛。对于我来说，三年的竞赛生涯有些枯燥，我牺牲了很多假期时间待在机房和竞赛小组的伙伴们一起学算法、做程序题，并于2001年、2002年获得全国信息学奥林匹克分区联赛一等奖（相当于学科竞赛的省赛一等奖）。尽管我们当时没能更进一步入选省队参加全国赛，但我却因此被保送到心目中理想的大学，并学习软件工程专业。 高中的我对于程序设计类竞赛的意义有些置疑：似乎花了那么多的时间，只是学了一些算法，会编一些没什么实际意义的程序，拿了几个奖被保送读大学而已，好像还没有学习计算机应用开发技术来得实在。所以，那时我并没有太多关注ACM-ICPC。 后来，当经历了一年多的大学生活后，我发现竞赛带给我很多知识、技能以外的东西。 比如我觉得大学里每天听老师授课的效率不如看书自学的高，比如自己在学习计算机相关基础课程时感觉比别人更轻松，而这些都与我高中的竞赛学习生活密切相关。在高中的竞赛培训中，老师很少通过上课的方式给我们灌输知识，而是安排我们学习，告诉我们去看哪些书、做哪些程序题，并且组织我们进行交流讨论。如果我们发现自己的知识存在缺陷，再翻阅相关资料进行学习。这样的模式能够锻炼我们的自学能力，让我们知道应当如何去获取知识、提高能力。可以说，这时我才深切感受到这些程序设计竞赛的内涵，它教给我们的是计算机科学的基本思想和内涵，教给我们的是学习计算机科学的方法，是真正的授之以“渔”，而不是授之以“鱼”。 2005年9月，软件学院代表学校参加ACM-ICPC竞赛，这时我才真正有了接触这个竞赛的机会，并做起了小教练，负责组织培训、参赛工作。其实当时我对ACM-ICPC竞赛了解得也不是很透彻，而且当时离各赛区的比赛开始只有一个月的时间。等到我们完成队员选拔、组好参赛队时，已经错过了国内杭州赛区和成都赛区的报名时间。缺乏教练经验的我组织队员匆匆培训、练习了不到一个月，就参加了北京赛区网上预赛，并获得了出线资格，让北航在近年来第一次顺利晋级，并且组织了一支全部由大一学生组成的队伍参加北京区的决赛。在决赛期间，我有幸与北大的李文新老师、浙大的陈越老师、中山大学的郭嵩山老师以及国内其他各高校的教练老师进行一些交流和讨论，更深刻地体会到该竞赛的意义与内涵。

ACM比赛试题

The 35th ACM-ICPC Asia Regional Contest (Hangzhou) Contest Section October 24, 2010 Sponsored by IBM & Alibaba Zhejiang Sci-Tech University This problem set should contain 10 problems on numbered 24 pages. Please inform a runner immediately if something is missing from your problem set.

Problem A. Naughty fairies Description Once upon a time, there lived a kind of fairy in the world. Those fairies could hear the voice of fruit trees, and helped people with a harvest. But people did n’t know that fruits are also those fairies’ favorite food. After the fairies ate people’s fruits, they always did something to cover it up. One day a little fairy named Lily flew into an orchard and found a large peach tree. Hungry as Lily was, she started eating without thinking until her stomach was full. In the fairy world, when a fairy ate the fruits in a fruit tree, sometimes the fruit tree would feel honored and bore more fruits immediately. That’s why sometimes the number of fruits in a tree got increased after a fairy ate fruits of that tree. But the fairies didn’t want people to find out weird things such as fruits become more or less suddenly. Lily decided to use a magic spell so that the orchard owner couldn’t find the change of the number of p eaches. Suppose there were N peaches on a tree originally and there were M peaches left after Lily was full. M may be greater than, less than or equal to N. All M peaches were visible at first, and Lily wanted to make an illusion so that exactly N peaches are visible. Lily can do 3 kinds of spell to change the total visible number of peaches: 1) “PAPADOLA”：This spell would increase the number of visible peaches by one. 2) “EXPETO POTRONUM”：This spell would double the number of visible peaches. 3) “SAVIDA LOHA”:This spell would decrease the number of visible peaches by one. Each spell would take one minute and Lily wanted to finish as fast as possible. Now please tell Lily the least time she needs to change the number of visible peaches to N. Input There are several test cases, ended by “0 0”. For each test case, there are only one line containing two numbers separated by a blank, N and M, the original numbers of peaches and the numbers of peaches left(0

ACM竞赛要掌握的知识

ACM竞赛要掌握的知识 图论 路径问题 最短路径 0/1边权最短路径 BFS 非负边权最短路径 Dijkstra 可以用Dijkstra解决的问题的特征 负边权最短路径 Bellman-Ford Bellman-Ford的Yen-氏优化 差分约束系统 Floyd 广义路径问题 传递闭包 极小极大距离/ 极大极小距离 Euler Path / Tour 圈套圈算法 混合图的Euler Path / Tour Hamilton Path / Tour 特殊图的Hamilton Path / Tour 构造 生成树问题 最小生成树 第k小生成树 最优比率生成树 0/1分数规划 度限制生成树 连通性问题 强大的DFS算法 无向图连通性 割点 割边 二连通分支 有向图连通性 强连通分支 2-SAT 最小点基 有向无环图 拓扑排序 有向无环图与动态规划的关系 二分图匹配问题 一般图问题与二分图问题的转换思路

最大匹配 有向图的最小路径覆盖 0 / 1矩阵的最小覆盖 完备匹配 最优匹配 网络流问题 网络流模型的简单特征和与线性规划的关系最大流最小割定理 最大流问题 有上下界的最大流问题 循环流 最小费用最大流/ 最大费用最大流 弦图的性质和判定 组合数学 解决组合数学问题时常用的思想 逼近 递推/ 动态规划 概率问题 Polya定理 计算几何/ 解析几何 计算几何的核心：*积/ 面积 解析几何的主力：复数 基本形 点 直线，线段 多边形 凸多边形/ 凸包 凸包算法的引进，卷包裹法 Graham扫描法 水平序的引进，共线凸包的补丁 完美凸包算法 相关判定 两直线相交 两线段相交 点在任意多边形内的判定 点在凸多边形内的判定 经典问题 最小外接圆 近似O(n)的最小外接圆算法 点集直径 旋转卡壳，对踵点

acm编程比赛入门题目集

最少钱币数： 【问题描述】 这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要2个钱币才能凑成15元。 你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。 【要求】 【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M（1 <= M <= 2000，整数），接着的一行中，第一个整数K（1 <= K <= 10）表示币种个数，随后是K 个互不相同的钱币面值Ki(1 <= Ki <= 1000)。输入M=0时结束。 【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。 【样例输入】 15 6 2 5 10 20 50 100 1 1 2 【样例输出】 2 Impossible

Feli 的生日礼物 【问题描述】 Felicia 的生日是11月1日（和Kitty是同一天生的哦）。于是Feli请来Kitty一起过生日。Kitty带来了最新款的“Kitty猫”玩具准备送给Feli，不过她说，这份礼物可不是白送的。Feli要帮她一个忙，才能够得到心仪已久的玩具。Kitty说，“Kitty猫”玩具已经卖出了n!个，n<=10^100 *_*，Kitty想知道确切的数字，而不是无聊的“一个数加个感叹号”。Feli 听了大吃一惊。要知道，算出n!是一个无比艰巨的任务。Feli告诉Kitty，就算Feli算出n!，Kitty也看不下去，因为当n=20 时，计算机的长整型已经存不下了（Kitty只能接受1-9之间的数字）。于是Kitty说，你只要告诉我n!最后一位非0的数就可以了。Feli想了想，立刻动手写了个程序算出了正确的答案。现在，请你也试试看！注意哦，AC的男生将会得到一个“Hello Kitty”计算器（可编程，CPU 1THz，Mem 1TMB），AC的女生将会得到一个仿真“Hello Kitty”宠物（善解人意，无须喂养，智商1101，附带写情书功能）。 【要求】 【数据输入】每行一个n，直到输入数据结束 【数据输出】对应输入的n，每行输出一个答案 【样例输入】 1101 【样例输出】 8

ACM竞赛简介和入门

ACM竞赛简介： ACM国际大学生程序设计竞赛是由国际计算机界历史悠久、颇具权威性的组织ACM学会（美国计算机协会）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。(网上有更详细的介绍，这里只做个简介) ACM竞赛特点： 竞赛中一般有10道题，比赛时间为5个小时，每支参赛队伍由3名选手组成，可以携带诸如书、手册、程序清单等参考资料，对每一道题编完代码后，将代码提交裁判，每一次提交会被判为正确或者错误，判决结果会及时通知参赛队伍。 在规定时间内提交并通过题目数越多排名越靠前。（时间5小时，题目8~12题，同题目数按所用时间多少排名） ACM题目限制： 时间限制（即程序运行所用的时间）空间限制（即程序运行时所开内存的多少） ACM基本要求 ?英语 ?分析理解能力 ?算法 ?编码 ?合作

ACM竞赛意义 学习编程，并不是为了参加竞赛，ACM竞赛对于我们的意义更多的还是专业能力的提高。在备战过程中，无论是对自己的编程能力，还是团队合作解决问题的能力，都是一种很好的锻炼机会。一般而言，每个在做ACM竞赛的学生，他们的编程能力会比较出色。与数学建模相比，由于ACM竞赛针对的是我们学计算机的同学，所以没有数学建模的比赛规模，但是依旧是国际上最有影响力的大学生竞赛之一。 ACM竞赛入门 现在有很多大学有专门为ACM竞赛开设自己的测评网站，上面有很多贴近竞赛的题目。比如说北大poj，浙大zoj等等。所以选择一个自己专门练习的网站，我们都用北大的poj，然后开始自己在上面做题，和同学交流经验。等到回到本部，要是有了一定的实力和基础，张震老师就会对我们进行选拔和组队，最后参加省赛和亚洲的区域赛。 ?在poj上做20左右道简单的题目，熟悉ACM题目的基本特点。（这里列出几道相对 较简单的题目的题号：1000，1003，1004，1046，1207，1226，1504，1552） ?熟悉了poj之后，按照poj的题目分类，买一本或借一本算法的书（暨大ACM校队 的基本都用机械工程出版社的《算法导论》）开始学习，然后做算法的专题，一般每个专题做10~30道。主流的算法分类为： 1.搜索//回溯 2.DP（动态规划） 3.贪心 4.图论//Dijkstra、最小生成树、网络流 5.数论//解模线性方程 6.计算几何//凸壳、同等安置矩形的并的面积与周长 7.组合数学//Polya定理 8.模拟 9.数据结构//并查集、堆 10.博弈论 ?专题做完后，你已经很强了，就可以找另外2个同学或师兄组成自己的队伍，开始 做poj上的难题，开始模拟比赛，为今后的竞赛做准备。

最新acm编程比赛入门题目集

程序设计比赛试题 主办方：迅翔计算机协会

最少钱币数： 【问题描述】 这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要2个钱币才能凑成15元。 你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。 【要求】 【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M（1 <= M <= 2000，整数），接着的一行中，第一个整数K（1 <= K <= 10）表示币种个数，随后是K 个互不相同的钱币面值Ki(1 <= Ki <= 1000)。输入M=0时结束。 【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。 【样例输入】 15 6 2 5 10 20 50 100 1 1 2 【样例输出】 2 Impossible

Feli 的生日礼物 【问题描述】 Felicia 的生日是11月1日（和Kitty是同一天生的哦）。于是Feli请来Kitty一起过生日。Kitty带来了最新款的“Kitty猫”玩具准备送给Feli，不过她说，这份礼物可不是白送的。Feli要帮她一个忙，才能够得到心仪已久的玩具。Kitty说，“Kitty猫”玩具已经卖出了n!个，n<=10^100 *_*，Kitty想知道确切的数字，而不是无聊的“一个数加个感叹号”。Feli 听了大吃一惊。要知道，算出n!是一个无比艰巨的任务。Feli告诉Kitty，就算Feli算出n!，Kitty也看不下去，因为当n=20 时，计算机的长整型已经存不下了（Kitty只能接受1-9之间的数字）。于是Kitty说，你只要告诉我n!最后一位非0的数就可以了。Feli想了想，立刻动手写了个程序算出了正确的答案。现在，请你也试试看！注意哦，AC的男生将会得到一个“Hello Kitty”计算器（可编程，CPU 1THz，Mem 1TMB），AC的女生将会得到一个仿真“Hello Kitty”宠物（善解人意，无须喂养，智商1101，附带写情书功能）。 【要求】 【数据输入】每行一个n，直到输入数据结束 【数据输出】对应输入的n，每行输出一个答案 【样例输入】 1101 【样例输出】 8