GESP C++ 赛前知识手册

目录

通用考场规则

读题

  • 圈出“正确 / 错误”“能 / 不能”“一定 / 可能”“至少 / 恰好”。
  • 判断题要找反例；只要有一个反例，“一定”“所有”“总是”就不成立。
  • 代码题先看问的是：值、类型、输出、复杂度，还是算法思想。
  • 编程题先看输入输出格式，不要急着写代码。

标准代码骨架

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    return 0;
}

编程题三步

  1. 输入：几行？几个数？有没有数组、字符串、矩阵、图？
  2. 处理：求和、计数、排序、模拟、搜索、DP、最短路？
  3. 输出：一个数、一行、多行、图形？有没有空格、换行、提示语？

考试输出不要写提示语，例如不要输出 please input。

一级：基础语句和基础运算

输入输出语句

int a;
cin >> a;
cout << a << '\n';
  • cin 读入数据。
  • cout 输出数据。
  • cout << a << b; 中间不会自动加空格。
  • '\n' 表示换行。

变量和常量

  • int：整数。
  • double：小数。
  • char：单个字符，例如 'A'。
  • string：字符串，例如 "ABC"。
  • bool：真假，输出常是 0 或 1。

易混点：

  • 3 是整数。
  • 3.0 是小数。
  • '3' 是字符。
  • "3" 是字符串。
  • C++ 区分大小写，PI 和 pi 是两个名字。

条件判断语句

if (x > 0) {
    cout << "positive";
} else {
    cout << "not positive";
}

常见写法：

  • 判断相等：a == b
  • 判断不等：a != b
  • 多条件同时满足：a > 0 && b > 0
  • 多条件满足一个即可：a > 0 || b > 0

循环语句

for (int i = 1; i <= n; i++) {
    cout << i << '\n';
}

while (n > 0) {
    n--;
}
  • break：跳出循环。
  • continue：跳过本轮，进入下一轮。
  • 手算循环时看四件事：初值、条件、循环体、变化量。

运算

  • 算术运算：+ - * / %
  • 关系运算：< <= > >= == !=
  • 逻辑运算：&& || !
  • 自增自减：++ --
  • 三目运算：条件 ? A : B
  • 位运算初步：& | ^ ~ << >>

常考：

  • int / int 是整数除法，37 / 4 == 9。
  • % 是余数，x % 2 == 0 表示偶数。
  • a += b 等价于 a = a + b。
  • C++ 没有乘方运算符 **。

二级：编码、类型转换和嵌套结构

ASCII 编码

常见编码：

  • '0' 是 48。
  • 'A' 是 65。
  • 'a' 是 97。

连续规律：

char c = 'C';
int x = c - 'A'; // 2

判断字符：

if ('0' <= c && c <= '9') { }
if ('A' <= c && c <= 'Z') { }
if ('a' <= c && c <= 'z') { }

大小写转换：

char c = 'd';
char upper = c - 'a' + 'A'; // 'D'

类型转换

强制类型转换：

int x = (int)3.9; // 3

隐式类型转换：

double x = 3 + 0.5; // 3.5

常见坑：

  • int / int 先做整数除法，再赋给 double 也已经丢掉小数。
  • sqrt(9.0) 的值是 3，但结果类型是浮点。

嵌套条件和嵌套循环

嵌套条件：

if (a > 0) {
    if (b > 0) {
        cout << "both positive";
    }
}

嵌套循环：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        cout << "*";
    }
    cout << '\n';
}

图形题口诀：外层控制行，内层控制列，每个格子判断输出什么。

常用函数

#include <cmath>
#include <algorithm>
  • abs(x)：绝对值。
  • sqrt(x)：平方根。
  • max(a, b)：最大值。
  • min(a, b)：最小值。
  • rand()：随机数。
  • srand(seed)：设置随机种子。

三级：数组、字符串、进制和位运算

一维数组

int a[100];
for (int i = 0; i < n; i++) {
    cin >> a[i];
}
  • 下标从 0 开始。
  • 长度为 n，最后一个下标是 n - 1。
  • 不要访问 a[n]。

常见题型：

  • 求和、计数、最大最小。
  • 找某个数是否出现。
  • 统计出现次数。

字符串

string s;
cin >> s;

常用：

  • s.size()：长度。
  • s[i]：第 i 个字符。
  • s.find(t)：查找。
  • s.substr(pos, len)：截取。
  • s + t：拼接。

常见应用：

  • 大小写转换。
  • 字符串搜索。
  • 分割字符串。
  • 替换字符或子串。
  • 判断回文。

字符数组：

