CSP-S 2026 复赛突击教材

为什么正确：按 d 排序后处理到 i 时，所有已选工作的截止时间都 ≤ d_i，因此"已选数量 ≤ d_i"是可行方案存在的充要条件（调度按截止时间从早到晚排即可）。堆中始终保持"当前 d 下的最优前 k 个收益"，被弹出的恰是最该放弃的。复杂度 O(n log n)。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<pair<long long, long long>> a(n);  // (d, p)
    for (int i = 0; i < n; i++) scanf("%lld %lld", &a[i].first, &a[i].second);
    sort(a.begin(), a.end());                  // 按截止时间排序
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long d = a[i].first, p = a[i].second;
        pq.push(p); ans += p;                  // 先贪心地"接下"
        if ((long long)pq.size() > d) {        // 超过 d 个时刻 → 必须反悔一个
            ans -= pq.top(); pq.pop();         // 踢掉收益最小的
        }
    }
    printf("%lld\n", ans);
    return 0;
}

走查一遍（4 个工作：(d,p) = (1,50)、(2,10)、(2,40)、(3,30)）：

第 3 步：先接下的工作②（报酬 10）在更优的工作③到来时被踢出——这就是"反悔"的具身化。

常见错误：① 忘开 long long（p ≤ 10⁹，n 个加起来爆 int）；② 误把条件写成 size() ≥ d——d 个时刻恰好能做 d 个工作。

题意：一排 n 个坑，收益 a[i]，选中的坑不相邻，最多选 k 个，求最大收益。

关键反悔设计：每次取全局最大 a[i] 并选中；随后把 i 与左右邻居从候选中删除，并插入一个新位置，其权值为 a[i-1] + a[i+1] − a[i]（可为负）。若之后选了这个新位置，等价于"撤销选 i，改选 i 的两个邻居"——恰好把不相邻约束修正回来。用双向链表维护左右邻居，大根堆 + 懒删除选最大。选 k 次取过程中最大累积和（收益为负时提前停止）。

复杂度：O(n log n)。对照：2025 社团招新的"按损失最小转出超编成员"本质就是这类反悔。

走查一遍（a = [3, 5, 2, 4]，至多 k = 2 棵）：

验证：不相邻选法中 {②,④} = 5+4 = 9 确为最大收益。

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string s; cin >> s;
    string t = "^#";
    for (char c : s) { t += c; t += '#'; }
    t += '$';                              // 哨兵保证 while 不越界
    int n = t.size(), C = 0, R = 0, ans = 0;
    vector<int> p(n, 0);
    for (int i = 1; i < n - 1; i++) {
        p[i] = (i < R) ? min(R - i, p[2 * C - i]) : 0;
        while (t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++;   // 暴力扩展
        if (i + p[i] > R) { C = i; R = i + p[i]; }           // 更新最右回文
        ans = max(ans, p[i]);
    }
    cout << ans << "\n";
    return 0;
}

走查一遍（s = "abba"，t = "^#a#b#b#a#$"，p[i] 为臂长，原串回文长度 = p[i]）：

i = 5 处理完后 R 推到 9，此后 i = 6~9 全部从镜像位置直接抄答案、零扩展——这就是 O(n) 的来源。

易错点：① 哨兵字符必须与 # 及所有字母不同（^ 和 $）；② 千万别写 cin 不关同步（1e7 数据会 TLE）；③ 若题目问"原串中的回文位置"，中心 i 在原串的坐标是 (i−2)/2，长度即 p[i]。

