## 夺宝奇猫
#数学 #贪心
首先我们需要构建一条 $1\sim n$ 和一条 $n\sim 1$ 的路径，这两个路径涵盖了所有的点组并且不重复。很显然后面 $n\sim 1$ 也等同于 $1\sim n$，因此我们需要构建两条 $1\sim n$ 的路径。
考虑相邻编号点 $i$ 和 $i+1$ 之间的路径方式，只有两种 ${} (i_0,(i+1)_{0})$ $(i_1,(i+1)_1) {}$ 和 ${} (i_0,(i+1)_1)$ $(i_1,(i+1)_0)$。因此我们只需要选择距离和最小的那一种，累加起来再额外加上第 $n$ 组点的贡献就行了。
时间复杂度 $\mathcal O(n)$。
```cpp
#include <fstream>
using namespace std;
using LL = long long;
const LL kMaxN = 1e5 + 5;
ifstream cin("treacat.in");
ofstream cout("treacat.out");
LL x[kMaxN][2], y[kMaxN][2], n, m, ans;
LL dis(LL x1, LL y1, LL x2, LL y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (LL i = 1; i <= n; i++) {
for (LL j = 0; j <= 1; j++) {
cin >> x[i][j] >> y[i][j];
}
}
for (LL i = 1; i < n; i++) {
ans += min(dis(x[i][0], y[i][0], x[i + 1][0], y[i + 1][0]) + dis(x[i][1], y[i][1], x[i + 1][1], y[i + 1][1]),
dis(x[i][0], y[i][0], x[i + 1][1], y[i + 1][1]) + dis(x[i][1], y[i][1], x[i + 1][0], y[i + 1][0]));
}
cout << ans + dis(x[n][0], y[n][0], x[n][1], y[n][1]) << '\n';
return 0;
}
```
## 爬山
#最短路 #优先队列
海拔上升会减少体力，海拔下降会增加体力，但是任意时刻体力不能为负，而 $h_1$ 不能改变（且改变了也不优），因此实际上可以走的海拔区间为 $(-\infty,h_1+k]$。对于路径上所有在区间之外的海拔，需要额外增加 $(h-h_1-k)^2$ 的代价。因此直接跑 dijkstra 额外增加贡献就行了。
时间复杂度 $\mathcal O(m\log_2 m)$。
```cpp
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
using LL = long long;
const LL kMaxN = 2e5 + 5;
ifstream cin("climb.in");
ofstream cout("climb.out");
struct Node {
LL to, v;
Node(LL to, LL v):
to(to), v(v) { }
friend bool operator<(const Node &a, const Node &b) {
return a.v > b.v;
}
};
LL a[kMaxN], f[kMaxN], d[kMaxN], n, m, k;
vector<Node> e[kMaxN];
priority_queue<Node> q;
LL sqr(LL x) {
return x * x;
}
void bfs() {
fill(d + 2, d + n + 1, 1e18);
for (q.emplace(1, 0); q.size(); q.pop()) {
auto t = q.top();
if (f[t.to]) {
continue;
}
f[t.to] = 1;
for (auto i : e[t.to]) {
LL v = d[t.to] + i.v + sqr(max(0LL, a[i.to] - a[1] - k));
if (v < d[i.to]) {
d[i.to] = v;
q.emplace(i.to, d[i.to]);
}
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> k;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
}
for (LL i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
bfs();
cout << d[n] << '\n';
return 0;
}
```
## 排列
#序列dp #前缀和
首先很容易想到简单的动态规划，设 $dp_{i,j}$ 表示为对于长度为 $i$ 的已构建排列，最后一个元素是 $j$ 的方案数。但是选择下一个数的时候无法判断是否已经被选过，为了避免这种情况我们将 $j$ 改为在已选排列中的排名。
设 $dp_{i,j}$ 表示最后一个元素的排名为 $j$，那么转移和之前是一样的进行，也是非常的简单。增加前缀和优化把时间复杂度 $\mathcal O(n^3)$ 变成 $\mathcal O(n^2)$，并加上滚动数组优化防止炸空间。
```cpp
#include <fstream>
using namespace std;
using LL = long long;
const LL kMaxN = 1e4 + 5, kMod = 1e9 + 7;
ifstream cin("perm.in");
ofstream cout("perm.out");
LL dp[kMaxN], prv[kMaxN], sum[kMaxN], n, ans;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
prv[1] = sum[1] = 1;
for (LL i = 2; i <= n; i++) {
for (LL j = 1; j <= i; j++) {
if (i % 2 == 0) {
dp[j] = (sum[i - 1] - sum[j - 1] + kMod) % kMod;
} else {
dp[j] = sum[j - 1];
}
}
for (LL j = 1; j <= i; j++) {
sum[j] = (sum[j - 1] + dp[j]) % kMod;
}
copy(dp + 1, dp + i + 1, prv);
}
for (LL i = 1; i <= n; i++) {
ans = (ans + dp[i]) % kMod;
}
cout << ans << '\n';
return 0;
}
```
## 夺宝奇鱼
#线段树 #排序 #贪心
首先由于限制对于所有怪兽都是启用的，因此可以枚举这个限制。枚举 $i$ 表示所有怪兽手上剩余的物品数量都小于 $i$，此时我们购买的物品数量就需要大于等于 $i$。从大到小枚举 $i$，这样每次都会把一些怪物手上的已有的物品删除。
现在我们让所有怪物都满足了 $i$ 的限制，但是自己手上可能还不到 $i$ 个物品。此时需要在怪物手上继续购买剩余的物品，肯定是优先购买便宜的，然而怪物手上的物品是越删越少的，因此可以使用权值线段树维护怪物手上的剩余物品，补充剩余的就在权值线段树上面二分就行了。
时间复杂度 $\mathcal O(m\log_2 m)$。注意需要进行离散化否则会 MLE。
```cpp
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
using LL = long long;
const LL kMaxN = 1e6 + 5;
ifstream cin("treasure.in");
ofstream cout("treasure.out");
struct Node {
LL cnt, sum;
} tr[4 * kMaxN];
LL val[kMaxN], n, m, q, cnt, use, buy, ans = 1e18;
vector<LL> v[kMaxN], id[kMaxN], rm;
multiset<LL> s;
void modify(LL p, LL l, LL r, LL x, LL d) {
tr[p].cnt += d;
tr[p].sum += val[x] * d;
if (l == r) {
return;
}
LL m = (l + r) / 2;
if (x <= m) {
modify(2 * p, l, m, x, d);
} else {
modify(2 * p + 1, m + 1, r, x, d);
}
}
LL query(LL p, LL l, LL r, LL k) {
if (l == r) {
return val[l] * k;
}
LL m = (l + r) / 2, cnt = tr[2 * p].cnt;
if (k <= cnt) {
return query(2 * p, l, m, k);
}
return tr[2 * p].sum + query(2 * p + 1, m + 1, r, k - cnt);
}
LL getHash(LL x) {
return lower_bound(val + 1, val + q + 1, x) - val;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (LL i = 1, a, c; i <= m; i++) {
cin >> a >> c;
v[c].push_back(a);
val[++q] = a;
}
sort(val + 1, val + q + 1);
q = unique(val + 1, val + q + 1) - val - 1;
for (LL i = 1; i <= n; i++) {
if (v[i].empty()) {
continue;
}
for (LL &j : v[i]) {
j = getHash(j);
modify(1, 1, q, j, 1);
}
sort(v[i].begin(), v[i].end(), greater<>());
id[v[i].size()].push_back(i);
}
// 所有怪物剩余物品数小于 i，购买数大于等于 i
for (LL i = m; i >= 1; i--) {
for (LL j : id[i]) {
rm.push_back(j);
}
for (LL j : rm) {
buy += val[v[j].back()];
modify(1, 1, q, v[j].back(), -1);
v[j].pop_back();
use++;
}
ans = min(ans, buy + query(1, 1, q, max(0LL, i - use)));
}
cout << ans << '\n';
return 0;
}
```
## 总结
总分：$100+100+100+100=400$。
第一、二、四题都做得很快，思路也不难想，就是第三题太糖了一个多小时才做出来。