char str[] = "Hello";

sizeof(str) 是 6，因为末尾有 '\0'；可见字符个数是 5。

原码、反码、补码

正数：原码、反码、补码相同。
负数补码：

  1. 写出正数的二进制。
  2. 按位取反。
  3. 加 1。

例子：8 位下 -1 的补码是 11111111。

进制转换

二进制转十进制：

1011(2) = 1*8 + 0*4 + 1*2 + 1 = 11

十进制转二进制：不断除以 2，记录余数，倒着读。

十六进制：

  • 0xA = 10
  • 0xF = 15
  • 0x10 = 16

位运算

  • &：两个都是 1 才是 1。
  • |：有一个是 1 就是 1。
  • ~：按位取反。
  • ^：相同为 0，不同为 1。
  • <<：左移，对非负整数常相当于乘 2。
  • >>：右移，对非负整数常相当于除 2。

常用结论：

  • x & 1 判断奇偶。
  • x ^ k ^ k == x。
  • 1 << k 在不溢出时表示 2^k。

四级：指针、多维数组、结构体、函数和排序

指针

int x = 10;
int* p = &x;
cout << *p;
  • &x 是 x 的地址。
  • p 保存地址。
  • *p 是指向的值。
  • 空指针常写 nullptr。
  • 指针自己也有地址。

多维数组

int a[10][10];

二维数组常用于矩阵、地图、棋盘。

遍历：

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        cin >> a[i][j];

结构体

struct Student {
    string name;
    int score;
};

结构体用于把多个属性放在一起。

函数

int add(int a, int b) {
    return a + b;
}
  • 参数：传入函数的数据。
  • 返回值：函数算出的结果。
  • void：没有返回值。

递推

从已知的小状态一步一步推出大状态。

f[1] = 1;
f[2] = 1;
for (int i = 3; i <= n; i++) {
    f[i] = f[i - 1] + f[i - 2];
}

简单排序

冒泡排序：相邻比较，大的往后冒。
插入排序：把当前数插到前面有序区。
选择排序：每轮选一个最小值放前面。

复杂度通常是 O(n^2)。

sort(a, a + n);
sort(v.begin(), v.end());

自定义排序：

sort(v.begin(), v.end(), [](int x, int y) {
    return x > y;
});

比较函数只回答：谁应该排前面。

五级：链表、数论、高精度、二分、递归、分治和贪心

链表

struct Node {
    int val;
    Node* next;
};
  • 单链表：每个节点指向下一个节点。
  • 双向链表：有 next 和 prev。
  • 循环链表：尾节点指回头节点。

链表题先画箭头，改指针时防止断链。

素数与合数

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

最大公因数和最小公倍数

欧几里得算法：

