2021 NOIP 题解

🕗 发布于 2024-11-10 20:56 算法

21年的题有点难啊（除了T1），竟然没绿题，直接紫题+黑题。

T1 P7960 [NOIP2021] 报数

原题链接

这道题还是挺水的。

因为是多组询问，首先预处理出答案，然后 $O (1)$ 查询。

在 $O (l o g n)$ 时间内判断一个数是否含有7，其中 $n$ 是数值的范围。

用筛法对每个含有 $7$ 的数的倍数给标记，因为含有 $7$ 的数密度很小，这一步近似看成是 $O (n)$

然后倒着循环一遍，处理一下每个数的下一个被标记的数是哪个，预处理的总时间复杂度为 $O (n l o g n)$

$co d e$

#include <bits/stdc++.h>
using namespace std;
int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
const int N = 1e7 + 5;
bool flag[N];
int ans[N];
//根据题意判断是否有7
bool check(int x) {
while (x) {
if (x % 10 == 7) {
return true;
}
x /= 10;
}
return false;
}
int main() {
for (int i = 1; i <= (N - 4); i++) {
//判断是否是7的倍数
if (check(i)) {
for (int j = i; j <= (N - 4); j += i) {
flag[j] = 1;
}
}
}
int x = 0;
for (int i = (N - 4); i >= 1; i--) {
if (flag[i])
ans[i] = -1;
else {
ans[i] = x;
x = i;
}
}
int T;
T=read();
while (T--) {
int x;
x=read();
printf("%d\n", ans[x]);
}
return 0;
}

T2 P7961 [NOIP2021] 数列

原题链接

这道题就开始没啥思路了，整的人挺无语的。

后来看了题解，感觉这道题还是可以理解的，当时比赛打暴力获得 $45 pt s$ ，还可以，比爆零好点。

先来说下暴力思路：

先不考虑序列里具体每个位置填哪些数，而是考虑每种数在序列中出现了多少次：

设 $x_i$ 为序列中值为 $i$ 的数的个数，即要满足 $x_0+x_1+x_2+...+x_m=n$ 。

这个不定方程的一个1非负整数解，即为一种不考虑具体位置的方案，如果要求真正1的方案数，只需乘以对应的组合数即可。

具体来说，就是第一步从 $n$ 个位置里选 $x_0$ 个，第二步是从 $n-x_0$ 个位置里选 $x_1$ 个，以此类推，方案数就会乘以 $C_{n}^{x_{0}} C_{n-x_{0}}^{x_{1}} C_{n-x_{0}-x_{1}}^{x_{1}} \cdots C_{x_{m}}^{x_{m}}$

而这道题每种方案的贡献是 $v_{a1}*v_{a2}*...*v_{an}$ ，也就是还要再乘以 $\prod_{i=0}^{m} v_{i}^{x_{i}} \text { }$

