NOIP 2021 题目解析

NOIP 2021

本次命题对于水平接近的选手区分度较低, 同时难度梯度偏大。第四题代码量偏高, 要拿到省队线分数的同学需要快速解决前三题好在最后一题上面拿到足够的分数。

每次题目前三题都可以被归类为动态规划方法, 第四题是图论问题。

作者认为一等奖分数线应为 \(150\), 弱省省队线 \(250\), 强省省队线 \(310\).

T1 普及 \(\rm{IV}\) / 提高 \(\rm{I}\) - 报数

\(x≤ 10^7\)

题目考点: 数论, 动态规划

通过题目可以发现游戏规则和质数筛法类似, 因此可以提前处理出所有含有数字 \(\rm{7}\) 的数字。之后, 使用这些处理出的数字去对于进行挨拉托色尼筛类似过程即可。

#include"bits/stdc++.h"
using namespace std;

int read () { 
	int x = 0;
	char c = getchar();
	while(c<'0'||c>'9'){
		c = getchar();
	}
	while(c>='0'&&c<='9'){
		x = x*10+c-'0';
		c = getchar();
	}
	return x;
}

int n;
const int maxt = 1e7+1e5;
int t[maxt];
int ans[maxt];

int check (int x) 
{
	while (x>0) {
		if (x%10==7) return true;
		x /= 10;
	}
	return false;
}
void init () {
	for (int i=1;i<=1e7;i++) {
		if (!t[i]) if (check(i)) {
			t[i] = true;
			for (int j=i;j<=1e7;j+=i) t[j] = true;
		}
	}
}
int main () {
	n = read();
	init();
	int pre = 1;
	for (int i=1;i<=1e7+1e3;i++) {
		if (t[i]) {
			ans[i] = -1;
			continue;
		}
		if (i!=1) {
			ans[pre] = i;
			pre = i;
		}
	}
	for (int i=1;i<=n;i++) {
		int x = read();
		printf("%d\n",ans[x]);
	}
}

T2 提高 \(\rm{V}\) - 数列

\(n ≤ 30, m ≤ 100\)

题目考点: 动态规划

观察到问题的核心其实是考虑对于 \(\rm{2}\) 的次方的求和的进位问题。这引导我们发现如果 \(a_i\) 从小到大考虑, 则只需要考虑 \(a_i\) 当前的进位即可。因此, \(\rm S\) 是不需要被状态压缩的。因此我们考虑使用动态规划解决问题。

考虑在选择了 \(i\) 个 \(a\) 中的元素后再选择 \(k\) 个值为 \(x\) 的元素。可以发现, 我们需要四个维度来进行动态规划, 因为除了题目给的两个限制之外, 进位还需要考虑。在进位的过程中, 假设进了 \(j\) 位, 则 \(j/2\) 的进位会保留, \(j \text{ mod } 2\) 的进位会直接使用。分两种情况讨论即可。

最后发现, 答案求的并不是有序数列, 因此要乘以一个组合数, 在动态规划的过程中做乘法即可。这是因为一个数列的权值是连积。

具体而言, 令 \(f[i][j][k][l]\) 是考虑到选则了 \(i\) 个元素, 和为 \(j\), 已经有了 \(k\) 个 1 的位置, 进位为 \(l\), 细节可以参考代码。

#include"bits/stdc++.h"
#define int long long 
using namespace std;

int read() { 
	int x = 0;
	char c = getchar();
	while(c<'0'||c>'9') {
		c = getchar();
	}
	while(c>='0'&&c<='9') {
		x = x*10+c-'0';
		c = getchar();
	}
	return x;
}

const int maxn = 35;
const int maxm = 105;
int n,m,k,V[maxm];
int f[maxm][maxm][maxm][maxm];
const int MOD = 998244353;
int C[maxm][maxm];
int Vp[maxm][maxm];
int ans;

