CCF GESP 编程能力等级认证（C++）· 知识点手册

#include <iostream>
using namespace std;
int main() {
    // 程序从这里开始
    return 0;
}

int a, b;
cin >> a >> b;          // 输入
cout << a + b << endl;  // 输出 + 换行
a = 10;                 // 赋值语句
a++;                    // 自增 a = a + 1
a--;                    // 自减 a = a - 1

const int MAXN = 100;   // 常量（不可改）
int age = 10;            // 变量：声明 + 初始化
age = 11;                // 修改变量的值
int n;                   // 先声明（不初始化）

int a = 10;
double b = 3.14;
char c = 'A';
printf("%d %.2lf %c\n", a, b, c);
scanf("%d", &a);     // 注意 & 取地址

int a = 7, b = 2;
cout << a + b << " " << a - b << " ";   // 9 5
cout << a * b << " " << a / b << " ";   // 14 3（整数除法）
cout << a % b << endl;                  // 1（取余）

int s = 85;
if (s >= 90) cout << "A";
else if (s >= 80) cout << "B";
else cout << "C";
// switch
int d = 2;
switch (d) {
    case 1: cout << "一"; break;
    case 2: cout << "二"; break;
    default: cout << "其他";
}

int sum = 0;
for (int i = 1; i <= 100; i++) sum += i;   // 5050
int j = 0;
while (j < 5) { cout << j; j++; }         // 01234
int k = 0;
do { cout << k; k++; } while (k < 3);     // 012 至少执行一次

char c = 'A';
cout << (int)c << endl;      // 65（字符转编码）
cout << (char)97 << endl;    // 'a'（编码转字符）
// 小写 = 大写 + 32
cout << (char)('A' + 32) << endl;   // 得到字符 a 

int a = 5, b = 2;
double d = (double)a / b;     // 强制转换：2.5
cout << d << endl;
// 隐式转换：int 参与小树运算自动变 double
cout << 5 / 2.0 << endl;       // 2.5
cout << (char)65 << endl;      // 得到字符 A 

int score = 85;
if (score >= 60) {
    if (score >= 90) cout << "优秀";
    else cout << "合格";
} else cout << "不合格";

for (int i = 1; i <= 5; i++) {
    for (int j = 1; j <= i; j++)
        cout << "*";
    cout << endl;
}

#include <cmath>
#include <cstdlib>
cout << abs(-5) << endl;          // 5  绝对值
cout << sqrt(25) << endl;         // 5  平方根
cout << max(3, 7) << " " << min(3, 7) << endl;  // 7 3
cout << pow(2, 10) << endl;       // 1024 乘方
// 随机数：先播种再取
srand(time(0));
int x = rand() % 6 + 1;           // 1~6 随机
cout << x;

int n = 13, a[100], cnt = 0;
while (n) { a[cnt++] = n % 2; n /= 2; }
for (int i = cnt - 1; i >= 0; i--) cout << a[i];   // 1101
// 流操作输出
cout << hex << 255 << endl;   // ff

int n = 7;
cout << (n & 1) << endl;    // 1 → 奇数（判奇偶）
cout << (n << 1) << endl;   // 14（×2）
cout << (n >> 1) << endl;   // 3（÷2）
int a = 5, b = 3;
a ^= b; b ^= a; a ^= b;     // 交换 a、b

int a[100];          // 定义能存 100 个整数的数组
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
// 下标从 0 开始
int sum = 0, mx = a[0];
for (int i = 0; i < n; i++) {
    sum += a[i];
    if (a[i] > mx) mx = a[i];
}
cout << sum << " " << mx << endl;

#include <string>
string s = "Hello World";
cout << s.size() << endl;         // 11 长度
cout << s.substr(0, 5) << endl;   // "Hello" 截取
cout << s.find("World") << endl;  // 6 查找位置
s += "!";                         // 拼接
// 大小写转换
for (char &c : s) if (c >= 'A' && c <= 'Z') c += 32;
cout << s << endl;                // 全小写

// 水仙花数：各位立方和等于本身
for (int n = 100; n <= 999; n++) {
    int a = n / 100, b = n / 10 % 10, c = n % 10;
    if (a*a*a + b*b*b + c*c*c == n)
        cout << n << " ";     // 153 370 371 407
}

