青少年软件编程（C/C++）等级考试 · 知识点手册

#include <iostream>     // 头文件：引入输入输出的功能
using namespace std;      // 使用标准命名空间
int main(){               // 主函数：程序从这里开始执行
    cout << "Hello World" << endl;   // 输出并换行
    return 0;             // 告诉系统程序正常结束
}

int age = 10;            // 声明并赋值
age = 11;                // 修改变量的值
double score = 95.5;
char grade = 'A';
bool pass = true;
cout << age << " " << score << endl;   // 输出 11 95.5

#include <iostream>
using namespace std;
int main(){
    int a, b;
    cin >> a >> b;          // 输入两个数（空格或回车隔开）
    cout << a + b << endl;  // 输出它们的和
    cout << "a=" << a << " b=" << b << endl;
    return 0;
}

#include <iostream>
#include <cmath>
using namespace std;
int main(){
    cout << sqrt(16) << endl;    // 平方根 → 4
    cout << pow(2, 10) << endl;  // 2 的 10 次方 → 1024
    cout << abs(-7) << endl;     // 绝对值 → 7
    cout << ceil(2.1) << endl;   // 向上取整 → 3
    cout << floor(2.9) << endl;  // 向下取整 → 2
    return 0;
}

#include <iostream>
using namespace std;
int main(){
    int a, b;
    cout << "请输入两个整数：";
    cin >> a >> b;
    int sum = a + b;         // 处理：求和
    cout << "和是：" << sum << endl;   // 输出
    return 0;
}

int score = 85;
if (score >= 60) {
    cout << "及格" << endl;
} else {
    cout << "不及格" << endl;
}
// 三目运算符：条件 ? 结果1 : 结果2
cout << (score >= 60 ? "pass" : "fail") << endl;

int day = 3;
switch (day) {
    case 1: cout << "星期一"; break;
    case 2: cout << "星期二"; break;
    case 3: cout << "星期三"; break;
    default: cout << "其他"; break;
}

// 从 1 加到 100
int sum = 0;
for (int i = 1; i <= 100; i++) {
    sum += i;
}
cout << sum << endl;   // 5050

int n = 12345, cnt = 0;
while (n > 0) {         // 不断取个位
    cnt++;
    n /= 10;
}
cout << "位数：" << cnt << endl;   // 5

int x;
do {
    cout << "请输入一个正数：";
    cin >> x;
} while (x <= 0);      // 直到输入正数才停

#include <cstdio>
int main(){
    freopen("in.txt", "r", stdin);    // 输入从 in.txt 读
    freopen("out.txt", "w", stdout);  // 输出写到 out.txt
    int a, b;
    scanf("%d %d", &a, &b);           // 从文件读入
    printf("%d\n", a + b);           // 写入文件
    fclose(stdin); fclose(stdout);
    return 0;
}

#include <fstream>
using namespace std;
int main(){
    ifstream fin("in.txt");       // 读
    ofstream fout("out.txt");     // 写
    int a, b;
    fin >> a >> b;
    fout << a + b << endl;
    fin.close(); fout.close();
    return 0;
}

int a = 5, b = 2;
double x = (double)a / b;      // 2.5（先转再除）
int y = (int)3.99;             // 3（小数被截断）
double z = a / b;              // 2.0！a/b 先整除成 2 再转 double
char c = 'A';
int ascii = (int)c;            // 65（字符转 ASCII 码）

int score = 85;
if (score >= 90)      cout << "优秀";
else if (score >= 80) cout << "良好";
else if (score >= 60) cout << "及格";
else                  cout << "不及格";

int a, b;  cin >> a >> b;
if (a == b) cout << "相等";
else {
    if (a > b) cout << "a 大";
    else       cout << "b 大";
}

// 打印直角三角形
for (int i = 1; i <= 5; i++) {
    for (int j = 1; j <= i; j++) {
        cout << "*";
    }
    cout << endl;
}
/* 输出：
*
**
***
****
***** */

// 九九乘法表
for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= i; j++) {
        cout << j << "*" << i << "=" << j*i << "\t";
    }
    cout << endl;
}

int a[5];               // 声明 5 个整数的数组
a[0] = 10; a[1] = 20;     // 赋值
for (int i = 0; i < 5; i++) cin >> a[i];   // 读入
// 求最大值
int mx = a[0];
for (int i = 1; i < 5; i++)
    if (a[i] > mx) mx = a[i];
