PrevNext

USACO 支持哪些语言？

USACO 支持的语言中，最流行的是 C++17、Java 和 Python 3。USACO 也支持 C，但它本质上可以看作功能更少的 C++，而且没有竞赛中经常使用的内置数据结构。

C++11 和 C++17 有什么区别？

如果你刚刚入门，大概还不会用到 C++17 特有的功能，所以用 C++11 或 C++17 提交都可以。要了解 C++11、C++14 和 C++17 引入的功能，请查看以下链接。

Python 2 和 Python 3 有什么区别？

如下方链接所述，Python 2 和 Python 3 之间存在许多区别。Python 3 更新，而且绝大多数 USACO 参赛者都选择 Python 3，而非 Python 2。

我应该从哪种语言开始？

一般而言，我们建议：

  • 如果你不会上述任何一种语言，最好从 C++ 开始。C++ 用户不太需要担心解法仅仅因为常数较大而慢到无法通过（更多信息请参阅下一节）。此外，目前有些模块尚未提供 Java 和 Python 支持。
  • 如果你已经会其中一种或多种语言，可以先使用自己最熟悉的语言——以后随时都能转向 C++。

每道题都能用每种语言通过吗？

C++ 通常比 Java 快，而 Java 通常又比 Python 快。虽然在 USACO 中，Python 和 Java 的时限是 C++ 的两倍，但其他大多数网站（如 Codeforces、CSES）并非如此。即使放宽了时限，Python 和 Java 有时仍难以通过。

  • 对于青铜组和白银组题目，USACO 工作人员有时会确保 C++、Python 和 Java 都能获得满分，但这并无保证。例如，这道近期的青铜组题目就不要求 Python 能够通过。
  • Python 的速度不足以通过大多数黄金组和铂金组题目。
  • 我们还没有发现绝对无法用 Java 通过的 USACO 题目，但确实存在这样的情况：把官方 C++ 代码直接翻译成等价的 Java 代码后，速度不足以获得满分。

示例——Wormhole Sort（USACO 2020 年 1 月白银组）

题解中的 Java 解法需要超过 3 秒才能运行完毕（时限为 4 秒）。

import java.io.*;
import java.util.*;
public class wormsort {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("wormsort.in"));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		loc = new int[n];
		component = new int[n];

与之相当的 C++ 解法运行时间不到 800 毫秒：

#include <bits/stdc++.h>
using namespace std;


int n, m;
vector<int> loc, lhs, rhs, weight;
vector<vector<int>> edges;
vector<int> component;


void dfs(int curr, int label) {
	if (component[curr] == label) return;

与之相当的 Python 解法只能通过前五个测试点：

import sys


sys.setrecursionlimit(1000000)


sys.stdin = open("wormsort.in", "r")
sys.stdout = open("wormsort.out", "w")


n, m = map(int, input().split())
loc = [0] * n
component = [0] * n

可以对这种方法进行优化，使它通过所有测试点。运行时间约为 3.8 秒。

def main():
	f = open("wormsort.in", "rb")
	n, m = map(int, f.readline().split())
	loc = [*map(int, f.readline().split())]
	edges = [[] for _ in range(n)]
	weights = []


	def valid(loc, minW):
		component = [-1] * n
		numcomps = 0

最后，下面的方法使用了并查集（黄金组知识点），运行时间约为 1 秒：

# Author: Nicolas Hsu


file = open("wormsort.in")
N, M = map(int, file.readline().split())
P = tuple(map(int, ("0 " + file.readline()).split()))
W = [tuple(map(int, file.readline().split())) for i in range(M)]
W.sort(key=lambda w: -w[2])


par = list(range(N + 1))

我应该掌握哪些知识？

在继续学习本指南的青铜组内容之前，你应当至少掌握上述语言中的一种。关于应掌握内容的详细列表，请阅读“预备知识”模块。

Module Progress:

PrevNext