前言
本 juruo 坐标 CQ 准考证号为 CQ-0212
如有亿些错误，欢迎各位 dalao 指出本 juruo 的错误。
本文章由三个部分组成:
1.游记
2.反思
3.\(t1\) 的题解
一.NOIP2021游记
1.考试之前
前两个月~前一个星期:一直在学习新知，挑战亿些难题。
前一个星期~考试前一天晚上:自己在 luogu 上面复习亿些算法，独立完成亿些算法的模板。
考前一天晚上:考试前最后一次打开电脑，复习那些在 NOI Linux 环境下可以使用的 STL 函数。
2.考试之时
前 \(30min\) : 别人十分钟做出来的 \(t1\) 我用了整整 \(30min\) 来完成，并且在本地没有开 O2 的情况写我的 \(code\) 跑了整整 \(2s\) 。（不知道为什么 luogu 上面只跑了 \(200-300s\) ，可能是因为我没有用快读快写和 O2 的原因吧）。
\(31min-1h30min\) : 一直在想 \(t2\) 。一开始先打了一个时间复杂度为 \(O(n^m)\) 的很暴力的爆搜。后来发现这代码在跑 CCF 给的第二组样例的时候跑了整整 \(20s\) ，于是我就准备换一种做法。既然打出了爆搜，所以我下面想出来的算法就是 dp 。但是我在打 dp 的时候始终没有搞清楚该向 dp 数组传那些参数，所以我的 dp 就始终没有过样例，最后很无奈的我只好交了我的 \(n^m\) 的爆搜。终于，这一种时间复杂度极高的算法还是倒在了 CCF 给的毒瘤数据范围之下，全部超时了。
\(1h31min-3h\) ：一直在想 \(t3\) 。一开始打了一个 \(2^n\) 的爆搜，更重要的是这种方法第二个样例答案错误。我看了看数据范围，发现 \(n\le 10^4\) ，所以我又开始想一个 \(n^2\) 的 dp 算法，但由于有一个方差的公式始终没有推出来，最后还是放弃了 dp 的算法，采用了爆搜。又 WA 又 TLE 拿到了 \(12\) 分的 好成绩。
\(3h1min-3h30min\) ：这一段时间一直在自己给自己出数据，然后打了一个对拍程序，来对拍 \(t1\) 。
\(3h31min-4h10min\) ：这一段时间一直在检查 \(t1,t2,t3\) 的代码，并且尝试对 \(t2,t3\) 的代码进行剪枝，但最终都没有见效。
\(4h11min-4h30min\) ：这一段时间我去看了看 \(t4\) 的题目，但因为题目过于长，所以我根本没有耐心读下去了，最后又果断放弃了 \(t4\) 。大概看了一些输入格式和输出格式之后，我就用字母拼了一个像素画，然后就去检查我的考场文件夹，把那些多余的 cpp 文件都删掉，然后吃了点东西，最后就考试结束了。
3.考试之后
考试之后也没有对自己抱有多少期待，拿着从老师那里得到的代码自测了一下，就等着老师讲题，放下 NOIP 不管了。
二.NOIP2021赛后反思
\(t1\) : 这个题目虽然我 AC 了，但是由于考试的时候我跑了整整 \(2s\) 所以我还是很慌的，主要还是由于我用的是埃氏筛的思想，没有用欧拉筛的思想，我一开始觉得我会 TLE，但后来我才发现其根本原因是因为读入数据和要输出的东西太多，而我用的是 scanf,printf 输入输出，没有用快读快写，才造成了这个我认为会 TLE 假象 。所以我希望下次考试的时候，对于这种输入量较大的题目，一定要记得打快读快写。（虽然说到现在为止，我还是不会打快读快写。）
\(t2\) ：这个题目我觉得我确实有一些可惜。首先是我的 DFS ，其实这个题目打 DFS 是可以得分的，但由于我的 check 函数（检查 \(a\) 序列是否符合要求） 的效率太低，导致我用时太长。然后就是我的剪枝，这个题目我没有打出剪枝，但其实可以运用排列组合来剪枝，我们只需要枚举出 \(a\) 数组可以由那些元素组成，而没必要把每种情况的枚举一遍，然后枚举出由那些元素组成之后，可以用排列组合来求出这种方案可以产生多少种情况。要是加了这两个剪枝，我相信我是肯定不会全部超时的。
\(t3\) ：这个题目没有什么值得遗憾的，主要问题就是我 DFS 的正确性，如果能够打出正确的深搜并且适当的加一些剪枝的话，肯定不会只得到 \(12\) 分的。
\(t4\) ：这个题目的话，我觉得当时我不应该果断放弃，应该去尝试着打一下暴力，怎么说也不应该让这个题目拿一个 \(0\) 鸭蛋回去吧。
三.NOIP2021题解
由于我目前只做对了 \(t1\) ,所以这里只讲解 \(t1\) 的做法。
该题思路
这个题目在报数游戏的基础上加了一条规则。通过我的话简化一下就是如果一个数 \(x\) ，它的各位数字上有一个 \(7\) ,则 \(x,yx\) 也不能报出来。（其中 \(y\) 为正整数）。
我们可以预处理出所有各位数字上有 \(7\) 的数，然后定义一个数组 \(st_i\) 表示 \(i\) 这个数是否需要报出来，要报出来就是 \(1\)，不报出来就是 \(0\) 。我们给所有这些数标记为 \(0\) 然后再将所有这些数的倍数都标记为 \(0\)。最后我们在根据 \(st\) 数组更新答案即可。
该题代码
#include<bits/stdc++.h>
using namespace std;
int t;
int x[2000005];
bool st[10000005];
int last,primes[10000005],cnt;
int ans[10000005];
bool getnum(int x)
{
while(x)
{
if(x%10==7)
return 0;
x/=10;
}
return 1;
}
int maxn;
void init()
{
for(int i=1;i<=maxn;++i)
{
st[i]=1;//先全部初始化为1
}
for(int i=1;i<=maxn;++i)
{
//预处理出所有各位数字上有 7 的数
if(!getnum(i))
{
primes[++cnt]=i;
st[i]=0;
}
}
for(int i=1;i<=maxn;++i)
{
for(int j=1;j<=cnt&&primes[j]*i<=maxn;++j)
{
st[i*primes[j]]=0;//讲所有预处理出的数的倍数标记为0
}
}
//处理最终答案
for(int i=1;i<=maxn;++i)
{
if(st[i])
{
ans[last]=i;
last=i;
}
else
{
ans[i]=-1;
}
}
}
int main()
{
// freopen("number.in","r",stdin);
// freopen("number.out","w",stdout);
scanf("%d",&t);
maxn=1e7+1;//注意需要预处理到 1e7+1 因为 1e7+1 要报，且 1e7 之前报的最后一个数报的下一个数就是 1e7+1
init();//直接预处理出答案
for(int i=1;i<=t;++i)
{
//输入
scanf("%d",&x[i]);
printf("%d\n",ans[x[i]]);
}
return 0;
}
该题的一个小优化
我们可以发现，如果这样做的话，一个数可能会被标记很多次，而事实上，他只需要被标记一次就可以了。所以，我们可以针对这个进行优化，是的一个数在被标记时，只能被被预处理出的数中最小的，且是他的因子标记到。其思想就相当于欧拉筛，实现此优化，我们只需要在标记预处理的倍数的你那一层循改一下。
实现优化的核心代码
for(int i=1;i<=maxn;++i)
{
for(int j=1;j<=cnt&&primes[j]*i<=maxn;++j)
{
st[i*primes[j]]=0;//讲所有预处理出的数的倍数标记为0
if(i%primes[j]==0)//通过这一个优化，使得他只能被被预处理出的数中最小的筛到
{
break;
}
}
}
结尾
关于 NOIP2021 今天本 juruo 就讲到这里了，see you! QwQ 。