signed main() {
    n = read();
    m = read();
    k = read();
    for (int i=0;i<=m;i++) V[i] = read();
    for (int i=0;i<=m;i++) {
        Vp[i][0] = 1;
        for (int j=1;j<=n;j++) {
			Vp[i][j] = Vp[i][j-1]*V[i]%MOD;
		}
    }
    C[0][0] = 1;
    for (int i=1;i<=n;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;
    }
    for (int i=0;i<=n;i++) {
        f[0][i][i/2][i%2] = Vp[0][i]*C[n][i]%MOD;
    }
    for (int i=0;i<m;i++) for (int j=0;j<=n;j++) {
		for (int p=0;p<=j/2;p++) for (int l=0;l<=min(i+1,j);l++) {
			if (!f[i][j][p][l]) continue;
			for (int t=j;t<=n;t++) {
				int q = t-j+p;
				f[i+1][t][q/2][l+q%2] += f[i][j][p][l]*Vp[i+1][t-j]%MOD*C[n-j][t-j]%MOD;
				f[i+1][t][q/2][l+q%2] %= MOD;
			}
		}
    }
    for (int p=0;p<=n;p++) for (int l=0;l<=m+1;l++) {
        int cnt = 0;
        int x = p;
		while (x) {
			if(x%2==1) cnt++;
			x /= 2;
		}   
        if (l+cnt<=k) ans = (ans+f[m][n][p][l])%MOD;
    }
    printf("%lld\n",ans);
}

T3 省选 \(\rm{III}\) - 方差

\(n≤10^4, a_i≤600\)

显然一个位置不能做两次连续操作。令这两个值是 \(X\) 和 \(Y\), 则 \[X+Y =a_{i-1} + a_{i+1}\]

可以得到

\[X = 1/2(a_{i-1} + a_{i+1}) + t \]

\[X = 1/2(a_{i-1} + a_{i+1}) - t \]

即一个是 +a, +b 的过程, 另一个是 +b, +a 的过程。这引导我们去考虑差分, 因为这一步是交换差分数组的相邻两个位置。这也说明这个差分数组是可以随意排序的。此时, 整理式子, 可以得到

\[D = n\sum_{i=1}^n a_i^2-(\sum_{i=1}^n {a_i})^2\]

对这个问题进行动态规划, 令 \(dp[i][S]\) 为 \[ \min\sum_{i=1}^na_i^2\]

在考虑到第 i 个差分值时 \(S = \sum_{i=1}^n {a_i}\) 的情况。此时可以得到56分的成绩。利用反证法可以证明 \(b_i\) 是单峰的, 这引导我们去将 \(b_i\) 排序, 之后前后插入作为转移的方法。这个时候可以得到72分的成绩。最后, 如果观察到非 \(\rm{0}\) 的 \(b_i\) 值只有 \(O(a_i)\) 种, 简单优化之后就可以得到100分。

#include"bits/stdc++.h"
typedef long long ll;
using namespace std;

const int inf = 2e9;
const int maxn = 605;
const int maxv = 605;
int a[10000+5];
int b[10000+5];
int p[10000+5];
int n;
int dp[maxv][maxn*maxv];
ll ans = 1e18;

int read() { 
	int x = 0;
	char c = getchar();
	while(c<'0'||c>'9') {
		c = getchar();
	}
	while(c>='0'&&c<='9') {
		x = x*10+c-'0';
		c = getchar();
	}
	return x;
}

void checkMin (int &_x, int _y) {
	_x = min(_x,_y);
	// cout<<_x<<endl;
}

