P1003 [NOIP 2011 提高组] 铺地毯

题目描述

为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 $n$ 张地毯，编号从 $1$ 到 $n$。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

输入格式

输入共 $n + 2$ 行。

第一行，一个整数 $n$，表示总共有 $n$ 张地毯。

接下来的 $n$ 行中，第 $i+1$ 行表示编号 $i$ 的地毯的信息，包含四个整数 $a ,b ,g ,k$，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标 $(a, b)$ 以及地毯在 $x$ 轴和 $y$ 轴方向的长度。

第 $n + 2$ 行包含两个整数 $x$ 和 $y$，表示所求的地面的点的坐标 $(x, y)$。

输出格式

输出共 $1$ 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出 -1。

输入输出样例 #1

输入 #1

输出 #1

1
2

输入输出样例 #2

输入 #2

输出 #2

-1

说明/提示

【样例解释 1】

如下图，$1$ 号地毯用实线表示，$2$ 号地毯用虚线表示，$3$ 号用双实线表示，覆盖点 $(2,2)$ 的最上面一张地毯是 $3$ 号地毯。

【数据范围】

对于 $30\%$ 的数据，有 $n \le 2$。
对于 $50\%$ 的数据，$0 \le a, b, g, k \le 100$。
对于 $100\%$ 的数据，有 $0 \le n \le 10^4$, $0 \le a, b, g, k \le {10}^5$。

noip2011 提高组 day1 第 $1$ 题。

思路分析

最聪明（傻波一）的一集

“哎呀， 1e5 爆了，偷偷改成 2.3e4 吧” ：

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 2.3e4;
int p[MAXN][MAXN];
int main() {
    int n, a, b, g, k, x, y;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d %d", &a, &b, &g, &k);
        g += a;
        k += b;
        for (; a <= g; a++)
            for (; b <= k; b++)
                p[a][b] = i;
    }
    cin >> x >> y;
    if (p[x][y] == 0)
        cout << -1;
    else
        cout << p[x][y];
    return 0;
}

~~喜提 50 pt 。~~

正解

记录矩形的四个参数，再扫一遍数组，通过检查坐标 (x,y) 是否在矩形 $Rect_i$ 内，更新最上面的地毯。

代码实现

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e4 + 5;
struct Rect {
    int x, y, a, b;
} a[MAXN];
int main() {
    int n, x, y, ans = -1;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y >> a[i].a >> a[i].b;
    cin >> x >> y;
    for (int i = 1; i <= n; i++) {
        int tx = a[i].x + a[i].a, ty = a[i].y + a[i].b;
        if (x >= a[i].x && x <= tx && y >= a[i].y && y <= ty)
            ans = i;
    }
    cout << ans;
    return 0;
}

P4933 大师

题目背景

建筑大师最近在跟着数学大师 ljt12138 学数学，今天他学了等差数列，ljt12138 决定给他留一道练习题。

题目描述

ljt12138 首先建了 $n$ 个特斯拉电磁塔，这些电塔排成一排，从左到右依次标号为 $1$ 到 $n$，第 $i$ 个电塔的高度为 $h[i]$。

建筑大师需要从中选出一些电塔，然后这些电塔就会缩到地下去。这时候，如果留在地上的电塔的高度，从左向右构成了一个等差数列，那么这个选择方案就会被认为是美观的。

建筑大师需要求出，一共有多少种美观的选择方案，答案模 $998244353$。

注意，如果地上只留了一个或者两个电塔，那么这种方案也是美观的。地上没有电塔的方案被认为是不美观的。

同时也要注意，等差数列的公差也可以为负数。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个非负整数，第 $i$ 个整数是第 $i$ 个电塔的高度 $h[i]$。

输出格式

输出一个整数，表示美观的方案数模 $998244353$ 的值。

输入输出样例 #1

输入 #1

1 2	8 13 14 6 20 27 34 34 41

输出 #1

输入输出样例 #2

输入 #2

1
2

100
90 1004 171 99 1835 108 81 117 141 126 135 144 81 153 193 81 962 162 1493 171 1780 864 297 180 532 1781 189 1059 198 333 1593 824 207 1877 216 270 225 1131 336 1875 362 234 81 288 1550 243 463 1755 252 406 261 270 279 288 1393 261 1263 297 135 333 872 234 881 180 198 81 225 306 180 90 315 81 81 198 252 81 297 1336 1140 1238 81 198 297 661 81 1372 469 1132 81 126 324 333 342 81 351 481 279 1770 1225 549

输出 #2

说明/提示

设 $v$ 为最高的电塔高度。

对于前 $30\%$ 的数据，$n \le 20 $。

对于前 $60\%$ 的数据，$n \le 100$，$v \le 2 \times 10^3$。

对于另外 $20\%$ 的数据，所有电塔的高度构成一个等差数列。

对于 $100\%$ 的数据，$n \le 10^3$，$v \leq2 \times 10^4$。

思路分析

状态设计：用 dp[i][d + MAXV] 表示以第 i 个数为结尾的，长度不小于 2 的公差为 d 的等差数列数。

技巧：这里用一个偏移量实现了负数数组。

转移方程：

$dp[i][h[i]-h[j]] = \sum_{j<i} (dp[j][h[i]-h[j]] + 1)$

代码实现