cout << mx << endl;

int g[3][4];            // 3 行 4 列的“表格”
// 双层循环读入 3×4 个数
for (int i = 0; i < 3; i++)
    for (int j = 0; j < 4; j++)
        cin >> g[i][j];

// 返回两数中较大者
int max2(int a, int b) {
    if (a > b) return a;
    return b;
}
int main(){
    cout << max2(3, 7) << endl;   // 7（调用）
    cout << max2(10, 4) << endl;  // 10
    return 0;
}

void swap1(int a, int b){   // 值传递：改的是副本
    int t = a; a = b; b = t;
}
void swap2(int &a, int &b){  // 引用传递：改的是原变量
    int t = a; a = b; b = t;
}
int main(){
    int x = 3, y = 5;
    swap1(x, y);  cout << x << y;   // 35（没交换！）
    swap2(x, y);  cout << x << y;   // 53（成功交换）
}

int fact(int n){           // n 的阶乘
    if (n <= 1) return 1;   // 出口
    return n * fact(n - 1); // 调用自己
}
// 斐波那契：1 1 2 3 5 8 ...
int fib(int n){
    if (n <= 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

char s[20] = "hello";      // 实际占 6 个位置（含 \0）
strlen(s);                  // 长度 5
strcmp(s, "hello");         // 0（相等）
strcpy(s, "world");         // 把 s 改成 world

#include <string>
string s = "abc";
s.length();                 // 3
s += "d";                   // "abcd"
s.substr(1, 2);             // "bc"（从下标 1 取 2 个）
s.find("bc");               // 返回位置 1

#include <cmath>
abs(-3)      // 3    整数绝对值
fabs(-3.5)   // 3.5  小数绝对值
sqrt(25)     // 5    平方根
pow(2, 3)    // 8    乘方
log(1)       // 0    自然对数
round(3.6)   // 4    四舍五入
ceil(2.1)    // 3    向上取整
floor(2.9)   // 2    向下取整

// 模拟：小智每天存 1 元、第 2 天存 2 元……问 n 天后共存多少
int n = 10, total = 0;
for (int day = 1; day <= n; day++)
    total += day;          // 每天按规则加
cout << total << endl;     // 55

// 水仙花数：三位数，各位立方和等于它本身
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
}

int a = 10;
int *p = &a;        // p 存的是 a 的地址
cout << p << endl;  // 输出一个地址（十六进制）
cout << *p << endl; // 10（*p 通过地址取到 a 的值）
*p = 99;            // 修改 a 的值！
cout << a << endl;  // 99

struct Student {
    string name;
    int score;
};
int main(){
    Student s;
    s.name = "小明";
    s.score = 95;
    cout << s.name << " " << s.score << endl;
    Student a[3];            // 结构体数组
    return 0;
}

class Counter {
private:
    int value = 0;
public:
    void add(){ value++; }
    int get(){ return value; }
};
int main(){
    Counter c;
    c.add(); c.add();
    cout << c.get() << endl;   // 2
    return 0;
}

int n = 13;
string bin = "";
while (n > 0) {
    bin = char('0' + n % 2) + bin;   // 余数往前拼
    n /= 2;
}
cout << bin << endl;   // 1101

cout << hex << 16 << endl;   // 10（十六进制）
cout << oct << 8 << endl;    // 10（八进制）
cout << dec << 10 << endl;   // 10（十进制）

// 判断奇偶：看最低位
if (n & 1) cout << "奇数"; else cout << "偶数";
// 交换两个数（不用临时变量）
a ^= b; b ^= a; a ^= b;
// 乘 2 / 除 2（比乘除快）
x = x << 1;   // x * 2
x = x >> 1;   // x / 2

int a[5] = {3, 1, 4, 1, 5};
int bucket[10] = {0};
for (int i = 0; i < 5; i++) bucket[a[i]]++;
for (int v = 0; v < 10; v++)
    while (bucket[v]--) cout << v << " ";

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]);

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]);
}

for (int i = 1; i < n; i++){
    int key = a[i], j = i - 1;
    while (j >= 0 && a[j] > key){ a[j+1] = a[j]; j--; }
    a[j + 1] = key;
}