signed main () {
	n = read();
	int V = 0;
	for (int i=1;i<=n;i++) a[i] = read();
	for (int i=0;i<n;i++) {
		b[i] = a[i+1]-a[i];
		V = max(V,a[i]);
	}
	sort(b+1,b+n);
	for (int i=1;i<n;i++) p[i] = p[i-1]+b[i];
	int cnt = 1;
	while (b[cnt]==0) cnt++;
	cnt--;
	for (int i=0;i+cnt<=n+1;i++) for (int v=0;v<=n*V;v++) dp[i][v] = inf;
	dp[0][0] = 0;
	for (int i=0;i+cnt+1<n;i++) for (int v=0;v<=n*V;v++) {
		if (dp[i][v]==inf) continue;
		// cout<<"i = "<<i<<" v = "<<v<<endl;
		int amt = cnt+i+1;
		// cout<<amt*b[amt]*b[amt]+2*b[amt]*v<<" "<<p[amt]*p[amt]<<endl;
		// cout<<dp[i][v]<<" ";
	    if (max(v+p[amt],v+amt*b[amt])>600*600) continue;
		checkMin(dp[i+1][v+amt*b[amt]],dp[i][v]+amt*b[amt]*b[amt]+2*b[amt]*v);
		// cout<<dp[i][v]<<" ";
		checkMin(dp[i+1][v+p[amt]],dp[i][v]+p[amt]*p[amt]);
	} 
	for (int v=1;v<=n*V;v++) {
	    if (v>600*600) continue;
		if (dp[n-cnt-1][v]==inf) continue;
		dp[n-cnt-1][v] += a[1]*a[1]*n+2*a[1]*v;
		int val = dp[n-cnt-1][v];
		// cout<<"v = "<<v<<endl;
		// cout<<"val = "<<val<<endl;
		ans = min(ans,(1ll*n*val-1ll*(v+a[1]*n)*(v+a[1]*n)));
	}
	printf("%lld\n",ans);
}

T4 省选

\(X ≤ 10^5\)

首先，我们倒序处理询问; 在过程中，尝试维护由 3 边连接而成的连通块, 其中不包含棋子. 这部分用并查集实现。

在每个连通块中，使用四个可持久化线段树, 其中两个需要储存连通块内所有点，一个储存 (x, y)，一个储存 (y, x), 另一个储存的是和这个连通块只相隔了一个 3 边的棋子信息, 然后对于 2 的路处理上下左右能走到哪, 四个实际是把白色和黑色分开，方便代码编写。

然后后续移除棋子的时候，我们先枚举向外的 3 边，将这些连通块中的棋子信息移除，然后合并连通块, 采取线段树启发式合并, 对于 2 的路，移除一个边，我们枚举外面的 2 边，考虑进行扩张。于是我们就完成了 3 路径和 2 路径连通块的维护。

对于每个要被拉出来的点, 先考虑 3，把连着的连通块编号储存起来，然后通过刚刚所说的连通块棋子信息计算出能干碎的棋子个数。这一部分的答案就是能被干碎的棋子数量加上连通块大小, 然后考虑 2 边，首先看能到达哪里, 然后特判终点，如果是棋子则判断可不可以干碎，如果是空地则不需要。

两种情况都需要看所在的连通块有没有出现在 3 路中储存的编号中, 考虑完之后，我们加上中间的点。但是注意到会有重复, 我们枚举刚刚储存的 ID，此时就需要看连通块内和一个线段交于几个点, 这个方法使用刚刚维护的连通块内节点信息处理, 这样子只会考虑 cnt(2) * cnt(3) = 4 种覆盖方式。

时间复杂度 \(O(n\log^2 n)\) 代码过于繁琐, 故不展示

什么是NOIP?

全国青少年信息学奥林匹克联赛（National Olympiad in Informatics in Provinces，简称NOIP）自1995年至2020年已举办25次。每年由中国计算机学会统一组织。 NOIP在同一时间、不同地点以各省市为单位由特派员组织。全国统一大纲、统一试卷。初、高中或其他中等专业学校的学生可报名参加联赛。联赛分初赛和复赛两个阶段。初赛考察通用和实用的计算机科学知识，以笔试形式进行。复赛为程序设计，须在计算机上调试完成。参加初赛者须达到一定分数线后才有资格参加复赛。联赛分普及组和提高组两个组别，难度不同，分别面向初中和高中阶段的学生。