这是一开始的代码（有错误）：

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e3 + 5;
constexpr int MAXV = 2e4 + 5;
constexpr int MOD = 998244353;
int dp[MAXN][MAXV * 2], h[MAXN];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> h[i];
        for(int j = 1; j < i; j++) {
            dp[i][h[i] - h[j] + MAXV] += 1 + dp[j][h[i] - h[j] + MAXV];
            dp[i][h[i] - h[j] + MAXV] %= MOD;
            ans += dp[i][h[i] - h[j] + MAXV];
            ans %= MOD;
        }
    }
    cout << (ans + n) % MOD; // 加上单个数的数列
    return 0;
}

上面代码的错误在于 dp[i][d] 是累加的。当处理不同的 j 值时，dp[i][d] 会不断增加。

原代码的统计方式 ans += dp[i][d] 只在 dp[i][d] 只被更新一次情况正确；但一般情况下，同一个公差 d 被更新多次，这时原代码就会重复统计。

正确的做法应该只统计新增的方案数，而不是每次加当前总和：

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e3 + 5;
constexpr int MAXV = 2e4 + 5;
constexpr int MOD = 998244353;
int dp[MAXN][MAXV * 2], h[MAXN];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> h[i];
        for(int j = 1; j < i; j++) {
            int add = 1 + dp[j][h[i] - h[j] + MAXV]; // 从 j 到 i 新增的等差数列数
            dp[i][h[i] - h[j] + MAXV] += add; // 累加到 dp[i][d]
            dp[i][h[i] - h[j] + MAXV] %= MOD;
            ans = (ans + add) % MOD; // 只加新增的部分，不是加 dp[i][d]
        }
    }
    cout << (ans + n) % MOD; // 加上单个数的数列
    return 0;
}

P2196 [NOIP 1996 提高组] 挖地雷

题目描述

在一个地图上有 $N\ (N \le 20)$ 个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后每次可以移动到一个编号比当前节点大且联通的节点去挖地雷，当无满足条件的节点时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入格式

有若干行。

第 $1$ 行只有一个数字，表示地窖的个数 $N$。

第 $2$ 行有 $N$ 个数，分别表示每个地窖中的地雷个数。

第 $3$ 行至第 $N+1$ 行表示地窖之间的连接情况：

第 $3$ 行有 $n-1$ 个数（$0$ 或 $1$），表示第一个地窖至第 $2$ 个、第 $3$ 个 $\dots$ 第 $n$ 个地窖有否路径连接。如第 $3$ 行为 $1\space 1\space 0\space 0\space 0\cdots 0$，则表示第 $1$ 个地窖至第 $2$ 个地窖有路径，至第 $3$ 个地窖有路径，至第 $4$ 个地窖、第 $5$ 个 $\dots$ 第 $n$ 个地窖没有路径。

第 $4$ 行有 $n-2$ 个数，表示第二个地窖至第 $3$ 个、第 $4$ 个 $\dots$ 第 $n$ 个地窖有否路径连接。

……

第 $n+1$ 行有 $1$ 个数，表示第 $n-1$ 个地窖至第 $n$ 个地窖有否路径连接。（为 $0$ 表示没有路径，为 $1$ 表示有路径）。

输出格式

第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。

第二行只有一个数，表示能挖到的最多地雷数。

输入输出样例 #1

输入 #1

输出 #1

1 2	1 3 4 5 27

说明/提示

【样例解释】
最优路径为 $1 \to 3 \to 4 \to 5$，结果为 $27$。

【题目来源】
NOIP 1996 提高组第三题。

思路分析 + 代码实现

地窖之间依据编号（从小到大）构成一个 DAG ，相当于一个在有向无环图（DAG）上求最长路径的问题，每个节点有正权值（地雷数）。所以一开始想到的是拓扑排序，用 BFS 解决，代码如下：

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 25;
vector<int> G[MAXN];
int a[MAXN];
struct State{
    int u, cnt;
    vector<int> rec;
};
int main(){
    int N, ans = 0;
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> a[i];
    for(int t, i = 1; i < N; i++)
        for(int j = i + 1; j <= N; j++) {
            cin >> t;
            if (t) G[i].push_back(j);
        }
    vector<int> ans_rec;
    queue<State> Q;
    for(int i = 1; i <= N; i++) {
        State t = {i, a[i]};
        t.rec.push_back(i);
        Q.push(t);
    }
    while (!Q.empty()) {
        State now = Q.front();
        Q.pop();
        if (now.cnt > ans) {
            ans = now.cnt;
            ans_rec.clear();
            ans_rec = now.rec;
        }
        for(int v : G[now.u]) {
            State t = now;
            t.u = v;
            t.rec.push_back(v);
            t.cnt += a[v];
            Q.push(t);
        }
    }
    for(int i : ans_rec)
        cout << i << " ";
    cout << "\n" << ans;
    return 0;
}