// 模拟：猴子吃桃，第 10 天剩 1 个，每天吃一半多一个
int x = 1;
for (int d = 9; d >= 1; d--) x = (x + 1) * 2;
cout << x << endl;    // 1534

int x = 10;
int *p = &x;       // p 存 x 的地址（&取地址）
cout << *p << endl;  // 10（*p 解引用取值）
*p = 20;           // 通过指针改 x
cout << x << endl; // 20

int add(int a, int b) {   // a、b 形参
    return a + b;
}
int main() {
    int r = add(3, 5);        // 3、5 实参
    cout << r << endl;        // 8
    return 0;
}

int g = 100;              // 全局变量（整个文件可见）
void f() { cout << g; }    // 函数里能用全局
int main() {
    int g = 5;             // 局部变量（遮蔽全局）
    cout << g << endl;     // 5
    return 0;
}

void by_val(int x) { x = 99; }        // 改不了外面
void by_ref(int &x) { x = 99; }        // 能改
void by_ptr(int *x) { *x = 99; }       // 也能改
int a = 1;
by_val(a); cout << a << endl;   // 1
by_ref(a); cout << a << endl;   // 99
by_ptr(&a); cout << a << endl;  // 99

struct Student {
    string name;
    int score;
};
Student a[100];                 // 结构体数组
cin >> a[0].name >> a[0].score;
cout << a[0].name << " " << a[0].score;
// 结构体排序
bool cmp(Student x, Student y) {
    return x.score > y.score;   // 按分数从高到低
}
sort(a, a + n, cmp);

int a[10][10];           // 行 × 列
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        cin >> a[i][j];
// 求和
int sum = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        sum += a[i][j];
cout << sum;

// 斐波那契
long long f[100];
f[1] = f[2] = 1;                       // 初始值
for (int i = 3; i <= n; i++)
    f[i] = f[i - 1] + f[i - 2];        // 递推关系
cout << f[n] << endl;

// 冒泡：相邻比较，大的往后
void bubble(int a[], int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j+1]) swap(a[j], a[j+1]);
}
// 选择：每轮挑最小放前面（不稳定）
void select(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int mn = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[mn]) mn = j;
        swap(a[i], a[mn]);
    }
}

freopen("in.txt", "r", stdin);     // 从文件读
freopen("out.txt", "w", stdout);   // 写到文件
int a; cin >> a; cout << a;        // 正常写代码
fclose(stdin); fclose(stdout);

#include <fstream>
ifstream fin("in.txt");
ofstream fout("out.txt");
int x; fin >> x;         // 读
fout << x * 2;           // 写
fin.close(); fout.close();

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

int gcd(int a, int b) {       // 辗转相除法
    while (b) { int t = a % b; a = b; b = t; }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }

// 质因数分解 12 = 2*2*3
int n = 12;
for (int i = 2; i * i <= n; i++)
    while (n % i == 0) { cout << i << " "; n /= i; }
if (n > 1) cout << n;      // 最后剩下的质数
// 输出 2 2 3

// 数字倒着存数组：a[0] 是个位
int a[500] = {0}, b[500] = {0}, c[505] = {0};
string s1 = "12345678901234567890", s2 = "9876543210";
for (int i = 0; i < s1.size(); i++) a[i] = s1[s1.size()-1-i] - '0';
for (int i = 0; i < s2.size(); i++) b[i] = s2[s2.size()-1-i] - '0';
int len = max(s1.size(), s2.size());
for (int i = 0; i < len; i++) {
    c[i] += a[i] + b[i];
    c[i+1] += c[i] / 10;      // 进位
    c[i] %= 10;
}
if (c[len]) len++;
for (int i = len - 1; i >= 0; i--) cout << c[i];

struct Node { int data; Node *next; };
// 头插法建链表
Node *head = nullptr;
for (int i = 1; i <= 5; i++) {
    Node *p = new Node();
    p->data = i;
    p->next = head;    // 新结点指向原头
    head = p;
}
// 遍历
for (Node *p = head; p; p = p->next)
    cout << p->data << " ";

const int N = 1000000;
bool isp[N + 1];
void sieve(int n) {
    fill(isp, isp + n + 1, true);
    isp[0] = isp[1] = false;
    for (int i = 2; i * i <= n; i++)
        if (isp[i])
            for (int j = i * i; j <= n; j += i)   // 从 i*i 开始筛
                isp[j] = false;
}