组合训练：会模板后做"回文划分计数"——f[i] = Σ f[j]（若 s[j..i] 是回文），用 Manacher/哈希 O(n²) 或 Eertree O(n) 实现，是 2026 最可能的出题方式。

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;                       // 模式串总长 + 1
int ch[N][26], fail[N], idx = 0;            // Trie（已做转移压缩）
int pos[N]; long long cnt[N]; int q[N];
int insert_(const char *s, int id) {
    int u = 0;
    for (; *s; s++) {
        int v = *s - 'a';
        if (!ch[u][v]) ch[u][v] = ++idx;
        u = ch[u][v];
    }
    return pos[id] = u;
}
void build() {                              // BFS 建 fail + 转移压缩
    int h = 0, t = 0;
    for (int c = 0; c < 26; c++) if (ch[0][c]) q[t++] = ch[0][c];
    while (h < t) {
        int u = q[h++];
        for (int c = 0; c < 26; c++) {
            int v = ch[u][c];
            if (v) { fail[v] = ch[fail[u]][c]; q[t++] = v; }
            else    ch[u][c]  = ch[fail[u]][c];
        }
    }
}
int main() {
    int n; scanf("%d", &n);
    static char buf[200006];                     // 单个模式串长度 ≤ 2e5
    for (int i = 0; i < n; i++) { scanf("%s", buf); insert_(buf, i); }
    build();
    static char text[2000006]; scanf("%s", text);
    int u = 0;
    for (char *p = text; *p; p++) { u = ch[u][*p - 'a']; cnt[u]++; }   // 只打标记
    // q[0..idx-1] 为 BFS 序（共 idx 个非根节点），倒序累加 = fail 树自底向上求子树和
    for (int i = idx - 1; i >= 0; i--) cnt[fail[q[i]]] += cnt[q[i]];
    for (int i = 0; i < n; i++) printf("%lld\n", cnt[pos[i]]);
    return 0;
}

走查一遍（模式串 {he, she}，文本 "ushers"）：

期望输出：he → 1，she → 1。若逐次跳 fail 链统计，a…a 型数据会被卡成 O(n²)——子树和的意义就在于此。

复杂度：O(Σ|模式| × 26 + |文本|)。易错点：① 累加必须沿 BFS 序逆序（fail[u] 的 BFS 序小于 u）；② 二次加强卡常，读入用 scanf/快读；③ cnt 开 long long（大文本同一位置可被统计多次）。

进阶对照（P3796 最出现次数的模式串）：同样的 cnt 统计，最后扫一遍 end 节点取 max，注意"重复答案按输入序输出"。套路完全一致。

#include <bits/stdc++.h>
using namespace std;
int n, w[20][20], dp[1 << 20][20];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &w[i][j]);
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;                                   // 只访问过起点
    for (int S = 1; S < (1 << n); S++)
        for (int i = 0; i < n; i++) {
            if (!(S >> i & 1) || dp[S][i] == 0x3f3f3f3f) continue;
            for (int j = 0; j < n; j++)
                if (!(S >> j & 1))
                    dp[S | 1 << j][j] = min(dp[S | 1 << j][j], dp[S][i] + w[i][j]);
        }
    int ans = INT_MAX;
    for (int i = 0; i < n; i++) ans = min(ans, dp[(1 << n) - 1][i] + w[i][0]);
    printf("%d\n", ans);
    return 0;
}

走查一遍（n = 3，距离矩阵 w：0↔1 为 1，1↔2 为 3，0↔2 为 2）：

两条回路 0→1→2→0 与 0→2→1→0 长度相同，都是 6。注意最后一步"+ w[i][0] 回起点"不能漏。

易错点：① 枚举 S 时内层直接跳过不合法状态（上面写法已保证）；② 内存 2^20×20×4B ≈ 84MB，若 MLE 用滚动数组或把 dp 压成 dp[S] 为 vector；③ 实际考点常变形为"2^k 枚举 + MST"（道路修复型），TSP 是打基础。