int gcd(int a, int b) {
    while (b) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

最小公倍数：

lcm(a, b) = a / gcd(a, b) * b

同余与模运算

如果 a % m == b % m，就说 a 和 b 在模 m 意义下同余。

常用：

  • 判断奇偶：x % 2
  • 判断倍数：x % k == 0
  • 防止大数：每一步都 % mod

质因数分解和唯一分解定理

任何大于 1 的整数，都可以唯一分解成若干质数的乘积。

例如：

60 = 2 * 2 * 3 * 5

筛法

埃氏筛：把每个素数的倍数划掉。
线性筛：每个合数尽量只被最小质因数筛一次。

高精度

数字超过 long long 时，用字符串或数组存每一位。

  • 加法：低位到高位，加进位。
  • 减法：处理借位。
  • 乘法：模拟竖式。
  • 除法：模拟长除法。

二分

适合有序或有单调性的题。

int l = 0, r = n - 1;
while (l <= r) {
    int mid = (l + r) / 2;
    if (a[mid] < x) l = mid + 1;
    else r = mid - 1;
}

复杂度：O(log n)。

递归

递归必须有：

  1. 终止条件。
  2. 规模变小。
  3. 返回或合并答案。
int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

分治

把大问题拆成小问题，解决后合并。
典型：归并排序、快速排序、二分。

贪心

每一步选择当前最优。
常见做法：先排序，再按规则选择。
贪心要能保证局部最优能推出全局最优。

六级：栈队列、树、搜索和简单动态规划

栈

后进先出。

stack<int> st;
st.push(x);
st.top();
st.pop();

常见：括号匹配、表达式、递归过程。

队列

先进先出。

queue<int> q;
q.push(x);
q.front();
q.pop();

常见：BFS。

循环队列

用数组和两个指针 head、tail 模拟队列，走到末尾后回到开头。

树

基本概念：

  • 根、父亲、孩子、兄弟、叶子。
  • 深度：从根往下数。
  • 高度：往最深叶子走的长度。

二叉树遍历：

  • 前序：根、左、右。
  • 中序：左、根、右。
  • 后序：左、右、根。
  • 层序：一层一层，用队列。

完全二叉树

除最后一层外都满，最后一层从左到右排列。

二叉排序树

也叫二叉搜索树。

  • 左子树都小于根。
  • 右子树都大于根。
  • 中序遍历得到有序序列。

哈夫曼树和哈夫曼码

  • 权值小的先合并。
  • 常用于压缩编码。
  • 等权时合并顺序不同，编码可能不唯一。

格雷码

相邻两个编码只有一位不同。

搜索

DFS：一条路走到底，再回退。
BFS：一层一层扩展，常用于每步代价相同的最少步数。
二叉树搜索：根据树的结构递归或循环查找。

简单动态规划

一维 DP：

dp[i] = max(dp[i], dp[i - w] + value);

简单背包：

  • 物品只能选一次：01 背包。
  • 物品可以选多次：完全背包。

七级：图、复杂动态规划、数学函数和哈希

图的基本概念

  • 点、边。
  • 有向图、无向图。
  • 带权图、无权图。
  • 连通、路径、环。

存图：

  • 邻接矩阵：适合点少。
  • 邻接表：适合边少。

图上广搜和深搜

BFS：

  • 用队列。
  • 一层一层走。
  • 常用于无权图或每步代价相同的最少步数。

DFS：

  • 用递归或栈。
  • 一条路走到底。
  • 常用于连通块、回溯。

泛洪算法：

  • 从一个格子向周围扩散。
  • 常用于地图连通区域。

复杂动态规划

二维 DP：

dp[i][j]

常见：网格、背包、LCS。

区间 DP：

dp[l][r] = min(dp[l][k] + dp[k+1][r] + cost);

常见：石子合并、区间合并。

滚动数组：

  • 只保留当前行和上一行。
  • 用来节省空间。

LIS：最长上升子序列。
LCS：最长公共子序列。

数学库函数

  • sin(x)、cos(x)、tan(x)：三角函数，参数是弧度。
  • log(x)：自然对数。
  • log10(x)：十进制对数。
  • exp(x)：指数函数。

哈希表

unordered_map<string, int> mp;
unordered_set<int> st;

用途：

  • 快速判断是否出现。
  • 统计次数。
  • 建立映射关系。

平均复杂度接近 O(1)，最坏可能退化。

八级：组合数学、倍增、最短路、最小生成树和复杂度

加法原理和乘法原理

分情况选择：用加法。
连续独立选择：用乘法。

例子：3 件上衣、4 条裤子，搭配数是 3 * 4 = 12。

排列组合

  • 排列：有顺序。
  • 组合：无顺序。
  • 重复元素排列要除以相同元素的阶乘。

杨辉三角

从第 0 行开始数，第 n 行数字和是 2^n；从第 1 行开始数，第 n 行数字和是 2^(n-1)。
每个数等于上一行相邻两个数之和。

方程和面积

常见公式：

  • 长方形面积：a * b
  • 三角形面积：底 * 高 / 2
  • 圆面积：pi * r * r

倍增法

每次跳 1, 2, 4, 8... 步。
常见：快速幂、树上跳祖先、区间查询。

快速幂：

long long qpow(long long a, long long b, long long mod) {
    long long ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

最短路

Dijkstra：

  • 单源最短路。
  • 边权不能为负。
  • 用优先队列优化常见复杂度 O((V+E)logV)。

Floyd：

  • 所有点对最短路。
  • 三重循环。
  • 复杂度 O(n^3)。

最小生成树

只用于无向连通图。

Prim：

  • 从一个点开始。
  • 每次加入离当前集合最近的新点。

Kruskal：

  • 边按权值从小到大排序。
  • 用并查集判断是否成环。

复杂度分析

  • 一层循环：O(n)。
  • 双层循环：O(n^2)。
  • 二分、快速幂：O(log n)。
  • 排序：O(n log n)。
  • Floyd：O(n^3)。
  • 朴素 Fibonacci 递归：指数级。

最后检查

  • 有没有看错“不正确、不能、至少、可能”？
  • 变量初始化了吗？
  • 数组下标会不会越界？
  • 整数除法和小数除法分清了吗？
  • 字符 '0' 和 '\0' 分清了吗？
  • 输出有没有多空格、少换行、多提示？
  • 需要 long long 吗？
  • 样例能手算通过吗？

























分类: 分享 · 更新时间 2026-6-26 11:56:59