void qsort(int a[], int l, int r){
    if (l >= r) return;
    int x = a[(l + r) / 2], i = l, j = r;
    while (i <= j){
        while (a[i] < x) i++;
        while (a[j] > x) j--;
        if (i <= j){ swap(a[i], a[j]); i++; j--; }
    }
    qsort(a, l, j);
    qsort(a, i, r);
}

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[1000], k = 0, i = l, j = mid + 1;
    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 (int t = 0; t < k; t++) a[l + t] = tmp[t];
}

// 高精度加法：a、b 为两个数组（低位在前），返回结果
string add(string x, string y){
    // 先把两个字符串反转，低位在前
    reverse(x.begin(), x.end());
    reverse(y.begin(), y.end());
    string r; int carry = 0;
    int n = max(x.size(), y.size());
    for (int i = 0; i < n; i++){
        int d = carry;
        if (i < x.size()) d += x[i] - '0';
        if (i < y.size()) d += y[i] - '0';
        r += char('0' + d % 10);
        carry = d / 10;
    }
    if (carry) r += char('0' + carry);
    reverse(r.begin(), r.end());
    return r;
}

long long qpow(long long a, long long b){
    long long r = 1;
    while (b > 0){
        if (b & 1) r = r * a;   // 当前二进制位是 1 就乘
        a = a * a;              // a 翻倍：a^1, a^2, a^4, a^8...
        b >>= 1;                // b 右移一位
    }
    return r;
}
// 例：qpow(2, 10) = 1024

// 斐波那契：f(1)=1, f(2)=1, f(n)=f(n-1)+f(n-2)
long long f[100];
f[1] = f[2] = 1;
for (int i = 3; i <= n; i++)
    f[i] = f[i - 1] + f[i - 2];

// 找零钱：用最少的硬币凑出 n 元（面值 1, 5, 10, 50）
int coins[] = {50, 10, 5, 1};
int n, cnt = 0;
cin >> n;
for (int i = 0; i < 4; i++){
    cnt += n / coins[i];     // 尽量用大面值
    n %= coins[i];
}
cout << cnt << endl;

int a[6] = {0, 1, 3, 2, 4, 5};   // a[1]~a[5]
int pre[6] = {0};
for (int i = 1; i <= 5; i++)
    pre[i] = pre[i - 1] + a[i];
// pre = {0, 1, 4, 6, 10, 15}
// 求 a[2]~a[4] 的和：pre[4] - pre[1] = 10 - 1 = 9
cout << pre[4] - pre[1] << endl;   // 9

int diff[1000] = {0};
// 区间 [l, r] 整体 +v
void add(int l, int r, int v){
    diff[l] += v;
    diff[r + 1] -= v;
}
// 多次 add 后，前缀和还原出每个位置的最终值
for (int i = 1; i <= n; i++){
    diff[i] += diff[i - 1];      // 累加还原
    cout << diff[i] << " ";      // 第 i 个位置的值
}

int a[10] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int find(int x){
    int l = 0, r = 9;
    while (l <= r){
        int mid = (l + r) / 2;
        if (a[mid] == x) return mid;
        if (a[mid] < x) l = mid + 1;
        else            r = mid - 1;
    }
    return -1;
}

// 例：有序数组中找两数和等于 target
int a[6] = {1, 3, 4, 6, 8, 10}, target = 14;
int i = 0, j = 5;              // 相向双指针
while (i < j){
    int s = a[i] + a[j];
    if (s == target){ cout << a[i] << " " << a[j]; break; }
    if (s < target) i++;       // 和小了，左边右移
    else            j--;       // 和大了，右边左移
}

#include <vector>
#include <set>
#include <map>
vector<int> v = {3, 1, 2};
v.push_back(5);          // 末尾加 5
sort(v.begin(), v.end());// 排序
v.size(); v[0];

set<int> s;              // 自动去重 + 排序
s.insert(5); s.insert(5); s.insert(3);
// s 里只有 {3, 5}

map<string, int> m;      // 键值对
m["apple"] = 3;          // 像字典
m["banana"] = 5;
cout << m["apple"];      // 3

#include <stack>
stack<int> st;
st.push(1); st.push(2); st.push(3);
st.top();        // 3
st.pop();        // 弹掉 3
st.size();       // 2

