专栏文章

2025-11-27 NOIP模拟赛总结

lliuyi0905
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0ivyg
此快照首次捕获于
2025/12/01 18:34
3 个月前
此快照最后确认于
2025/12/01 18:34
3 个月前
查看原文

前言

【MX-S5】梦熊 NOIP 2024 模拟赛 1（同步赛）

NOIP 前最后一场模拟赛了，是想让我在死前先把 rp 全都用光吗？
100+100+43+8=251100 + 100 + 43 + 8 = 251，rk1 好吧😆
不好，后天就是 NOIP 了😵 希望至少做出一道题了，不然就真的变成 cutezrr 了。

A

非常 ez 的题目，看到从 xx 跳 kk 步，这一眼倍增好吧。
主要是看一些奇怪的细节，因为串是 S∞S^{\infty}，所以倍增只能维护到的位置对 nn 取模的结果。🤔 这不简单，再维护一个经过段数的数量不就可以了。
设 fi,j,ki,jf_{i, j}, k_{i, j} 分别表示从位置 ii 跳 2j2^j 步走到的位置（对 nn 取模）和经过点 00 的次数，也就表示位置为 ki,jn+fi,jk_{i, j} n + f_{i, j}。
转移就非常板了
{fi,j=ffi,j−1,j−1ki,j=ki,j−1+kfi,j−1,j−1\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}
重点就在于初始化了，求出 fi,0f_{i, 0} 与 ki,0k_{i, 0} 是个问题😕 不过聪明的我一下子就想到了，预处理每一个点 ii 前面的最后一个 11 的位置 pip_i（若没有则记为 −1-1），每一个点做神秘分讨：
设 x=p(i+m) mod nx = p_{(i + m) \bmod n}，即可以够到的最远点。
  1. x≠−1x \not= -1 且 xx 不是 ii 本身，表示可以直接找到目标点，所以 fi,0←x,ki,0←⌊i+mn⌋f_{i, 0} \gets x, k_{i, 0} \gets \lfloor\frac{i + m}{n}\rfloor。
  2. 无法直接找到目标，则若目标可以存在 xx 前一段的末尾，fi,0←pn−1,ki,0←⌊i+mn⌋−1f_{i, 0} \gets p_{n - 1}, k_{i, 0} \gets \lfloor\frac{i + m}{n}\rfloor - 1。
  3. 若不行，则 fi,0←(i+1) mod n,ki,0←⌊i+1n⌋f_{i, 0} \gets (i + 1) \bmod n, k_{i, 0} \gets \lfloor\frac{i + 1}{n}\rfloor。
这样就可以愉快的做倍增了，记得取模，不然就是 zrr。代码中下标从 00 开始，注意细节。还有个问题，总感觉少了点什么，没错！需要特判 S=0nS = \texttt{0}^n 的情况，不然就会喜提 9595 分的好成绩：
耗时 40min 终于写出。
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=0nS = \texttt{0}^n 最开始判成了 S=1nS = \texttt{1}^n 而且里面没有取模，大样例寄了，调了半天硬是没找到哪里错了😌。

B

水到不能再水了，返回贪心板子题啊，1515 分钟秒了>
感觉还没 T1 难（貌似是这样的）。
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,20, 1, 2 三个数，看 popc⁡\operatorname{popc} 表：
popc⁡(x+y)\operatorname{popc}(x + y)001122
00001111
11111122
22112211
可貌似并不是很好做😞 还只想到了 O(n!)\mathcal{O}(n!) 的暴力，但马上又想到了 O(n3)\mathcal{O}(n^3) 求第一问的区间 DP。他那个求字典序最小的方案太烦人了，根本不知道如何处理。
突然发现 aa 中不含 00 的特殊性质非常有趣，因为 popc⁡(1+1)=1,popc⁡(2+2)=1,popc⁡(1+2)=2\operatorname{popc}(1 + 1) = 1, \operatorname{popc}(2 + 2) = 1, \operatorname{popc}(1 + 2) = 2，也就是说当两数相同，答案为 11，否则答案为 22。注意到，无论如何操作，最终剩下的数是一个定值，所以模拟一遍求一下即可。字典序最小嘛，肯定是全对序列的开头操作。
很快就有 2727 分了，但就要止步于此了吗？还有两个多小时呢，感觉可以用一些骚操作把第一问求出来。惊人的注意力再次到来，当且仅当 aa 为 11⋯120211⋯111\cdots120211\cdots1 的形式时答案为 22，否则答案为 11。
证明
首先可以得到几个结论：
  • 因为没有 00 的情况已经被判掉了，所以序列中一定有 00。
  • 考虑将每个 00 的左右两边进行合成，如果两边不都是 22，那么一定可以合出 11。
  • 对于一个没有 00 的序列，她的答案为 22 的个数对 22 取模的结果加一。
对此展开分类讨论：
  1. 00 的数量超过一个，可以证明答案具有单调性，00 的个数越多越可能合出 11，所以只讨论两个 00 的情况。
    序列 aa 一定形如 A0B0CA0B0C，则又有两种情况：
    • A,B,CA, B, C 均为 22，那么这样操作：20202→2012→212→22→120202 \to 2012 \to 212 \to 22 \to 1。
    • A,B,CA, B, C 不全为 22，那么先将所有的 22 与 00 凑成 11，最后就变为了一个没有 22 的序列，答案一定为 11。
  2. 只有一个 00：
    • 若 22 的个数为偶数，那么判断 00 的左右是否都是 22。如果有一个不是 22，那么和 11 合并，达到目标；如果两个都是 22，因为序列不为 11⋯120211⋯111\cdots120211\cdots1 的形式，所以让所有 22 先把 11 干掉，aa 变为 22⋯2022⋯222\cdots2022\cdots2 的形式。至少有一边有至少两个 22，将最靠近 00 的两个 22 合出 11，再用 11 将 00 消掉，最终也变成了一个没有 00 且 22 的个数为偶数的序列。
    • 若 22 的个数为奇数，则让最靠近 00 的那个二把中间的 11 全部干掉，和 00 合并变为 11，使 22 的个数变为偶数。
所有情况全都讨论到了，证毕。
这个证明还是有点小复杂的啊，那么多情况，证了我半天。不过这样就可以拿到第一问的 2525 分，共计 4343 分😥 我真是太强了👍
T3 - IMAWANOKIWACPP
#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 停留了。什么？只有 1010 分钟了？！这我玩你睿融啊，赶紧开 T4！

D

5！4！3！2！1！最后一秒极限提交，什么叫真正的实力！你可不要小瞧这 88 分了，因为要是没有这 88 分我就……还是 rk1……那我可真的是要要小瞧这 88 分了😰
没有什么时间了，只写了纯暴力，O(2knm(∣S∣+∣T∣))\mathcal{O}(2^k nm(|S| + |T|))。我是张蓉蓉，特殊性质 A 都没写，都怪 zrr。
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++！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...