当然也可以用记忆化搜索，时间复杂度 $O(n^2)$ ，代码如下：

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 25;
bool connected[MAXN][MAXN];
int a[MAXN], dp[MAXN], N;
int dfs(int x) {
    if (dp[x]) return dp[x];
    int t = 0;
    for(int i = x + 1; i <= N; i++)
        if (connected[x][i])
            t = max(t, dfs(i));
    return dp[x] = a[x] + t;
}
int main() {
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> a[i];
    for(int i = 1; i < N; i++)
        for(int j = i + 1; j <= N; j++)
            cin >> connected[i][j];
    int ans = 0;
    for(int i = 1; i <= N; i++)
        ans = max(ans, dfs(i));
    for(int i = 1; i <= N; i++)
        if (dp[i] == ans) {
            cout << i << " ";
            for(int j = i + 1; j <= N; j++)
                if (connected[i][j] && dp[i] == a[i] + dp[j])
                    cout << (i = j) << " "; // 输出与赋值合并
        }
    cout << "\n" << ans;
    return 0;
}

注意根据答案推路径的细节。

当然， DP 更加简洁，设 $dp[i]$ 表示以地窖 $i$ 为起点能挖到的最大地雷数。

对于每个地窖 $i$，考虑它所有能到达的后续节点 $j$（满足 $j > i$ 且 $connected[i][j] = 1$）则状态转移方程为：

$dp[i] = a[i] + \max_{j>i \&\& connected[i][j]} dp[j]$

DP 部分代码如下（其他与 DFS 做法相同）：

for(int i = N; i >= 1; i--) {
    dp[i] = a[i];
    for(int j = N; j > i; j--)
        if (connected[i][j])
            dp[i] = max(dp[i], a[i] + dp[j]);
    ans = max(ans, dp[i]);
}

P14826 踩踩标

发表于 2025-12-22 更新于 2026-01-11

P14826 踩踩标

题目描述

现在题库里有 $n$ 道题，你想要刷穿整个题库。你会按以下过程进行训练：

套题训练：打 $b$ 场每场有 $a$ 题的模拟赛。模拟赛可以提升你的效率，你打完所有模拟赛后的思维能力提升 $a+b$ 点。显然，这些比赛的题目不会重合，总题数也不会超过 $n$ 道。
单题训练：对于没有被刷过的每道题目，你都可以提升 $k$ 点思维能力。

由于你很颓，所以你想知道在所有 $a,b$ 中，最少可以让你提升多少点思维能力。

形式化题意：给定 $n,k$，求所有使得 $n=ab+c$ 的自然数三元组 $(a,b,c)$ 中，$a+b+kc$ 的最小值。

输入格式

本题单个测试点内包含多组测试数据。

第一行一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行两个整数 $n,k$，代表一组测试数据。

输出格式

对于每组测试数据输出一行，即最少的提升点数。

输入输出样例 #1

输入 #1

输出 #1

1
2
3

15
2
0

说明/提示

样例解释

对于第一组测试数据，组 $7$ 场每场有 $7$ 道题的比赛，并进行 $1$ 次单题训练。总提升为 $7+7+1=15$ 点。可以证明不存在提升更少的方案。

对于第三组测试数据，直接进行单题训练不会提升思维能力。

数据范围

记单个测试点内 $n$ 的总和为 $N$。

对于 $100\%$ 的数据，保证 $1\le T\le 10^5$，$1\le n,N\le 10^{12}$，$0\le k\le 10^6$。

测试点编号	$N\le$	特殊性质
$1,2$	$1000$	无
$3,4$	$10^6$	无
$5,6$	$10^{12}$	有
$7\sim 10$	$10^{12}$	无

特殊性质：$n$ 为完全平方数。

问题简述

给定 $n,k$，求所有自然数 $(a,b,c)$ 满足 $n = a \times b + c$ 时，$a + b + k \cdot c$ 的最小值。

核心思路

1. 特判 $k = 0$

若 $k = 0$，可取 $a = b = 0,\ c = n$，得 $a + b + k \cdot c = 0$，直接输出 0。

2. 一般情况 ($k > 0$)

对于固定的 $a$，为了最小化 $a + b + k \cdot c$，应让 $b$ 尽量大（从而 $c$ 尽量小），因为 $k > 0$。
因此最优 $b = \lfloor n/a \rfloor$，对应 $c = n - a \cdot b$。

关键问题：为什么需要两个循环？

疑问：$a$ 和 $b$ 都是乘法的因数，看起来对称，为什么不能只枚举 $a \le \sqrt{n}$？

原因：目标函数中的 $c$ 取决于 被除数 $a$（或 $b$）的余数，而不仅仅是乘积 $a \cdot b$。

具体来说：

当我们枚举 $a$ 时，计算 $b = \lfloor n/a \rfloor$，余数 $c = n \% a$。
当我们枚举 $b$ 时，计算 $a = \lfloor n/b \rfloor$，余数 $c = n \% a$。

这两者不同：$n \% a$ 与 $n \% b$ 一般不相等。
因此，只枚举 $a \le \sqrt{n}$ 会漏掉那些 $a > \sqrt{n}$ 但 $n \% a$ 很小的情况。

例子说明

设 $n = 10$，$k = 1$。

若只枚举 $a \le \sqrt{10} \approx 3$：
- $a=1,\ b=10,\ c=0$ → 值 $1+10+0=11$
- $a=2,\ b=5,\ c=0$ → 值 $2+5+0=7$
- $a=3,\ b=3,\ c=1$ → 值 $3+3+1=7$
  最优值为 $7$。
但考虑 $a=9$（$> \sqrt{10}$）：
- $b = \lfloor 10/9 \rfloor = 1$
- $c = 10 \% 9 = 1$
- 值 $9+1+1=11$，不如 $7$ 优。

