专栏文章

染色csp-s2024 T3

___czy
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqvl29m
此快照首次捕获于
2025/12/04 11:27
3 个月前
此快照最后确认于
2025/12/04 11:27
3 个月前
查看原文

文章背景

由于本蒟蒻在周六的GESP考试中，过于贪心导致10分部分分都没拿到，以67分（大约）险过5级，心中种种不甘促成要打这道题的决心，再加上还要改改马蜂，这便是改马蜂后的第一道AC的题。
题目链接

歪门邪道的方法

这个题肯定能爆搜，据说考场上能得35分，但洛谷上只能得20分，洛谷机子是不是慢很多啊。

正解

很显而易见这道题的正解肯定是dp，思路见B站大佬。

坎坷的做题过程（错误百出）

第一份代码：
CPP
#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int xx = 2e5+5; 

int t,n;
int a[xx],sum[xx],f[xx][5],book[xx];

inline ll read(){
	ll 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*10+ch-'0';
		ch=getchar();	
	}
	return x*f;
}

int main(){
	t=read();
	while(t--){
		for(int i=1;i<=n;++i){
			a[i]=0;
			sum[i]=0;
			book[i]=0;
			for(int j=0;j<=1;++j){
				f[i][j]=0;	
			}
		}
		n=read();
		for(int i=1;i<=n;++i){
			a[i]=read();
			if(a[i]==a[i-1]) sum[i]=sum[i-1]+a[i];
			else sum[i]=sum[i-1];	
		}
		for(int i=1;i<=n;++i){
			ll now=a[i];
			ll l=book[now];
			f[i][0]=max(f[i-1][0],f[i-1][1]);
			if(l>0){
				ll best1=sum[i-1]-sum[l];
				ll best2=max(f[l+1][0],f[l+1][1]);
				f[i][1]=best1+best2+now;
			}
			book[now]=i;
		}
		cout<<max(f[n][0],f[n][1])<<"\n";
	}
	return 0;
}
只得了65pts，RE on #11，12，16~20 。观察数据范围发现这几个点的共同特点是AiA_i ≤106\leq 10^6，很明显book数组要开到1e6 。 于是第二份代码出来了：
CPP
#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int xx = 2e5+50; 
const int maxn = 1e6+10;

ll t,n;
ll a[xx],sum[xx],f[xx][5],book[maxn];

inline ll read(){
	ll x=0;
	char ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();	
	}
	return x;
}

int main(){
	t=read();
	while(t--){
		for(ll i=1;i<=n;++i){
			a[i]=0;
			sum[i]=0;
			book[i]=0;
			for(int j=0;j<=1;++j){
				f[i][j]=0;	
			}
		}
		n=read();
		for(ll i=1;i<=n;++i){
			a[i]=read();
			if(a[i]==a[i-1]) sum[i]=sum[i-1]+a[i];
			else sum[i]=sum[i-1];	
		}
		for(ll i=1;i<=n;++i){
			ll now=a[i];
			ll l=book[now];
			f[i][0]=max(f[i-1][0],f[i-1][1]);
			if(l>0){
				ll best1=sum[i-1]-sum[l];
				ll best2=max(f[l+1][0],f[l+1][1]);
				f[i][1]=best1+best2+now;
			}
			book[now]=i;
		}
		cout<<max(f[n][0],f[n][1])<<"\n";
	}
	return 0;
}
自我感觉是很对的，但是只有75pts，为什么呢？？苦思冥想了一会，发现book数组清空的时候应该把它的值域清空，而非清空到n，于是把for()改为memset，第三份代码新鲜出炉：
CPP
#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int xx = 2e5+50; 
const int maxn = 1e6+10;

ll t,n;
ll a[xx],sum[xx],f[xx][5],book[maxn];

inline ll read(){
	ll x=0;
	char ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();	
	}
	return x;
}

int main(){
	t=read();
	while(t--){
		for(ll i=1;i<=n;++i){
			a[i]=0;
			sum[i]=0;
			for(int j=0;j<=1;++j){
				f[i][j]=0;	
			}
		}
		memset(book,0,sizeof(book));
		n=read();
		for(ll i=1;i<=n;++i){
			a[i]=read();
			if(a[i]==a[i-1]) sum[i]=sum[i-1]+a[i];
			else sum[i]=sum[i-1];	
		}
		for(ll i=1;i<=n;++i){
			ll now=a[i];
			ll l=book[now];
			f[i][0]=max(f[i-1][0],f[i-1][1]);
			if(l>0){
				ll best1=sum[i-1]-sum[l];
				ll best2=max(f[l+1][0],f[l+1][1]);
				f[i][1]=best1+best2+now;
			}
			book[now]=i;
		}
		cout<<max(f[n][0],f[n][1])<<"\n";
	}
	return 0;
}
AC记录，完结撒花~~~。（下一次我绝不会那么贪了！！！！10pts也是分啊！！！！）

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...