NOIP2021 游记及题解

浅述我的 NOIP2021 学习（划水）经历

$day -9:$

开始了停文化课的生活。

$day -6$

一天冲了 10 道题，大部分是弱项 DP，非常地开心。

$day -2:$

打了场全真模拟，靠瞎暴力和瞎骗分水了个 Rank 5, 没个卵用。。。

$day -1:$

上午回顾了一下自暑假以来被吊打的生活。

下午和学弟一起敲板子，被学弟吊打了/kk，做了一下去年 CSP 题（你问为什么不是 NOIP？我太弱了）瞄了一眼贪吃蛇题解发现我去年好像推出来结论了很开心。

头熄灯前照着本部的照片拍了个低仿版… 感谢 $\text{凉笙}$ 大神帮忙拍照

晚上睡不着和 $\text{宝硕}$，$youwike$，$zzf$ 在机房聊天，聊着聊着发现原来人家在叙旧，我在…

$day 0:$

在公交车上拿着昨天没写完的贪吃蛇，用 kupi 学长的热点交了一发 20 分，确认没挂，再瞄一眼题解：哦，只对了一半…（也不想想怎么可能切黑的）。

扭头一看，一车人都在睡觉。

上考场之前想再写一遍 FHQ 板子，结果没写出来。。。

马上进考场发现笔还在书包里，赶紧跑回去拿 $rp--$ 。

上考场，发现坐在离老师最远的一排，不错，风水宝地。
刚开题，四道都还没瞅完，机房里键盘声已经“振聋发聩”了。看到 T4 一页多的题面，我…

开始写 T1。想到了筛法，也不知道可不可过，莽他就完事了。测了一下大样例，挂了。哦 $1e7 + 1$。改了之后又在 Linux 测了一下。没变？？ Windows 一跑，对了。噫~好，玄学。把 Linux 终端重开一下，重复上面操作，哪里不对劲，刚刚忘编译了。。。

来来回回折腾了 1 小时，开 T2。一看 S 太大，必然爆 long long 。又涉及到了组合数（永远的痛）。果断爆搜。

T3 莫名奇妙拿到式子就想推，推一步，错一步，验算一步，改一步，来来回回什么也没有得到。赶紧打了个最小得分暴力爬了。

距离考试结束还剩 30 分钟，看了眼 T4，哦，可做，亏大了！！赶紧补救，最后 CE 遗憾删代码。

出考场，怎么都在随机化啊啊喂，这还是我认识的 OI 吗？

一测部分分拿稳了，民间数据最终得分：

$$100 + 20 + 12 + 0 = 132$$

唯一的遗憾就是被 T4 题面吓到了，没有来及写暴力。补了一周多的 DP 连 T2 两维暴力都没想出来也挺可惜的。替挂分遗憾退役的学长感到惋惜，尤其是刘雅奇学长，人真的很好，还有 kupi 学长，拿到了迟来的一等。

下午回学校昏昏沉沉的，感冒又反复了。

$day:1$

水了一天，写了游记

后记：

分数和估的一样（毕竟是暴力），HE rank 60。

update: 2021-12-21

补叙：貌似 T4 写了暴力也拿不到分…

NOIP T1-T3 题解

P7960 [NOIP2021] 报数

题目大意

多组询问，求出来在 $x \in [1, 1e7], f(x)$ 其中 $f(x)$ 表示 x 的下一个不是任意一个含 7 的数的整数倍的数，若 x 本身不满足，输出 -1。

题目正解

类素数筛法 + 指针/二分

题目思路

没有什么思维难度，写一个含 7 数判定函数和一个类素数筛，边筛边更新指针，最后一问一答 $O(1)$ 输出。

时间复杂度

$O(nloglogn)$

题目代码 (多写了一个右指针，不过没什么影响)

#include <bits/stdc++.h>
const int Maxn= 1e7 + 10;
using namespace std;

inline int read () {
    int x = 0, f = 1;
    char c = getchar ();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar ();
    }
    while (c >= '0' && c <='9') {
        x = x * 10 + (c ^ 48);
        c = getchar ();
    }
    return x * f;
}

