10.16 模拟赛小记

比赛链接

A.link

徐爷爷很强的用线段树切了，orz。正解大概是树形 dp 但是有 O(1) 的解法没想到吧...？

咕咕了，还不会。

B.link

赛时只会写 30pts 的暴力，感觉成飞舞了。

C.link

先写了一个二维 \(n^2\) 的暴力 dp。根据式子就可以优化掉一层循环，然后 \(O(n*a[i])\) 就有 60pts 的好成绩了。

然后就不会了。

赛后，很容易想到一个性质：温度差不会超过 \(O(\sqrt{C})\)。

据此能把复杂度降到 \(O(n\sqrt{C})\)。

但是这个飞舞自以为写了很对的东西调了很久一直挂到 40pts。还是很不理解。顺便附上码。

60pts:

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
const int inf=0x3f3f3f3f;
int n,m;
int a[N];
int f[N][N];
int maxn,ans=inf,t;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		maxn=max(maxn,a[i]);
	}
	memset(f,inf,sizeof f);
	for(int i=1;i<=maxn;i++) f[1][i]=(a[1]-i)*(a[1]-i);
	for(int i=2;i<=n;i++){
		t=inf;
		for(int j=1;j<=maxn;j++) if(j!=a[i]) t=min(t,f[i-1][j]);
		for(int j=1;j<=maxn;j++)
			f[i][j]=(a[i]-j)*(a[i]-j)+min(f[i-1][j],t+m);
	}
	for(int i=1;i<=maxn;i++) ans=min(ans,f[n][i]);
	printf("%d",ans);
}

这是修改后的 40pts 的码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e4+10;
const int M=1010;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,m;
int a[N];
ll f[N][M];
ll ans=inf,t;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int k=sqrt(m);
	memset(f,0x3f,sizeof f);
	for(int i=-k;i<=k;i++) f[1][310+i]=i*i;
	for(int i=2;i<=n;i++){
		t=inf;
		for(int j=-k;j<=k;j++) if(j+a[i-1]!=a[i]) t=min(t,f[i-1][j+310]);
		for(int j=-k;j<=k;j++)
			f[i][j+310]=j*j+min(f[i-1][a[i]-a[i-1]+j+310],t+m);
	}
	for(int i=310-k;i<=310+k;i++) ans=min(ans,f[n][i]);
	printf("%lld",ans);
}

总结：杨神的模拟赛。感觉质量很高。