PrevNext

Resources
IUSACO

本模块以此为基础

Python

类型intfloatboolstr
说明任意大小的整数双精度(64 位)IEEE 754 浮点数真/假值字符串
取值任意整数-1.7E+308+1.7E+308true/false任意长度文本

比赛中主要使用几类数据类型:整数、浮点数、布尔值、字符和字符串。如果你 已经熟悉所使用的语言,这一部分应当主要是复习。

普通的32 位整数(C++ 和 Java 中的 int)取值范围为 2147483648-2\,147\,483\,64821474836472\,147\,483\,647,约为 ±2109\pm 2 \cdot 10^9

部分题目要求使用64 位整数(C++ 的 long long、Java 的 long),而非 32 位 int。64 位整数不易溢出,其取值范围为 9223372036854775808-9\,223\,372\,036\,854\,775\,80892233720368547758079\,223\,372\,036\,854\,775\,807, 约为 ±9×1018\pm 9 \times 10^{18}。Python 中的 int 大小不受固定字长限制。

USACO 题面有时(但并非总是)会像 Haircut 一样给出如下警告:

请注意,本题涉及的整数较大,可能需要使用 64 位整数类型(例如 C/C++ 中的 long long)。

比赛通常保证 64 位整数足够使用,因此在低组别中可以考虑统一用 64 位整数代替 32 位整数。但在更高组别、时间或内存限制严格时不应盲目这样做。还要注意, Java 访问数组下标时需要把 long 转回 int

此外还有 16 位整数(C++ 和 Java 中的 short),但节省的内存通常可以忽略, 所以很少有用。无符号整数(unsigned intunsigned long long 等)也存在, 虽不常用,但其正数范围扩大一倍有时能决定是否溢出。

浮点数用于存储小数。由于计算机的二进制结构只能以有限精度表示小数,浮点数 并不精确。因此应当预期它们存在微小误差,通常不应使用 == 比较两个浮点数 是否完全相等。

比赛题通常会允许浮点误差:检查输出与标准答案的绝对误差相对误差是否 小于 ϵ=109\epsilon=10^{-9} 等较小常数。

  • 若输出为 xx、答案为 yy,绝对误差为 xy|x-y|
  • 若输出为 xx、答案为 yy,相对误差为 xyy\frac{|x-y|}{|y|}

USACO 通常要求唯一的精确输出,因此做法不同。必须使用浮点数时,题目可能要求: “输出恰好收到一个已接受邀请的最大概率乘以 10610^6 后向下取整的结果。”例如 Cow Dating

布尔变量只有 truefalse 两种状态,常用于标记某个过程是否完成; 布尔数组则可标记算法中的哪些部分已经完成。布尔值通常占 1 字节(8 位),而非 1 位,其余 7 位被浪费。为节省内存,可以使用位集(C++ 的 std::bitset、 Java 的 BitSet)。遗憾的是,Python 没有对应的内置位集。

字符变量表示单个字符。访问字符串中某个下标时会得到字符。ASCII 标准为每个 字符分配对应整数,因此可以对字符做算术运算。例如 C++ 的 cout << ('f' - 'a'); 和 Java 的 System.out.print('f' - 'a'); 都会 输出 5。Java 字符为 16 位,C/C++ 字符为 8 位。

字符串本质上是字符数组。可以方便地访问指定下标的字符或截取子串(Java 中对应 charAt()substring())。

Module Progress:

PrevNext