vector<int> primes;
bool np[N + 1];
for (int i = 2; i <= n; i++) {
    if (!np[i]) primes.push_back(i);
    for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
        np[i * primes[j]] = true;
        if (i % primes[j] == 0) break;   // 保证每个数只被最小质因子筛一次
    }
}

int a[100], n, x;
// 前提：a 已升序
int l = 0, r = n - 1, ans = -1;
while (l <= r) {
    int mid = (l + r) / 2;
    if (a[mid] == x) { ans = mid; break; }
    else if (a[mid] < x) l = mid + 1;
    else r = mid - 1;
}
cout << ans;

// 例：m 段绳子切成长度 len，每段最长多少
bool ok(int len, int a[], int m) {
    long long cnt = 0;
    for (int i = 0; i < n; i++) cnt += a[i] / len;
    return cnt >= m;
}
int l = 1, r = maxlen;
while (l <= r) {
    int mid = (l + r) / 2;
    if (ok(mid, a, m)) l = mid + 1;   // 还能更长
    else r = mid - 1;
}
cout << r;

int fact(int n) {
    if (n <= 1) return 1;      // 终止条件
    return n * fact(n - 1);    // 自己调自己
}
int fib(int n) {
    if (n <= 2) return 1;
    return fib(n - 1) + fib(n - 2);   // O(2^n) 太慢！
}

long long memo[100];
long long fib2(int n) {
    if (n <= 2) return 1;
    if (memo[n]) return memo[n];      // 算过直接返回
    return memo[n] = fib2(n - 1) + fib2(n - 2);
}

void merge_sort(int a[], int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    // 合并两个有序段
    int tmp[100], i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r)
        tmp[k++] = a[i] < a[j] ? a[i++] : a[j++];
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (i = l; i <= r; i++) a[i] = tmp[i];
}

void quick_sort(int a[], int l, int r) {
    if (l >= r) return;
    int i = l, j = r, p = a[l];
    while (i < j) {
        while (i < j && a[j] >= p) j--;
        a[i] = a[j];
        while (i < j && a[i] <= p) i++;
        a[j] = a[i];
    }
    a[i] = p;
    quick_sort(a, l, i - 1);
    quick_sort(a, i + 1, r);
}

// 活动安排：按结束时间排序，每次选最早结束且不冲突的
struct Act { int s, e; };
bool cmp(Act a, Act b) { return a.e < b.e; }
sort(act, act + n, cmp);
int cnt = 0, last = -1;
for (int i = 0; i < n; i++)
    if (act[i].s >= last) { cnt++; last = act[i].e; }
cout << cnt;

struct Node { int v; Node *l, *r; };
void preorder(Node *p) {        // 前序：根-左-右
    if (!p) return;
    cout << p->v << " "; preorder(p->l); preorder(p->r);
}
void inorder(Node *p) {         // 中序：左-根-右
    if (!p) return;
    inorder(p->l); cout << p->v << " "; inorder(p->r);
}
void postorder(Node *p) {       // 后序：左-右-根
    if (!p) return;
    postorder(p->l); postorder(p->r); cout << p->v << " ";
}

Node* insert(Node *p, int x) {
    if (!p) { p = new Node(); p->v = x; return p; }
    if (x < p->v) p->l = insert(p->l, x);
    else p->r = insert(p->r, x);
    return p;
}
// BST 中序遍历 = 有序输出

// 十进制 n 转格雷码：g = n ^ (n >> 1)
for (int i = 0; i < 8; i++) {
    int g = i ^ (i >> 1);
    cout << i << "->" << g << endl;
}
// 0->0 1->1 2->3 3->2 4->6 5->7 6->5 7->4

bool vis[1005];
vector<int> g[1005];
void dfs(int u) {
    vis[u] = true;
    cout << u << " ";
    for (int v : g[u])
        if (!vis[v]) dfs(v);
}

#include <queue>
queue<int> q;
bool vis[1005];
vector<int> g[1005];
void bfs(int s) {
    q.push(s); vis[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int v : g[u])
            if (!vis[v]) { vis[v] = true; q.push(v); }
    }
}