这个例子中 $a> \sqrt{n}$ 没有更优，但可能存在其他 $n,k$ 使 $a> \sqrt{n}$ 更优。

覆盖所有情况的技巧

对于任意 $(a,b)$，至少有一个 $\le \sqrt{n}$（因为若 $a > \sqrt{n}$ 且 $b > \sqrt{n}$，则 $a \cdot b > n$，矛盾）。
因此：

第一层循环：枚举 $a = 1 \dots \sqrt{n}$，计算 $b = \lfloor n/a \rfloor$，更新答案。
第二层循环：枚举 $b = 1 \dots \sqrt{n}$，计算 $a = \lfloor n/b \rfloor$，更新答案。

这两个循环合起来，所有可能的 $(a,b)$ 对都被覆盖。

算法步骤

若 $k = 0$，输出 0。
初始化答案 ans = n * k（对应 $a = b = 0$）。
循环 $a$ 从 $1$ 到 $\sqrt{n}$：
- $b = n / a$（整除）
- $c = n - a * b$
- ans = min(ans, a + b + c * k)
循环 $b$ 从 $1$ 到 $\sqrt{n}$：
- $a = n / b$（整除）
- $c = n - a * b$
- ans = min(ans, a + b + c * k)
输出 ans。

代码（简洁版）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long T, n, k;
    cin >> T;
    while (T--) {
        cin >> n >> k;
        if (k == 0) { cout << "0\n"; continue; }
        long long ans = n * k;
        for (long long a = 1; a * a <= n; a++) {
            long long b = n / a, c = n - a * b;
            ans = min(ans, a + b + c * k);
        }
        for (long long b = 1; b * b <= n; b++) {
            long long a = n / b, c = n - a * b;
            ans = min(ans, a + b + c * k);
        }
        cout << ans << "\n";
    }
    return 0;
}

时间复杂度

每组数据循环 $2\sqrt{n}$ 次，即 $O(\sqrt{n})$。
$n \le 10^{12}$ 时 $\sqrt{n} \le 10^6$，可接受。

总结

两个循环分别枚举 $a$ 和 $b$，确保所有 $(a,b)$ 对都被检查。
核心原因是余数 $c$ 依赖于被除数，而 $a,b$ 在余数计算中不等价。

P3367 【模板】并查集

发表于 2025-12-21 更新于 2026-01-11

P3367 【模板】并查集

题目背景

本题数据范围已经更新到 $1\le N\le 2\times 10^5$，$1\le M\le 10^6$。

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 $N,M$ ,表示共有 $N$ 个元素和 $M$ 个操作。

接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。

当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。

当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出
Y ；否则输出 N 。

输出格式

对于每一个 $Z_i=2$ 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

输入输出样例 #1

输入 #1

输出 #1

N
Y
N
Y

说明/提示

对于 $15\%$ 的数据，$N \le 10$，$M \le 20$。

对于 $35\%$ 的数据，$N \le 100$，$M \le 10^3$。

对于 $50\%$ 的数据，$1\le N \le 10^4$，$1\le M \le 2\times 10^5$。

对于 $100\%$ 的数据，$1\le N\le 2\times 10^5$，$1\le M\le 10^6$，$1 \le X_i, Y_i \le N$，$Z_i \in { 1, 2 }$。

思路分析 + 代码实现

并查集模板。 $parent$ 数组简写为 $fa$ 。

优化1：迭代路径压缩

int find(int x) {
    while (fa[x] != x) {
        fa[x] = fa[fa[x]]; // 将x的父节点指向祖父节点
        x = fa[x]; // 继续向上查找
    }
    return x;
}

递归版本

int find(int x) {
    if (x == fa[x]) return x;
    return x = find(fa[x]);
}

优化2：按秩合并

用 $rk$ （即 $rank$ ）记录集合的秩（树的高度上界），令 $fx$ 为秩更小的一方，将 $fx$ 合并到 $fy$ 下，并更新 $fy$ 的秩。

void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return; // 已在同一集合
    if (rk[fx] > rk[fy]) swap(fx, fy);
    rk[fy] = max(rk[fy], rk[fx] + 1);
    fa[fx] = fy;
}

完整代码：

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 2e5 + 5;
int fa[MAXN], rk[MAXN];
int find(int x) {
    while (fa[x] != x) {
        fa[x] = fa[fa[x]];
        x = fa[x];
    }
    return x;
}
void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return; 
    if (rk[fx] > rk[fy]) swap(fx, fy);
    rk[fy] = max(rk[fy], rk[fx] + 1);
    fa[fx] = fy;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, z, x, y;
    cin >> N >> M;  
    for(int i = 1; i <= N; i++)
        fa[i] = i; // 每个元素初始时父节点是自己
    while (M--) {
        cin >> z >> x >> y;
        if (z == 1) unite(x, y);
        else puts(find(x) == find(y) ? "Y" : "N");
    }
    return 0;
}

常见错误：

未初始化：忘记将每个元素的父节点初始化为自身。
混淆合并顺序：在按秩合并时，应确保将秩小的树合并到秩大的树下。

B3872 [GESP202309 五级] 巧夺大奖

发表于 2025-12-21 更新于 2026-01-11

B3872 [GESP202309 五级] 巧夺大奖

