专栏文章

2025-11-13 NOIP模拟赛总结

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

文章操作

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

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

前言

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

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

演都不演了，直接放洛谷比赛😒
我怎么才知道我打过原赛😭 时隔两年再来做，分数直接比以前提高了 ∞\infty 倍好吧（你怎么知道我之前爆零了）
绿紫紫黑，我请问呢？然后又垫底了，100+20+32+4=156100 + 20 + 32 + 4 = 156，怎么感觉二等都没有了呢……

A

简单题，30 分钟秒了啊😁
前置知识：小学数学，设 n=∏i=1kpicin = \prod\limits_{i = 1}^k{p_i}^{c_i}，有 τ(n)=∏i=1k(ci+1)\tau(n) = \prod\limits_{i = 1}^k (c_i + 1)。
题目中要求 ∏i=1nτ(ai)\prod\limits_{i = 1}^n \tau(a_i) 的最大值，考虑将 ww 的质因子一个一个乘入 aa 中。注意到，每次乘一定是要乘到贡献最大的数中，且贡献为 ∏j=1kτ(aj)ci,w+1\frac{\prod\limits_{j = 1}^k \tau(a_j)}{c_{i, w} + 1}，直接模拟即可。
原来 NOIP 也有送分题啊
代码CPP
#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=1k = 1 且 nn 为偶数的做法😪
这是正解：
相邻无序数对的个数为 n(n−1)2\frac{n(n - 1)}{2}，而不同的无序数对个数也为 n(n−1)2\frac{n(n - 1)}{2}，所以要将所有无序数对填入格子中。
可以发现差为 11 的数对个数为 n−1n - 1 个，差为 22 的数对个数为 n−2n - 2 个，以此类推，差为 nn 的数对个数为 11 个，考虑将他们填入格子。
注意到：
对于开头为 xx 的序列，若这样填
x   x+1   x−1   x+2   x−2 ⋯x~~~x + 1~~~x - 1~~~x + 2~~~x - 2~\cdots
将 1∼n1 \sim n 的所有 xx 开头的序列填入格子中就可以满足条件。
举个例子，当 n=7n = 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}$$ 按长度排序后输出即可。
代码就非常短了
CPP
#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≥29n \ge 29 时最小值出现次数已经超过 101810^{18} 了，而 kk 最大也就 101810^{18}，所以求第 kk 小也就是求最小值了。
可惜考场也没想到怎么快速求最小值，也算是废了吧
而且没有发现 n∈[105,106]n \in [10^5, 10^6] 也有一档，痛失 2020 分呜呜呜
5252 分代码CPP
#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

很大的博弈论题目，黑色的\
暴力应该是有 2828 分的，可不知为什么因为一些奇奇怪怪的情况导致只有 44。
测试点 1∼21 \sim 2 和 1111：直接暴力 dfs，记录当前状态。
测试点 3∼53 \sim 5：记忆化，时间复杂度 O(n2k2)\mathcal{O}(n^2 k^2)。
测试点 1616：预处理区间每个数在数列中出现的位置，查询时二分查找 [l,r][l, r] 中第一个出现 xx 的位置，选那个数的人赢。
2828 分代码：
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 2e5 + 5;
int n, m, k, a[M], f[N][N][N][N];
vector<int> p[M];
int S(int l, int r, int x, int y) {
  if (l > r) return 0;
  if (a[l] == x) return 1;
  if (k > 2 && f[l][r][x][y] != 0x3f3f3f3f) return f[l][r][x][y];
  int s = max(a[l] == y ? -1 : -S(l + 1, r, y, x), x == y ? -1 : -S(l + 1, r, y, a[l]));
  return k <= 2 ? s : (f[l][r][x][y] = s);
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++)
    cin >> a[i], p[a[i]].push_back(i);
  memset(f, 0x3f, sizeof(f));
  for (int x, y, l, r, w; m; m--) {
    cin >> x >> y >> l >> r;
    if (x == y) {
      int v = lower_bound(p[x].begin(), p[x].end(), l) - p[x].begin();
      cout << (v < p[x].size() && p[x][v] <= r ? (p[x][v] % 2 ? "A" : "B") : "D") << "\n";
    } else {
      w = S(l, r, x, y), cout << (!w ? "D" : (~w ? "A" : "B")) << "\n";
    }
  }
  return 0;
}

总结

第一次打 NOIP 模拟赛，发现水平并不咋地，需要以后继续加油。

评论

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

正在加载评论...