long long dp[100];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
    dp[i] = dp[i - 1];
    if (i >= 2) dp[i] += dp[i - 2];
}
cout << dp[n];

int W, n, w[105], v[105], dp[10005];
cin >> W >> n;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++)
    for (int j = W; j >= w[i]; j--)      // 倒序！
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[W];

class Dog {
public:
    Dog(string n, int a) { name = n; age = a; }   // 构造函数
    void bark() { cout << name << " 汪汪！" << endl; }
private:
    string name;      // 封装：私有成员
    int age;
};
int main() {
    Dog d("旺财", 3);
    d.bark();       // 旺财 汪汪！
    return 0;
}

#include <stack>
stack<int> st;
st.push(1); st.push(2);
cout << st.top();   // 2（栈顶）
st.pop();           // 弹出

#include <queue>
queue<int> q;
q.push(1); q.push(2);
cout << q.front();  // 1
q.pop();            // 出队

#include <cmath>
sin(M_PI / 2)      // 1  正弦（弧度）
cos(0)             // 1  余弦
log10(1000)        // 3  以 10 为底对数
log2(8)            // 3  以 2 为底对数
exp(1)             // e ≈ 2.718
pow(2, 10)         // 1024

int a[1005], dp[1005];
for (int i = 0; i < n; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++)
        if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
}
int ans = 0;
for (int i = 0; i < n; i++) ans = max(ans, dp[i]);
cout << ans;   // O(n^2)

string s1 = "abcde", s2 = "ace";
int dp[1005][1005];
for (int i = 1; i <= s1.size(); i++)
    for (int j = 1; j <= s2.size(); j++) {
        if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
        else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    }
cout << dp[s1.size()][s2.size()];   // 3

vector<int> g[1005];   // 邻接表
g[u].push_back(v);       // 加边 u→v
// DFS / BFS 遍历与树相同，加 vis 防重复

int a[105][105], n, m;
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
void flood(int x, int y) {
    a[x][y] = 0;                       // 淹掉（标记访问）
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && a[nx][ny] == 1)
            flood(nx, ny);
    }
}
int cnt = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        if (a[i][j] == 1) { cnt++; flood(i, j); }
cout << cnt;

#include <unordered_map>
#include <unordered_set>
unordered_map<string, int> mp;
mp["apple"] = 3;                 // 插入
cout << mp["apple"];             // 3  O(1)
unordered_set<int> st;
st.insert(5);
cout << st.count(5);             // 1 判断存在

// 用递推求组合数 C(n,k)（杨辉三角法）
long long C[50][50];
for (int i = 0; i <= n; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; j++)
        C[i][j] = C[i-1][j-1] + C[i-1][j];   // 防溢出
}

int t[20][20];
for (int i = 0; i < n; i++) {
    t[i][0] = t[i][i] = 1;          // 两边是 1
    for (int j = 1; j < i; j++)
        t[i][j] = t[i-1][j-1] + t[i-1][j];   // 肩上两数相加
}
// 第 i 行第 k 个数 = C(i, k)

// 快速幂：a^b % m
long long qpow(long long a, long long b, long long m) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
// qpow(2, 10, 1e9+7) = 1024

// 解 ax + b = 0
double a = 2, b = -8;
cout << -b / a << endl;        // 4
// 解方程组（克莱默法则）：a1x+b1y=c1, a2x+b2y=c2
double a1=1,b1=1,c1=5, a2=2,b2=-1,c2=1;
double det = a1*b2 - a2*b1;                 // 行列式
double x = (c1*b2 - c2*b1) / det;           // 2
double y = (a1*c2 - a2*c1) / det;           // 3
cout << x << " " << y;

struct Edge { int u, v, w; };
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int fa[1005];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
sort(edges.begin(), edges.end(), cmp);
long long ans = 0;
for (auto &e : edges) {
    int fu = find(e.u), fv = find(e.v);
    if (fu != fv) { fa[fu] = fv; ans += e.w; }   // 不成环就选
}

#include <queue>
vector<pair<int,int>> g[1005];
long long dist[1005];
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
dist[s] = 0; pq.push({0, s});
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;
    for (auto [v, w] : g[u])
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
}

for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (d[i][k] + d[k][j] < d[i][j])
                d[i][j] = d[i][k] + d[k][j];