2025-11-13 NOIP模拟赛总结

liuyi0905 · 2025-11-13 15:51:38 · 生活·游记

前言

刚考完期中 我是不会告诉你我期中班排 40 名的😰 还好 CSP-S 考了分数线分，卡线来 NOIP 集训。

【LGR-165-Div.2】洛谷 NOIP 2023 模拟赛

演都不演了，直接放洛谷比赛😒

我怎么才知道我打过原赛😭 时隔两年再来做，分数直接比以前提高了 \infty 倍好吧（你怎么知道我之前爆零了）

绿紫紫黑，我请问呢？然后又垫底了，100 + 20 + 32 + 4 = 156，怎么感觉二等都没有了呢……

A

简单题，30 分钟秒了啊😁

前置知识：小学数学，设 n = \prod\limits_{i = 1}^k{p_i}^{c_i}，有 \tau(n) = \prod\limits_{i = 1}^k (c_i + 1)。

题目中要求 \prod\limits_{i = 1}^n \tau(a_i) 的最大值，考虑将 w 的质因子一个一个乘入 a 中。注意到，每次乘一定是要乘到贡献最大的数中，且贡献为 \frac{\prod\limits_{j = 1}^k \tau(a_j)}{c_{i, w} + 1}，直接模拟即可。

原来 NOIP 也有送分题啊

::::success[代码]

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e4 + 5, M = 998244353;
LL n, w, a[N], k[N];
vector<int> v;
vector<pair<int, int>> c[N];
pair<int, int> x[N];
int main() {
  // freopen("plant3.in", "r", stdin);
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> w;
  for (int i = 1, x; i <= n; i++) {
    cin >> a[i], x = a[i], k[i] = 1;
    for (int j = 2; j * j <= x; j++)
      if (!(x % j)) {
        c[i].push_back({j, 0});
        for (; !(x % j); c[i].back().second++, x /= j);
      }
    x > 1 && (c[i].push_back({x, 1}), 1);
    for (auto w : c[i]) k[i] *= w.second + 1;
  }
  for (int i = 2; i * i <= w; i++)
    for (; !(w % i); v.push_back(i), w /= i);
  w > 1 && (v.push_back(w), 1);
  for (auto o : v) {
    // cout << o << "\n";
    for (int i = 1; i <= n; i++) {
      int l = lower_bound(c[i].begin(), c[i].end(), make_pair(o, 0)) - c[i].begin();
      x[i] = {l < c[i].size() && c[i][l].first == o ? c[i][l].second + 1 : 1, i};
    }
    sort(x + 1, x + n + 1);
    int i = x[1].second, l = lower_bound(c[i].begin(), c[i].end(), make_pair(o, 0)) - c[i].begin();
    // cout << o << " " << i << " " << x[1].first << "\n";
    k[i] += k[i] / x[1].first;
    l < c[i].size() && c[i][l].first == o ? c[i][l].second++ : (c[i].push_back({o, 1}), 1);
    sort(c[i].begin(), c[i].end());
  }
  LL s = 1;
  for (int i = 1; i <= n; i++) s = s * k[i] % M;
  cout << s;
  return 0;
}

::::

B

刚做完送分题，这下是送命题了😱 又是神人构造题，怎么在做的各位都是注意力惊人的场切紫题大佬 orz

死磕 3h 无果，后来果断放弃，只好写其他的题去了，只想到了 k = 1 且 n 为偶数的做法😪

这是正解：

相邻无序数对的个数为 \frac{n(n - 1)}{2}，而不同的无序数对个数也为 \frac{n(n - 1)}{2}，所以要将所有无序数对填入格子中。

可以发现差为 1 的数对个数为 n - 1 个，差为 2 的数对个数为 n - 2 个，以此类推，差为 n 的数对个数为 1 个，考虑将他们填入格子。

注意到：

对于开头为 x 的序列，若这样填

x~~~x + 1~~~x - 1~~~x + 2~~~x - 2~\cdots

将 1 \sim n 的所有 x 开头的序列填入格子中就可以满足条件。

举个例子，当 n = 7 时：

1 & 2\\ 2 & 3 & 1 & 4\\ 3 & 4 & 2 & 5 & 1 & 6\\ 4 & 5 & 3 & 6 & 2 & 7 & 1\\ 5 & 6 & 4 & 7 & 3\\ 6 & 7 & 5\\ 7\end{matrix}

按长度排序后输出即可。

代码就非常短了

#include <bits/stdc++.h>
using namespace std;
int n, t;
int main() {
  cin >> n >> t;
  for (int i = n, j = n - 1, o = -1; ~j; i += o * j, j--, o = -o) {
    cout << i << " ";
    for (int k = 1; k <= min(i, n - i); k++)
      cout << i + k << " ", i - k && (cout << i - k << " ");
    cout << "\n";
  }
  return 0;
}

我是可爱zrr，怎么这都没想到😢 该退役了>

C

紫色的人类智慧 恐怖如斯

通过大眼观察法，容易发现当 n \ge 29 时最小值出现次数已经超过 10^{18} 了，而 k 最大也就 10^{18}，所以求第 k 小也就是求最小值了。

可惜考场也没想到怎么快速求最小值，也算是废了吧

而且没有发现 n \in [10^5, 10^6] 也有一档，痛失 20 分呜呜呜

::::success[52 分代码]

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e6 + 5, M = 998244353;
LL t, n, m, k[N], a[N], b[10 * N], p[N];
int main() {
  // freopen("npc.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n >> m, b[0] = 0;
    for (LL i = 1; i <= n; i++)
      k[i] = i * (n - i + 1), a[i] = 1 + __lg(i & -i);
    sort(a + 1, a + n + 1);
    if (n <= 10) {
      iota(p + 1, p + n + 1, 1);
      do {
        b[++b[0]] = 0;
        for (int i = 1; i <= n; i++) b[b[0]] += k[i] * a[p[i]];
      } while(next_permutation(p + 1, p + n + 1));
      sort(b + 1, b + b[0] + 1);
      cout << b[m] << "\n";
    } else {
      sort(k + 1, k + n + 1, greater<LL>());
      LL s = 0;
      for (int i = 1; i <= n; i++) s = (s + k[i] * a[i] % M) % M;
      if (n > 28 || m == 1) {
        cout << s << "\n";
      } else {
        LL r = 1e18;
        for (int i = 1; i <= n; i++)
          for (int j = 1; j < i; j++)
            r = min(r, (k[j] - k[i]) * (a[i] - a[j]));
        cout << s + r << "\n";
      }
    }
  }
  return 0;
}

::::

D

很大的博弈论题目，黑色的\

暴力应该是有 28 分的，可不知为什么因为一些奇奇怪怪的情况导致只有 4。

测试点 1 \sim 2 和 11：直接暴力 dfs，记录当前状态。

测试点 3 \sim 5：记忆化，时间复杂度 \mathcal{O}(n^2 k^2)。

测试点 16：预处理区间每个数在数列中出现的位置，查询时二分查找 [l, r] 中第一个出现 x 的位置，选那个数的人赢。