CSP-S2024游记（总评）

· · 生活·游记

CSP-S2024游记

前言:本篇不含任何文学色彩,纯作为考后反思与感悟,以及对一个月后的省赛考试作一个警示作用.<惊世厚仁!>

25日晚上是FZYZOJ对CSP考前的最后一次模拟,虽说代码中含有借鉴性(组合数公式C[i][j]=C[i-1][j]+C[i-1][j-1])(记录重要递推式ing),但是最后拿了120Pts.想着在YZOJ如此困难的OJ系统下都能拿120.第二天CSP应该会更好吧...抱着这样一种心态,晚上开开心心打了T3的订正.20Pts→40Pts一个小细节没处理好,导致挂了20pts 怎么又是细节??!接下来戏剧性的就要出现了！

晚上放弃图论和SPFA等重难点算法.26日早上本想学习一下搜索算法,结是发现一个早上根本学不懂，还是去翻了一下学长们留下的警示后人,学到了一个很新的东西叫数据分治(为下文埋伏笔)

下午2:30开题,很搞笑,为什么先发的是早上J组题目.旁边坐的是一个一中高三学长,我想两年后我一定也还在考场上吧...5分钟后S组题目下发,浏览一遍题目,发觉T1和去年差应多.T2传统大模拟应该能打.T3应该朴素搜索/动归n2优化.T4题目太长不想读.

14:40-15:06.不到1h打T1,把T1快速AC了,由于不知道这种题如何对拍于是放弃对拍

15:06-17:30整整2:30小时打大模拟,没打出.接下来整理一下错误点

①未访问到点应设INF,而非0!

②不要再在考场上贪正解,要暴力打满

于是17:30-18:00打特殊性质B.然后试着打了T3搜索,不出防料我的半吊子搜索水平无法支持我打出.

最傻的来了.到了18:20,交题前10min.我发现我T2的C特殊性质点也能拿20Pts、于是迅速打好solved2函数.本没有想能对的,就随便交吧,最后连调试运行的时间也没有，这其实是数据分治的小应用,但没有调试又埋下伏笔。当晚不眠之夜,和npy聊天到2点.心情才好点,本来要一直emo下去了

10.27.代码公示,在我写这篇游记之前,我提交了代码跑分,结果120Pts(怎么和YZOJ一样?)在我写这篇游记第一段时,突然好奇我为什么T2会RE,于是打开洛谷,静查代码,然后就看到了我此生最不愿意看到的景象————

我solved2函数没有调用？？？！

原代码只有if(Is1)solved1();

而我加上else solved2();

直接就40pts了??!和YZOJ一样傻!

都是原本140Pts→→120Pts

如果1=切线140我心态将爆炸!(但是显然不可能)

可以看出,精神已经失常了,写到这里的时候开怀大笑,因为人在无语时真的会笑

后记：本人今晚在机房3个小时把T2和T3都AC了，发现我应该要去拿T2的满分，最后还是时间投入太多动摇了我...以后看见这种大模拟还是应该直接硬刚，最后发现我也就只有INF设置这边错了，还有一堆边界条件（详见游记2），但是T3呢也是常规的dp啦...dp题做的太少了，相信多练练是可以完成T3这种比较水的蓝题的（？）

下面附上T3思路（我很喜欢的思路介绍）还有我的代码

#include<bits/stdc++.h>
#define reg register 
using namespace std;
const int N=2e5+5;
const int A=1e6+5;
int T,n,a[N],t[A];
long long bck[N],f[N][2],s[N];
void solved(){
    scanf("%d",&n);
    memset(bck,0,sizeof(bck));
    memset(t,0,sizeof(t));
    for(reg int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(t[a[i]])bck[i]=t[a[i]];
        if(a[i]==a[i-1])s[i]=a[i];
        else s[i]=0;
        s[i]=s[i-1]+s[i];
        t[a[i]]=i;
    }
    //for(reg int i=1;i<=n;i++)printf("%lld\n",s[i]);
    for(reg int i=1;i<=n;i++){
        int lst=bck[i];
        if(lst){
            if(lst+1!=i){
                f[i][0]=f[lst+1][1]+s[i-1]-s[lst+1]+a[i];
                f[i][1]=f[lst+1][0]+s[i-1]-s[lst+1]+a[i];
            }
            else{
                f[i][1]=f[i-1][1]+a[i];
                f[i][0]=f[i-1][0]+a[i];
            }
            f[i][0]=max(f[i][0],max(f[i-1][0],f[i-1][1]));
            f[i][1]=max(f[i][1],max(f[i-1][0],f[i-1][1]));
        }//Get max!!!
        else {
            f[i][1]=max(f[i-1][0],f[i-1][1]);
            f[i][0]=f[i][1];
        }//No contribution!
    }
    /*for(int i=1;i<=n;i++){
        cout<<f[i][0]<<' '<<f[i][1]<<endl;
    }*/
    printf("%lld\n",max(f[n][0],f[n][1]));
}
int main(){
    //freopen("color.in","r",stdin);

    scanf("%d",&T);
    while(T--)solved();
    return 0;
}