#include <queue>
queue<int> q;
q.push(1); q.push(2); q.push(3);
q.front();       // 1（队首）
q.pop();         // 弹掉 1
q.size();        // 2

struct Node { int val; Node *next; };
// 在头节点后面插入新节点
void insert(Node *&head, int x){
    Node *p = new Node;
    p->val = x;
    p->next = head;
    head = p;
}
// 遍历链表
void print(Node *p){
    while (p){ cout << p->val << " "; p = p->next; }
}

// 例：全排列 1~n（用 DFS 回溯）
int n = 3, a[10];
bool used[10] = {false};
void dfs(int k){
    if (k > n){                       // 选满 n 个，输出
        for (int i = 1; i <= n; i++) cout << a[i] << " ";
        cout << endl; return;
    }
    for (int i = 1; i <= n; i++){     // 尝试每个没用过的数
        if (!used[i]){
            used[i] = true;  a[k] = i;
            dfs(k + 1);               // 深入下一层
            used[i] = false;          // 回溯：撤销选择
        }
    }
}

#include <queue>
// 例：迷宫最短步数（0 可走，1 是墙），从 (sx,sy) 到 (ex,ey)
int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
int dist[105][105];              // -1 表示未访问
queue<pair<int,int>> q;
q.push({sx, sy}); dist[sx][sy] = 0;
while (!q.empty()){
    auto [x, y] = q.front(); q.pop();
    for (int k = 0; k < 4; k++){
        int nx = x + dx[k], ny = y + dy[k];
        if (nx<0||ny<0||nx>=n||ny>=m) continue;   // 越界
        if (maze[nx][ny]) continue;               // 墙
        if (dist[nx][ny] != -1) continue;         // 已访问
        dist[nx][ny] = dist[x][y] + 1;
        q.push({nx, ny});
    }
}
cout << dist[ex][ey];

// f[i] = 到第 i 级台阶的走法数
// 转移方程：f[i] = f[i-1] + f[i-2]
int f[50];
f[1] = 1; f[2] = 2;
for (int i = 3; i <= n; i++)
    f[i] = f[i - 1] + f[i - 2];

// dp[j] = 容量 j 时能装的最大价值
int dp[1005] = {0};
for (int i = 0; i < n; i++)              // 遍历物品
    for (int j = c; j >= w[i]; j--)      // 容量倒着遍历（保证每件只拿一次）
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[c] << endl;

// 石子合并：合并相邻石子堆的最小代价
int dp[305][305];
for (int len = 2; len <= n; len++)          // 区间长度
    for (int i = 1; i + len - 1 <= n; i++){
        int j = i + len - 1;
        dp[i][j] = 1e9;
        for (int k = i; k < j; k++)          // 分割点
            dp[i][j] = min(dp[i][j],
                dp[i][k] + dp[k+1][j] + sum(i, j));
    }

int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b){
    return a / gcd(a, b) * b;    // 最小公倍数
}

bool isprime[1000005];
void sieve(int n){
    for (int i = 2; i <= n; i++) isprime[i] = true;
    for (int i = 2; i * i <= n; i++)
        if (isprime[i])
            for (int j = i * i; j <= n; j += i)
                isprime[j] = false;   // 划掉 i 的倍数
}

