考前集训 · 一本通

// 竞赛标准程序模板（文件输入输出）
#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
    
    fclose(stdin); fclose(stdout);
    return 0;
}

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

int main() {
    int a = 42;
    long long b = 1e18;      // 10^18
    double pi = 3.14159265358979;
    char ch = 'A';
    bool flag = true;
    
    int x, y; cin >> x >> y;
    cout << x + y << endl;
    printf("%d + %d = %d\n", x, y, x+y);
    printf("pi = %.10f\n", pi);
    
    // 快速IO（大数据量时使用）
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}

// 完整程序：分支结构与循环综合演示
#include <bits/stdc++.h>
using namespace std;

int main() {
    // ===== 分支结构 =====
    int score;
    cin >> score;
    if (score >= 90)      cout << "A" << endl;
    else if (score >= 80) cout << "B" << endl;
    else if (score >= 70) cout << "C" << endl;
    else if (score >= 60) cout << "D" << endl;
    else                  cout << "F" << endl;
    
    // ===== for循环：高斯求和 =====
    int n = 100, sum = 0;
    for (int i = 1; i <= n; i++) sum += i;
    cout << "1+2+...+100 = " << sum << endl;  // 5050
    
    // ===== while循环：数字反转 =====
    int num = 12345, rev = 0;
    while (num > 0) {
        rev = rev * 10 + num % 10;
        num /= 10;
    }
    cout << "reversed: " << rev << endl;  // 54321
    
    // ===== 嵌套循环：九九乘法表 =====
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= i; j++)
            printf("%d*%d=%-2d ", j, i, i * j);
        cout << endl;
    }
    // ===== 三目运算符 =====
    int maxVal = (sum > rev) ? sum : rev;
    cout << "max = " << maxVal << endl;
    return 0;
}

// 完整程序：位运算十大必背技巧
#include <bits/stdc++.h>
using namespace std;

int main() {
    int x = 10;  // 二进制: 1010
    
    // 1. 判断奇偶
    cout << (x & 1 ? "odd" : "even") << endl;  // even
    // 2. 获取第k位（从0开始）
    int k = 3;
    cout << "bit " << k << ": " << ((x >> k) & 1) << endl; // 1
    // 3. 将第k位设为1
    cout << "set bit: " << (x | (1 << k)) << endl;        // 18
    // 4. 消去最低位的1
    cout << "pop lowest 1: " << (x & (x - 1)) << endl;    // 8
    // 5. lowbit: x & -x
    cout << "lowbit: " << (x & -x) << endl;               // 2
    // 6. 交换两数（异或，不用临时变量）
    int a = 5, b = 7;
    a ^= b; b ^= a; a ^= b;
    cout << "swap: a=" << a << ", b=" << b << endl;       // a=7, b=5
    // 7. 判断是否为2的幂
    bool isPow2 = (x > 0) && ((x & (x - 1)) == 0);
    cout << "is power of 2: " << (isPow2 ? "yes" : "no") << endl;
    // 8. 统计二进制中1的个数
    int cnt = 0, tmp = 15;  // 1111
    while (tmp) { tmp &= (tmp - 1); cnt++; }
    cout << "popcount(15) = " << cnt << endl;  // 4
    // 9. 翻转第k位
    cout << "flip bit 0: " << (x ^ (1 << 0)) << endl;  // 11
    // 10. 枚举子集
    int mask = 0b1101;  // 13
    cout << "subsets: ";
    for (int sub = mask; sub; sub = (sub - 1) & mask)
        cout << sub << " ";
    cout << endl;
    return 0;
}

// 完整程序：数学库函数演示
#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;

int main() {
    double x = -3.7;
    cout << fixed << setprecision(4);
    cout << "floor(" << x << ") = " << floor(x) << endl;   // -4.0000
    cout << "ceil(" << x << ") = " << ceil(x) << endl;     // -3.0000
    cout << "round(" << x << ") = " << round(x) << endl;   // -4.0000
    
    cout << "sqrt(2) = " << sqrt(2) << endl;               // 1.4142
    cout << "log2(1024) = " << log2(1024) << endl;          // 10
    
    // 高精度π
    const double PI = acos(-1.0);
    cout << "PI = " << setprecision(10) << PI << endl;
    
    // 浮点数比较（不能用==！）
    double a = 0.1 + 0.2, b = 0.3;
    if (fabs(a - b) < EPS)
        cout << "0.1+0.2 == 0.3 (within eps)" << endl;
    else
        cout << "WARNING: float precision error!" << endl;
    
    // 求整数位数
    int n = 12345;
    cout << "digits: " << (int)log10(n) + 1 << endl;  // 5
    
    return 0;
}

// 完整程序：数组与 vector 使用演示
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int globalArr[N]; // 全局数组自动初始化为0

