2025-11-27 NOIP模拟赛总结
liuyi0905
·
·
生活·游记
前言
【MX-S5】梦熊 NOIP 2024 模拟赛 1（同步赛）
NOIP 前最后一场模拟赛了，是想让我在死前先把 rp 全都用光吗？
不好，后天就是 NOIP 了😵 希望至少做出一道题了，不然就真的变成 cutezrr 了。
## A
非常 ez 的题目，看到从 $x$ 跳 $k$ 步，这一眼倍增好吧。
主要是看一些奇怪的细节，因为串是 $S^{\infty}$，所以倍增只能维护到的位置对 $n$ 取模的结果。🤔 这不简单，再维护一个经过段数的数量不就可以了。
设 $f_{i, j}, k_{i, j}$ 分别表示从位置 $i$ 跳 $2^j$ 步走到的位置（对 $n$ 取模）和经过点 $0$ 的次数，也就表示位置为 $k_{i, j} n + f_{i, j}$。
转移就非常板了
$$\begin{cases}f_{i, j} = f_{f_{i, j - 1}, j - 1}\\k_{i, j} = k_{i, j - 1} + k_{f_{i, j - 1}, j - 1}\end{cases}$$
重点就在于初始化了，求出 $f_{i, 0}$ 与 $k_{i, 0}$ 是个问题😕 不过聪明的我一下子就想到了，预处理每一个点 $i$ 前面的最后一个 $1$ 的位置 $p_i$（若没有则记为 $-1$），每一个点做神秘分讨：
设 $x = p_{(i + m) \bmod n}$，即可以够到的最远点。
1. $x \not= -1$ 且 $x$ 不是 $i$ 本身，表示可以直接找到目标点，所以 $f_{i, 0} \gets x, k_{i, 0} \gets \lfloor\frac{i + m}{n}\rfloor$。
2. 无法直接找到目标，则若目标可以存在 $x$ 前一段的末尾，$f_{i, 0} \gets p_{n - 1}, k_{i, 0} \gets \lfloor\frac{i + m}{n}\rfloor - 1$。
3. 若不行，则 $f_{i, 0} \gets (i + 1) \bmod n, k_{i, 0} \gets \lfloor\frac{i + 1}{n}\rfloor$。
这样就可以愉快的做倍增了，记得取模，不然就是 zrr。代码中下标从 $0$ 开始，注意细节。还有个问题，总感觉少了点什么，没错！需要特判 $S = \texttt{0}^n$ 的情况，不然就会喜提 $95$ 分的好成绩：
耗时 40min 终于写出。
::::success[T1 - 王国边缘]
```cpp
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, M = 1e9 + 7;
LL n, m, q, p[N], f[N][61], k[N][61];
string s;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q >> s;
if (!~s.find('1')) {
for (LL x, l; q; q--) {
cin >> x >> l, cout << (x + l) % M << "\n";
}
exit(0);
}
for (int i = 0; i < n; i++) {
p[i] = (s[i] == '1' ? i : (i ? p[i - 1] : -1));
}
for (int i = 0; i < n; i++) {
int x = p[(i + m) % n];
if (~x && (x != i || m >= n)) {
f[i][0] = x, k[i][0] = (i + m) / n;
} else if (i + m >= 2 * n - 1 || i + m >= n - 1 && i < p[n - 1]) {
f[i][0] = p[n - 1], k[i][0] = (i + m) / n - 1;
} else {
f[i][0] = (i + 1) % n, k[i][0] = (i == n - 1);
}
}
for (int j = 1; j < 61; j++)
for (int i = 0; i < n; i++) {
f[i][j] = f[f[i][j - 1]][j - 1];
k[i][j] = (k[i][j - 1] + k[f[i][j - 1]][j - 1]) % M;
}
for (LL x, y, l, s; q; q--) {
cin >> x >> l, x--;
y = x % n, s = x / n % M;
for (LL i = 60; ~i; i--) {
(1ll << i) <= l && (s = (s + k[y][i]) % M, y = f[y][i], l -= (1ll << i));
}
cout << (s * n % M + y + 1) % M << "\n";
}
return 0;
}
```
::::
ps: 特判 $S = \texttt{0}^n$ 最开始判成了 $S = \texttt{1}^n$ 而且里面没有取模，大样例寄了，调了半天硬是没找到哪里错了😌。
## B
水到不能再水了，返回贪心板子题啊，$15$ 分钟秒了>
感觉还没 T1 难（貌似是这样的）。
::::success[T2 - 买东西题]
```cpp
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e6 + 5;
LL n, m, s;
pair<LL, LL> a[N], v[N];
priority_queue<LL> q;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;
}
for (int i = 1; i <= m; i++) {
cin >> v[i].first >> v[i].second;
}
sort(a + 1, a + n + 1);
sort(v + 1, v + m + 1);
for (int i = 1, j = 1; i <= n; i++) {
auto [x, k] = a[i];
for (; j <= m && x >= v[j].first; j++) q.push(v[j].second);
if (q.size() && x - q.top() < k) {
s += x - q.top(), q.pop(), q.push(x - k);
} else s += k;
}
cout << s;
return 0;
}
```
::::
## C
挺有意思的一道题。
很容易发现，整个序列在操作过程中一定只有 $0, 1, 2$ 三个数，看 $\operatorname{popc}$ 表：
|$\operatorname{popc}(x + y)$|$0$|$1$|$2$|
|:-:|:-:|:-:|:-:|
|$0$|$0$|$1$|$1$|
|$1$|$1$|$1$|$2$|
|$2$|$1$|$2$|$1$|
可貌似并不是很好做😞 还只想到了 $\mathcal{O}(n!)$ 的暴力，但马上又想到了 $\mathcal{O}(n^3)$ 求第一问的区间 DP。他那个求字典序最小的方案太烦人了，根本不知道如何处理。
突然发现 $a$ 中不含 $0$ 的特殊性质非常有趣，因为 $\operatorname{popc}(1 + 1) = 1, \operatorname{popc}(2 + 2) = 1, \operatorname{popc}(1 + 2) = 2$，也就是说当两数相同，答案为 $1$，否则答案为 $2$。注意到，无论如何操作，最终剩下的数是一个定值，所以模拟一遍求一下即可。字典序最小嘛，肯定是全对序列的开头操作。
很快就有 $27$ 分了，但就要止步于此了吗？还有两个多小时呢，感觉可以用一些骚操作把第一问求出来。惊人的注意力再次到来，当且仅当 $a$ 为 $11\cdots120211\cdots1$ 的形式时答案为 $2$，否则答案为 $1$。
::::info[证明]
首先可以得到几个结论：
+ 因为没有 $0$ 的情况已经被判掉了，所以序列中一定有 $0$。
+ 考虑将每个 $0$ 的左右两边进行合成，如果两边不都是 $2$，那么一定可以合出 $1$。
+ 对于一个没有 $0$ 的序列，她的答案为 $2$ 的个数对 $2$ 取模的结果加一。
对此展开分类讨论：
1. $0$ 的数量超过一个，可以证明答案具有单调性，$0$ 的个数越多越可能合出 $1$，所以只讨论两个 $0$ 的情况。
序列 $a$ 一定形如 $A0B0C$，则又有两种情况：
+ $A, B, C$ 均为 $2$，那么这样操作：$20202 \to 2012 \to 212 \to 22 \to 1$。
+ $A, B, C$ 不全为 $2$，那么先将所有的 $2$ 与 $0$ 凑成 $1$，最后就变为了一个没有 $2$ 的序列，答案一定为 $1$。
2. 只有一个 $0$：
+ 若 $2$ 的个数为偶数，那么判断 $0$ 的左右是否都是 $2$。如果有一个不是 $2$，那么和 $1$ 合并，达到目标；如果两个都是 $2$，因为序列不为 $11\cdots120211\cdots1$ 的形式，所以让所有 $2$ 先把 $1$ 干掉，$a$ 变为 $22\cdots2022\cdots2$ 的形式。至少有一边有至少两个 $2$，将最靠近 $0$ 的两个 $2$ 合出 $1$，再用 $1$ 将 $0$ 消掉，最终也变成了一个没有 $0$ 且 $2$ 的个数为偶数的序列。
+ 若 $2$ 的个数为奇数，则让最靠近 $0$ 的那个二把中间的 $1$ 全部干掉，和 $0$ 合并变为 $1$，使 $2$ 的个数变为偶数。
所有情况全都讨论到了，证毕。
::::
这个证明还是有点小复杂的啊，那么多情况，证了我半天。不过这样就可以拿到第一问的 $25$ 分，共计 $43$ 分😥 我真是太强了👍
::::success[T3 - IMAWANOKIWA]
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int t, n, a[N], v;
unsigned long long H;
bool f[N];
array<int, N> o, w;
string c;
int C(int x) { return (x == 3 ? 2 : !!x); }
void S(int x, vector<int> a) {
if (x > n - 1) {
if (a[0] == v && o < w) {
w = o;
for (int i = H = 0; i < n; i++) H = H * 13331 + o[i];
}
return;
}
for (int i = 0; i + 1 < a.size(); i++) {
vector<int> b = a;
b.erase(b.begin() + i, b.begin() + i + 2);
b.insert(b.begin() + i, C(a[i] + a[i + 1]));
o[x] = i + 1, S(x + 1, b);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> c, n = c.size(), c = " " + c;
bool l = 1, p = 1;
for (int i = 1; i <= n; i++) {
a[i] = c[i] - '0', l &= !!a[i], p &= !a[i];
}
unsigned long long h = 0;
for (int i = 2; i <= n; i++) h = h * 13331 + 1;
if (p) {
cout << "0 " << h << "\n";
} else if (l) {
int s = a[1];
for (int i = 2; i <= n; i++) s = C(s + a[i]);
cout << s << " " << h << "\n";
} else {
fill(f + 1, f + n + 1, 0), f[n + 1] = 1;
for (int i = n; i; i--) {
f[i] = f[i + 1] & (a[i] == 1);
}
bool e = 1, g = 0;
for (int i = 1; i + 2 <= n && e && !g; i++) {
g |= a[i] == 2 && !a[i + 1] && a[i + 2] == 2 && f[i + 3];
e &= a[i] == 1;
}
v = g + 1;
vector<int> z;
for (int i = 1; i <= n; i++) z.push_back(a[i]);
cout << v << " " << (n <= 10 ? w.fill(n + 1), S(1, z), H : 0) << "\n";
}
}
return 0;
}
```
::::
根本干不动了，这个结论太烧脑了，绝对不能继续在 T3 停留了。什么？只有 $10$ 分钟了？！这我玩你睿融啊，赶紧开 T4！
## D
5！4！3！2！1！最后一秒极限提交，什么叫真正的实力！你可不要小瞧这 $8$ 分了，因为要是没有这 $8$ 分我就……还是 rk1……那我可真的是要要小瞧这 $8$ 分了😰
没有什么时间了，只写了纯暴力，$\mathcal{O}(2^k nm(|S| + |T|))$。我是张蓉蓉，特殊性质 A 都没写，都怪 zrr。
::::success[T4 - 魔法少女们]
```cpp
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5e5 + 5, M = 1e9 + 7;
LL c, n, m, k, l, r;
string s[N], t[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> c >> n >> m >> k;
for (int i = 1; i <= n; i++) cin >> s[i];
for (int i = 1; i <= m; i++) cin >> t[i];
for (int i = 0; i < (1 << k); i++) {
l = 0;
bool f = 1;
for (int j = 0; j < k && f; j++) {
((i >> j) & 1) ? (l ? l-- : f = 0) : (l++);
}
if (!f || l) continue;
string v = "";
for (int j = 0; j < k; j++) {
v += ((i >> j) & 1) ? ")" : "(";
}
for (int x = 1; x <= n; x++)
for (int y = 1; y <= m; y++) {
r += v.substr(0, s[x].size()) == s[x] && v.substr(k - t[y].size()) == t[y];
}
}
cout << r;
return 0;
}
```
::::
## 后记
最后一次模拟赛了，也希望后天 NOIP 正常发挥，rp++！