题目描述

小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则：

游戏分为 $n$ 个时间段，参加者每个时间段可以选择一个小游戏。
游戏中共有 $n$ 个小游戏可供选择。
每个小游戏有规定的时限和奖励。对于第 $i$ 个小游戏，参加者必须在第 $T_i$ 个时间段结束前完成才能得到奖励 $R_i$。

小明发现，这些小游戏都很简单，不管选择哪个小游戏，他都能在一个时间段内完成。关键问题在于，如何安排每个时间段分别选择哪个小游戏，才能使得总奖励最高？

输入格式

输入第一行，包含一个正整数 $n$。$n$ 既是游戏时间段的个数，也是小游戏的个数。约定 $1\le n\le500$。

输入第二行，包含 $n$ 个正整数。第 $i$ 个正整数为 $T_i$，即第 $i$ 个小游戏的完成期限。约定 $1\le T_i\le n$。

输入第三行，包含 $n$ 个正整数。第 $i$ 个正整数为 $R_i$，即第 $i$ 个小游戏的完成奖励。约定 $1\le R_i\le 1000$。

输出格式

输出一行，包含一个正整数 $C$，为最高可获得的奖励。

输入输出样例 #1

输入 #1

1
2
3

7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

输出 #1

说明/提示

样例解释 1

$7$ 个时间段可分别安排完成第 4、2、3、1、6、7、5 个小游戏，其中第 4、2、3、1、7 个小游戏在期限内完成。因此，可以获得总计 $40+60+50+70+10=230$ 的奖励。

思路分析 + 代码实现

我们发现按时间顺序安排较难，因为越靠前的时间点可选的游戏越多，还要考虑对全局的影响。

所以我们考虑从最后一个游戏开始往前安排，这样可选的游戏就少了，因为排除了完成期限较早的游戏。

因此让游戏按完成期限降序排序。令 $t$ （初始为 $n$ ）表示当前正在安排的时间段，每次让 $T >= t$ 的游戏的奖励进入优先队列（贪心：每次挑奖励最高的玩）。~~奖池还在累加！~~

然后如果队列非空，则取队首，加上奖励，出队，即完成一次安排。重复上述步骤直到安排完所有时间段。

时间复杂度 $O(n \log n)$ ，代码如下：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e2 + 5;
struct Game {
    int T, R;
    bool operator < (const Game &b) const {
        return T > b.T;
    }
} a[MAXN];
int main(){
    int n, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i].T;
    for(int i = 0; i < n; i++)
        cin >> a[i].R;
    sort(a, a + n);
    priority_queue<int> Q;
    for(int p = 0, t = n; t > 0; t--) {
        while (a[p].T >= t) 
            Q.push(a[p++].R);
        if (Q.empty()) continue;
        ans += Q.top();
        Q.pop();
    }
    cout << ans;
    return 0;
}

P1395 会议

发表于 2025-12-20 更新于 2026-01-11

P1395 会议

题目描述

有一个村庄居住着 $n$ 个村民，有 $n-1$ 条路径使得这 $n$ 个村民的家联通，每条路径的长度都为 $1$。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。

输入格式

第一行，一个数 $n$，表示有 $n$ 个村民。

接下来 $n-1$ 行，每行两个数字 $a$ 和 $b$，表示村民 $a$ 的家和村民 $b$ 的家之间存在一条路径。

输出格式

一行输出两个数字 $x$ 和 $y$。

$x$ 表示村长将会在哪个村民家中举办会议。

$y$ 表示距离之和的最小值。

输入输出样例 #1

输入 #1

输出 #1

2 4

说明/提示

数据范围

对于 $70\%$ 数据 $n \le 10^3$。

对于 $100\%$ 数据 $n \le 5 \times 10^4$。

思路分析 + 代码实现

树的重心

树的重心的有关证明在这里均省略

定义：

无根树 $T$ 中的结点 $v$ 是它的重心，当且仅当以下任意一条成立：

在树中删去结点 $v$ 后，得到的图 $T\setminus{v}$ 中每个连通分量的大小均不超过原树结点数的一半。

在所有删去某个结点后得到的最大连通分量大小中，删去结点 $v$ 时所得到的值最小。

树中所有结点到某个结点的距离和中，到结点 $v$ 的距离和最小。
引自OI Wiki

由定义 3 可知，本题需要求树的编号较小的重心（树的重心如果不唯一，则恰有两个）

求法：

根据重心的等价定义，有 DFS 统计子树大小 和 换根 DP 统计深度和 两种方法可以在 $O(n)$ 时间内求出树的所有重心。这里用第一种。

用 $sz[i]$ 储存以节点 $i$ 为根的子树大小（所有子树上节点数 + 该节点）。
用 $w[i]$ 储存节点 $i$ 的重量，即 $i$ 的所有子树大小（不包括该节点）的最大值。
对每个结点，记录它的所有子结点对应子树的大小，并更新 $w[i]$ 。再利用总结点数减去当前子树大小得到“向上”的子树的大小，再更新 $w[i]$ 。
如果 $w[i] \leq n / 2$ ，则节点 $i$ 符合重心的定义，更新重心。

