NOIP2021 题解（T1-T3）

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600134.html

我太弱了，改不出T4，就把T1-3题解码了。

T1 报数

题目链接

想着T2，T3的题解都写了，就补一下T1的吧。

典型的筛法。

假如一个数含有7，则把它的倍数全筛走。

这里可以加一个小优化，假如这个数已经被筛过，就不需要再筛它的倍数了。

最后再倒着预处理每个数的下一个没被筛的是什么。

如果不预处理，不断6999999就可以卡死你。

Code

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline 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<<1)+(x<<3)+(ch^48);
ch=getchar();}return x*f;}
//#define M
//#define mo
#define N 10000050
int n, m, i, j, k; 
int f[N], s[N], t, x; 

int pan(int x)
{
	while(x)
	{
		if(x%10==7) return 1; 
		x/=10; 
	} 
	return 0; 
}

signed main()
{
//	freopen("number.in", "r", stdin);
//	freopen("number.out", "w", stdout);
	for(i=1; i<=10000005; ++i)
	{
		if(pan(i))  
		{
			if(!f[i])
			for(j=i; j<=10000005; j+=i)  f[j]=1; 
		} 
//		if(!f[i]) printf("%d\n", i); 
	}
	for(i=10000005; i>=1; --i)
	{
		if(!f[i]) s[i]=i; 
		else s[i]=s[i+1]; 
//		printf("s[%d]=%d\n", i, s[i]); 
	} 
	t=read(); 
	while(t--)
	{
		x=read(); 
		if(f[x]) printf("-1\n"); 
		else printf("%d\n", s[x+1]); 
	}
	return 0;
}

T2 数列

题目链接

首先dp得从低位向高位枚举，因为高位无论如果使用 $2^{a_i}$ 都对低位二进制1的个数无影响，满足dp的无后效性。

设 $dp(k, i, x, y)$ 为 $S$ 从低的高二进制的前 $k$ 位中，用了数列 $a$ 的前 $i$ 项，且此时 $S$ 中共有 $x$ 个二进制位为1，第 $i+1$ 位进了 $y$ 过去。

则：

$$dp(k, i, x, y)=\sum_{j=0}^{n-i}dp(k+1, i+j, x+(y+j\&1),y+j>>1)\times C_{i+j}^j\times v_k^j$$

假设这一位有 $j$ 个 $a_j$ 满足 $a_j=k$，则下一位就有 $i+j$ 个 $a$ 的元素确定，如果这一位是1，则 $x+1$，在转移中的 $x+(y+j\&1)$ 体现。而进位到下一位的就是 $y+j>>1$ 了。

对于每种方案，其对于答案的贡献为 $v_k^j$，而方案相当于在 $i+j$ 个数中插 $j$ 块板，即 $C_{i+j}^j$。

建议用记忆化搜索实现。

Code

// Problem: P7961 [NOIP2021] 数列【民间数据】
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7961
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline 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<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define mo 998244353
#define N 40
#define M 110
int n, m, i, j, k; 
int c[M][M], s[M][M]; 
int f[M][N][N][N], v[M], K; 

int count(int x)
{
	int ans=0; 
	while(x) x-=x&-x, ++ans; 
	return ans; 
}

int dfs(int k, int u, int x, int y)
{
	if(u==n)
	{
		// printf("> f[%lld][%lld][%lld][%lld]=%lld\n", k, u, x, y, x+count(y)<=K);
		if(x+count(y)>K) return 0; 
		// printf("----------"); 
		return 1; 
	}
	if(k>m) return 0; 
	if(f[k][u][x][y]!=-1) return f[k][u][x][y]; 
	int ans=0;  
	for(int i=0; i<=n-u; ++i)
	{
		ans=(ans+dfs(k+1, u+i, x+((y+i)&1), (y+i)>>1)
						*s[k][i]%mo*c[u+i][i]%mo)%mo; 
		// printf("%lld %lld\n", s[k][i], c[n-u][i]); 
	}
	f[k][u][x][y]=ans; 
	// printf("f[%lld][%lld][%lld][%lld]=%lld\n", k, u, x, y, f[k][u][x][y]); 
	return f[k][u][x][y]; 
}


signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout); 
	memset(f, -1, sizeof(f)); 
	n=read(); m=read(); K=read(); 
	for(i=0; i<=m; ++i) v[i]=read(); 
	c[0][0]=1; 
	for(i=1; i<=n; ++i)
		for(j=c[i][0]=1; j<=i; ++j) 
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%mo; 
	for(i=0; i<=m; ++i)
	{
		s[i][0]=1; 
		for(j=1; j<=n; ++j) s[i][j]=(s[i][j-1]*v[i])%mo; 
	}
	printf("%lld\n", dfs(0, 0, 0, 0)); 
	return 0;
}

T3 方差

题目链接

Part A 式子化简

首先题目要求的式子就是 $n^2$ 乘上 $\frac{1}{n}\sum_{i=1}^n(a_i-\bar a)^2$，其中 $\bar a=\frac{1}{n}\sum_{i=1}^n a_i$。

我们把这三合在一起也就是：

$$n^2\times\frac{1}{n}\sum_{i=1}^n(a_i-\frac{1}{n}\sum_{j=1}^n a_j)^2$$

前面化简一下，后面用完全平方公式展开：

$$n\times\sum_{i=1}^n(a_i^2-2\times(\frac{1}{n}\sum_{j=1}^n a_j)\times a_i+\frac{1}{n^2}(\sum_{j=1}^n a_j)^2)$$

拆开：

$$n\times\sum_{i=1}^n a_i^2-n\times\sum_{i=1}^n(2\times \frac{1}{n}(\sum_{j=1}^n a_j)\times a_i)+n\times \sum_{i=1}^n(\frac{1}{n^2}(\sum_{j=1}^n a_j)^2)$$

对于第二坨，把与 $a_i$ 无关的抽出来：

$$n\times\sum_{i=1}^n a_i^2-n\times 2\times \frac{1}{n}(\sum_{j=1}^n a_j)\times\sum_{i=1}^n a_i+n\times \sum_{i=1}^n(\frac{1}{n^2}(\sum_{j=1}^n a_j)^2)$$

把第二坨化简一下：

$$n\times\sum_{i=1}^n a_i^2-2\times\sum_{i=1}^n a_i\times\sum_{i=1}^n a_i+n\times \sum_{i=1}^n(\frac{1}{n^2}(\sum_{j=1}^n a_j)^2)$$

把第二坨的后两个写成平方的形式：

$$n\times\sum_{i=1}^n a_i^2-2\times(\sum_{i=1}^n a_i)^2+n\times \sum_{i=1}^n(\frac{1}{n^2}(\sum_{j=1}^n a_j)^2)$$

看第三坨，发现没有和 $i$ 有关的项，之间把 $\sum_{i=1}^n$ 变成乘 $n$：

$$n\times\sum_{i=1}^n a_i^2-2\times(\sum_{i=1}^n a_i)^2+n\times n\times\frac{1}{n^2}(\sum_{j=1}^n a_j)^2$$

化简一下第三坨：

$$n\times\sum_{i=1}^n a_i^2-2\times(\sum_{i=1}^n a_i)^2+(\sum_{i=1}^n a_i)^2$$

然后我们发现二、三坨可以合并：

$$n\times(\sum_{i=1}^n a_i^2)-(\sum_{i=1}^n a_i)^2$$

于是对于每种 $a$ 我们都有直接算的方法了。

Part B 差分交换

现在让我们考虑令一个问题。

对于相邻的三个数 $a_{i-1}$、$a_i$、$a_{i+1}$，我们计算相邻两数的差分别为 $a_i-a_{i-1}$、$a_{i+1}-a_i$。

先在我们把 $a_i$ 变成 $a_{i-1}+a_{i+1}-a_i$，现在就是 $a_{i-1}$、$a_{i-1}+a_{i+1}-a_i$、$a_{i+1}$。

然后我们再对相邻两数作差分别为：$a_{i+1}-a_i$、$a_i-a_{i-1}$。

发现了什么？

没错，我们对每个数进行交换，只不过是把相邻两项的差交换。

于是我们对 $a$ 作差分序列 $d$，这样无论我们对 $a$ 序列进行怎样的变换，$d$ 序列的元素始终不变，只是顺序改变。

基于这个结论，我们可以枚举 $d$ 的顺序，时间复杂度 $O(n!)$。

Part C 差分单谷性

这里我们可以引出一个结论：$d$ 的排列必然是先从大到小，再从小到大。

这里可以感性理解一下，因为对于每个 $a$ 只有不断靠近平均数，方差才最小。

我们也可以大致运用反证法证明。（有误请指出）

