如何更好地食用 UVa OJ

$\Large\textbf{-4 }\textsf{更新日志}$ - **2020.10** 根据评论修改了部分内容。 - **2021.12.10** 美化了排版。 - **2022.01.08~09** 更新了大部分内容。 只要笔者还记得洛谷，就会一直更新（确信 $\Large\textbf{-3 }\textsf{声明}$ 为了保护隐私与更好的展现，更改了部分图片。 $\Large\textbf{-2 }\textsf{一些无聊的统计}$ 从 $\text{Part. 0}$ 开始到 $\text{Part. 5}$ 为止，本文共计 $\color{#c04851}\textbf{2021}$ 字，$3162$ 个字符，$5$ 张配图，$2$ 段代码。 $\Large\textbf{-1 }\textsf{目录}$ 0. 引子 - 0.1 背景 - 0.2 前置工具 1. UVa 官网使用指南与提醒 - 1.1 注册与登录 - 1.2 查找与提交题目 - 1.2.1 位置 - 1.2.2 例子 - 1.3 提醒与警告 2. UVa 辅助网站 - 2.1 洛谷 - 2.2 uDebug - 2.3 vjudge 3. UVa 辅助工具 - 3.1 UVA-Arena - 3.2 UVA Tab Problem Title - 3.3 UVa Tag 4. UVa 配套书籍 - 4.1 《算法竞赛入门经典》，刘汝佳 - 4.2 《C++，挑战编程——程序设计竞赛进阶训练指南》，metaphysis 5. 写在最后 6. 回复 熟悉了内容，我们继续。 $\Large\textbf{0 }\textsf{引子}$ $\large\textsf{0.1 }\textbf{背景}$ UVa OJ，是国外知名在线 OJ。但由于创始人 Miguel Ángel Revilla 教授已于 2018 年 4 月去世，且资金提供方暂停提供维护成本，这个外国网站在国内访问速度极慢~~比 CF 还慢~~。 UVa 本来是一个题目丰富的网站，但由于国内做题者偏少，导致题目难度与考察范围不清楚，给刷题带来了很大困难。 本文通过介绍一些方法，使得在 UVa 刷题变得轻松有趣（迫真 $\large\textsf{0.2 }\textbf{前置工具}$ - 一台电脑和一个能用的浏览器 - 洛谷 - [UVa 官网](https://onlinejudge.org/) Go on。 $\Large\textbf{1 }\textsf{UVa 官网使用指南与提醒}$ $\large\textsf{1.1 }\textbf{注册与登录}$ 稍微看得懂英文的人都会吧。略。 $\large\textsf{1.2 }\textbf{查找与提交题目}$ $\text{1.2.1 }\textbf{位置}$ 在 **[这个网址](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8)** ，有 UVa 的详细题目题单。我们可以看到，里面既有基础题库 1000 题，也有比赛题目收集（如 ACM-ICPC），更有刘汝佳大佬书里的题目。 $\text{1.2.2 }\textbf{例子}$ 以 [UVa10055 Hashmat the Brave Warrior](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=996) 为例。 相信智慧的你们一眼就看出来答案是 $|a-b|$。 $\color{Red}\text{当然，注意看输入格式和输出格式。}$ **这句警告对所有的 UVa 题目均有效，若未遵守这一点，很可能导致你出现奇怪的 $\color{red}\tt{WA}$。**  注意到此时并没有 `0 0` 之类的东西结束输入，所以我们用 `while(scanf("%d%d", &a, &b) == 2)` 即可。 点击右上角的 $\tt Submit$ 按钮即可提交代码进行评测。 UVa 良心网站还会给你发 email（ $\large\textsf{1.3 }\textbf{提醒与警告}$ - 注意题目的输入输出格式，以免造成 WA 惨案。 - 敢于读题，不要为冗长的题目描述所困扰。 - 尽量不要借助题解与他人的帮忙。 以上。 $\Large\textbf{2 }\textsf{UVa 辅助网站}$ $\large\textsf{2.1 }\textbf{洛谷}$ 当然应该是洛谷啦，洛谷在远古时期爬取了 UVa 上的大部分题目，RMJ 让评测轻而易举。 UPD：并不是全部，例如 UVa11303 kewl Texting，洛谷上就没有。 还应该指出的是，在洛谷上的 UVa 题面是支离破碎的 pdf 题面，点击 PDF 的链接会发现无法访问，且一般情况下都没有提交翻译的按钮，希望什么时候能 update 一下。 UPD：pdf 链接可以访问，点击PDF的链接后点击“高级”，然后点击“继续访问 uva.onlinejudge.org(不安全)”即可访问。感谢 @[东方澂 ](https://www.luogu.com.cn/user/161223) 及时指出了这一点。 **本文默认使用洛谷提交。** $\large\textsf{2.2 }\text{uDebug}$ **[uDebug 官网](https://www.udebug.com/)** 这应该是一个比较官方的网站，毕竟在 UVa 的题目界面，$\tt Submit$ 按钮下面就是它，$\tt Debug$ 按钮，直达 uDebug。  在首页可以看到，uDebug 支持 $10$ 个 OJ，有 $14119$ 道题目。 （虽然这些 OJ 除了 UVa 笔者一个都没听过） 以 [UVa11582 Colossal Fibonacci Numbers!](/problem/UVA11582) 为例。 先上 AC 代码： ```cpp //UVA11582 #include <cstdio> #include <cstring> using namespace std; typedef unsigned long long ULL; ULL a, b; int n, mod; int f[1000010] = {0, 1, 1}; int qpow(ULL a, ULL b, int mod){ a %= mod; ULL ans = 1, base = a; while(b > 0){ if(b & 1){ ans *= base; ans %= mod; } base *= base; base %= mod; b >>= 1; } return ans % mod; } void Work(){ scanf("%llu%llu%d", &a, &b, &n); if(n == 1 || a == 0){ printf("0\n"); return; } for(int i = 3 ; i <= n * n + 4 ; i ++){ f[i] = (f[i - 1] + f[i - 2]) % n; if(f[i] == 1 && f[i - 1] == 1){ mod = i - 2; break; } } printf("%d\n", f[qpow(a, b, mod)]); } int main(){ int t; scanf("%d", &t); while(t--) Work(); return 0; } ``` 第一发交的时候，笔者把定义 $f$ 数组初值的 $\{0,1,1\}$ 写成了 $\{1,1,1\}$，导致 WA。 然后笔者访问 uDebug，找到该题。  地址：[Link](https://www.udebug.com/UVa/11582)。 然后笔者把 $\tt Select\ Input$ 里的 3 个输入挨个试一遍。最后在 [Anjupiter](https://www.udebug.com/Anjupiter) 大佬的数据里找到了 Hack 数据： ``` 1 30 79 217 ``` 笔者的输出是 $\tt1$，标准输出是 $\tt0$。 然后一发调试，就 AC 了。 $\large\textsf{2.3 }\text{vjudge}$ **[网址](https://vjudge.net/)** 虚拟评测网站，和洛谷 RMJ 类似，网上很多人说这是个稳定的好网站，但笔者从来没进去过，可能有点用吧。所以就放在这里。 UPD：@[昒昕](/user/84132) 指出需要挂点东西才能进入，但笔者于 2022 年 6 月 8 日失败。另外，可用的镜像站：<https://vjudge.csgrandeur.cn/>。 $\Large\textbf{3 }\textsf{UVa 辅助工具}$ $\large\textsf{3.1 }\text{UVA-Arena}$ 这是一个专门面对 UVa 的软件，~~不过现在应该已经炸了~~。 UPD：没炸，在 GitHub 上发布的 ver 1.9，完美解决了之前存在的大部分问题，现在没有任何问题。感谢 @[tiger2005](https://www.luogu.com.cn/user/60864) 指出了这一点。 **[下载地址](https://github.com/dipu-bd/UVA-Arena)** ，下滑找到 $\texttt{Download v1.9}$ 点击即可。 然后经过一发操作后，你就能在软件左边的题目列表找到你想看的题目并下载 pdf，实现在该软件上写代码。 你甚至可以一次性下载完所有题目，没网也能轻松看题目。 $\large\textsf{3.2 }\text{UVA Tab Problem Title}$ **[安装地址](https://greasyfork.org/zh-CN/scripts/28844-uva-tab-problem-title)** 如果你是在 UVa 本站刷题，那么这个脚本对你应该会有帮助。 当你打开一系列 UVa 题目后，你会发现标签页上全是清一色的 Online Judge，毫无分辨性。 所以此时就需要这个脚本。 需要说明的是，这个脚本由于网站的更新，已无法正常使用，所以只要在油猴上添加以下代码即可： ```javascript // ==UserScript== // @name UVA Tab Problem Title // @description Put problem name in as title when viewing a problem on UVA // @include https://onlinejudge.org/* // @version 1 // @grant none // ==/UserScript== var probname = document.getElementById('col3_content_wrapper').getElementsByTagName('h3') [0].innerText; if (probname !== undefined) { document.title = probname; } ``` 看一下使用前后对比图：  $\large\textsf{3.3 }\text{UVa Tag}$ **[UVa Tag 项目地址](https://github.com/Sept0913/UVa-Tag)** 夹带私货预警。 就是个给 UVa 里面题目按算法分类的项目。 虽然这个还没火起来，还没有什么生机，但是会有成果的（确信 食用方法在 `README.md` 里都有了，众人拾柴火焰高（ $\Large\textbf{4 }\textsf{UVa 配套书籍}$ 如果你确定要以 UVa 题库为基础进行提升，那么可以以以下书籍为参考进行学习。 $\large\textsf{4.1 }\textbf{《算法竞赛入门经典》，\textit{刘汝佳}}$ 建议有一定基础的 OIer 阅读，当然笔者并没有看过这本书（ 要阅读此书，前提是有 CSP-J 一等水平。 本书的例题是建立在 UVa 的基础上的，所以推荐本书作为 UVa 题库的配套工具。 当然深基肯定更好（确信 $\large\textsf{4.2 }\textbf{《C++，挑战编程——程序设计竞赛进阶训练指南》，\textit{metaphysis}}$ >感谢[作者](/user/333388)本人对笔者的帮助与支持。 **[电子书链接](https://blog.csdn.net/metaphysis/article/details/90288252)** 本书笔者现在正在使用，同样建议**至少有 CSP-J 一等水平的 OIer** 使用，部分章节建议**省选水平 OIer** 使用。 全书细致地讲解了 ACM / OI 等算法竞赛涉及到的知识点，同样以 UVa 题库为基础。作者刷遍了 UVa 题库中的 $2156$ 题（共 $4965$ 道题），对 UVa 的题目有着细致的理解与完美的分类。 如果学有余力的话，可以参考阅读。 以本书 2.12 章并查集为例，在章末给出了如下习题：  共 $6$ 题，这些题目在洛谷上的情况如下（数据截止至 2021 年 8 月 19 日）： 1. [UVA10583](/problem/UVA10583)：板子题，非常热闹，有难度评分，也有算法标签。 2. [UVA10608](/problem/UVA10608)：提交量 24，通过量 7，无难度评分，无标签。 3. [UVA10685](/problem/UVA10685)：提交量与通过量均为 1，无难度评分，无标签。 4. [UVA10503](/problem/UVA10503)：提交量 33，通过量 10，有难度评分，无标签。 5. [UVA1160](/problem/UVA1160)：较为热闹，有难度评分，无标签。 6. [UVA11987](/problem/UVA11987)：较为热闹，有难度评分，无标签。 由此可见，如果没有这样系统的分类，许多 UVa 的题目便会石沉大海，终究还是没多少人发现。 $\Large\textbf{5 }\textsf{写在最后}$ UVa 的题目还只是一部分，CF，AT，洛谷上的题目，多为新题巧题思维题，也同样具有很高的训练价值。我们不能忽视了这方面的训练。 愿你我均能乘风破浪，在 OI 的路上勇往直前。 $\Large\textbf{6 }\textsf{回复}$ 数据更新至 $\textit{2022.01.09}$。 1. $\textsf{sto Sept orz}$ 别假（恼 2. $\small\text{UVA-Arena }\textsf{是不是挂了，安装下来一直无法连接}\text{ UVA}$ $\text{By}$ [$\textbf{\textit{distant\_skys}}$](/user/392380) ~~qs，感谢指正，已在文章中指出。~~ **请使用最新版的 UVA Arena。** 3. $\small{\text{UVA }\textsf{现在是不是挂了，无法访问？}}$ $\text{By}$ [$\textbf{\textit{Xiaohuba}}$](/user/356003) **并不，只是访问不稳定罢了。** 4. $\small{\textsf{不妨想想为什么会这样，如果}\text{ uva }\textsf{上真的有很多好题还会没人做吗（}}$ $\text{By}$ [$\textbf{\textit{rxjdasiwzl}}$](/user/96446) **这只是很小一方面的因素罢，事实上格式过于繁琐与题目描述不清占了很大比重。**