如何更好地食用 UVa OJ
CSP_Sept
·
2021-07-31 16:46:19
·
科技·工程
\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.1 背景
0.2 前置工具
UVa 官网使用指南与提醒
1.1 注册与登录
1.2 查找与提交题目
1.2.1 位置
1.2.2 例子
1.3 提醒与警告
UVa 辅助网站
2.1 洛谷
2.2 uDebug
2.3 vjudge
UVa 辅助工具
3.1 UVA-Arena
3.2 UVA Tab Problem Title
3.3 UVa Tag
UVa 配套书籍
4.1 《算法竞赛入门经典》，刘汝佳
4.2 《C++，挑战编程——程序设计竞赛进阶训练指南》，metaphysis
写在最后
回复
熟悉了内容，我们继续。
\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 官网
Go on。
\Large\textbf{1 }\textsf{UVa 官网使用指南与提醒}
\large\textsf{1.1 }\textbf{注册与登录}
稍微看得懂英文的人都会吧。略。
\large\textsf{1.2 }\textbf{查找与提交题目}
\text{1.2.1 }\textbf{位置}
在 这个网址 ，有 UVa 的详细题目题单。我们可以看到，里面既有基础题库 1000 题，也有比赛题目收集（如 ACM-ICPC），更有刘汝佳大佬书里的题目。
\text{1.2.2 }\textbf{例子}
以 UVa10055 Hashmat the Brave Warrior 为例。
相信智慧的你们一眼就看出来答案是 |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(不安全)”即可访问。感谢 @东方澂
及时指出了这一点。
本文默认使用洛谷提交。
\large\textsf{2.2 }\text{uDebug}
uDebug 官网
这应该是一个比较官方的网站，毕竟在 UVa 的题目界面，\tt Submit 按钮下面就是它，\tt Debug 按钮，直达 uDebug。
在首页可以看到，uDebug 支持 10 个 OJ，有 14119 道题目。
（虽然这些 OJ 除了 UVa 笔者一个都没听过）
以 UVa11582 Colossal Fibonacci Numbers! 为例。
先上 AC 代码：
//UVA11582
#include
#include
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。
然后笔者把 \tt Select\ Input 里的 3 个输入挨个试一遍。最后在 Anjupiter 大佬的数据里找到了 Hack 数据：
1
30 79 217
笔者的输出是 \tt1，标准输出是 \tt0。
然后一发调试，就 AC 了。
\large\textsf{2.3 }\text{vjudge}
网址
虚拟评测网站，和洛谷 RMJ 类似，网上很多人说这是个稳定的好网站，但笔者从来没进去过，可能有点用吧。所以就放在这里。
UPD：@昒昕 指出需要挂点东西才能进入，但笔者于 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 指出了这一点。
下载地址 ，下滑找到 \texttt{Download v1.9} 点击即可。
然后经过一发操作后，你就能在软件左边的题目列表找到你想看的题目并下载 pdf，实现在该软件上写代码。
你甚至可以一次性下载完所有题目，没网也能轻松看题目。
\large\textsf{3.2 }\text{UVA Tab Problem Title}
安装地址
如果你是在 UVa 本站刷题，那么这个脚本对你应该会有帮助。
当你打开一系列 UVa 题目后，你会发现标签页上全是清一色的 Online Judge，毫无分辨性。
所以此时就需要这个脚本。
需要说明的是，这个脚本由于网站的更新，已无法正常使用，所以只要在油猴上添加以下代码即可：
// ==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 项目地址
夹带私货预警。
就是个给 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}}
感谢作者本人对笔者的帮助与支持。
电子书链接
本书笔者现在正在使用，同样建议至少有 CSP-J 一等水平的 OIer 使用，部分章节建议省选水平 OIer 使用。
全书细致地讲解了 ACM / OI 等算法竞赛涉及到的知识点，同样以 UVa 题库为基础。作者刷遍了 UVa 题库中的 2156 题（共 4965 道题），对 UVa 的题目有着细致的理解与完美的分类。
如果学有余力的话，可以参考阅读。
以本书 2.12 章并查集为例，在章末给出了如下习题：
共 6 题，这些题目在洛谷上的情况如下（数据截止至 2021 年 8 月 19 日）：
UVA10583：板子题，非常热闹，有难度评分，也有算法标签。
UVA10608：提交量 24，通过量 7，无难度评分，无标签。
UVA10685：提交量与通过量均为 1，无难度评分，无标签。
UVA10503：提交量 33，通过量 10，有难度评分，无标签。
UVA1160：较为热闹，有难度评分，无标签。
UVA11987：较为热闹，有难度评分，无标签。
由此可见，如果没有这样系统的分类，许多 UVa 的题目便会石沉大海，终究还是没多少人发现。
\Large\textbf{5 }\textsf{写在最后}
UVa 的题目还只是一部分，CF，AT，洛谷上的题目，多为新题巧题思维题，也同样具有很高的训练价值。我们不能忽视了这方面的训练。
愿你我均能乘风破浪，在 OI 的路上勇往直前。
\Large\textbf{6 }\textsf{回复}
数据更新至 \textit{2022.01.09}。
\textsf{sto Sept orz}
别假（恼
\small\text{UVA-Arena }\textsf{是不是挂了，安装下来一直无法连接}\text{ UVA}
~~qs，感谢指正，已在文章中指出。~~
**请使用最新版的 UVA Arena。**
\small{\text{UVA }\textsf{现在是不是挂了，无法访问？}}
**并不，只是访问不稳定罢了。**
\small{\textsf{不妨想想为什么会这样，如果}\text{ uva }\textsf{上真的有很多好题还会没人做吗（}}
**这只是很小一方面的因素罢，事实上格式过于繁琐与题目描述不清占了很大比重。**