看不到？戳这里查看图片

图中 $d_1>d_2$，我们发现 $a_1$ 与 $a_3$ 的值不变，图2相比图1中只有 $a_2$ 变大了。

两个 $a_2$ 相比，显然图1中的 $a_2$ 更靠近谷底，也就是 $\bar a$。按照开始的式子 $\frac{1}{n}\sum_{i=1}^n(a_i-\bar a)^2$ 我们发现 $a_2$ 取图1的情况更优。

有了这个结论，我们可以把 $d$ 按从大到小排序，对于 $d_i$，要么放左边，要么放右边，通过此方法，我们就得到了一种 $O(2^n)$ 的暴力。

48分Code

// Problem: P7962 [NOIP2021] 方差【民间数据】
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7962
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
// #define int long long
inline 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<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define N 410
//#define mo
int n, m, i, j, k; 
int a[N], d[N], b[N]; 
int ans=0x7fffffff; 
int sum, num; 

bool cmp(int x, int y)
{
	return x>y; 
}

void dfs(int x, int l, int r, int s, int t)
{
	if(l==r-1)
	{
		ans=min(ans, n*t-s*s);
		return ; 
	}
	int k; 
	k=a[l+1]=a[l]+d[x]; dfs(x+1, l+1, r, s+k, t+k*k); 
	k=a[r-1]=a[r]-d[x]; dfs(x+1, l, r-1, s+k, t+k*k); 
}

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	n=read(); 
	for(i=1; i<=n; ++i) a[i]=read(); 
	for(i=2; i<=n; ++i) d[i-1]=a[i]-a[i-1];  
	sort(d+1, d+n, cmp); 
	dfs(1, 1, n, a[1]+a[n], a[1]*a[1]+a[n]*a[n]); 
	printf("%d", ans); 
	return 0;
}

Part D 相对位置代替绝对位置

可以发现，我们在上面的方法中每次都把 $a$ 的绝对位置求出来。但其实我们可以只求出其相对位置。

我们先对 $d$ 从小到达排序，再一条一条放进去。此时 $a_i$ 的位置是在这种放进去的方法下的 $\sum_{j=1}^i d_j$。

首先让我们把之前的式子搬回出来：