int main() {
    // ===== 基本数组操作 =====
    int arr[10] = {1, 2, 3};  // 其余为0
    cout << "arr[0]=" << arr[0] << " arr[9]=" << arr[9] << endl;
    
    // 二维数组
    int mat[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
    cout << "mat[1][2] = " << mat[1][2] << endl;  // 6
    
    // memset 清零 (仅 0 或 -1)
    int memo[100];
    memset(memo, -1, sizeof(memo));
    cout << "memo[0] = " << memo[0] << endl;  // -1
    
    // fill 设置任意值
    fill(memo, memo + 100, 42);
    cout << "filled: " << memo[0] << endl;  // 42
    
    // ===== vector 动态数组 =====
    vector<int> v = {1, 2, 3};
    v.push_back(4); v.pop_back();
    sort(v.begin(), v.end());
    cout << "vector: ";
    for (int x : v) cout << x << " ";  // 1 2 3
    cout << endl;
    
    // reverse
    reverse(v.begin(), v.end());
    cout << "reversed: ";
    for (int x : v) cout << x << " ";  // 3 2 1
    cout << endl;
    
    // 去重
    vector<int> v2 = {3,1,4,1,5};
    sort(v2.begin(), v2.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());
    cout << "unique: ";
    for (int x : v2) cout << x << " ";  // 1 3 4 5
    cout << endl;
    
    return 0;
}

// 完整程序：字符串操作全解
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "Hello World";
    cout << "length: " << s.length() << endl;         // 11
    cout << "substr(0,5): " << s.substr(0, 5) << endl; // "Hello"
    cout << "find Wo: " << (int)s.find("Wo") << endl;  // 6
    cout << "find xyz: " << (int)s.find("xyz") << endl; // -1 (npos)
    
    // 遍历转换大小写
    string mixed = "HeLLo123";
    for (char& c : mixed) {
        if (isupper(c)) c = tolower(c);
        else if (islower(c)) c = toupper(c);
    }
    cout << "swapped: " << mixed << endl;  // hEllO123
    
    // 数字与字符串互转
    string numStr = "12345";
    int num = stoi(numStr);
    cout << "stoi+1: " << num + 1 << endl;                // 12346
    cout << "to_string: " << to_string(num + 1) << endl;   // "12346"
    
    // 判断回文
    string s2 = "racecar";
    string rev = s2;
    reverse(rev.begin(), rev.end());
    cout << s2 << " is palindrome: " << (s2 == rev ? "YES" : "NO") << endl;
    
    // 统计字符频率
    int cnt[26] = {0};
    for (char c : s)
        if (isalpha(c)) cnt[tolower(c) - 'a']++;
    
    // C风格字符串
    char cstr[100] = "hello";
    strcat(cstr, " world");
    cout << "C style: " << cstr << " (len=" << strlen(cstr) << ")" << endl;
    
    return 0;
}

// 完整程序：函数、递归与记忆化搜索
#include <bits/stdc++.h>
using namespace std;

// 传引用：直接修改原变量
void swap_ref(int& a, int& b) { int t = a; a = b; b = t; }

// 阶乘（递归）
long long factorial(int n) {
    if (n <= 1) return 1;  // 边界条件
    return n * factorial(n - 1);
}

// 记忆化搜索：斐波那契 O(n)
long long memo[100] = {0};
long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];
    return memo[n] = fib(n-1) + fib(n-2);
}

// 汉诺塔递归
int hanoiSteps = 0;
void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("%c -> %c\n", from, to); hanoiSteps++; return;
    }
    hanoi(n-1, from, aux, to);
    printf("%c -> %c\n", from, to); hanoiSteps++;
    hanoi(n-1, aux, to, from);
}

int main() {
    int a = 10, b = 20;
    swap_ref(a, b);
    cout << "swap: a=" << a << ", b=" << b << endl;  // a=20, b=10
    
    cout << "5! = " << factorial(5) << endl;         // 120
    cout << "fib(40) = " << fib(40) << endl;          // 102334155
    
    cout << "Hanoi(3):" << endl;
    hanoi(3, 'A', 'C', 'B');
    cout << "steps: " << hanoiSteps << endl;          // 7
    
    // 全排列
    vector<int> v = {1, 2, 3};
    cout << "Permutations: ";
    do {
        for (int x : v) cout << x;
        cout << " ";
    } while (next_permutation(v.begin(), v.end()));
    cout << endl;
    return 0;
}

// 完整程序：结构体、排序与引用
#include <bits/stdc++.h>
using namespace std;

struct Student {
    string name;
    int chinese, math, english;
    int total() const { return chinese+math+english; }
    bool operator < (const Student& o) const {
        if (total() != o.total()) return total() > o.total();
        return name < o.name;
    }
};