本题代码如下（树的重心求法见函数 get_center ）

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 5e4 + 5;
int w[MAXN], dep[MAXN], sz[MAXN], n;
vector<int> G[MAXN];
void get_center(int u, int f, int &tar) {
    sz[u] = 1;
    for(int v : G[u]) {
        if (v == f) continue;
        get_center(v, u, tar);
        sz[u] += sz[v];
        w[u] = max(w[u], sz[v]);
    }
    w[u] = max(w[u], n - sz[u]);
    if (w[u] <= n / 2)
        tar = min(tar, u);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int u, v, i = 1; i < n; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int center = MAXN, ans = 0;
    get_center(1, 0, center);
    queue<int> Q;
    Q.push(center);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for(int v : G[u]) {
            if (dep[v] || v == center) continue;
            dep[v] = dep[u] + 1;
            ans += dep[v];
            Q.push(v);
        }
    }
    cout << center << ' ' << ans;
    return 0;
}

其中 BFS 求距离和（深度和）也可以用 DFS ，代码如下：

int dfs(int u, int f) {
    int acc = dep[u];
    for(int v : G[u]) {
        if (v == f) continue;
        dep[v] = dep[u] + 1;
        acc += dfs(v, u);
    }
    return acc;
}
int main() {
    // 省略读入和求重心
    int ans = dfs(center, 0);
    cout << center << ' ' << ans;
    return 0;
}

P4017 最大食物链计数

发表于 2025-12-13 更新于 2026-01-11

P4017 最大食物链计数

题目背景

你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。

题目描述

给你一个食物网，你要求出这个食物网中最大食物链的数量。

（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）

Delia 非常急，所以你只有 $1$ 秒的时间。

由于这个结果可能过大，你只需要输出总数模上 $80112002$ 的结果。

输入格式

第一行，两个正整数 $n$、$m$，表示生物种类 $n$ 和吃与被吃的关系数 $m$。

接下来 $m$ 行，每行两个正整数，表示被吃的生物 A 和吃 A 的生物 B。

输出格式

一行一个整数，为最大食物链数量模上 $80112002$ 的结果。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

各测试点满足以下约定：

测试点编号	$n$	$m$
$1,2$	$\le 40$	$\le 400$
$3,4$	$\le 100$	$\le 2\times 10^3$
$5,6$	$\le 10^3$	$\le 6\times 10^4$
$7,8$	$\le 2\times 10^3$	$\le 2\times 10^5$
$9,10$	$\le 5\times 10^3$	$\le 5\times 10^5$

对于 $100\%$ 的数据，$1 \le n \le 5\times 10^3,1\le m \le 5\times 10^5$

【补充说明】

数据中不会出现环，满足生物学的要求。（感谢 @AKEE）

思路分析 + 代码实现

本题是经典的拓扑排序例题，加上动态规划的思想。

什么是拓扑排序？

拓扑排序是对 有向无环图（DAG） 进行线性排序的方法，使得对于图中的每条有向边 $(u, v)$ ，节点 $u$ 在排序中都出现在节点 $v$ 之前。

为什么本题需要拓扑排序？

因为食物链是有方向的（A被B吃），且不能有环（生物学上食物链不能循环），这正好符合DAG的性质。我们需要按照食物链的方向计算路径数。

具体步骤

用 $indeg[i]$ 记录节点 $i$ 的入度， $cnt[i]$ 记录以节点 $i$ 结尾的食物链条数（取模后）

初始化队列： 将入度为零的点（生产者）加入队列（作为食物链的起点），并初始化 $cnt[i] = 1$
BFS遍历：

从队列中取出节点 $u$
遍历 $u$ 的所有后继节点 $i$
对每个后继节点 $v$：
- 减少 $v$ 的入度（相当于删除边 $u \rightarrow i$）
- 进行状态转移：$cnt[i] = (cnt[i] + cnt[u]) \mod MOD$
  - 状态转移方程 $cnt[i] = \sum cnt[u]$（其中 $u$ 是 $i$ 的前驱）
  - 意义：到达 $i$ 的路径数 = 所有到达 $u$ 的路径数之和（因为每条到 $u$ 的路径都可以延伸到 $i$）
  - 如果 $v$ 的入度变为 $0$ ，将 $v$ 加入队列
重复直到队列为空

统计结果： 遍历所有节点，如果节点的出度为 $0$（即 $G[i].empty()$，顶级消费者），将 $cnt[i]$ 累加到答案中

本题中拓扑排序的作用

拓扑排序确保了计算顺序的正确性：

只有在节点 $i$ 的所有前驱节点都被处理完后，$i$ 的入度才会变为0，$i$ 才会被加入队列
这意味着当计算 $cnt[i]$ 时，所有到达 $i$ 的路径都已经被考虑到了
从而保证了 $cnt[i] = \sum cnt[u]$ 的正确性

时间复杂度分析

每个节点入队一次：$O(n)$
每条边被访问一次：$O(m)$
总时间复杂度：$O(n + m)$

代码如下：

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 5e3 + 5, MOD = 80112002;
vector<int> G[MAXN];
int indeg[MAXN], cnt[MAXN];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, ans = 0;
    cin >> n >> m;
    for(int u, v, i = 0; i < m; i++) {
        cin >> u >> v;
        indeg[v]++;
        G[u].push_back(v);
    }
    queue<int> Q;
    for(int i = 1; i <= n; i++)
        if (indeg[i] == 0) {
            Q.push(i);
            cnt[i] = 1;
        }
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for(int i : G[u]) {
            indeg[i]--;
            cnt[i] = (cnt[i] + cnt[u]) % MOD;
            if (indeg[i] == 0) Q.push(i);
        }
    }
    for(int i = 1; i <= n; i++)
        if (G[i].empty()) 
            ans = (ans + cnt[i]) % MOD;
    cout << ans;
}