这样可以首先预处理组合数以及每个 $v_i$ 的幂次，然后写一个爆搜把每个不定方程的解求出来1，最后检查 $1$ 的个数是否合法。
$45 pt s$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
const LL mod = 998244353;
const int N=40;
LL ans;
LL c[N][N];
LL a[105][40];
int n, m, K;
void dfs(int u, int x, LL now, LL s) {
if (u == m + 1) {
//__builtin_popcountll()函数非常好用，返回二进制中1的个数
if (x == 0 && __builtin_popcountll(s) <= K){
ans = (ans + now) % mod;
}
return;
}
for (int i = 0; i <= x; i++) {
dfs(u + 1, x - i, now * c[x][i] % mod * a[u][i] % mod, s + ((LL)i << u));
}
}
int main() {
for (int i = 0; i <= 30; i++) {
c[i][0] = 1;
for (int j = 1; j <= i; j++){
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
n=read(),m=read(),K=read();
for (int i = 0; i <= m; i++) {
int x;
x=read();
a[i][0] = 1;
for (int j = 1; j <= n; j++) {
a[i][j] = a[i][j - 1] * x % mod;
}
}
dfs(0, n, 1, 0);
printf("%lld\n", ans);
return 0;
}

接下来想想正解：

注意道在从小到大枚举 $x_i$ 的时候，可以把 $S=2^{a_1}+2^{a_2}+...+2^{a_n}$ 分成两部分：

$.$ 前面 $0\sim 1$ 位中一共出现了多少个 $1$
$.$ 当前有多少个位进位道 $i + 1$ 位

现在我们就能dp了，我们设 $f [u] [i] [j] [k]$ 表示考虑完 $\le u$ 的数的个数后，已经用了 $i$ 个数，进位为 $j$ ， $\sim u$ 位一共有 $k$ 个 $1$ 的总贡献。

最后 $d p$ 完将所有的贡献加起来就行了。

$co d e$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 998244353;
const int N = 40;

LL c[N][N], a[105][N], f[105][N][N][N];
// f[u][i][j][k] 考虑完<=u的数的个数后，已经用了i个数，进位为j，0~u 位一共有k个1

int main() {
    int n, m, K;
    for (int i = 0; i <= 30; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 0; i <= m; i++) {
        int x;
        scanf("%d", &x);
        a[i][0] = 1;
        for (int j = 1; j <= n; j++) {
            a[i][j] = a[i][j - 1] * x % mod;
        }
    };

    f[0][0][0][0] = 1;
    for (int u = 0; u <= m; u++) {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                for (int k = 0; k <= i; k++) {
                    for (int x = 0; x <= n - i; x++) {
                        f[u + 1][i + x][(j + x) / 2][k + (j + x) % 2] += f[u][i][j][k] * a[u][x] % mod * c[n - i][x] % mod;
                        f[u + 1][i + x][(j + x) / 2][k + (j + x) % 2] %= mod;
                    }
                }
            }
        }
    }
    LL ans = 0;
    for (int j = 0; j <= n; j++) {
        for (int k = 0; k <= n; k++) {
            if (__builtin_popcount(j) + k <= K) ans += f[m + 1][n][j][k];
        }
    }
    printf("%lld\n", ans % mod);
    return 0;
}

T3 P7962 [NOIP2021] 方差

原题链接

这道题有点难，考的偏数学（好像这几道题都跟数学有关）

来看暴力思路：

首先需要知道方差公式为平方的平均数减去平均数的平方。

这题突破口是把 $a_{i+1}+a_{i-1}-a_i->a_i$ 这个操作和差分联系起来,不然会觉得操作可以执行无限次,很难有一个最终的目标。

记差分数组 $d_i=a_i-a_{i-1}$ ,观察到对 $a_x$ 进行操作后,其差分仅 $d_x$ 和 $d_{x+1}$ 发生了改变,具体为:

$d_x = (a_{x+1} + a_{x-1} -a_x)-a_{x-1}= a_{x+1} - a_x = d_{x+1}$
$d_{x+1}=a_{x+1}-(a_{x+1}+a_{x-1}-a_x)=a_x -a_{x-1} = d_x$

可以发现一次操作仅仅是改变了相邻的两个差分,原数组的差分 $d_1$ 是固定不变的,除此之外的 $d_2\sim d_n$ 显然都可以随便换位置,也就一共有 $(n - 1)!$ 种可能,那么全排列一下能骗20分。

可以 $s h u ff l e$ 一些初始情况,然后每次随机交换两个数,检查一下是否方差更小,若不是则不交换,这样直到方差到极值为止。(前置知识)

这种方法可以骗到72分。

$72 pt s$