$$n\times(\sum_{i=1}^n a_i^2）-(\sum_{i=1}^n a_i)^2$$

我们要让结果最小，就是要让 $\sum_{i=1}^n a_i$ 最大，$\sum_{i=1}^n a_i^2$ 最小。

让我们设 $f(i, j)$ 表示已经决定的 $i$ 个 $a$ 里面，和为 $j$ 的最小平方和。设 $S$ 为当前的 $i$ 的 $\sum_{j=1}^i d_i$ 。

$j$ 可以理解为 $\sum_{i=1}^n a_i$，$f(i, j)$ 可以理解为 $\sum_{i=1}^n a_i^2$。

现在对于 $d_{i+1}$，要么放在左边，要么放在右边。

先说放在右边，$j$ 则会加上当前点的坐标，答案加上当前的平方，而当前点为 $S+d_i$。

$$f(i+1, j+(S+d_i))=f(i, j)+S\times S$$

放在左边的话，就是整体 $a$ 右移 $d_{i+1}$，$j$ 就明显是加上 $(i+1)\times d_{i+1}$，至于 $f$ 的话，这里要手推一下。

首先至少要加上这个点 $d_i^2$，然后后面的和变成 $\sum_{k=1}^i(a_k+d_i)^2$，而原先是 $\sum_{k=1}^i a_k^2$，所以加上的是：

$$\sum_{k=1}^i(a_k+d_i)^2-\sum_{k=1}^i a_k^2$$

前面用完全平方公式拆一下：

$$\sum_{k=1}^i a_k^2+\sum_{k=1}^i(2\times a_k\times d_i)+\sum_{k=1}^i d_i^2-\sum_{k=1}^i a_k^2$$

最前面与最后面两坨消去：

$$\sum_{k=1}^i(2\times a_k\times d_i)+\sum_{k=1}^i d_i^2$$

前面那坨把无关紧要的提出了：

$$2\times d_i\times\sum_{k=1} a_k+\sum_{k=1}^i d_i^2$$

把 $j$ 套进去：

$$2\times d_i\times j+\sum_{k=1}^i d_i^2$$

后面那坨直接把 $\sum_{k=1}^i$ 变成乘 $i$：

$$2\times d_i\times j+i\times d_i^2$$

根据这个，我们可以把放左边的dp推出了：

$$f(i+1, j+d_{i+1}\times (i+1))=f(i, j)+2\times d_i\times j+i\times d_i^2+d_i^2$$

后面两个合一下：

$$f(i+1, j+d_{i+1}\times (i+1))=f(i, j)+2\times d_i\times j+(i+1)\times d_i^2$$

然后就行了。

转移方程与最终代码可能有一些细节的东西，改一改就行了。

可是按照这个方法打只有72分。

72分code

// Problem: P7962 [NOIP2021] 方差【民间数据】
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7962
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline 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<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define N 410
#define M 610
//#define mo
int n, m, i, j, k; 
int a[N], d[N]; 
int ans=0x7fffffffff; 
int sum, num; 
int f[N][N*M]; 

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	n=read(); 
	for(i=1; i<=n; ++i) a[i]=read(); 
	for(i=2; i<=n; ++i) d[i-1]=a[i]-a[i-1];  
	sort(d+1, d+n); 
	for(i=0; i<=n; ++i) for(j=0; j<=240000; ++j) f[i][j]=ans; 
	f[0][0]=0; 
	for(i=0; i<n-1; ++i)
	{
		sum+=d[i+1]; 
		for(j=0; j<=240000; ++j)
		{
			f[i+1][j+sum]=min(f[i+1][j+sum], f[i][j]+sum*sum); 
			f[i+1][j+d[i+1]*(i+1)]=min(f[i+1][j+d[i+1]*(i+1)], f[i][j]+2*j*d[i+1]+(i+1)*d[i+1]*d[i+1]); 
			// if(f[i][j]!=ans)
			// printf("f[%lld][%lld]=%lld\n", i, j, f[i][j]); 
		}
	}
		
	for(i=0; i<=24000; ++i) 
	{
		// if(f[n-1][i]!=0x7fffffffff) printf("f[%lld][%lld]=%lld\n", n-1, i, f[n-1][i]); 
		// ans=min(ans, n*(f[n-1][i]+2*i*a[1]+(n-1)*a[1]*a[1]+a[1]*a[1])-(a[1]*n+i)*(a[1]*n+i));  
		ans=min(ans, n*f[n-1][i]-i*i); 
	}
		
	printf("%lld", ans); 
	return 0;
}

Part E 小优化

我们发现主要是集中在MLE和TLE。

MLE方面，我们可以使用滚动数组。

TLE的话，对于 $j$ 的循环范围，我们可以动态分配。

提一句，最后加不加上 $a_1$ 都行（实测可以）。

最后贴上AC code：

// Problem: P7962 [NOIP2021] 方差【民间数据】
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7962
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline 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<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define N 10010
#define M 610
//#define mo
int n, m, i, j, k; 
int a[N], d[N]; 
int ans=0x7ffffffffff; 
int sum, num, p, q; 
int f[2][500010]; 

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	n=read(); 
	for(i=1; i<=n; ++i) a[i]=read(); 
	for(i=2; i<=n; ++i) d[i-1]=a[i]-a[i-1];  
	sort(d+1, d+n); 
	for(j=0; j<=500000; ++j) f[1][j]=f[0][j]=ans; 
	f[0][0]=0; 
	for(i=0; i<n-1; ++i)
	{
		sum+=d[i+1]; 
		p=(i+1)%2; q=i%2; num+=d[i+1]*(i+1); 
		for(j=0; j<=num; ++j) f[p][j]=ans; 
		for(j=0; j<=num; ++j)
		{
			if(j+sum<=num)
				f[p][j+sum]=min(f[p][j+sum], f[q][j]+sum*sum); 
			if(j+d[i+1]*(i+1)<=num)
				f[p][j+d[i+1]*(i+1)]=min(f[p][j+d[i+1]*(i+1)], f[q][j]+2*j*d[i+1]+(i+1)*d[i+1]*d[i+1]); 
		}
	}
		
	for(i=0; i<=500000; ++i) 
	{
		//ans=min(ans, n*(f[(n-1)%2][i]+2*i*a[1]+(n-1)*a[1]*a[1]+a[1]*a[1])-(a[1]*n+i)*(a[1]*n+i));  
//可写可不写，是是否加上a1的情况
		ans=min(ans, n*f[n-1][i]-i*i); 
	}
		
	printf("%lld", ans); 
	return 0;
}