此外，还有利用 DFS + 记忆化搜索的方法，代码更简洁。

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 5e3 + 5, MOD = 80112002;
vector<int> G[MAXN];
int indeg[MAXN], cnt[MAXN];
int dfs(int u) {
    if (cnt[u]) return cnt[u]; // 已经计算过
    if (G[u].empty()) // 顶级消费者，只有自身一条链
        return cnt[u] = 1;
    int res = 0;
    for (int v : G[u]) // 累加所有后继的路径数
        res = (res + dfs(v)) % MOD;
    return cnt[u] = res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, ans = 0;
    cin >> n >> m;
    for(int u, v, i = 0; i < m; i++) {
        cin >> u >> v;
        indeg[v]++;
        G[u].push_back(v);
    }
    for(int i = 1; i <= n; i++)
        if (indeg[i] == 0)
            ans = (ans + dfs(i)) % MOD;
    cout << ans;
}

P3916 图的遍历

发表于 2025-12-13 更新于 2026-01-11

P3916 图的遍历

题目描述

给出 $N$ 个点，$M$ 条边的有向图，对于每个点 $v$，令 $A(v)$ 表示从点 $v$ 出发，能到达的编号最大的点。现在请求出 $A(1),A(2),\dots,A(N)$ 的值。

输入格式

第 $1$ 行 $2$ 个整数 $N,M$，表示点数和边数。

接下来 $M$ 行，每行 $2$ 个整数 $U_i,V_i$，表示边 $(U_i,V_i)$。点用 $1,2,\dots,N$ 编号。

输出格式

一行 $N$ 个整数 $A(1),A(2),\dots,A(N)$。

输入输出样例 #1

输入 #1

输出 #1

4 4 3 4

说明/提示

对于 $60\%$ 的数据，$1 \leq N,M \leq 10^3$。
对于 $100\%$ 的数据，$1 \leq N,M \leq 10^5$。

思路分析 + 代码实现