int a[N], d[N], n;
LL ans = INF;
LL cal() {
    for (int i = 1; i <= n; i++) {
        a[i] = a[i - 1] + d[i];
    }
    LL now = 0, s1 = 0, s2 = 0;
    for (int i = 1; i <= n; i++) s1 += a[i], s2 += a[i] * a[i];
    now = -s1 * s1 + s2 * n;
    return now;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), d[i] = a[i] - a[i - 1];

    int wc = 2000;
    mt19937 g(114514);
    uniform_int_distribution<int> u1(2, n);//生成伪随机数
    while (wc--) {
        shuffle(d + 2, d + n + 1, g);
        int t = 0;
        LL now = INF;
        while (t < 300) {
            int x = u1(g), y = u1(g);
            if (x != y) {
                swap(d[x], d[y]);
                LL tmp = cal();
                if (tmp < now) {
                    t = 0;
                    now = tmp;
                } else {
                    swap(d[x], d[y]);
                    t++;
                }
            }
        }
        ans = min(ans, now);
    }
    cout << ans << endl;
    return 0;
}

等等再想正解

阿江又讲了种办法，感觉就是 $72 pt s$ 的简单版，就是去了生成随机数。加了全排列。并且 $72 pt s$ 的代码更加细节一点。

$28 pt s$

#include<bits/stdc++.h> 
const int N=11000;
using namespace std;
int n,a[N],b[N];
long long ans;
inline long long getvar() {
long long sm=0,x=0,x2=0;
for(int i=1; i<=n; ++i) {
x+=sm,x2+=sm*sm;
sm+=b[i];
}
return n*x2-x*x;
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; ++i)
scanf("%d",&a[i]);
for(int i=1; i<n; ++i)
b[i]=a[i+1]-a[i];
ans=getvar();
while(next_permutation(b+1,b+n))
ans=min(ans,getvar());
printf("%lld",ans);
return 0;
}

下面来想正解：

正解的话需要知道一个性质:方差最小时,d数组一定是先递减后递增。
也就是把差分数组从小到大排序后,考虑存在一个核心不停往左右两边扩展,一个个地安排每个 $d_i$ 的位置(放当前的最左边或者最右边),每次有两种选择,这样是可以DP的。

我们用 $f [i] [j]$ 表示考虑完前 $i$ 小的差分后,当前总和 $\sum a_i=j$ 时, $\sum a_i^2$ 的最小值。

·若把 $d_i$ 放到当前核心的右端,记 $t=\sum _{k=1}^i d_k$ ,新的 $a_i=t$ ,之前核心里的所有数都不会变化,转移为 $f [i] [j] = f [i - 1] [j - t] + t * t$

·若把 $d_i$ 放到当前核心的左端,这 $i$ 个数都加上了 $d_i$ (包括新加进去的 $a_i$ ,初始看成0),这样总和是加了 $i*d_i$ ,转移为 $f[i][j]=f[i-1][j-i*d_i]+2d_i(j-i*d_i)+i*d_i^2$

上述DP总状态数有 $n^2a$ 个,每个状态都是 $O (1)$ 转移,空间需要用滚动数组来优化。

$co d e$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 1e18;
const LL mod = 1e9 + 7;
const int N = 10005;

int a[N], d[N];
LL f[2][500005];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int m = n - 1;
    for (int i = 1; i <= m; i++) {
        d[i] = a[i + 1] - a[i];
    }
    sort(d + 1, d + m + 1);
    int s = 0;
    for (int i = 1; i <= n; i++) s += d[i] * i;
    int now = 0, u = 0;
    for (int j = 0; j <= s; j++) f[u][j] = INF;
    f[0][0] = 0;
    for (int i = 1; i <= m; i++) {
        if (d[i] == 0) continue;
        u ^= 1;
        now += d[i];
        for (int j = 0; j <= s; j++) {
            f[u][j] = INF;
            int k = j - i * d[i];
            if (k >= 0) f[u][j] = min(f[u][j], f[u ^ 1][k] + (LL)i * d[i] * d[i] + (LL)2 * k * d[i]);
            k = j - now;
            if (k >= 0) f[u][j] = min(f[u][j], f[u ^ 1][k] + now * now);
        }
    }
    LL ans = INF;
    for (int j = 0; j <= s; j++) {
        if (f[u][j] < INF)
            ans = min(ans, n * f[u][j] - (LL)j * j);
    }
    cout << ans << endl;
    return 0;
}

