书名：程序设计竞赛训练营：基础与数学概念
ISBN：978-7-115-57861-7
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
编 著 邱 秋
责任编辑 秦 健
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
本书是ACM主办的国际大学生程序设计竞赛的训练指南，主要介绍程序设计和针对竞赛训练所需的基础知识和基本数学概念，包括UVa OJ平台的使用方法、C++的输入输出处理、C++库实现所包含的数据结构、高级数据结构、字符串的处理和相关算法、排序与查找算法、代数、组合数学、数论、几何等内容。本书在介绍基础概念的基础上，引入了众多题目，以C++解题，针对部分题目给出参考代码，方便参考和练习。
本书适合有意参加国际大学生程序设计竞赛的本科生、研究生阅读，对有意参加国际信息学奥林匹克竞赛的中学生具有参考价值，也可作为计算机专业相关课程的参考教材。
子曰：“知之者不如好之者，好之者不如乐之者”。
——《论语·雍也》
人们常说“兴趣是最好的老师”。1998年，我还在读高一的时候，就对计算机产生了浓厚的兴趣。那时候计算机尚未全面普及，加上自己家庭条件也一般，根本无力购买“昂贵”的个人电脑，平时只能对着《电脑爱好者》[1]杂志上的广告，想象自己拥有一台个人电脑的情景。高中期间，每逢周末放假，我都要去县城的新华书店逛一逛，看看是否有新书可“免费”阅读。一次偶然的机会，看到书架上有一本《C语言教程》，我便不假思索地买了下来并开始自学。那时候学校的微机室建立不久，上面只有最简单的QBasic，我经常在上面尝试用QBasic语句编写一些小程序。有一次，在学习了高中物理的核裂变反应后，禁不住想使用QBasic编写一个程序来演示原子核的裂变反应。具体来说，就是模拟中子撞击原子核，原子核分裂，释放出更多中子，这些中子继续撞击其他原子核……最终形成链式反应的过程。我用QBasic中的绘图函数绘制一个小点表示中子，用较大的圆圈表示原子核，当中子碰到原子核时，表示中子的小点消失，原子核分裂为两个较小的原子核，释放一个中子，继续撞击其他原子核。当程序最终调试运行成功，看着链式反应的图像逐渐展现的时候，自己的内心非常具有成就感。我想，作为一个编程爱好者，当看到自己的“作品”能够良好地运行或者解决某个编程难题时，那应该便是最开心和最自豪的“高光”时刻。
不过阴差阳错，我并未如愿选择感兴趣的计算机专业，而是进入了医学院校，于是编程便成了我最大的业余爱好。2011年，我用了半年多的时间，完成了由Skiena和Revilla[2]合著的《挑战编程：程序设计竞赛训练手册》[1]一书的习题。在全部完成后，感觉书中每一章讲解部分的内容较为简略，使得中低水平的编程爱好者在读完各章的内容后，难以获得足够的知识来解决相应章的问题，因此打算写一本用C++来进行解题的参考书籍，以弥补上述不足。但是由于种种原因，一直没有下定决心来做，至此成为了一个“心结”。一方面是已经有很多关于算法和编程竞赛的图书，例如，Skiena的The Algorithm Design Manual[2]、Sedgewick的Algorithms[3]、Halim的Competitive Programming[4]等；另一方面我本人也没有足够的时间和精力去进一步深入学习算法，缺乏知识积累和写书的资料。不过非常幸运，从2015年11月开始，我终于有许多时间可以做这件事，于是本书逐渐写成。
本书以C++进行解题，读者对象是已经具备一定C或者C++基础的编程爱好者，或者是准备参加程序竞赛正在进行训练的高中生，或者是期望通过学习算法和练习以获得进一步提高的大学生。代码采用GCC 5.3.0进行编译，使用C++11语言标准（需要启用编译符号：-std=c++11）。例题和练习以University of Valladolid Online Judge（UVa OJ）题库中题号100～1099的题目、Halim的Competitive Programming所介绍的习题，以及我本人在写作过程中解决的题目为基础，涵盖了绝大部分的基本算法。
考虑到篇幅限制，我将出版《程序设计竞赛训练营：基础与数学概念》《程序设计竞赛训练营：算法和实践》两本图书，本书主要包括“基础”和“数学”两部分。“基础”部分包括UVa OJ平台的使用方法、C++的输入输出处理、C++库实现所包含的数据结构、高级数据结构、字符串的处理和相关算法、排序与查找算法。“数学”部分包括代数、组合数学、数论、几何、计算几何。在编程竞赛中，较难的题目往往是由多个“子问题”构成，每个“子问题”涉及一个基础问题，解决整道题需要对这几个“子问题”都熟悉才可以。本卷介绍了在编程竞赛中出现次数较多的“子问题”，掌握这些“子问题”的解决方法，是提高解题能力的基础。
虽然一本书主要集中于基础和数学，另一本书主要集中于算法和技巧，但两本书的划分并不是绝对的。例如，在本卷中，介绍了KMP匹配算法、Aho-Corasick算法、扫描线算法、Graham扫描法、Jarvis步进法、Andrew合并法等，也介绍了诸如坐标离散化等处理问题的技巧。因此，有些练习所涉及的内容可能会跨越两本书的内容，请读者予以注意。
正如武术宗师的练成，如果不学习各种武术套路，建宗立派就如无根之木、无水之鱼，但是如果将武术套路学“死”，那就容易形成惯性思维，失去自身的创造力，更别谈创立新的武术流派。学习算法的最高境界，我认为和武术宗师的练成类似，既对各派的武功招数、优缺点了如指掌（就如同对基本算法的原理及实现非常熟悉一样），但又不囿于各派的武功路数（就像深刻理解了算法原理，掌握了算法的精髓所在），能够根据具体情况进行变通。不过本书并不是一本算法大全，并未将算法的所有细节介绍得面面俱到，只是摘录了要点，列出了关键所在，正所谓“师傅领进门，修行在自身”，需要读者在阅读本书的时候主动查阅相关资料并加以练习，以便进一步加深理解。“授人以鱼，不如授之以渔”，我认为学习过程中最重要的是掌握学习的方法，而不是仅仅满足于某种具体算法的掌握，同时也不要被已经学习过的算法束缚了自己的想象力。
不言而喻，对于任何一道题目来说，“理解问题的解决过程”比“记住问题的解决过程”更为重要。解题的途径绝非只有书中所述的一种。在理解问题的基础上，重新对问题进行定义，从某个新的角度再对原问题进行思考，激发解题的动力和突破既往解题思路的束缚，将已有的算法和数据结构知识予以重新组合，通过语言和编程技术使头脑中的想法变成计算机的实现代码，这样才能够在题目和编程解题间架设一座真正属于自己的桥梁[5]。我认为这是学习编程的过程中应该努力达到的一种更高境界。
感谢父亲[3]、母亲、妻子的辛劳付出，以及女儿、儿子对我未能给予更多时间陪伴的理解，因为她（他）们，我能够有时间专心思考，本书才得以完成。阚元伟通读了本书的初稿，对行文上不连贯或描述有歧义的地方提出了修改意见，在此表示衷心的感谢。在编写本书的过程中，我参考了许多互联网上的资料和编程爱好者的博客文章，从他（她）们的解题思路中得到了诸多启发，由于篇幅所限，不能在此一一列出致谢。正如散文家陈之藩在《谢天》中所说的：“即是无论什么事，得之于人者太多，出之于己者太少。因为需要感谢的人太多了，就感谢天罢。”
编写本书的过程，实际上也是一个不断学习和进步的过程，由于本人水平有限，书中存在谬误不当之处在所难免，敬请读者不吝指出，以便本书有机会再版时予以改进。如有任何意见或建议，请发送邮件到我的邮箱：metaphysis@yeah.net。
衷心希望读者在阅读本书的过程中能够独立思考，勤加练习，融会贯通，学有所得。祝解题愉快！
邱秋（寂静山林）
二〇二〇年一月一日于海南琼海
[1] 由中国科学院主管，北京《电脑爱好者》杂志社出版的一本日常计算机应用相关的杂志。
[2] 2018年7月，在与uDebug网站管理员Vinit Shah就UVa 12348 Fun Coloring的评测问题进行电子邮件交流的过程中，遗憾得知Miguel Ángel Revilla教授已于2018年4月去世。
[3] 在编著本书的过程中，由于工作的原因，父亲于2018年3月17日来海南帮忙照顾家庭。父亲有多年的高血压病史，海南天气炎热，使父亲血压控制得不理想，加之我对父亲的血压变化关注不够，且父亲自身对高血压可能导致的风险也未引起重视，长期服用降血压药物但未能规范检测血压变化……多种不利因素，导致父亲于2018年7月27日不幸去世，这让我心中深感愧疚，抱憾终生。
尽信《书》，则不如无《书》。
——《孟子·尽心下》
纸上得来终觉浅，绝知此事要躬行。
——陆游，《冬夜读书示子聿》
本书的读者对象为计算机专业（或对ACM-ICPC竞赛感兴趣的其他专业）学生及编程爱好者，可以作为ACM-ICPC竞赛训练的辅助参考书。本书不是面向初学者的C++语言教程，要求读者已经具备一定的C或C++编程基础，有一定的英语阅读能力，了解基本的数据结构，已经掌握了初步的程序设计思想和方法，具备一定程度的算法分析和设计能力。本书的目标是引导读者进一步深入学习算法，同时结合习题来提高分析和解决算法问题的能力。
本书既是训练指南，又兼有读书笔记的性质。为了表达对Skiena和Revilla合著的《挑战编程：程序设计竞赛训练手册》一书的敬意（它激发了我对算法的兴趣，促使我编写这本书，可以说是让我对编程竞赛产生兴趣的“启蒙老师”），本书的章节名称参考了该书的目录结构，但章节编排、叙述方式和具体内容已“面目全非”。每章均以“知识点”为单元进行介绍，每个“知识点”基本上都会有一份解题报告（题目源于UVa OJ），之后再列出若干题目作为强化练习或者扩展练习。强化练习所给出的题目，一般只需要掌握当前所介绍的知识点就能予以解决。扩展练习所给出的题目，一般需要综合运用其他章节所介绍的知识点，甚至需要自行查询相关资料，对题目所涉及的相关背景知识及算法进行理解、消化、吸收后才能予以解决，其难度相对较高。第 3 章～第 5 章的最后一节内容对一些在解题中常用的算法库函数作出了简要的解析和示例。
本书英语姓名的汉译名参考《英语姓名译名手册》[6]。
本书各章习题的解题代码有两个版本，最初的版本于2011年上传至CSDN。2016年，对部分解题代码进行了修改完善，并对编码风格进行了若干调整，将其与已解决题目的代码合并，上传至GitHub[1]。由于UVa OJ上的评测数据可能已经发生了变化，个别涉及浮点数精度的代码在提交时可能会得到“Wrong Answer”的评判，但解题的基本思路是正确的，请读者酌情参考使用。
本书着重于算法的思想介绍和实现，一般不对算法的正确性给予证明。对正确性证明感兴趣的读者可参考标注的文献资料或者相关的专著，或者查阅“算法圣经”——Knuth的《计算机程序设计艺术》[7]及Cormen等人的《算法导论》[8]。参考文献或资料仅在第一次引用的时候给出标注，对于后续引用不再予以标注。
本书的所有题目中，除个别题目以外，其他题目均选自UVa OJ，因此不在每道题目前附加UVa以区分题目的来源。为了练习选择的便利，题目的右上角使用A～E的字母来标识此题的“相对难度”。以2020年1月1日为截止日期，按“解决该题目的不同用户数”（Distinct Accepted User，DACU）进行分级：A（容易），DACU≥2000；B（偏易），1999≥DACU≥1000；C（中等难度），999≥DACU≥500；D（偏难），499≥DACU≥100；E（较难），99≥DACU。难度等级为A～C的题目建议全部完成，难度等级为D和E的题目尽自己最大努力去完成（对于某些尝试人数较少的题目，根据上述难度分级原则得到的难度值可能并不能准确反映题目的实际难度，本书适当进行了调整）。如果某道题的DACU较小，原因有多种，或者是该题所涉及的算法不太常见，具有一定难度；或者是输入的陷阱较多，不太容易获得通过；或者是题目本身描述不够清楚导致读题时容易产生歧义；或者是题目的描述过于冗长，愿意尝试的人较少[2]；或者是在线评测系统没有提供评测数据，导致无法对提交的代码进行评判[3]。不管是什么原因，你都应该尝试去解题。对于学有余力的读者来说，研读文献资料并亲自实现算法，然后用习题来检验实现代码的正确性，是提升能力素质的较好途径。
由于本书包含较多代码，为了尽量减少篇幅，每份代码均省略了头文件和默认的命名空间声明。为了代码能够正常运行，请读者直接下载GitHub上的代码，或者在手工输入的代码前增加如下的头文件和命名空间声明[4]：
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;对于使用GCC 5.3.0（或以上）版本编译器的读者，可以使用下述更为简洁的方式来包含所有头文件：
#include <bits/stdc++.h>本书中的算法实现旨在帮助读者理解算法，较多借助C++的标准模板库（Standard Template Library，STL），在运行效率和简洁性上可能并不是最佳的，建议读者在掌握算法后，自行尝试编写更为高效和简洁的算法实现作为自己的标准代码库（Standard Code Library，SCL）。
所有示例代码和参考代码均可从本书的配套资源获得。每个章节内属于同一节的示例代码按顺序排列，位于以章节编号命名的文件夹内。例如，第2章2.1.1小节的内容为“整数的表示”，假设该小节包含两份示例代码，则按出现的先后顺序依次命名为2.1.1.1.cpp、2.1.1.2.cpp，如果只包含一份示例代码，则命名为2.1.1.cpp，均位于文件夹“Books/PCC1/02”内，文件命名在示例代码的第一行给出。
位于同一个文件中的、连续的示例代码采用如下的文件命名样式：
//------------------------------2.1.1.cpp------------------------------//
// 连续的示例代码。
//------------------------------2.1.1.cpp------------------------------//对应地，一些代码跨越正文的多个段落，这样的代码采用如下的文件命名样式：
//++++++++++++++++++++++++++++++2.1.1.cpp++++++++++++++++++++++++++++++//
// 跨越多个段落的示例代码（第1部分）。正文分隔了多个这样的示例代码片段，多个这样的片段构成了整个示例代码。
// 跨越多个段落的示例代码（第2部分）。
//++++++++++++++++++++++++++++++2.1.1.cpp++++++++++++++++++++++++++++++//[1] 读者可在GitHub搜索metaphysis/Code了解更多。
[2] 例如：199 Partial Differential Equations。
[3] 例如：510 Optimal Routing。
[4] 头文件<cassert>和<regex>极少使用，未加入列表，不过它们在某些特定题目的示例代码中有应用。
本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。
本书提供编程题目解答的参考代码文件。
要获得以上配套资源，请在异步社区本书页面中单击
，跳转到下载界面，按提示进行操作即可。注意：为保证购书读者的权益，该操作会给出相关提示，要求输入提取码进行验证。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，单击“提交勘误”，输入勘误信息，单击“提交”按钮即可（见下图）。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿。
如果您所在学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近30年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。
异步社区
微信服务号
凡事预则立，不预则废。
——《礼记•中庸》
本章旨在帮助读者了解什么是程序设计竞赛，以及如何开始自己的第一次挑战。如果读者已经熟悉相关内容，可以跳过此章，直接从第2章开始阅读。
本书所指的程序设计竞赛是解题竞赛，指参赛者利用自己所学的计算机相关知识，在限定的时间内解决若干道具有一定难度的编程题目。这些题目一般都与某种算法有关，如果读者没有经过相关的训练，一般难以在限定时间内予以解决。除了解题竞赛以外，还有很多其他类型的程序设计竞赛。例如，以提高程序运行效率为目标的性能竞赛，以完成某个具有特定功能的软件为目标的创意竞赛等。下面介绍一些具有较大影响力的解题程序设计竞赛。
美国计算机协会（Association for Computing Machinery，ACM）主办的国际大学生程序设计竞赛（International Collegiate Programming Contest，ICPC），是历史悠久的国际大学生程序设计竞赛，其目的在于使大学生运用计算机来充分展示自己分析问题和解决问题的能力。
该项竞赛自从1977年第一次举办世界总决赛以来，截至2020年1月，已经连续举办了43届。该项竞赛一直受到国际各知名大学的重视，全世界各大IT企业也给予了高度关注，有的企业（如IBM、Oracle、惠普、微软等公司）还经常出资赞助比赛的进行。
ACM-ICPC以团队代表各学校的形式参赛，每队不超过3名队员。队员必须是在校学生，满足一定的年龄限制条件，并且每年最多可以参加两站区域选拔赛。比赛期间，每队需要通过1台计算机在5个小时内使用C/C++、Java和Python中的一种语言编写程序解决7～13个问题。程序完成之后提交裁判运行，运行的结果会判定为正确或错误两种并及时通知参赛队。最后的获胜者为正确解答题目最多且总用时最少的队伍。
与其他计算机程序竞赛相比，ACM-ICPC的特点在于其题量大，每队需要在5小时内完成7道或以上的题目。另外，一支队伍有3名队员却只有1台计算机，使得时间显得更为紧张。因此，除了扎实的专业水平，良好的团队协作和心理素质同样是获胜的关键。
Google Code Jam（谷歌全球编程挑战赛）是Google举行的一项国际编程竞赛，目标是为Google选拔顶尖的工程人才。
比赛的每道题目均由Google的工程师仔细设计，既有趣也极具挑战性，选手不仅能测试自己的编程水平，更能在比赛环境中快速提升实践技能，丰富自身履历。该项赛事始于2003年，竞赛内容包括在限定时间内解决一系列特定的算法问题，编程语言和环境的选择不受限制。每年竞赛中所有参赛者在经过4轮线上比赛后，将会诞生25位选手参加在不同Google Offices地点举办的The World Finals，竞争现金大奖及奖杯。
TopCoder是一个面向平面设计师和程序员的网站，它采用比赛、评分、支酬等方式吸引众多平面设计师和程序员进行业余工作。
该网站每个月都有两次或三次在线比赛，根据比赛的结果对参赛者进行新的排名。参赛者可根据自己的爱好选用Java、C++、C#、VB或Python进行编程。参赛者必须在1小时15分钟内完成三道不同难度的题目，每道题完成的时间决定该题在编程部分所得的分数。比赛可分为三部分：Coding Phase、Challenge Phase和System Test Phase，比ACM-ICPC多了Challenge Phase，这部分是让参赛者浏览分配在同一房间的其他参赛者的源代码，然后设法找出其中的错误，并构造一组数据使其不能通过测试。如果某参赛者的程序不能通过别人或系统的测试，则该参赛者在此题目的得分将为零。
CodeForces是一个提供在线评测系统的俄罗斯网站，该网站由一群来自俄罗斯萨拉托夫国立大学的程序员创建并维护，其中主要的领导者为Mike Mirzayanov。
CodeForces的每位用户在参加比赛后都会有一个得分，系统根据得分及用户在以往比赛中的表现赋予用户一个Rating并冠以不同的头衔，名字也会以不同的颜色显示。参加比赛的用户按Rating以某个分值为界划分为Div1和Div2两类。相应地，CodeForces上的比赛也会指明是Div1还是Div2，抑或同时进行。Div1的比赛较难，Div2的比赛较简单。如果同时进行，Div1的A、B、C三题会和Div2的C、D、E三题相同。每次比赛结束后Rating都会依据此前各个选手的Rating和公式重新计算。
比赛中，选手有2个小时的时间去解决5道题目，这里的“解决某道题目”是指预测试通过，即通过了一次仅含部分测试点的测评，而最终决定是否得到这道题的分数，要看比赛结束后的统一测评。某道题的分数随着时间线性减少，但不会低于初始分值的30%。也就是说，选手解决问题的速度越快，得分也相应越高。而且，对于选手的每次提交都会扣除一定的分数。例如，某道题目的初始分为1000分，每过1分钟，该题的分数减少4分，如果选手在10分钟内尝试提交了3次并在第3次最终通过了预测试，每次错误提交扣除50分，那么该题的得分为1000−4×10−2×50=860。
同一个Div的选手将被划分到若干个房间里，每个房间约有20位选手。当某道题的预测试通过之后，选手可以选择锁定该题代码，锁定该代码后，选手之后将无法就该道题目进行再次提交（即使发现代码中包含错误）。之后选手就可以查看同一个房间内其他参赛者的代码并试图找出其中的漏洞了。选手可以自己构造一个测试（可以是数据，也可以是数据生成器）使得该代码不能通过，称之为Hack（有时也称Challenge）。一次成功的Hack可以得100分，而如果没有成功，将会被扣50分。最后，所有通过预测试的代码将提交进行最终测试，选手的最终得分为通过最终测试的代码分数和Hack其他选手所获得（扣除）的分数。
CodeForces的题目偏向于考察解题思路，一般较少涉及复杂的算法，标程的代码一般都比较简短而精巧。
国际信息学奥林匹克竞赛（International Olympiad in Informatics，IOI），是面向中学生的一年一度的信息学科竞赛。
这项竞赛包含两天的计算机程序设计，用以解决算法问题。选手以个人为单位，每个国家最多可选派4名选手参加。参赛选手从各国相应计算机竞赛中选拔。国际信息学奥林匹克竞赛属于智力与应用计算机解题能力的比赛，题目有相当的难度，解好这类题目，需要具备很强的综合能力。第一，具备观察和分析问题的能力；第二，具备将实际问题转化为数学模型的能力；第三，具备灵活地运用各种算法的能力；第四，具备熟练编写程序并将其调试通过的能力；第五，具备根据题目的要求，独立设计测试数据，检查自己的解法是否正确、是否完备的能力。能够参加IOI的选手应该具有很强的自学能力和动手能力，需要学习有关组合数学、图论、基本算法、数据结构、人工智能搜索算法及数学建模等知识，还要学会高级语言和编程技巧，要具备很强的上机操作能力。国际信息学奥林匹克竞赛鼓励创造性，在评分的标准上给予倾斜，创造性强的解题方法可以拿到高分。
随着ACM-ICPC程序设计竞赛的推广，各种在线评测（Online Judge，OJ）网站及工具应运而生。其中数University of Valladolid Online Judge（简称UVa OJ或UVa）历史悠久[1]。UVa OJ的特点是题目丰富、题型多样，比较适合中等水平的ACM-ICPC选手训练。
要想在UVa OJ上解题，必须先注册一个账号。在互联网搜索onlinejudge即可登录UVa OJ的官方主页，登录后单击“Register”即可跳转到账户注册页面，如图1-1所示。填写必要的信息之后，UVa OJ会向用户填写的邮箱地址发送一封验证邮件，通过邮件验证后，账户即被激活。
图1-1 注册UVa OJ账号
在注册并登录账号之后，你就可以选择题库中的题目开始解题并提交答案了。提交有两种方式，一种是先浏览具体的题目描述界面，单击“Submit”按钮进行提交，另外一种是“Quick Submit”。
先介绍第一种方法。以提交UVa 100 The 3
＋1 Problem为例，首先，选择左侧功能栏中的“Browse Problems”选项，如图1-2所示。
图1-2 选择“Browse Problems”选项
其次，选择“Problem Set Volumes（100…1999）”选项，如图1-3所示。
图1-3 选择“Problem Set Volumes（100…1999）”选项
再次，选择“Volume 1（100-199）”选项，如图1-4所示。
图1-4 选择“Volume 1（100-199）”选项
选择“100 - The 3n＋1 problem”选项，如图1-5所示。
图1-5 选择“100 - The 3n＋1 problem”选项
最后，进入题目描述页面，单击“Submit”按钮，如图1-6所示。
图1-6 提交代码
将解题代码粘贴到输入框中（或者单击“Browser”按钮选择本机上的代码文件上传），单击“Submit”按钮即可，如图1-7所示。
图1-7 选择代码文件并提交
提交成功后，会显示该提交的编号，如图1-8所示。
图1-8 提交编号
第二种提交方法适用于用户已经熟悉了题目描述而且已经编写了题目的解题代码的情形，用户只需选择“Quick Submit”，再填写问题的编号，其他项目与第一种方法的相同，如图1-9所示。
图1-9 Quick Submit方法
在提交以后，就可以通过选择浏览器左侧功能栏中的“My Submissions”选项查看提交结果，如图1-10所示。
图1-10 查看提交结果
在UVa OJ上提交，可能会有以下几种结果。
Accepted（AC）：通过。用户的程序在限定的时间和内存下产生了正确的输出，恭喜该题获得通过！
Wrong Answer（WA）：错误提交。用户的程序产生的输出与参考输出不匹配。
Presentation Error（PE）：格式错误。用户的代码所产生的输出内容是正确的，但是格式有错误。检查输出是否有多余的空格，或者对齐、换行符是否正确。
Compile Error（CE）：编译错误。用户的代码存在语法或其他错误而无法被正确编译。
Runtime Error（RE）：运行时错误。用户的代码在运行过程中出现错误被强制退出。例如，引用了声明范围以外的数组元素，除数为零错误等。
Time Limit Exceeded（TLE）：时间超出限制。用户的代码所采用的算法时间效率不高或者出现无限循环，导致程序运行时间超出限制。
Memory Limit Exceeded（MLE）：内存超出限制。用户的代码内存使用效率不高或者出现无限循环，导致程序使用的内存超出限制。
Output Limit Exceeded（OLE）：输出超出限制。用户的代码产生的输出太长，超出了输出限制。一般是由于存在无限循环而导致输出过长。
Submission Error（SE）：代码提交未成功。在代码提交处理的过程中由于某些错误或提交的数据损坏而导致提交失败。
Restricted Function（RF）：限制使用的函数。某些系统函数在评测中限制使用，用户的代码中包含这些限制使用的函数时会出现该错误。
Can’t Be Judged（CJ）：无法评测。所选择的题目可能不存在测试输入或者测试输出，因此无法进行评测。
In Queue（QU）：评测机繁忙未能对用户的提交进行评测，当评测机空闲时将尽快对用户的提交进行评测。
一般来说，在编程竞赛中比较的是谁能够在有限的时间内解决最多的问题，因此程序只要能够在给定的时限内通过即可，语言的效率并不是第一位的考虑因素。C++具有丰富的库函数以及字符串类，因此推荐使用C++作为编程竞赛的首选语言。如果某些竞赛对语言的运行效率要求非常高，又或者不允许使用C++的库函数，抑或需要自行实现某些基本的数据结构（例如，堆），那么可以考虑使用C语言。
值得一提的是，其他语言由于一些非常便利的特性，如果学有余力，也建议适当掌握。例如，Java中的高精度整数类BigInteger在解决有关大数的问题时就非常有用。同样地，掌握Python也会在某些场景下带来便利。例如，Python本身就直接支持高精度整数的运算。
本节将介绍若干有助于提高学习效率的工具，熟练掌握和应用这些工具可以使大家的学习过程事半功倍。
UVa Arena是一款用于UVa OJ解题的辅助软件，用户可以通过该软件下载整个UVa OJ题库，并且可以从网上数据库更新自己的解题完成情况信息。除此之外，还包括一些诸如保存解题代码、调用编译器编译、代码提交等实用功能。
uHunt是一个跟踪UVa OJ解题情况的网站，用户输入自己在UVa OJ上的用户名即可查看其当前题目的完成情况，还可根据题目的通过率、通过提交数等对题目排序，便于寻找符合自己需求的题目进行训练。
uDebug是专门针对网上各大题库建立的测试数据网站，它包括绝大多数的UVa OJ上题目的测试数据。用户可以先下载测试数据（一般通过复制粘贴的方式），使用自己的解决方案生成输出，然后与网站上已经获得过“Accepted”的程序的输出进行比对，检查是否匹配以发现自己代码的问题。
VirtualBox是一款虚拟机软件，通过该软件可以在Windows操作系统上安装一个“真正”的Linux系统，在此虚拟系统中配置GCC编译器搭建编程环境即可开始UVa OJ解题，便于使用Windows系统但又不愿意安装双系统的用户使用。
Virtual Judge是一个虚拟评测网站，通过该网站可以对各大主要在线评测网站的问题进行间接提交。通过此网站进行提交，能够较为快速地查看提交结果。
洛谷是国内较为知名的奥林匹克竞赛网站，在该网站的题库中，包含了UVa OJ的几乎全部题目，其中有一部分给出了中文翻译，对于英语水平不是很好的解题者较为友好。解题者可以通过洛谷将UVa OJ上注册的账号予以绑定，之后即可使用洛谷的相应接口进行代码远程提交并获得相应评测结果。
[1] 2018年4月，创建UVa OJ的Miguel Ángel Revilla教授不幸去世，而Valladolid大学校方宣布不再继续提供资金以维持UVa OJ的运行，因此UVa OJ有停止运行的可能。不过好消息是，Revilla教授的儿子Miguel Revilla Rodríguez表示愿意继续为UVa OJ的运行做出努力。目前他正在使用Wt框架开发新一版的在线评测系统（读者可以在Github上搜索TheOnlineJudge/ojudge 以了解更多）。乐观地估计，有望在2022年正式上线运行。
