05 · 回顾一：基础语法综合训练

对每种包装单独结算：包数 × 价格，就是“只用这一种包装”的总花费。

包数 = n ÷ 每包支数 向上取整。整数除法的写法是 (n + p - 1) / p：先补到“刚好差一点点也进一”。

三种花费取 min，就是答案。

为什么不能“先挑单价最低的”？单价不是整数，而且凑包会浪费；n=57 时第三种包装单价更低、浪费更多，但总价仍然最低——只有结算总价才能比较。

复杂度 O(1)，只看 3 组数据。int 足够：包数 ≤ 10⁴，花费 ≤ 10⁸。

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

int main() {
    int n;
    cin >> n;

    int best = INT_MAX;               // 擂主：int 的最大值，保证第一次一定被替换
    for (int i = 0; i < 3; ++i) {
        int p, c;
        cin >> p >> c;                // p 支一包，c 元一包
        int packs = (n + p - 1) / p;  // 向上取整：不足一包也要买一包
        best = min(best, packs * c);  // 三种包装各自结算，取最小
    }
    cout << best << "\n";
    return 0;
}

第 k 条斜线有 k 个数，前 k 条一共 k(k+1)/2 个数。所以找最小的 k 使 k(k+1)/2 ≥ N，它就在第 k 条斜线上。

第 k 条斜线之前的数是 k(k-1)/2 个，于是 N 在这条斜线上是第 pos = N − k(k-1)/2 个（从 1 数）。

同一条斜线上分子 + 分母 = k+1。k 为偶数时分子从 1 递增，分子 = pos；k 为奇数时分子从 k 递减，分子 = k+1−pos。分母由和减去分子得到。

验证：N=7。k=3 时 3×4/2=6 < 7，k=4 时 4×5/2=10 ≥ 7，所以在第 4 条斜线；pos = 7 − 4×3/2 = 1；k 是偶数，分子 1、分母 4 → 1/4。

复杂度：k 最大约 4472，循环几千次，O(√N)，10⁷ 的 N 瞬间出结果。

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

int main() {
    long long n;
    cin >> n;

    long long k = 1;
    while (k * (k + 1) / 2 < n) ++k;       // 找到 N 所在的斜线编号 k

    long long pos = n - k * (k - 1) / 2;   // 在这条斜线上是第几个（从 1 数）
    long long a, b;                        // a 分子，b 分母
    if (k % 2 == 0) {                      // 偶数斜线：分子 1,2,3,...
        a = pos;
        b = k + 1 - pos;
    } else {                               // 奇数斜线：分子 k,k-1,...
        a = k + 1 - pos;
        b = pos;
    }
    cout << a << "/" << b << "\n";
    return 0;
}

开一个数组 cut[0..l]，cut[i] = 1 表示第 i 米处那棵树已被移走，初值全 0。

每读入一个区间 [u,v]，就 for (j = u; j <= v; ++j) cut[j] = 1。

全部区间处理完后，统计 cut[j] == 0 的个数，就是剩下的树。

为什么用标记法而不是“总长度减并集长度”：并集要判断重叠，而标记法把“砍两次”自动压成“砍一次”，重叠问题根本不存在。

复杂度 O(l·m) = 10⁴ × 100 = 10⁶，稳过 1 秒。

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

int cut[10005];                  // cut[i] = 1 表示第 i 米处的树被移走

int main() {
    int l, m;
    cin >> l >> m;

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        for (int j = u; j <= v; ++j) cut[j] = 1;   // 端点也要砍，所以是 <=
    }

    int ans = 0;
    for (int j = 0; j <= l; ++j)                   // 0..l 一共 l+1 棵树
        if (cut[j] == 0) ++ans;

    cout << ans << "\n";
    return 0;
}

外层枚举 i = 1 … n，内层把 i 的每一位拆出来，等于 x 就加一。

拆位三件套：t % 10 取末位，t /= 10 去掉末位，循环到 t == 0 为止。

关键：拆位一定要用副本 t = i，否则会把外层循环变量 i 改成 0，直接死循环。

复杂度 O(n log n)：10⁶ 个数平均 6~7 位，约 7×10⁶ 次操作，过。

答案最大约 6×10⁶，int 够用；若 n 改成 10⁹ 就必须 long long。

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

int main() {
    int n, x;
    cin >> n >> x;

    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        int t = i;                     // 用副本拆位，绝不能动 i
        while (t > 0) {
            if (t % 10 == x) ++cnt;    // 末位等于 x 就计数
            t /= 10;                   // 砍掉末位：123 -> 12 -> 1 -> 0
        }
    }
    cout << cnt << "\n";
    return 0;
}

把“A 出 i、B 出 j 时 A 是否赢”做成一张 5×5 的表，值为 1 表示 A 赢。

5×5 的表按行拼成一个长度 25 的一维数组：第 i 行第 j 列存在 W[i*5 + j]。这样只用一维数组，不用等后面的二维数组。

第 k 拳（k 从 0 数）：x = a[k % nA]，y = b[k % nB]。若 W[x*5+y] 则 A 得分；否则若 W[y*5+x] 则 B 得分；两个都不成立就是平局，两人都不加分。

为什么用表而不是 if：胜负关系有 10 组，if 分支至少 10 个，漏一个就 WA 且很难查；表只有 25 个数字，能逐行核对（每行恰好 2 个 1，全表 10 个 1）。

复杂度 O(N)，N ≤ 200，几乎不耗时。

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

// W[i*5+j] == 1 表示：小 A 出 i、小 B 出 j 时，A 赢
// 0 剪刀   1 石头   2 布   3 蜥蜴人   4 斯波克
const int W[25] = {
    0, 0, 1, 1, 0,        // 剪刀 胜 布、蜥蜴人
    1, 0, 0, 1, 0,        // 石头 胜 剪刀、蜥蜴人
    0, 1, 0, 0, 1,        // 布   胜 石头、斯波克
    0, 0, 1, 0, 1,        // 蜥蜴人 胜 布、斯波克
    1, 1, 0, 0, 0         // 斯波克 胜 剪刀、石头
};

int a[205], b[205];

int main() {
    int n, na, nb;
    cin >> n >> na >> nb;

    for (int i = 0; i < na; ++i) cin >> a[i];
    for (int i = 0; i < nb; ++i) cin >> b[i];

    int sa = 0, sb = 0;
    for (int k = 0; k < n; ++k) {
        int x = a[k % na];             // 周期序列：第 k 拳 = 周期的第 k%na 项
        int y = b[k % nb];
        if (W[x * 5 + y])      ++sa;   // 查表：A 赢
        else if (W[y * 5 + x]) ++sb;   // 交换顺序再查：B 赢
        // 都不成立就是平局，两人都不加分，不必写分支
    }
    cout << sa << " " << sb << "\n";
    return 0;
}