bool check (int x){
    if (x % 7==0) return false;
    for (; x; x /= 10) if (x % 10 == 7) return false;
    return true;
}
int l[Maxn], r[Maxn], lst;
bool vis[Maxn];

void init () {
    memset (l, -1, sizeof (l));
    memset (r, -1, sizeof (r));
    for (int i = 1; i <= (int)1e7 + 1; ++i) {
        if (vis[i])continue;
        if (!check (i)) {
            for (int j = 1; i * j <= (int)1e7 + 1; j++) {
                vis[i * j] = 1;
            }
        } else {
            l[i] = lst, r[lst] = i;
            lst = i;
        }
    }
}

int main () {
    init ();
    int t = read ();
    for (int i = 1; i <= t; ++i) {
        int x = read ();
        if (l[x] == -1 && r[x] == -1) {
            printf ("-1\n");
        } else {
            printf ("%d\n", r[x]);
        }
    }
}

P7961 [NOIP2021] 数列

题目

给定整数 $n, m, k$，和一个长度为 $m + 1$ 的正整数数组 $v_0, v_1, \ldots, v_m$ 。
对于一个长度为 $n$，下标从 $1$ 开始且每个元素均不超过 $m$ 的非负整数序列 $\{a_i\}$ ，我们定义它的权值为 $v_{a_1} \times v_{a_2} \times \cdots \times v_{a_n}$ 。
当这样的序列 $\{a_i\}$ 满足整数 $S = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_n}$ 的二进制表示中 $1$ 的个数不超过 $k$ 时，我们认为 $\{a_i\}$ 是一个合法序列。

计算所有合法序列 $\{a_i\}$ 的权值和对 $998244353$ 取模的结果。

题目正解

状压 DP + 可重集排列

题目思路

首先考场上是没有想到的，出考场之后听说 DP 能拿 50, wtc?

然后写了一下 50 分 DP, 大概可以把它算成背包？
$f_{i, s}$ 表示当前 dp 到第 i 位，已经选出来的总和为 s 的贡献（这里实际上是消掉了 j 维），枚举 i, j(现在在考虑 m 中的哪个元素), s ，最后根据 popcnt 计算合法，统计答案。

$$f_{i, s} += f_{i - 1, s - 2^j} \times v_j$$

复杂度 $O(n^2m\times 2^m)$

