ACM/ICPC 竞赛笔记

ACM/ICPC 概览

Online Judge (OJ)

返回结果	含义
Accept (AC)	答案正确，被系统接受
Wrong Answer (WA)	答案错误
Runtime Error (RE)	运行时错误
Compile Error (CE)	编译错误
Presentation Error (PE)	答案格式错误
Time Limit Exceeded (TLE)	超时
Memory Limit Exceeded (MLE)	超内存
Output Limit Exceeded (OLE)	超输出
Restrict Function Call (RFC)	使用不允许的API
System Error	系统错误
Queuing	排队等待系统测评
Judging	评测中

基本输入

1. 输入不说明有多少个 Input Block, 以 EOF 为结束标志。

   • C 版本

     while(scanf("%d %d", &a, &b) != EOF) {
        // 在这处理数据
     }

   • C++ 版本

     while(cin >> a >> b) {
        // 在这处理数据
     } 

2. 输入说明了有多少个

   int n;
   cin >> n;
   while(--n) {
      // 在这处理数据
   }

确保代码效率

1. 除了循环控制变量以外，变量全部和标准 C 一样先声明好再使用，能赋初值的赋初值初始化

2. 数组不要反复开，用的时候直接用 memset(array_pointer, 0, sizeof(array_pointer)); 清空数组

3. 不混用 C 和 C++ 的输入输出流时，直接禁用运行时流同步

   ios::sync_with_stdio(false);

4. 禁用流绑定

   std::cin.tie(nullptr);

基本算法

字符串

C 标准库函数

头文件：#include <string.h> 或 #include <cstring>

赋值

// 函数原型 strcpy(destination, str);
char str[40];
strcpy(str, "C Programming Language");
// 把字符串赋给 str 字符数组

将字符串复制到字符数组中。如果字符串的长度小于数组的长度，其余部分用 '\0' 填补。返回处理完成的字符串。

// 函数原型 strncpy(destination, str, length);
char str[20]; 
strcpy(str, "C Programming Language", 13);
// 把字符串至多前 n 个字符的子串赋给 str 字符数组

将字符串中至多前 n 个字符，复制到字符数组中。如果字符串的长度小于数组的长度，其余部分用 '\0' 填补。返回处理完成的字符串。（有点类似于 Python 中对 str 类型取 slice：str = string[:n]）

长度

// 函数原型 strlen(str);
strlen("Hello"); // 结果是 5（不是 6）

返回字符串的有效字符数（除空字符以外的的字符个数）。

⚠ 注意

strlen() 和 sizeof() 是有区别的，sizeof("Hello") 的值是 6。

C++ 标准库函数

头文件：#include <string>

子串匹配

排序

C++ 标准库函数

头文件：#include <algorithm>

排序函数：std::sort(first, last, compare_function)

二分查找：

std::upper_bound

std::lower_bound

高精度

高精度加法

flowchart TB;
input(输入字符串)-->reverse(倒序字符串, 使得个位对齐方便计算)-->add(逐位相加)-->carry(逐位处理进位问题)-->highest(根据最高位处理前导 0 问题)

高精度减法

高精度乘法

高精度除法

杂谈

无穷大的表示问题

C++ 中整型 int 最大能表示的值是 \(2^{31} - 1\) 换成十六进制就是 0x7fffffff，除以 2 后即得到 0x3fffffff，也是 \(10^9\) 这个量级的了，基本上不大可能会超过这个值。为了初始化的方便，也就是调用 memset 这个函数的时候写起来方便，将 4 个字节全部置为 0x3f，也就是用 0x3f3f3f3f 这个值来近似地表示无穷大。

位操作

位操作	意义
(number >> x) & 1	检查第 \(x\) 位
number \| (1 << x)	设置第 \(x\) 位
number ^ (1 << x)	翻转第 \(x\) 位
number & ~(1 << x)	清除第 \(x\) 位

Brian Kernighan 算法

template<typename NumberLikeType, 
         typename enable_if<is_integral<NumberLikeType>::value, int>::type = 0>
unsigned setBitsCount(NumberLikeType number) {
    unsigned count = 0;
    while(number) {
        number = number & (number - 1);
        ++count;
    }
    return count;
}