int primes[100000], pc = 0;
bool np[1000005];
void linear_sieve(int n){
    for (int i = 2; i <= n; i++){
        if (!np[i]) primes[pc++] = i;
        for (int j = 0; j < pc && i * primes[j] <= n; j++){
            np[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

long long C(int n, int m){     // 组合数（m <= n）
    if (m > n - m) m = n - m;
    long long r = 1;
    for (int i = 0; i < m; i++)
        r = r * (n - i) / (i + 1);   // 边乘边除防溢出
    return r;
}

vector<int> children[1005];   // 邻接表存树：children[父亲] = 孩子们
int n, root;
void dfs(int u){                // 先序遍历：先访问自己，再访问孩子
    cout << u << " ";
    for (int v : children[u])
        dfs(v);
}

struct Node { int val; Node *l, *r; };
void pre(Node *p){          // 前序：根 左 右
    if (!p) return;
    cout << p->val << " ";  pre(p->l);  pre(p->r);
}
void in(Node *p){           // 中序：左 根 右
    if (!p) return;
    in(p->l);  cout << p->val << " ";  in(p->r);
}
void post(Node *p){         // 后序：左 右 根
    if (!p) return;
    post(p->l);  post(p->r);  cout << p->val << " ";
}

// 例：活动安排——选最多互不冲突的活动
// 先按结束时间排序
sort(a, a + n, [](Act x, Act y){ return x.r < y.r; });
int last = -1, cnt = 0;
for (int i = 0; i < n; i++)
    if (a[i].l > last){        // 不与上一个冲突就选
        cnt++; last = a[i].r;
    }

// 例：数字三角形最大路径和
int f[105][105];
for (int i = n - 1; i >= 1; i--)       // 从下往上推
    for (int j = 1; j <= i; j++)
        f[i][j] += max(f[i+1][j], f[i+1][j+1]);
cout << f[1][1];

// 邻接矩阵（n 较小、边多时）
int g[505][505];
g[u][v] = w;                 // u 到 v 权值为 w

// 邻接表（n 大、边少时，推荐）
vector<pair<int,int>> adj[1005];
adj[u].push_back({v, w});    // u 有一条边到 v，权值 w

bool vis[1005];
void dfs(int u){             // DFS 遍历
    vis[u] = true;
    for (auto [v, w] : adj[u])
        if (!vis[v]) dfs(v);
}

queue<int> q;
int indeg[1005];
for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.push(i);
while (!q.empty()){
    int u = q.front(); q.pop();
    cout << u << " ";
    for (int v : adj[u])
        if (--indeg[v] == 0) q.push(v);
}
// 若输出的点数 < n，说明图里有环

// 用优先队列（堆）优化
int dist[1005]; bool done[1005];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
memset(dist, 0x3f, sizeof dist);
dist[s] = 0; pq.push({0, s});
while (!pq.empty()){
    auto [d, u] = pq.top(); pq.pop();
    if (done[u]) continue; done[u] = true;
    for (auto [v, w] : adj[u])
        if (dist[v] > dist[u] + w){
            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];

struct Edge { int u, v, w; };
sort(e, e + m, [](Edge a, Edge b){ return a.w < b.w; });
int ans = 0, cnt = 0;
for (int i = 0; i < m && cnt < n - 1; i++){
    int ru = find(e[i].u), rv = find(e[i].v);
    if (ru != rv){           // 不成环就加
        uni(ru, rv);
        ans += e[i].w; cnt++;
    }
}

// 字符串哈希：把字符串变成一个整数
long long hash_str(const string &s){
    long long h = 0, P = 131, MOD = 1e9+7;
    for (char c : s)
        h = (h * P + c) % MOD;
    return h;
}
// 哈希表：用 unordered_map 直接实现
#include <unordered_map>
unordered_map<string, int> cnt;
cnt["apple"]++;              // O(1) 增删查

// st[i][k] = 从 i 开始、长度 2^k 的区间最大值
int st[100005][20], lg[100005];
void build(int n, int a[]){
    for (int i = 1; i <= n; i++) st[i][0] = a[i];
    for (int k = 1; (1 << k) <= n; k++)
        for (int i = 1; i + (1 << k) - 1 <= n; i++)
            st[i][k] = max(st[i][k-1], st[i + (1<<(k-1))][k-1]);
    for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
}
int query(int l, int r){      // O(1) 查区间最大值
    int k = lg[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

int fa[100005];
void init(int n){ for (int i = 1; i <= n; i++) fa[i] = i; }
int find(int x){               // 找根（带路径压缩）
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
void uni(int a, int b){        // 合并
    fa[find(a)] = find(b);
}
bool same(int a, int b){ return find(a) == find(b); }

int tree[100005], n;
int lowbit(int x){ return x & (-x); }
void add(int i, int v){          // 单点加 v
    for (; i <= n; i += lowbit(i)) tree[i] += v;
}
int sum(int i){                  // 前缀和 [1..i]
    int r = 0;
    for (; i > 0; i -= lowbit(i)) r += tree[i];
    return r;
}
int query(int l, int r){ return sum(r) - sum(l - 1); }

int sum[4 * 100005], lazy[4 * 100005];
// 建树：节点 p 表示 [l, r]
void build(int p, int l, int r, int a[]){
    if (l == r){ sum[p] = a[l]; return; }
    int mid = (l + r) / 2;
    build(p*2, l, mid, a);
    build(p*2+1, mid+1, r, a);
    sum[p] = sum[p*2] + sum[p*2+1];
}
// 区间加 v 的“懒标记”更新
void add(int p, int l, int r, int ql, int qr, int v){
    if (ql <= l && r <= qr){ sum[p] += v*(r-l+1); lazy[p] += v; return; }
    // 下传懒标记……
}

int nxt[100005][26], cnt[100005], tot = 0;
void insert(const string &s){      // 插入单词
    int u = 0;
    for (char c : s){
        int k = c - 'a';
        if (!nxt[u][k]) nxt[u][k] = ++tot;
        u = nxt[u][k];
    }
    cnt[u]++;                       // 这个单词出现次数
}
int query(const string &s){        // 查询单词出现次数
    int u = 0;
    for (char c : s){
        int k = c - 'a';
        if (!nxt[u][k]) return 0;
        u = nxt[u][k];
    }
    return cnt[u];
}

// Hierholzer 算法求欧拉回路
void dfs(int u){
    for (int &i = head[u]; i < adj[u].size();){
        int v = adj[u][i++];
        dfs(v);                 // 先深入再输出
    }
    path.push_back(u);          // 反序存路径
}
// 最后把 path 倒过来输出就是欧拉回路

// next[i]：模式串前 i 个字符中，最长相等前后缀长度
int nxt[100005];
void get_next(const string &p){
    int n = p.size();
    nxt[0] = -1;
    for (int i = 1, j = -1; i < n; i++){
        while (j >= 0 && p[i] != p[j+1]) j = nxt[j];
        if (p[i] == p[j+1]) j++;
        nxt[i] = j;
    }
}
// 匹配
int kmp(const string &s, const string &p){
    int n = s.size(), m = p.size(), j = -1;
    for (int i = 0; i < n; i++){
        while (j >= 0 && s[i] != p[j+1]) j = nxt[j];
        if (s[i] == p[j+1]) j++;
        if (j == m - 1) return i - m + 1;   // 匹配成功位置
    }
    return -1;
}

// 例：没有上司的舞会——选父亲就不能选孩子
// dp[u][0] 不选 u，dp[u][1] 选 u
void dfs(int u){
    dp[u][1] = val[u];
    for (int v : children[u]){
        dfs(v);
        dp[u][0] += max(dp[v][0], dp[v][1]);   // 不选 u，孩子随便
        dp[u][1] += dp[v][0];                  // 选 u，孩子不能选
    }
}

// 例：旅行商问题（TSP）状态：dp[visited][last]
int dp[1<<20][20];   // visited 是二进制集合，last 是当前城市
memset(dp, 0x3f, sizeof dp);
dp[1][0] = 0;                       // 从 0 出发
for (int S = 1; S < (1<<n); S++)
    for (int u = 0; u < n; u++)
        if (S >> u & 1)
            for (int v = 0; v < n; v++)
                if (!(S >> v & 1))
                    dp[S | (1<<v)][v] =
                        min(dp[S | (1<<v)][v], dp[S][u] + g[u][v]);

int dfn[1005], low[1005], tim = 0, scc_cnt = 0;
int scc[1005]; stack<int> st; bool instk[1005];
void tarjan(int u){
    dfn[u] = low[u] = ++tim;
    st.push(u); instk[u] = true;
    for (int v : adj[u]){
        if (!dfn[v]){ tarjan(v); low[u] = min(low[u], low[v]); }
        else if (instk[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]){         // 找到强连通分量的根
        scc_cnt++;
        while (true){
            int x = st.top(); st.pop(); instk[x] = false;
            scc[x] = scc_cnt;
            if (x == u) break;
        }
    }
}

long long exgcd(long long a, long long b,
                 long long &x, long long &y){
    if (b == 0){ x = 1; y = 0; return a; }
    long long g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}
// 求 ax ≡ 1 (mod m) 的 x（a 与 m 互质时存在）

// 用快速幂求逆元：a^(p-2) % p
long long inv(long long a, long long p){
    return qpow(a, p - 2, p);    // 快速幂 + 取模
}
// 也可用扩展欧几里得求逆元
long long x, y;
exgcd(a, p, x, y);
long long inv2 = (x % p + p) % p;

// [[f(n)], [f(n-1)]] = [[1,1],[1,0]]^(n-1) × [[f(1)],[f(0)]]
using Mat = vector<vector<long long>>;
Mat mul(Mat A, Mat B){            // 矩阵乘法
    int n = A.size();
    Mat C(n, vector<long long>(n));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
            if (A[i][k])
                for (int j = 0; j < n; j++)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}
Mat qpow(Mat base, long long e){  // 矩阵快速幂
    int n = base.size();
    Mat r(n, vector<long long>(n));
    for (int i = 0; i < n; i++) r[i][i] = 1;   // 单位矩阵
    while (e){ if (e & 1) r = mul(r, base); base = mul(base, base); e >>= 1; }
    return r;
}

// 解 n 元线性方程组（增广矩阵 a[i][n] 是常数项）
double a[105][105];
bool gauss(int n){
    for (int col = 0, row = 0; col < n && row < n; col++){
        // 找这一列绝对值最大的行，换到当前行
        int mx = row;
        for (int i = row; i < n; i++)
            if (fabs(a[i][col]) > fabs(a[mx][col])) mx = i;
        if (fabs(a[mx][col]) < 1e-9) continue;   // 无解/无穷解
        swap(a[mx], a[row]);
        // 用当前行消去下面各行的这一列
        for (int i = row + 1; i < n; i++){
            double t = a[i][col] / a[row][col];
            for (int j = col; j <= n; j++) a[i][j] -= t * a[row][j];
        }
        row++;
    }
    // 回代求每个未知数
    return true;
}

// 例：1~n 中能被 a 或 b 整除的数的个数
int cnt = n / a + n / b - n / lcm(a, b);
// 三个集合：|A∪B∪C| = |A|+|B|+|C| - |AB| - |AC| - |BC| + |ABC|

struct Node { int key, pri, cnt, sz; Node *l, *r; };
// 旋转：右旋 / 左旋，保持 BST 性质并修正堆性质
void rotate_right(Node *&p){
    Node *q = p->l;
    p->l = q->r;  q->r = p;  p = q;
    upd(p->r); upd(p);
}
// 插入：先按 BST 插入，若子节点优先级更高就旋转上来

// 例：区间 DP 状态 dp[i][j]（区间）
// 例：状压 DP 状态 dp[S][u]（集合 S + 当前点 u）
// 例：数位 DP 状态 dp[pos][limit][pre]（数位 + 边界 + 前一位）
// 例：树形背包 dp[u][k]（节点 u，容量 k）
int dp[105][105];   // 设计时想清楚每个维度代表什么

// 例：经典“玩具装箱”式转移（示意）
// dp[i] = min over j< i of (dp[j] + (sum[i]-sum[j]+i-j-1-L)²)
// 令 x = sum[j]+j, y = dp[j]+(sum[j]+j)²，则每步都是
// “用斜率 k 在凸包上求最小截距”，维护单调队列即可。

int phi(int n){                 // 欧拉函数
    int r = n;
    for (int p = 2; p * p <= n; p++)
        if (n % p == 0){
            while (n % p == 0) n /= p;
            r -= r / p;           // r * (1 - 1/p)
        }
    if (n > 1) r -= r / n;
    return r;
}

// x ≡ a[i] (mod m[i])，m 两两互质
long long crt(int n, long long a[], long long m[]){
    long long M = 1, x = 0;
    for (int i = 0; i < n; i++) M *= m[i];
    for (int i = 0; i < n; i++){
        long long Mi = M / m[i];
        long long inv = mod_inv(Mi, m[i]);   // 逆元
        x = (x + a[i] * Mi % M * inv % M) % M;
    }
    return (x % M + M) % M;
}

long long base[64];               // base[i] 最高位是 i 的数
void insert(long long x){         // 插入一个数
    for (int i = 60; i >= 0; i--)
        if (x >> i & 1){
            if (!base[i]){ base[i] = x; return; }
            x ^= base[i];
        }
}
long long max_xor(){              // 求最大异或和
    long long r = 0;
    for (int i = 60; i >= 0; i--)
        r = max(r, r ^ base[i]);
    return r;
}