铺设道路
Description
有 $n$ 个连续的区域，第 $i$ 个区域下陷的深度为 $d_i$。你每次可以选择一段连续的区间 $[L,R]$，使这段区间内每个区域的深度减少 $1$，但是必须保证任何时刻 $d_i\ge 0$。求将所有区域的深度都变为 $0$ 的最短时间。
数据范围：$1\le n\le 10^5$，$0\le d_i\le 10^4$。
Solution
我在考场上的第一个反应就是分治，对于当前区间找到最小值，这个最小值一定把区间拆成了若干段，对这些段递归计算。
时间复杂度：$\mathcal O(n\log n)$。
其实此题还有另一个结论：$\sum_{i=1}^n \max(0,d_i-d_{i-1})$，其中 $d_0=0$。
这个结论可以用递推证明，令 $f_i$ 表示填好前 $i$ 个区域所需的最短时间。那么我们对当前的 $d_i$ 分类讨论。
- 如果 $d_i\le d_{i-1}$，那么我们可以在填 $d_{i-1}$ 时顺便把 $d_i$ 填好，即 $f_i=f_{i-1}$。
- 如果 $d_i>d_{i-1}$，那么我们需要单独把 $d_i$ 高出的部分填上，即 $f_i=f_{i-1}+(d_i-d_{i-1})$。
由于我们需要的只是 $f_n$，所以就是上面那个式子了！
时间复杂度：$\mathcal O(n)$。
Code
第一种做法：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
const int N = 1e5 + 5, M = 1e4 + 5, logN = 20;
int n, a[N], f[N][logN], lg[N], ans;
std::vector<int> b[M];
void build() {
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= n; i++) {
f[i][0] = a[i];
b[a[i]].push_back(i);
}
for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
f[i][j] = std::min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r) {
int k = lg[r - l + 1];
return std::min(f[l][k], f[r - (1 << k) + 1][k]);
}
void solve(int l, int r, int last) {
if (l > r) return;
int mn = query(l, r);
ans += mn - last;
int st = std::lower_bound(b[mn].begin(), b[mn].end(), l) - b[mn].begin();
int ed = std::upper_bound(b[mn].begin(), b[mn].end(), r) - b[mn].begin() - 1;
int p = l - 1;
for (int i = st; i <= ed; i++) {
solve(p + 1, b[mn][i] - 1, mn);
p = b[mn][i];
}
solve(p + 1, r, mn);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build();
solve(1, n, 0);
printf("%d\n", ans);
return 0;
}第二种做法：
#include <cstdio>
#include <algorithm>
int main() {
int n, ans = 0;
scanf("%d", &n);
for (int y = 0, i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
ans += std::max(x - y, 0);
y = x;
}
printf("%d\n", ans);
return 0;
}货币系统
Description
有 $n$ 种不同面额的货币，第 $i$ 种货币的面额为 $a_i$，每种货币都有无限张，我们把这个货币系统记作 $(n,a)$。两个货币系统 $(n,a)$ 和 $(m,b)$ 是等价的，当且仅当对于任意的非负整数 $x$，要么能被两个货币系统都表示出来，要么两者都无法表示。
现在给出一个货币系统 $(n,a)$，你需要求出一个货币系统 $(m,b)$ 使得两者等价并最小化 $m$。
本题有 $T$ 组数据。
数据范围：$1\le T\le 20$，$1\le n\le 100$，$1\le a_i\le 25000$。
Solution
通过感性证明可以得到：新的货币系统内的货币一定属于原来的货币系统。
那么我们把货币从小到大排序，如果某个货币 $a_i$ 能被之前的货币表示出来，那么这个 $a_i$ 一定是多余的；否则 $a_i$ 一定属于新的货币系统。这个过程显然用一个完全背包就能实现了！（我在考场竟然写了一个 $\text{bitset}$ 优化的多重背包 QAQ）
时间复杂度：$\mathcal O(n\cdot a_i)$。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 105, M = 3e4 + 5;
int n, a[N];
bool f[M];
int main() {
int T;
for (scanf("%d", &T); T--; ) {
scanf("%d", &n);
int mx = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
mx = std::max(mx, a[i]);
}
std::sort(a + 1, a + n + 1);
memset(f, 0, sizeof(f));
f[0] = 1;
int ans = 0;
for (int i = 1; i <= n; i++) {
if (!f[a[i]]) {
ans++;
for (int j = a[i]; j <= mx; j++) {
f[j] |= f[j - a[i]];
}
}
}
printf("%d\n", ans);
}
return 0;
}赛道修建
Description
C 城要举办赛车比赛，需要在城内修建 $m$ 条赛道。C 城有 $n$ 个路口和 $n-1$ 条适合修建赛道的双向通行的道路，第 $i$ 条道路的长度为 $l_i$，所有路口都直接或间接连通。一条赛道由一组互不相同的道路组成，满足从起点出发依次经过这些道路到达终点。一条赛道的长度等于经过的各道路的长度之和。为保证安全，要求每条道路至多被一条赛道经过。
你的任务是设计一种赛道修建的方案，使得修建的 $m$ 条赛道中长度最小的赛道长度最大。
数据范围：$2\le n\le 5\times 10^4$，$1\le m < n$，$1\le l_i\le 10^4$。
Solution
首先，看到“最大化最小值”可以想到二分答案 $ans$，那么将问题转化为：是否可以选择 $m$ 条长度至少是 $ans$ 的链。
考虑以 $u$ 为根的子树，最优解中有一些链完全在子树内部，还可能有一条链经过 $u$ 向子树外扩展。在子树内部的链的数量相同的情况下，我们肯定要尽量使可以往上扩展的链尽可能长（如果没有，那么这个长度就是 $0$）。
我们用 $f(x)$ 表示子树 $x$ 内部最多有多少条链，$g(x)$ 表示当子树内部链最多时，剩下的以 $x$ 结尾的链最长是多少。
考虑怎么用这两个值进行转移。对于 $u$ 的每个孩子 $v$，它为 $u$ 提供了长度为 $len(v)=g(v)+w(u,v)$ 的可以用于拼接的链，以及 $f(v)$ 的答案。如果 $len(v)\ge ans$，那么可以直接选择这条链并使答案 $f(u)$ 增加 $1$。否则我们可以选择两条满足 $len(v_1)+len(v_2)\ge ans$ 的链进行匹配并使答案 $f(u)$ 增加 $1$，接下来我们分析选择两条链匹配的问题。
我们要使得 $len(v)$ 匹配的对数最多。这显然就是一个双指针贪心的过程。但是我们还要使剩下的一条链尽可能长。那我们稍微改变一下算法：每次考虑 $len$ 最小的 $v$，并找到最小的 $len(v')$ 满足 $len(v)+len(v')\ge ans$（如果不存在就不考虑 $v$ 这条链），把 $v$ 和 $v'$ 这两条链进行匹配。这样这样把所有的 $len(v)$ 匹配完之后，可以证明 $g(u)$ 就是未匹配的最长的链。
时间复杂度：$\mathcal O(n\log n\log T)$，其中 $T$ 为二分答案的值域，上界为 $\sum l_i$。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
const int N = 5e4 + 5, M = 1e5 + 5;
int n, m, tot, lnk[N], ter[M], nxt[M], val[M], f[N], g[N];
void add(int u, int v, int w) {
ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w;
}
void dfs(int u, int p, int len) {
std::vector<int> t;
std::multiset<int> s;
for (int i = lnk[u]; i; i = nxt[i]) {
int v = ter[i];
if (v == p) continue;
dfs(v, u, len);
int sum = g[v] + val[i];
f[u] += f[v];
if (sum >= len) {
f[u]++;
} else {
s.insert(sum);
t.push_back(sum);
}
}
std::sort(t.begin(), t.end());
for (int x: t) {
if (s.empty()) break;
std::multiset<int>::iterator l = s.find(x);
if (l == s.end()) continue;
std::multiset<int>::iterator r = s.lower_bound(len - x);
if (l == r) r++;
if (r == s.end()) continue;
if (*l + *r >= len) {
f[u]++, s.erase(l), s.erase(r);
}
}
if(!s.empty()) g[u] = *s.rbegin();
}
bool check(int len) {
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
dfs(1, 0, len);
return f[1] >= m;
}
int main() {
scanf("%d%d", &n, &m);
int l = 0, r = 0, ans = 0;
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w), add(v, u, w);
r += w;
}
while (l <= r) {
int mid = (l + r) >> 1;
if(check(mid)) {
l = (ans = mid) + 1;
} else {
r = mid - 1;
}
}
printf("%d\n", ans);
return 0;
}旅行
Description
X 国有 $n$ 个城市，之间有 $m$ 条双向道路（不存在重边和自环，保证所有城市直接或间接连通）。小 Y 的旅行方案如下：任意选定一个城市作为起点，然后从起点开始沿道路走向一个没有去过的城市，或者沿着第一次访问该城市时经过的道路后退到上一个城市。在小 Y 的旅行方案中，每个城市都要被访问到。
小 Y 在第一次访问某个城市时，会记录下这个城市的编号，这样会形成一个长度为 $n$ 的序列，你需要求出字典序最小的序列。
数据范围：$1\le n\le 5000$，$m=n-1$ 或 $m=n$。
Solution
由于每次访问一个新的点（除了起点），一定会经过一条新的边。除了起点，我们一共要访问 $n-1$ 个点，那么会有 $n-1$ 条边，所以最终的路径会形成一棵生成树。
我们对 $m=n-1$ 和 $m=n$ 的情况分开考虑。
- 当 $m=n-1$ 时
我们一定选择编号为 $1$ 的点作为起点，可以发现题目中的限制等价于对原图进行 $\text{DFS}$，形成的序列就是 $\text{DFS}$ 序，我们要让 $\text{DFS}$ 序字典序最小，那么只需要对儿子节点排序，按照编号从小到大访问即可。 - 当 $m=n$ 时
根据之前证明的结论，我们可以知道一定有一条边不会被经过。那么我们只要枚举这条边。如果剩下的是一棵树，那么就按照树的方法进行 $\text{DFS}$，在所有情况中取字典序最小的作为答案。注意：并不是每次 $\text{DFS}$ 都需要进行排序，我们可以事先对每个节点的相邻节点排序。
时间复杂度：$\mathcal O(n^2)$。
然而这题是可以优化到 $\mathcal O(n\log n)$ 的！
如果我们把环单独考虑，那么在每棵树上肯定是正常走，走到环上之后肯定会走较小的那一条边。因此我们可以把环找出来，很容易确定下来在环上的走的方向，接下来就可以直接 $\text{DFS}$ 求解了！
时间复杂度：$\mathcal O(n\log n)$。
Code
第一种做法：
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 5005;
int n, m, tot, sz[N], e[N][N], ans[N], now[N], du, dv;
bool vis[N], flg;
bool check(int u, int v) {
return !((u == du && v == dv) || (u == dv && v == du));
}
bool cmp() {
for (int i = 1; i <= n; i++) {
if (now[i] < ans[i]) return 1;
if (now[i] > ans[i]) return 0;
}
return 0;
}
bool dfs(int u) {
tot++;
if (u < ans[tot]) flg = 1;
if (u > ans[tot] && !flg) return 1;
vis[now[tot] = u] = 1;
for (int i = 1; i <= sz[u]; i++) {
int v = e[u][i];
if (!vis[v] && check(u, v)) {
if (dfs(v)) return 1;
}
}
return 0;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
e[u][++sz[u]] = v;
e[v][++sz[v]] = u;
}
for (int i = 1; i <= n; i++) {
std::sort(e[i] + 1, e[i] + sz[i] + 1);
}
ans[1] = 5001;
if (m == n - 1) {
dfs(1);
memcpy(ans, now, sizeof(now));
} else {
for (int i = 1; i <= n; i++) {
du = i;
for(int j = 1; j <= sz[i]; j++) {
dv = e[i][j];
if (dv > du) continue;
tot = flg = 0;
memset(vis, 0, sizeof(vis));
dfs(1);
if (tot == n && cmp()) {
memcpy(ans, now, sizeof(now));
}
}
}
}
for (int i = 1; i <= n; i++) {
printf("%d%c", ans[i], " \n"[i == n]);
}
return 0;
}第二种做法：
// 我也不会写啊 QAQ填数游戏
咕咕咕
保卫王国
咕咕咕