题目：[[2024.10.20 题目]]
![[LZH文明语录2.png]]
详情请见：[[2024.10.20 星期日]]
## 袜子分配
有 $n$ 双袜子，随机取 $n$ 次，每次抽出随机两只袜子，如果两双袜子正好是一双就开心一次，求随机 $n$ 次的开心次数期望，与答案误差小于 $10^{-8}$。
---
一共有 $2\times n$ 只袜子，因此总共有 $2n!$ 种拿法。每一种袜子有 $2$ 只，拿完剩下的 $2n-2$ 只袜子随便拿，因此有 $2n^2\times (2n-2)!$ 种拿法可以拿到袜子。因此答案为 $\cfrac{2n^2\times (2n-2)!}{2n!}$，拆开阶乘得到 $\cfrac{2n^2}{(2n-1)\times 2n}$，化简得到 $\cfrac{2n}{2n-1}$，也就是本题的解了，时间复杂度 $\mathcal O(1)$，赛时 $100$ 分。
```cpp
#include <fstream>
#include <iomanip>
using namespace std;
using LL = long long;
ifstream cin("socks.in");
ofstream cout("socks.out");
LL n;
int main() {
cin >> n;
cout << fixed << setprecision(10) << 1.0 * n / (2 * n - 1) << '\n';
return 0;
}
```
## 艰难睡眠
每天有 $m$ 个时间单位，有 $n$ 个人，第 $i$ 个人默认在 $[a_i,a_i+b_i-1]$ 这段时间吵闹。可以花费 $c_{i,j}$ 的代价让第 $i$ 个人到 $j$ 的时间吵（即让 $a_i\gets j$）。牛牛每天至少睡觉 $k$ 分钟，这 $k$ 分钟不能有人吵闹。请问想让牛牛满足要求需要花费的最小代价是多少？
---
注意到 $2\le n\le 5000$ 且 $1\le m\le 2000$，因此我们枚举牛牛 $i$ $(1\le i\le m)$ 时开始睡觉，那么 $[i,i+k)$ 都不能有人吵闹。因此对于每一个人我们都做一个 ST 表处理区间最小值，然后将不会影响牛牛睡觉的部分的 $c_{i,j}$ 取最小值并加入答案，最后对于每个 $i$ 的答案的最小值就是最终答案了。
该方法的时间复杂度与空间复杂度均为 $\mathcal O(nm\log_2 m)$，但是 ST 表的大数组不能开成 `long long`，否则会超出空间限制。开成 `int` 勉强能过，出题人我爱你❤。（MLE 保灵了）
如果你成功开了 `int`，那么在快一点的评测机上可以正常通过。值得注意的是本题并没有无解输出 $-1$ 的测试点，因为 TYK 输出 $-1$ 没有分。
```cpp
#include <fstream>
using namespace std;
const int kMaxN = 5005, kMaxM = 2005, kLog = 11;
ifstream cin("sleep.in");
ofstream cout("sleep.out");
int a[kMaxN], b[kMaxN], dp[kMaxN][kMaxM][kLog], lg[kMaxN], n, m, k, ans = 1e9;
int query(int i, int l, int r) {
int k = lg[r - l + 1];
return min(dp[i][l][k], dp[i][r - (1 << k) + 1][k]);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> dp[i][j][0];
}
for (int k = 1; k < kLog; k++) {
for (int j = 1; j + (1 << k) - 1 <= m; j++) {
dp[i][j][k] = min(dp[i][j][k - 1], dp[i][j + (1 << (k - 1))][k - 1]);
}
}
}
for (int i = 2; i <= m; i++) {
lg[i] = lg[i / 2] + 1;
}
for (int i = 1; i <= m; i++) {
int sum = 0;
for (int j = 1; j <= n; j++) {
if (m - b[j] < k) {
cout << "-1\n";
return 0;
}
int x = 1e9, l = i + k, r = i - b[j];
if (l > m) {
x = query(j, l - m, r);
} else if (r < 1) {
x = query(j, l, m + r);
} else {
x = min(query(j, l, m), query(j, 1, r));
}
sum += x;
}
ans = min(ans, sum);
}
cout << ans << '\n';
return 0;
}
```
## 路径难题
一座城市有 $n$ 个点，编号为 $1\sim n$，由 $m$ 条无向边连通，第 $i$ 条边连通 $u_i$ 和 $v_i$，距离为 $d_i$。有出租车可以从任意结点坐到任意结点，行走 $p$ 距离收费 $\left\lfloor\cfrac{p}{r}\right\rfloor$ 元，多次乘坐多次收费。还有 $k$ 路公交车，第 $i$ 路公交车有 $t_i$ 个站台，在任意两个站台之间乘坐公交车花费 $c_i$。给定 $q$ 次询问，每次询问为 $(s,t)$ 的格式，求 $s$ 到 $t$ 最少需要花费的钱数。
---
做出租车很好处理，只需要将边权开成浮点数类型然后最后将答案向上取整即可。但是坐公交的方式又将如何处理呢？不难发现对于一路公交车的 $t_i$ 个站台 $\{s_i,s_2,\cdots,s_{t_i}\}$，他们两两直接连通且花费为 $c_i$，其实我们没有必要去将他们的边连起来，只需要增加一个虚拟结点让这些车站的点都忘虚拟结点连一条双向边，且其中一条边边权为 $c_i$，另一条边为 $0$ 即可。
注意一下坐完出租车立马去做公交车的情况，这里需要在切换时向上取整，再注意一下精度，这道题目就成了一道 dijkstra 的板子题了。时间复杂度 $\mathcal O(m\log_2 m)$，成功获得 $100$ 分。
```cpp
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
using LL = long long;
const LL kMaxN = 4e5 + 5;
ifstream cin("path.in");
ofstream cout("path.out");
struct Edge {
LL to;
double v;
Edge(LL to, double v):
to(to), v(v) { }
friend bool operator<(const Edge &a, const Edge &b) {
return a.v > b.v;
}
};
LL f[kMaxN], n, m, k, r, T;
double d[kMaxN];
vector<Edge> e[kMaxN];
priority_queue<Edge> q;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> k >> r >> T;
for (LL i = 1, u, v, d; i <= m; i++) {
cin >> u >> v >> d;
e[u].emplace_back(v, 1.0 * d / r);
e[v].emplace_back(u, 1.0 * d / r);
}
for (LL i = 1, t, c, x; i <= k; i++) {
for (cin >> t >> c; t; t--) {
cin >> x;
e[x].emplace_back(n + i, c);
e[n + i].emplace_back(x, 0);
}
}
for (LL s, t; T; T--) {
cin >> s >> t;
for (; q.size(); q.pop()) { }
fill(f + 1, f + n + k + 1, 0);
fill(d + 1, d + n + k + 1, 1e18);
for (q.emplace(s, 0), d[s] = 0; q.size(); q.pop()) {
Edge t = q.top();
if (f[t.to]) {
continue;
}
f[t.to] = 1;
for (auto i : e[t.to]) {
double x = i.to > n ? ceil(d[t.to]) : d[t.to];
if (x + i.v < d[i.to]) {
d[i.to] = x + i.v;
q.emplace(i.to, d[i.to]);
}
}
}
cout << (LL)ceil(d[t]) << '\n';
}
return 0;
}
```
## 牛半仙的妹子序列
有 $n$ 个妹子，魅力值为 $1\sim n$。牛半仙会选择若干个妹子组成序列 $\{p_1,p_2,\cdots,p_m\}$，当且仅当他是一个上升序列，不存在 $j$ 使得 $j>p_m$ 且 $v_j>v_{p_m}$，不存在 $j$ 使得 $j<p_1$ 且 $v_j<v_{p_1}$，且不存在 $j$ 使得 $p_i<j<p_{i+1},v_{p_i}<v_j<v_{p_{i+1}}$。求选择序列的方式，答案对 $998244353$ 取模。
---
不会写，题目都没有完全看懂，输出 $0$，一分没有。
## 总结
- **排名**：$9$；
- **比赛分数**：$200/400$；
- **情况**：相比 [[2024.10.17 模拟赛]]，一般；
- **问题**：不管空间然后 MLE。