对于NOIP2021的全面总结
赛时：
考场拿到题目较为镇定，直接开 T1 ,一眼秒掉了根号预处理，$30min$ 喜提 $70pts$ 的好成绩。按照先暴力再正解的策略，去看 T2。读题后有些恍惚，没有看数据范围直接做，觉得不太可做，看了数据范围有 $m\leq 12$，果断计数 DP，转移后谨慎的判了边界条件，过掉了 7 位数样例后觉得 $50pts$ 稳了，哇，第一次考场上 dp 耶。T3 本来看上去非常亲切，之前模拟有两道无上限操作的题目，还有方差公式，设计了 dp 状态，但是并不会转移方差，想了很久无奈去写了暴搜。T4 题面很长，由于 T3 耽误了太多时间，T4暴力没有太敢写，因为一写又要很长时间，然后怕自己调不完，于是决定先去写 T1 正解。发现可以用类似埃氏筛法做，但怕复杂度炸掉，亲测规模 $2.8\times 10^7$，但考场上把八位数看成了八次方，所以以为自己被卡常了，觉得不太好，一直在想怎么改成类似于线性筛，于是时间流逝而去，T4暴力终究没写无奈固输，导致貌似有 $44pts$ 没拿到，非常可惜。
题目分析
T1
$70pts$ 根号维护，复杂度 $O(\sqrt n+T)$。正解类埃氏筛法，复杂度 $O(nloglogn)$ ?。
1 #include<bits/stdc++.h>
2 using namespace std;
3 int vis[10000005],pos,ans[10000005],T,n[200005],maxn;
4 bool check(int x)
5 {
6 while(x)
7 {
8 if(x % 10 == 7) return true;
9 x /= 10;
10 }
11 return false;
12 }
13 int main()
14 {
15 freopen("number.in","r",stdin);
16 freopen("number.out","w",stdout);
17 scanf("%d",&T);
18 for(int t = 1;t <= T;t++)
19 {
20 scanf("%d",&n[t]);
21 maxn = max(n[t],maxn);
22 }
23 if(maxn <= 200000)
24 {
25 for(int i = 1;i <= 9;i++) vis[i] = (i == 7) ? -1 : 1;
26 for(int i = 10;i <= 200002;i++)
27 {
28 if(check(i))
29 {
30 vis[i] = -1;
31 continue;
32 }
33 int flag = 0;
34 for(int j = 1;j * j <= i;j++)
35 {
36 if(i % j != 0) continue;
37 if(vis[j] == -1 or vis[i / j] == -1)
38 {
39 flag = 1;
40 break;
41 }
42 }
43 vis[i] = flag ? -1 : 1;
44 }
45 ans[200000] = 200002;
46 pos = 200000;
47 for(int i = 199999;i >= 1;i--)
48 {
49 if(vis[i] == -1) ans[i] = -1;
50 else
51 {
52 ans[i] = pos;
53 pos = i;
54 }
55 }
56 for(int t = 1;t <= T;t++)
57 printf("%d\n",ans[n[t]]);
58 return 0;
59 }
60 for(int i = 1;i <= 10000001;i++)
61 {
62 if(vis[i] == -1) continue;
63 if(not check(i)) continue;
64 for(int j = 1;j * i <= 10000001;j++)
65 {
66 if(vis[i*j] == -1) continue;
67 vis[i*j] = -1;
68 }
69 }
70 pos = 10000001;
71 for(int i = 10000000;i >= 1;i--)
72 {
73 if(vis[i] == -1) ans[i] = -1;
74 else
75 {
76 ans[i] = pos;
77 pos = i;
78 }
79 }
80 for(int t = 1;t <= T;t++)
81 printf("%d\n",ans[n[t]]);
82 return 0;
83 }
View Code
T2
$50pts$ 设 $f_{i,j}$ 表示第 $i$ 个填完后 $S$ 值为 $j$ 的权值和，计数转移即可，复杂度 $O(n^2m2^m)$。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int N = 35;
5 const ll mod = 998244353;
6 ll f[N][150000];
7 ll ans;
8 ll v[110];
9 int n,m,k;
10 bool check(int x)
11 {
12 int cnt = 0;
13 while(x)
14 {
15 if(x & 1) cnt++;
16 x >>= 1;
17 }
18 if(cnt > k) return false;
19 else return true;
20 }
21 int main()
22 {
23 freopen("sequence.in","r",stdin);
24 freopen("sequence.out","w",stdout);
25 scanf("%d%d%d",&n,&m,&k);
26 for(int i = 0;i <= m;i++) scanf("%lld",&v[i]);
27 for(int i = 0;i <= n * (1 << m);i++) f[0][i] = 1;
28 for(int i = 1;i <= n;i++)
29 for(int j = 0;j <= i * (1 << m);j++)
30 for(int k = 0;k <= m;k++)
31 if(j - (1 << k) >= 0 and j - (1 << k) <= (i - 1) * (1 << m)) f[i][j] = (f[i][j] + f[i-1][j - (1 << k)] * v[k] % mod) % mod;
32 for(int i = n;i <= n * (1 << m);i++)
33 {
34 if(not check(i)) continue;
35 //cout << i << endl;
36 ans = (ans + f[n][i]) % mod;
37 }
38 printf("%lld\n",ans);
39 return 0;
40 }
View Code
T3
搜的性质没有找好，$12pts$，别人 $20pts$。（好像挂了？）
T4
。。。，时间与暴力，我。。。，没有看出特殊性质暴力分好拿非常可惜。
赛后
期望：$100+50+12+0=162$
实际：待测