染色csp-s2024 T3

· · 个人记录

文章背景

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

题目链接

歪门邪道的方法

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

正解

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

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

第一份代码：

#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 。观察数据范围发现这几个点的共同特点是A_i \leq 10^6，很明显book数组要开到1e6 。 于是第二份代码出来了：

#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，第三份代码新鲜出炉：

#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也是分啊！！！！）~~