2025-11-25 NOIP模拟赛总结
liuyi0905
·
·
生活·游记
::::info[温馨提示]
正文部分提及了 56 次 zrr、24 次祝等，共计 85 次。
累计提及了 83 次 zrr、270 次祝等，共计 367 次。
zrr 不要杀我
::::
前言
【MX-S7】梦熊 ZRR 2024 模拟赛 3 & SMOI Round 2（同祝赛）
我是 cutezrr。zrr 还是太可爱了好吧（写出了我们都喜欢 zrr 的原因）。
## A
我是 cutezrr（呼应开头、点题）。zrr 题目，写了我两个半小时……
最开始受到 zrr 的影响，导致完全偏离正解，根本没想到，脑袋里全是乱的，都怪 zrr（呼应前文）。
好在有 zrr 的帮助下，终于打破了误解的隔阂。zrr 偷偷告诉我，**炸弹和三带一都可以总结为一种情况：三张相同的 zrr 再带一个 cutezrr（简称三带祝）**。
所以题目就简化为了单牌、对子、三带祝。zrr 又告诉我，三带祝一次可以打出 $4$ 张牌，而其他的只能打出 $1 \sim 2$ 张。cutezrr！也就是说，要尽可能多拿三张牌，去带另一个祝！
容易发现，当每一种牌拿出所有的三张，剩下的一定是 $\varnothing$、单牌或祝子。所以有两种情况：
1. 三张牌的数量不少于剩下的牌的数量，也就是所有牌为很多三带祝和很多三张，显然是最优方案。那么剩下的三张肯定是继续分为三带祝和其他的，zrr 已经帮我算好了，直接输出 $c_3 + \frac{s_l}{4} + \lceil\frac{s_l \bmod 4}{2}\rceil$。
2. 三张牌的数量少于剩下的牌的数量，也就是说凑完所有三带祝后还会剩下一些单牌或祝子，答案肯定就是三张牌的组数加上剩下的祝的种类数。要使答案尽可能小，显然三带祝要先带单牌，再带祝子。
zrr 早就帮我证明了，这个方法是最优的。大样例全过！祝！两个小时的奋斗后，终于做出 T1，感谢 zrr（作者对 zrr 的态度由讨厌转变为赞美，侧面体现了 zrr 的实力之强）！
::::success[Happy Zrr]
```cpp
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 3e5 + 5;
int t, n, c[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n;
LL s = 0, v = 0;
for (int i = 1; i <= n; i++) {
cin >> c[i], s += c[i] / 3, c[i] %= 3, v += c[i];
}
sort(c + 1, c + n + 1);
if (s >= v) {
LL k = (s - v) * 3;
cout << v + k / 4 + (k % 4 + 1) / 2 << "\n";
} else {
int i = 0, x = s;
for (; i < n && c[i + 1] <= x; i++) x -= c[i + 1];
cout << s + n - i << "\n";
}
}
return 0;
}
```
::::
最开始忘开 `long long` 了，直接变身 cutezrr。还是那句话，十年 OI 一场空，不开 `long long` 见睿融（引用 zrr 的话，增强说服力）。
## B
zrr 有实力啊，帮助我再下一城（为后文 zrr 发力做铺垫）！感觉 T2 比 T1 简单多了，原来是 zrr 发力了。
很一眼的题目，要求
$$\max_{z = 1}^n \{a_x+a_z+ a_y - \operatorname{dist}(x, z) - \operatorname{dist}(z, y)\}$$
融易发现
$$a_x + a_z + a_y - \operatorname{dist}(x, z) - \operatorname{dist}(z, y)$$
$$=a_x + a_y - \operatorname{dist}(x, y) + \max_{p \in \operatorname{path}(x, y)}\{a_z - 2\operatorname{dist}(z, p)\}$$
zrr 给予了我灵感（表达对 zrr 的赞美与喜爱）！考虑对每个 zrr 求出
$$\max_{i = 1}^n\{a_i - 2\operatorname{dist}(i, zrr)\}$$
🤔那这也不好求啊，cutezrr 吧。只好先写了一个暴力骗 $60$ 分。哎呀！我是美丽 zrr！张蓉蓉吧，不是直接祝形 DP 马。射 $f_i$ 表示点 $i$ 的最大贡献，对于边 $u \to v$，祝态转移方程：
$$\begin{cases}f_u = \max(f_u, f_v - 2w)\\f_v = \max(f_v, f_u - 2w)\end{cases}$$
真是奇怪，好没有逻辑的 DP 啊，一上一下的。zrr 快救我！怎么感觉，跑两遍 DFS 就可以了喵！还是张蓉蓉厉害（反复强调 zrr 的巨），这样就可以正确的求出所有值了。
然后就要解决 $\max_{i \in \operatorname{path}(x, y)}\{f_i\}$ 了，这有如何是好呢？我可不想写熟练剖粪，那是不是直接 LCA！大祝睿全过了！好祝！（侧面体现出 zrr 的强大）
::::success[Zhu Speaker]
```cpp
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5;
LL n, q, a[N], h[N], d[N], p[N][25], f[N][25];
vector<pair<int, LL>> e[N];
void C(int u, int fa) {
for (auto [v, w] : e[u]) {
if (v == fa) continue;
f[v][0] = max(f[v][0], f[u][0] - 2 * w), C(v, u), f[u][0] = max(f[u][0], f[v][0] - 2 * w);
}
}
void S(int u, int fa) {
h[u] = h[fa] + 1;
p[u][0] = fa;
for (int i = 1; (1 << i) <= h[u]; i++) {
p[u][i] = p[p[u][i - 1]][i - 1];
f[u][i] = max(f[u][i - 1], f[p[u][i - 1]][i - 1]);
}
for (auto [v, w] : e[u])
v != fa && (d[v] = d[u] + w, S(v, u), 1);
}
int L(int x, int y, bool o) {
h[x] > h[y] && (swap(x, y), 1);
LL s = 0;
for (int i = 20; ~i; i--) {
h[x] <= h[p[y][i]] && (s = max(s, f[y][i]), y = p[y][i]);
}
if (x == y) return (o ? x : max(s, f[x][0]));
for (int i = 20; ~i; i--) {
if (p[x][i] == p[y][i]) continue;
s = max({s, f[x][i], f[y][i]}), x = p[x][i], y = p[y][i];
}
return (o ? p[x][0] : max({s, f[x][1], f[y][1]}));
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i], f[i][0] = a[i];
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
e[u].push_back({v, w}), e[v].push_back({u, w});
}
C(1, 0), C(1, 0), S(1, 0);
for (int x, y; q; q--) {
cin >> x >> y;
cout << a[x] + a[y] + L(x, y, 0) - d[x] - d[y] + 2 * d[L(x, y, 1)] << "\n";
}
return 0;
}
```
::::
跑两边 DFS 的人类智慧做法也是耗费整整半个小时才想到的好吧，要不是 zrr 帮了我，估计就做不出来了呢，zrr 是我最好的朋友！（直抒胸臆，表达对 zrr 的喜爱）
## C
好抽象的题目喵，怎么还有伪代码喵，根本看不懂喵（体现出 ly 的无能，反衬出 zrr 的巨）。这下就都得靠 zrr 了，能否上 $300$ 只看张蓉蓉的实力了。
弄了半天，还是没有简化 `sum` 具体算的是什么，时间也不多了。唯一的发现就是题目错了，他的代码明明就是错的！他 RE 了！跟个 cutezrr 一样，`deque` 都不判空就在那 `.front()`。
只有 20 分钟了，在 zrr 的提醒下（写出了 zrr 的善良的品质），只好打出了 $\mathcal{O}(n!^2n^2)$ 的超级大暴力，可以通过 $n \le 6$ 的 $4$ 分的测试点！zrr 太聪明了。
通过观察，数据中有很~~小~~大可能性答案为 $0$，所以在 $n > 6$ 的时候直接输出祝！
::::success[Monotonic Zhu]
```cpp
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5e5 + 5;
LL n, c[N], a[N], l[N], r[N], s;
LL C() {
deque<int> q;
LL s = 0;
for (int i = 1; i <= n; i++) {
for (int j = r[i - 1] + 1; j <= r[i]; j++) {
for (; q.size() && a[q.back()] < a[j]; q.pop_back()) s += c[q.back()];
q.push_back(j);
}
for (; q.size() && q.front() < l[i]; q.pop_front());
}
return s;
}
void R(int x) {
if (x > n) {
s = max(s, C());
return;
}
for (int i = max(l[x], r[x - 1]); i <= n; i++) r[x] = i, R(x + 1);
}
void L(int x) {
if (x > n) return R(1);
for (int i = l[x - 1]; i <= n; i++) l[x] = i, L(x + 1);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 1; i <= n; i++) cin >> a[i];
n <= 6 ? L(1), cout << s : cout << 0;
return 0;
}
```
::::
膜拜一下 xbc 巨姥暴切 T3，太强了%%%
## D
饿啊！神秘祝弈论，好难啊。$n \le 20$ 的暴力都不会打，只写了一个 $10$ 分的特殊性质。可……可……祝睿融吧！情况倒是判对了，但是输出错了！答案是 $2^n$，我输出了一个 $1$，为什么，我在干什么？太生气了，都怪 zrr（可以看到一个虽然巨但是爱导乱的 zrr）。
zrr 你不能这样，你必须教我打其他的分数。于是写了一个暴力，就是那个 $\mathcal{O}(2^{2n})$ 的暴力……找规律。终究是拼尽全力无法战胜了，一分也没有……一直写到最后一分钟，还是不会。
It's all zrr's fault, I hate zrr!（zrr 是个人物）
## 后记
这次难度偏低，绿蓝蓝紫（怪不得 zrr AK 了）。T3 好像也没有祝么难，就是一个简单的 DP 或者贪心，下次不能再靠 zrr 了。
只有三天就要考 NOIP 了（为什么 NOIP 要在长郡考啊，是不是又是 zrr 搞的鬼），也只有三天就要上文化课了，唉……时间怎么过的这么快啊。也希望 NOIP 和一个月后的期末都能在 cutezrr 的帮助下好起来（总结全文，升华主旨，表达对 zrr 的赞美、喜爱、厌恶、嫉妒与敬佩之情）！
ps: 今天使用了 pty 昨天教的技术：Arbiter 测试、使用脚本编译代码和 gdb。一个没用的，一个有用的，一个将来有用的，非常的高级。
::::info[Arbiter]
一个 NOI-Linux 的软件，用来帮助你测试你的程序，其环境和评测系统相同。给一些肢体有残缺的 zrr 使用。
1. 创建考试（默认 day1），添加试题（将四道题目加进去）。系统会自动创建一些文件与文件夹，其中只有 `evaldata`、`players` 和 `result` 有用。
2. 配置题目：将每一题的数据（样例）放入 `evaldata` 中，放一起，不需要建子文件夹。更改时间、空间限制、比较方式和编译选项。
3. **保存 保存 保存** ~~不然就要崩溃了~~。
4. 添加选手：在文件夹 `players` 下创立子文件夹 `day1`（没错，必须和比赛名称一样），将选手代码的快捷方式放入 `day1` 中（使用命令行 `ln -s` 创建）。
5. 测试程序，然后就可以看到你的得分了。
::::
::::info[run.sh]
一个用来测样例的 `Bash` 语言脚本（为了方便就取名 `run.sh`）。
:::success[点击查看代码]
```bash
set -e # 作用为如果任何命令执行失败，脚本将立即退出
name="shit" # 文件名
g++ -O2 -std=c++14 -Wall -Wextra -fsanitize=address,undefined -o $name $name.cpp # 编译代码
for i in {1..2}; do # for i in 1 2; do
eval "cp $name$i.in $name.in" # 将第 i 个样例输入存入 shit.in 中
./$name # 运行代码
eval "diff -Z $name.out $name$i.ans > diff.txt" # 比较输出与答案是否一致，并将差异存储到 diff.txt 文件中
echo "Testcase $i is correct." # 第 i 个样例通过
done
```
:::
其中 `shit` 表示文件名（题目名称）。
运行时，系统会提示你权限不足，所以要键入 `chmod +x run.sh` 开启权限。然后 `./run.sh` 运行脚本，就可以看到结果了。
考试前花两分钟提前打好，不浪费时间。
::::
gdb 根本没有听懂，太复杂了，不过看起来是一个对调试代码非常有用的东西，之后花点时间弄明白😃
::::warning[写在最后，祝意！]
祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝
祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝祝
```
祝 祝祝祝祝祝祝祝祝
祝 祝 祝
祝 祝 祝
祝 祝 祝
祝祝祝祝祝祝 祝 祝
祝 祝祝祝祝祝祝祝祝
祝祝 祝 祝
祝祝 祝 祝 祝
祝 祝 祝 祝 祝
祝 祝 祝 祝
祝 祝 祝
祝 祝 祝
祝 祝 祝 祝
祝 祝 祝 祝
祝 祝 祝祝祝祝祝
```
cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr cutezrr
::::