然后考虑优化，首先可以想到用可重集排列来优化，因为样例解释中已经给到提示了。
因为很显然 S 的大小会爆 long long ，所以要考虑把 S 维拆掉，进行一些替换。
因为在 v 中依次选择的数下标是单调的增。所以已经计算过的位就不必计较具体数值。
且可以发现，一个数对当前 s 的影响最多比当前位高 5 位，
所以思路逐渐清晰，可以将 s 拆成 k 和 s’ 分别表示已经弃掉的位置一共包含几个 1 以及 s 当前和未来 5 位。
设 $f_{i, j, k, s'}$ 表示当前 dp 到选择了 i 个数，当前拓展到 v 数组第 j 位，向高位拓展 5 位为 k, 已经弃掉的位置共有 s’ 个 1 的贡献数。
嵌套枚举 i, j, k, s’, p(当前位置新选择的个数) 来更新 f 数组。
现在刷表已经不太合适了，所以改用填表。

于是乎转移方程为

$$f_{i + p, j, k + ((s' \& 1) xor (p \& 1)), (s' / 2) + (p / 2) + ((s' \& 1) \&\& (p \& 1))} += f_{i, j - 1, k, s'} \times v^p_i / (p!)$$

时间复杂度

$O(n^3m^2)$

题目代码

// Code By CloudySky
#include <bits/stdc++.h>
#define popcnt __builtin_popcountll
#define int long long
namespace IO  // namespace IO
using namespace IO;
const int M = 110, N = 40;
const int P = 998244353;
using namespace std;

// dp 数组， v 数组的次方
int f[N][M][N][M], v[M][N];
// 阶乘， 阶乘的逆， 线性求逆元数组
int fac[M], ifac[M], inv[M];

signed main() {
  // 预处理阶乘和阶乘的逆。
  fac[1] = fac[0] = 1;
  ifac[1] = ifac[0] = inv[1] = 1;
  for (int i = 2; i <= 100; ++i) {
    fac[i] = fac[i - 1] * i % P;
    inv[i] = (P - P / i) * inv[P % i] % P;
    ifac[i] = ifac[i - 1] * inv[i] % P;
  }
  // 读入与预处理 v 的次方
  int n = read(), m = read() + 1, K = read();
  for (int i = 1; i <= m; ++i) {
    v[i][1] = read(), v[i][0] = 1ll;
    for (int j = 2; j <= n; ++j)
      v[i][j] = v[i][j - 1] * v[i][1] % P;
  }
  // dp
  f[0][0][0][0] = 1;
  for (int i = 0; i <= n; ++i) {
    for (int j = 1; j <= m; ++j)
      for (int k = 0; k <= K; ++k)
        for (int s = 0; s <= 70; ++s)
          for (int p = 0; p <= n - i; ++p)
            (f[i + p][j][k + ((s & 1) ^ (p & 1))][(s / 2) + (p / 2) + ((s & 1) && (p & 1))] += f[i][j - 1][k][s] * v[j][p] % P * ifac[p] % P) %= P;
  }
  // 统计答案
  int ans = 0;
  for (int k = 0; k <= K; ++k) {
    for (int s = 0; s <= 70; ++s)
      if (k + popcnt(s) <= K)
        ans = (ans + f[n][m][k][s] * fac[n] % P) % P;
  }
  print(ans);
  return 0;
}

P7962 [NOIP2021] 方差

题目大意

给定一个序列 a, 每次可以选定 $x\in (1, n)$ ， 将 $a_x$ 改为 $a_{x - 1} + a_{x + 1} - a_x$ 。求经过任意次操作后的最小方差的 $n^2$ 倍。

题目正解

构造 + dp

题目思路

这道题能提供的思路就比较匮乏了。
首先，这道题和差分有关。怎们想到差分的不懂。发现每次操作相当于交换差分数组的两个位置。
发现最优情况下差分数组一定是单谷形的。
然后考虑先排序再 dp ，思路大概是一个反着的方格取数。
题中的差分可以化简为 $n\sum a_i^2 + (\sum a_i)^2$
$f_{i, j}$ 表示已经放了 i 个数，当前总和为 j 的平方和的最小值。
每次考虑将当前数放在左边还是右边即可。

时间复杂度

$O(na^2)$

题目代码

// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO  // namespace IO
using namespace IO;
const int Maxn = 5e5 + 10;
const int inf = 1e18;
using namespace std;

int a[Maxn], x[Maxn], f[2][Maxn];

signed main() {
  int n = read ();
  for (int i = 1; i <= n; ++i)
    a[i] = read ();
  n--;
  for (int i = 1; i <= n; ++i)
    x[i] = a[i + 1] - a[i];
  sort (x + 1, x + n + 1);
  int s = 0;
  for (int i = 1; i <= n; ++i)
    s += x[i] * i;
  int cnt = 0, u = 0;
  for (int j = 0; j <= s; ++ j)
    f[u][j] = inf;
  f[0][0] = 0;
  for (int i = 1, d; i <= n; ++i) {
    if (x[i] == 0) continue;
    d = x[i], u ^= 1, cnt += d;
    for (int j = 0, k; j <= s; ++j) {
      f[u][j] = inf;
      k = j - i * d;
      if (k >= 0)
        f[u][j] = min (f[u][j], f[u ^ 1][k] + i * d * d + 2 * k * d);
      k = j - cnt;
      if (k >= 0)
        f[u][j] = min (f[u][j], f[u ^ 1][k] + cnt * cnt);
    }
  }
  int ans = inf;
  for (int j = 0; j <= s; ++j)
    if (f[u][j] < inf)
      ans = min (ans, (n + 1) * f[u][j] - j * j);
  printf ("%lld\n", ans);
  return 0;
}

本文作者：CloudySky
写作时间： 2021-11-21
最后更新时间： 2021-12-21
遵循协议： BY-NC-SA