int main() {
    vector<Student> stu = {
        {"Alice",90,88,95},
        {"Bob",85,92,87},
        {"Carol",92,90,93},
        {"David",85,92,87}
    };
    sort(stu.begin(), stu.end());
    cout << "Ranking:" << endl;
    for (auto& s : stu)
        printf("  %s: %d (C:%d M:%d E:%d)\n",
               s.name.c_str(), s.total(), s.chinese, s.math, s.english);
    
    // 引用传参
    auto addOne = [](int& x) { x++; };
    int a = 10; addOne(a);
    cout << "addOne: " << a << endl;  // 11
    
    // 指针基础
    int* p = &a;
    cout << "*p = " << *p << endl;  // 11
    *p = 20;
    cout << "a = " << a << endl;    // 20
    
    return 0;
}

// 完整程序：STL 容器与算法综合演示
#include <bits/stdc++.h>
using namespace std;

int main() {
    // ===== vector 排序去重 =====
    vector<int> v = {3,1,4,1,5,9,2,6};
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(),v.end()), v.end());
    cout << "unique: ";
    for (int x : v) cout << x << " ";
    cout << endl;  // 1 2 3 4 5 6 9
    
    // ===== stack 括号匹配 =====
    string s = "(()())";
    stack<char> stk;
    bool ok = true;
    for (char c : s) {
        if (c == '(') stk.push(c);
        else if (!stk.empty()) stk.pop();
        else { ok = false; break; }
    }
    cout << (ok && stk.empty() ? "OK" : "FAIL") << endl;
    
    // ===== priority_queue 小顶堆 =====
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : {3,1,4,1,5}) pq.push(x);
    cout << "min-heap: ";
    while (!pq.empty()) { cout << pq.top(); pq.pop(); }
    cout << endl;  // 1 1 3 4 5
    
    // ===== map 词频统计 =====
    map<string, int> freq;
    for (auto w : {"apple","banana","apple"}) freq[w]++;
    for (auto& [k,v] : freq) cout << k << ":" << v << " ";
    cout << endl;
    
    // ===== lower_bound =====
    auto it = lower_bound(v.begin(), v.end(), 5);
    cout << "first>=5: " << *it << " at idx " << it-v.begin() << endl;
    return 0;
}

// 完整程序：线性结构综合演示
#include <bits/stdc++.h>
using namespace std;

int main() {
    // ===== 数组模拟栈 =====
    const int MAX = 1000;
    int stk[MAX], top = 0;
    stk[++top] = 10; stk[++top] = 20; stk[++top] = 30;
    cout << "stack pop: ";
    while (top > 0) cout << stk[top--] << " ";
    cout << endl;  // 30 20 10
    
    // ===== 数组模拟队列 =====
    int q[MAX], head = 0, tail = -1;
    q[++tail] = 1; q[++tail] = 2; q[++tail] = 3;
    cout << "queue pop: ";
    while (head <= tail) cout << q[head++] << " ";
    cout << endl;  // 1 2 3
    
    // ===== 链表实现（头插法）=====
    struct Node {
        int val; Node* next;
        Node(int v) : val(v), next(nullptr) {}
    };
    Node* headNode = nullptr;
    for (int i = 1; i <= 3; i++) {
        Node* n = new Node(i);
        n->next = headNode; headNode = n;
    }
    cout << "linked list: ";
    for (Node* p = headNode; p; p = p->next)
        cout << p->val << " -> ";
    cout << "null" << endl;  // 3 -> 2 -> 1 -> null
    
    while (headNode) { Node* t = headNode; headNode = headNode->next; delete t; }
    return 0;
}

// 完整程序：二叉树定义与四种遍历
#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// 前序遍历：根-左-右
void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

// 中序遍历：左-根-右
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

// 后序遍历：左-右-根
void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

// 层序遍历（BFS）
void levelorder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front(); q.pop();
        cout << cur->val << " ";
        if (cur->left)  q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

int main() {
    // 手动构建一棵二叉树
    //       1
    //      / \
    //     2   3
    //    / \   \
    //   4   5   6
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
    
    cout << "Preorder:  "; preorder(root); cout << endl;   // 1 2 4 5 3 6
    cout << "Inorder:   "; inorder(root); cout << endl;    // 4 2 5 1 3 6
    cout << "Postorder: "; postorder(root); cout << endl;  // 4 5 2 6 3 1
    cout << "Levelorder:"; levelorder(root); cout << endl;  // 1 2 3 4 5 6
    
    // 完全二叉树数组存储示例
    // root=1, i的左子=2i, i的右子=2i+1, i的父=i/2
    int tree[20] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    cout << "Array tree: node1=" << tree[1]
         << " left=" << tree[2] << " right=" << tree[3] << endl;
    return 0;
}