T4 P7963 [NOIP2021] 棋局

原题链接

这道题还不是很会。。。

总结

这个NOIP2021年的题除了T1简单一点，其他的都挺难的，两道是dp，但暴力还是都有部分分的，还不少，dp真的好考思维，TMD。先做简单题，把能拿得分拿到手，在尽可能地争取高分，先易后难，循序渐进，最后的分数也不会很低。

原文地址：https://blog.csdn.net/xiebohang/article/details/143660784

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：ollama + fastGPT + m3e 本地部署指南
下一篇：整合全文检索引擎 Lucene 添加站内搜索子模块

(时序论文阅读)TimeMixer: Decomposable Multiscale Mixing for Time Series Forecasting
来源论文iclr2024论文地址：https://arxiv.org/abs/2405.14616源码地址： https://github.com/kwuking/TimeMixer。
阅读更多2024-11-13
HTML文件中引入jQuery的库文件
HTML文件中引入jQuery的库文件
阅读更多2024-11-13
10款PDF合并工具的使用体验与推荐！！！
在如今的信息洪流中，我们几乎每个人都被淹没在大量的数字文档之中。无论是学生、教师还是职场人士，我们都需要高效地管理和处理这些文档。而PDF文件，凭借其跨平台的稳定性和通用性，成了最常用的文档格式之一。
阅读更多2024-11-13
红日靶机(七)笔记
在 VulnStack7 是由 5 台目标机器组成的三层网络环境，分别为 DMZ 区、第二层网络、第三层网络。涉及到的知识点也是有很多，redis未授权的利用、laravel的历史漏洞、docker逃
阅读更多2024-11-13
【分布式】CAP理论
是分布式系统中的三个基本要求，但根据CAP定理，在分布式系统中，不能同时满足这三者。当网络发生分区时（网络分区通常是不可避免的），系统只能在。每个分布式系统根据具体的业务需求、使用场景和网络环境，都会
阅读更多2024-11-13
【linux】TCP网络编程及Web服务器搭建
默认的情况下，如果一个网络应用程序的一个套接字绑定了一个端口( 占用了 8000 )，这时候，别的套接字就无法使用这个端口( 8000 )端口复用：允许在一个应用程序可以把 n 个套接字绑在一个端
阅读更多2024-11-13
全媒体数字化转型浪潮下半场，有效流量&创新业务是转型成功与否的最好证明
不少传媒企业已经开始积极探索转型之路。通过打造个性IP工作室、重视C端用户服务、深化G端合作等方式，传媒行业正在逐步构建起一个以用户为中心、以数据为驱动、以创新为核心的新型媒体生态。
阅读更多2024-11-13
C++- 基于多设计模式下的同步&异步日志系统
13万字项目带源代码
阅读更多2024-11-13
多路转接之select
表示timeout->tv_sec时间内没有文件描述符的资源准备就绪，就一直阻塞等待，直到等待时间超过timeout->tv_sec才返回。在timeout->tv_sec时间内有文
阅读更多2024-11-13
Android Studio | 修改镜像地址为阿里云镜像地址，启动App
在项目文件的目录下的 settings.gradle.kts 中修改配置，配置中包含插件和依赖项。
阅读更多2024-11-13

2021 NOIP 题解

T1 P7960 [NOIP2021] 报数

T2 P7961 [NOIP2021] 数列

先来说下暴力思路：

接下来想想正解：

T3 P7962 [NOIP2021] 方差

来看暴力思路：

等等再想正解

下面来想正解：

T4 P7963 [NOIP2021] 棋局

总结

相关文章