ACM宣讲-竞赛规则3.ppt

* * ACM/ICPC 规则和内容 By 王寅 YhnoLh ? yhnolh@ From Zealonox@XJTU 什么是ACM/ICPC？ 　　ACM/ICPC(ACM International Collegiate Programming Contest, 国际大学生程序设计竞赛)是由国际计算机界历史悠久、颇具权威性的组织ACM（Association for Computing Machinery，国际计算机协会）主办的，世界上公认的规模最大、水平最高的国际大学生程序设计竞赛。 赛场图片 赛场图片 赛场图片 赛场图片 赛场图片 赛场图片 比赛形式 三人组队，一台计算机 比赛时间为5小时 题目数量6~10道不等 通过指定途径提交源代码（网页、客户端） 根据通过题目数量和时间来排名 比赛形式 比赛期间可以随时提交源代码、查看各队的排名及题目通过情况 比赛最后一小时封榜（不能看到排名） 题目形式 全英文 首先描述题目需求（有时会很有意思） 接下来提供输入和输出数据的标准格式 然后提供样例输入和样例输出 题目作者的提供一些额外信息（不一定有） 你的程序需要： 用规定语言编写（C/C++/Java/(Python?)） 通过编译，并且没有使用非法库和函数 在规定的运行时间内对测试使用的所有输入数据得出正确的结果（并非只有样例） 评测机制 黑箱法，只关注输出结果（例外：抄袭） 测试用输入输出数据不公开 系统返回程序运行的评测信息 每出现一次未通过的提交，罚时20分钟 根据通过题目数量排名，如果题目数量相同则按照解题总用时排名 未通过的题目不计入总用时 常见评测信息： Accepted : 程序通过测试 Presentation Error : 输出数据正确，但是格式错误 Wrong Answer : 输出数据错误 Time Limit Exceeded : 程序运行时间超过题目限制 Memory Limit Exceeded : 程序使用的内存超过题目限制 Runtime Error : 程序运行中出错导致崩溃 Compile Error : 编译出错 题目内容 竞赛涵盖的范围很广，大致划分如下： Direct（简单题） Computational Geometry（计算几何） Number Theory（数论） Combinatorics（组合数学） Search Techniques（搜索技术） Dynamic Programming（动态规划） Graph Theory（图论） Other（其他） 题目特点 叙述往往十分有趣（著名的Cow?） 不涉及十分高深的算法和数据结构，贴近实际问题 程序代码较短，不会出现成千上万行代码 要求快速、清晰、准确的思路 设置陷阱，考察选手考虑问题的周全性 一些贴心的提示（准备篇）? 可以带纸质的参考资料入场，但是不可以带电子设备 比赛时间较长，精力消耗较大，建议带些食品饮品，正式比赛中会发 队中至少要有一名英语水平较高的同学，或者翻字典很快的同学XD 明确自己擅长的方面 赛前充分休息，不要打夜战 一些贴心的提示（比赛篇）? 一定要看清题目要求 对于不同的输入格式采取不同的策略 尽量避免出现CE，PE 通过样例不等于通过程序 输出末尾换行（除非有特殊要求） 对于多组数据的处理策略 比如，多组数据，每组数据两个整数a和b C: while(scanf(%d %d,a, b) != EOF) {…} C++: while(cin a b){…} Java: while (in.hasNextInt()) {…} 一道很有趣的题目 题目描述 Jim和Anna是好朋友。有一天，他们玩了一个游戏，游戏的规则是这样的： 有两堆石子，一堆有a个，一堆有b个。两人轮流取石子，Jim先取。每一步必须从其中一堆中取两个石子扔掉，并且从这堆中取出一些石子放入另一堆中（可以取0个，但是不能取完）。取的过程中要保持两堆石子都至少剩1个，最后让对手没有办法取的人获胜。 他们玩了一会儿，发现这个游戏对于某一方是有必胜策略的，即如果两堆石子的个数是确定的，那么有一个人一定可以有办法获胜，不管另一个人如何取。 现在给出两堆石子的个数a和b，问最终谁可以获胜？ 输入格式 本题有多组输入数据，每组输入数据有一行，每行两个正整数，用空格隔开，分别代表a和b。(1=a,b=100000) 输出格式 对于每组输入数据，输出一行，为获胜者的名字，Jim或者Anna，行尾不要有多余空格。 样例输入 1 2 4 5 7 10 样例输出 Anna Jim Jim 题目简单分析 首先，最自然的想法就是枚举所有情况，然后检验有没有必胜策略 实现很