用反向边建图，这样构建的反向图可以将原问题转化为从每个节点出发在反向图中能到达哪些节点。从编号最大的点开始遍历（这里写了 BFS 和 DFS 两种做法）。如果遍历到的点未被遍历过，则记录答案，继续遍历。时间复杂度和空间复杂度都是为 $O(N+M)$ ，代码如下：

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e5 + 5;
vector<int> G[MAXN];
int Dans[MAXN], Bans[MAXN];
void dfs(int x, int v) {
    if (Dans[x]) return;
    Dans[x] = v;
    for(int i : G[x])
        dfs(i, v);
}
void bfs(int x, int v) {
    if (Bans[x]) return;
    Bans[x] = v;
    queue<int> Q;
    Q.push(x);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for(int i : G[u]) {
            if (Bans[i]) continue;
            Bans[i] = v;
            Q.push(i);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    for(int u, v, i = 0; i < M; i++) {
        cin >> u >> v;
        G[v].push_back(u);
    }
    for(int i = N; i > 0; i--)
        dfs(i, i);
    for(int i = N; i > 0; i--)
        bfs(i, i);
    for(int i = 1; i <= N; i++)
        cout << Bans[i] << " ";
        // cout << Dans[i] << " ";
    return 0;
}

Markdown 数学公式语法指南

发表于 2025-12-07 更新于 2026-01-11

Markdown 数学公式语法指南

Markdown 中使用 LaTeX 语法来编写数学公式.

常见运算符

基本算术运算符

运算符	LaTeX 语法	示例	效果
加号	`+`	`a + b`	$a + b$
减号	`-`	`a - b`	$a - b$
乘号	`\times`	`a \times b`	$a \times b$
点乘	`\cdot`	`a \cdot b`	$a \cdot b$
除号	`\div`	`a \div b`	$a \div b$
分数	`\frac{a}{b}`	`\frac{a}{b}`	$\frac{a}{b}$
平方根	`\sqrt{x}`	`\sqrt{x}`	$\sqrt{x}$
n次方根	`\sqrt[n]{x}`	`\sqrt[3]{x}`	$\sqrt[3]{x}$
对数	`\log`	`\log x`	$\log x$
自然对数	`\ln`	`\ln x`	$\ln x$
以a为底对数	`\log_a b`	`\log_a b`	$\log_a b$

取模运算

Markdown/LaTeX 中有多种方式表示取模运算：

运算符	LaTeX 语法	示例	效果	说明
取模	`\bmod`	`a \bmod b`	$a \bmod b$	二元取模运算符
同余	`\pmod`	`a \equiv b \pmod{n}`	$a \equiv b \pmod{n}$	模 n 同余
同余	`\mod`	`a \equiv b \mod n`	$a \equiv b \mod n$	同余关系
函数形式	`\operatorname{mod}`	`\operatorname{mod}(a, b)`	$\operatorname{mod}(a, b)$	函数形式

逻辑运算符

运算符	LaTeX 语法	示例	效果
与	`\land` 或 `\wedge`	`a \land b`	$a \land b$
或	`\lor` 或 `\vee`	`a \lor b`	$a \lor b$
非	`\lnot` 或 `\neg`	`\lnot a`	$\lnot a$
异或	`\oplus`	`a \oplus b`	$a \oplus b$
同或	`\odot`	`a \odot b`	$a \odot b$
蕴含	`\rightarrow` 或 `\implies`	`a \rightarrow b`	$a \rightarrow b$
等价	`\leftrightarrow` 或 `\iff`	`a \leftrightarrow b`	$a \leftrightarrow b$
对于所有	`\forall`	`\forall x \in \mathbb{R}`	$\forall x \in \mathbb{R}$
存在	`\exists`	`\exists x \in \mathbb{R}`	$\exists x \in \mathbb{R}$

上下标

类型	LaTeX 语法	示例	效果
上标	`^`	`x^2`	$x^2$
下标	`_`	`x_1`	$x_1$
组合	`^{}_{}`	`x^{2}_{1}`	$x^{2}_{1}$

关系运算符

运算符	LaTeX 语法	示例	效果
等于	`=`	`a = b`	$a = b$
不等于	`\neq`	`a \neq b`	$a \neq b$
约等于	`\approx`	`a \approx b`	$a \approx b$
大于	`>`	`a > b`	$a > b$
小于	`<`	`a < b`	$a < b$
大于等于	`\geq`	`a \geq b`	$a \geq b$
小于等于	`\leq`	`a \leq b`	$a \leq b$
正比于	`\propto`	`a \propto b`	$a \propto b$

求和、积分、极限

运算符	LaTeX 语法	示例	效果
求和	`\sum`	`\sum_{i=1}^{n} i`	$\sum_{i=1}^{n} i$
积分	`\int`	`\int_{a}^{b} f(x)dx`	$\int_{a}^{b} f(x)dx$
极限	`\lim`	`\lim_{x \to \infty} f(x)`	$\lim_{x \to \infty} f(x)$
乘积	`\prod`	`\prod_{i=1}^{n} i`	$\prod_{i=1}^{n} i$

希腊字母

字母	LaTeX 语法	示例	效果
α	`\alpha`	`\alpha`	$\alpha$
β	`\beta`	`\beta`	$\beta$
γ	`\gamma`	`\gamma`	$\gamma$
Δ	`\Delta`	`\Delta`	$\Delta$
π	`\pi`	`\pi$`	$\pi$
θ	`\theta`	`\theta`	$\theta$
μ	`\mu`	`\mu$`	$\mu$
σ	`\sigma`	`\sigma`	$\sigma$
ω	`\omega`	`\omega`	$\omega$

集合运算符

运算符	LaTeX 语法	示例	效果
属于	`\in`	`a \in A`	$a \in A$
不属于	`\notin`	`a \notin A`	$a \notin A$
子集	`\subset`	`A \subset B`	$A \subset B$
真子集	`\subseteq`	`A \subseteq B`	$A \subseteq B$
并集	`\cup`	`A \cup B`	$A \cup B$
交集	`\cap`	`A \cap B`	$A \cap B$
空集	`\emptyset`	`\emptyset`	$\emptyset$

函数表达式

常用数学函数

函数	LaTeX 语法	示例	效果
正弦	`\sin`	`\sin x`	$\sin x$
余弦	`\cos`	`\cos x`	$\cos x$
正切	`\tan`	`\tan x`	$\tan x$
指数	`\exp`	`\exp(x)`	$\exp(x)$
最大值	`\max`	`\max(a, b)`	$\max(a, b)$
最小值	`\min`	`\min(a, b)`	$\min(a, b)$

矩阵和行列式

$$
\begin{matrix}
a & b \\
c & d
\end{matrix}
$$

$$
\begin{pmatrix}
a & b \\
c & d
\end{pmatrix}
$$

$$
\begin{vmatrix}
a & b \\
c & d
\end{vmatrix}
$$

效果：

$\begin{matrix} a & b \\ c & d \end{matrix}$ $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ $\begin{vmatrix} a & b \\ c & d \end{vmatrix}$

括号和定界符

类型	LaTeX 语法	示例	效果
花括号	`\{ \}`	`\{a+b\}`	${a+b}$
自适应括号	`\left( \right)`	`\left(\frac{a}{b}\right)`	$\left(\frac{a}{b}\right)$

P1003 [NOIP 2011 提高组] 铺地毯

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

说明/提示

思路分析

最聪明 （傻波一） 的一集

正解

代码实现

P4933 大师

题目背景

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

说明/提示

思路分析

代码实现

P2196 [NOIP 1996 提高组] 挖地雷

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

思路分析 + 代码实现

P14826 踩踩标

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

样例解释

数据范围

问题简述

核心思路

1. 特判 $k = 0$

2. 一般情况 ($k > 0$)

关键问题：为什么需要两个循环？

例子说明

覆盖所有情况的技巧

算法步骤

代码（简洁版）

时间复杂度

总结

P3367 【模板】并查集

题目背景

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

思路分析 + 代码实现

优化1：迭代路径压缩

优化2：按秩合并

B3872 [GESP202309 五级] 巧夺大奖

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

思路分析 + 代码实现

最聪明（傻波一）的一集