bitset 练手（P2709 小 B 的询问 · 要点）：莫队 + 桶统计，把"某颜色出现次数是否为奇数/平方贡献"用 bitset 维护，体会"位运算压集合"的写法即可，不必追求满分。

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
long long sz[N], f[N];
int n;
void dfs1(int u, int fa, long long d) {          // 算子树大小与 f[1]
    sz[u] = 1; f[1] += d;
    for (int v : g[u]) if (v != fa) { dfs1(v, u, d + 1); sz[u] += sz[v]; }
}
void dfs2(int u, int fa) {                       // 换根递推
    for (int v : g[u]) if (v != fa) {
        f[v] = f[u] + (long long)(n - sz[v]) - sz[v];
        dfs2(v, u);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i < n; i++) { scanf("%d%d", &x, &y); g[x].push_back(y); g[y].push_back(x); }
    dfs1(1, 0, 0); dfs2(1, 0);
    long long best = LLONG_MAX; int id = 0;
    for (int i = 1; i <= n; i++)
        if (f[i] < best) { best = f[i]; id = i; }    // 顺序遍历 → 天然取最小编号
    printf("%d %lld\n", id, best);
    return 0;
}

走查一遍（链 1—2—3，n = 3）：第一遍 dfs 得 sz = [3,2,1]（1 号起）、f[1] = 深度和 0+1+2 = 3；第二遍换根：f[2] = f[1] + (3−2) − 2 = 2，f[3] = f[2] + (3−1) − 1 = 3。最小距离和 2 在村庄 2 ✓（中间点开会更公平，符合直觉）。

易错点：① 链形树下距离和最大约 n²/2 ≈ 1.3×10⁹（n ≤ 5×10⁴），已逼近 int 上限，稳妥起见用 long long；② 递归深度——若 n 达 10⁶ 级别需改成 BFS/迭代栈（考场上 NOI Linux 栈与内存限制相同，一般安全，但要有意识）；③ "同值取最小编号"这类输出细节是真实考点。

进阶对照（P3047 Nearby Cows · 要点）：求每个点周围 k 步内的权和——维护"向上 i 层祖先的子树和"的前缀套 DP（f[u][j] 覆盖子树内、g[u][j] 覆盖子树外），体会"子树内 + 子树外"的拆分。

方向推导（务必自己画圈验证）：朝内的玩具，"左边"是逆时针方向（下标减小）；朝外的玩具，"左边"反而是顺时针（下标增大）。归纳：face 与 dir 相同 → 下标减 s；不同 → 下标加 s。

走查一遍（n = 4，face = [0,1,0,1]，从 0 号出发，指令：(0 左, s=1)、(1 右, s=2)）：

最终停在 1 号玩具。减法分支后的 + n 再 % n 是防负数的关键。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; scanf("%d%d", &n, &m);
    vector<int> face(n); vector<string> name(n);
    for (int i = 0; i < n; i++) {
        char s[12]; scanf("%d %s", &face[i], s); name[i] = s;
    }
    int pos = 0;
    while (m--) {
        int dir; long long s; scanf("%d%lld", &dir, &s);
        if (dir == face[pos]) pos = ((pos - s % n) % n + n) % n;   // 同向：逆着编号走
        else                  pos = (pos + s) % n;
    }
    printf("%s\n", name[pos].c_str());
    return 0;
}

易错点：① s 可达 10⁹，先模 n 再运算，且减法后要 +n 防负；② "同向相减"记错方向就全错——考场上用样例验证（样例一定能检验方向规则）；③ 面向 2026：真正的考场大模拟（结构体/儒略日级别）会把本题材放大 10 倍，务必练"规则清单 + 分函数 + 对拍"三件套。

进阶对照（P1514 引水入城 · 要点）：第一问 BFS 可达性；第二问把"每个第一行点能覆盖的最后一段区间"求出后做区间覆盖贪心——与 2024 超速检测的区间选点同族，模拟+贪心复合是流行出题法。

容斥推导：设 A_i = "第 i 种硬币用量 ≥ d_i+1" 的方案集合。答案 = |无任何 A_i| = Σ_{S⊆{1,2,3,4}} (−1)^|S| · g(s − Σ_i∈S(d_i+1)c_i)，其中 g(x) 为无上限时凑出 x 的方案数（完全背包预处理）。金额为负时该项为 0。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[100005]; int c[4], d[4];
int main() {
    for (int i = 0; i < 4; i++) scanf("%d", &c[i]);
    f[0] = 1;
    for (int i = 0; i < 4; i++)                 // 完全背包：无上限方案数
        for (int x = c[i]; x <= 100000; x++) f[x] += f[x - c[i]];
    int q; scanf("%d", &q);
    while (q--) {
        for (int i = 0; i < 4; i++) scanf("%d", &d[i]);
        ll s, ans = 0; scanf("%lld", &s);
        for (int S = 0; S < 16; S++) {          // 2^4 枚举越界集合
            ll t = s; int bits = 0;
            for (int i = 0; i < 4; i++)
                if (S >> i & 1) { t -= (ll)(d[i] + 1) * c[i]; bits++; }
            if (t >= 0) ans += (bits & 1 ? -1 : 1) * f[t];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

走查一遍（c = [1,2,3,4]，询问 d = [2,1,0,0]，s = 4；预处理得 f[0]=1、f[1]=1、f[4]=5）：

无上限的 5 种凑法逐一被 4 个"单条件越界"项排除——容斥就是这样"先全算、再逐个扣掉犯规的"。

易错点：① (d+1)·c 可能溢出 int → long long；② 符号 (−1)^{|S|} 别写反；③ f[t] 本身就是 ll，无需再取模（本题不取模，若考场题要求取模则全程取模）。本题是"容斥 + 多维约束计数"的最小完整模型，直接对标 2025 T4 的思维框架。

进阶对照（P7914 括号序列 · 要点）：区间 DP 防重技巧——f[l][r]（两端匹配）与 g[l][r]（整体合法但不匹配），并列拼接时"规定最后一段是完整匹配段"来去重；转移枚举中间 * 段长度 ≤ k。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
struct Node { int cnt; ll len; } t[8 * N];      // 离散化后最多 2n-1 ≈ 2e5 段 → 需 8e5 节点
struct Ev { ll x, y1, y2; int v; };              // v=+1 进 -1 出
vector<Ev> ev; vector<ll> ys;
void pushup(int u, int l, int r) {
    if (t[u].cnt) t[u].len = ys[r + 1] - ys[l];  // 整段被覆盖
    else t[u].len = (l == r) ? 0 : t[u*2].len + t[u*2+1].len;
}
void update(int u, int l, int r, int ql, int qr, int v) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { t[u].cnt += v; pushup(u, l, r); return; }
    int m = (l + r) / 2;
    update(u*2, l, m, ql, qr, v); update(u*2+1, m+1, r, ql, qr, v);
    pushup(u, l, r);
}
int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        ll x1, y1, x2, y2; scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
        ev.push_back({x1, y1, y2, 1}); ev.push_back({x2, y1, y2, -1});
        ys.push_back(y1); ys.push_back(y2);
    }
    sort(ev.begin(), ev.end(), [](auto&a, auto&b){ return a.x < b.x; });
    sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
    int m = ys.size() - 1;                       // m 段
    ll ans = 0, lastX = ev[0].x;
    for (auto &e : ev) {
        ans += t[1].len * (e.x - lastX);         // 上一状态覆盖了 (lastX, e.x)
        int l = lower_bound(ys.begin(), ys.end(), e.y1) - ys.begin();
        int r = lower_bound(ys.begin(), ys.end(), e.y2) - ys.begin() - 1;
        if (l <= r) update(1, 0, m - 1, l, r, e.v);
        lastX = e.x;
    }
    printf("%lld\n", ans);
    return 0;
}

走查一遍（矩形 A：x∈[0,3)、y∈[0,2)；矩形 B：x∈[2,5)、y∈[1,3)）：

x=2 处的贡献用的是 B 进入之前的覆盖长 2——"先算旧状态、再更新"的顺序一眼可见。

易错点：① 线段树叶子对应段 [ys[i], ys[i+1])，右边界查询要 −1；② 面积累加放在"处理事件前"用旧 len 乘 Δx；③ 坐标 1e9 必须 ll；④ 周长并（P1856）还需维护覆盖段数与左右端点，是本题的加练变式。