NOIP2023 退役记

· · 个人记录

本人最后一场OI竞赛

发生了一系列的变故：
本人因为T1输入输出写到样例，于是在CSP-S2023中取得了85分的好成绩（见CSP2023 翻车记）
考虑到今年CSP-S T1难度比肩J组T1，NOIP切线可能会涨到100分以上，而且教练手上没有C类名额，感到凶多吉少。
于是家长联系了大量有C类名额的教练，感谢素未谋面的zxh老师，让我有了参加NOIP2023的机会。
然后戏剧性的变故发生了，（据说是为了抬高省一线以增加省队名额）今年FJ在没有通知的情况下暗改报名机制，取消了以前的AB类自动报名，导致许多选手（包括同年段CSP—S160分的选手）无法参加NOIP。切线也切到了80分。（之后似乎遭到了抗议，然后掉到了30分）。
然后本人成了本校今年唯一一个参加NOIP的选手。

因为受到了期中考的打击，没怎么复习OI，和教练两个人乘上了前往福州的高铁，途中背了一些板子（然而完全没有用上）。
这次吃住大概是几年来参加竞赛配置最好的一次。

今年FJ没有试机，但因为已经在附中参加过多次考试了，所以没什么关系。
今年linux机房的配置似乎比FJOI2022时的好上很多，丝滑无比。

就题目而言，今年似乎是有了复古的倾向。

T1和CSP-ST1有的一拼，水到了新高度。
T2似乎比去年T1略难一些，一个码量不大的小清新基环树，今年T2《去年T3<去年T2，大概绿到水蓝。
T3写了个mnt的dp跑路
T4感觉是个线段树优化dp，但当时只剩下大约1.5h，为了防止重蹈之前几次的覆辙，草草写了个nkt的dp

剩下时间都用来检查，这次用上了ulimit,加上自己写的评测程序，断绝了MLE和输入输出写挂的问题，然而一个小时并没有发现任何问题。

似乎本人是唯一一次每题都交了代码的考试，之前都因被前面的题吊住浪费了很多部分分

教练请了次麦当劳，然后座上了回家的动车。
自估 100+100+35+36=271
洛谷 100+100+40+48=288
小图灵 100+100+35+60=290(T4数据真离谱)
云斗 100+100+35+36=271（唯一正常的）

271大概是板上钉钉的事了，似乎是大众分，认识的就有好几个271。

对一个退役一年的选手来说似乎还行。

小图灵估出FJ省一线235，似乎是可以开香槟了。

去年因为爆空间与心心念念的省队失之交臂，现在拿个本校第一个NOIP省一也算勉强回了点血，希望不会再出什么意外。

这就是正式退役了，祝大家都有光明的未来
高考加油

upd 2023/11/24:申诉页面：100+100+35+36=271。希望有FJ省一。

附代码
T1

#include<cstdio>
#include<algorithm>
using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9')f=(c!='-'),c=getchar();
    while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
    if(f)return x;return -x;
}
inline int getc(){
    char c=getchar();
    while(c<'a'||c>'z')c=getchar();
    return c-'a';
}
const int maxn=4000;
int n,m;
int a[maxn][26],mx[maxn],mn[maxn];
signed main(){
    freopen("dict.in","r",stdin);
    freopen("dict.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][getc()]++;
    for(int i=1;i<=n;i++)mx[i]=0,mn[i]=26;
    for(int i=1;i<=n;i++)for(int j=0;j<26;j++)if(a[i][j])mx[i]=max(mx[i],j),mn[i]=min(mn[i],j);
    for(int i=1;i<=n;i++){
        int ok=1;for(int j=1;j<=n;j++)if(j!=i)if(mx[j]<=mn[i]){ok=0;break;}
        printf("%d",ok);
    }return 0;
}

T2

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9')f=(c!='-'),c=getchar();
    while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
    if(f)return x;return -x;
}
inline int getc(){
    char c=getchar();
    while(c!='U'&&c!='T'&&c!='F'&&c!='+'&&c!='-')c=getchar();
    if(c=='U')return 0;
    if(c=='T')return 1;
    if(c=='F')return -1;
    if(c=='+')return 2;
    return 3;
}
const int maxn=2e5+10;
int a[maxn],col[maxn],root[maxn],ins[maxn],siz[maxn],vis[maxn],ans,n,m;
vector<int> son[maxn];
void cut(int u){
    ins[u]=1,vis[u]=1;
    if(u>n){root[u]=1;ins[u]=0;return;}
    int v=a[u];if(v<0)v=-v;
    if(ins[v])root[u]=1;
    else if(!vis[v])cut(v);
    ins[u]=0;
}
void dfs(int u){
    if(root[u])col[u]=1;else{
        if(a[u]<0)col[u]=-col[-a[u]];
        else col[u]=col[a[u]];
    }
    siz[u]=1;
    for(int v:son[u]){
        dfs(v);siz[u]+=siz[v];
    }
}
signed main(){
    freopen("tribool.in","r",stdin);
    freopen("tribool.out","w",stdout);
    read();int T=read();while(T--){
        n=read(),m=read(),ans=0;
        for(int i=1;i<=n;i++)a[i]=i;
        for(int i=1;i<=n+3;i++)ins[i]=vis[i]=root[i]=0;
        for(int i=1;i<=n+3;i++)son[i].clear();
        for(int i=1;i<=m;i++)switch(getc()){
            int x,y;
            case 0:x=read();a[x]=n+1;break;
            case 1:x=read();a[x]=n+2;break;
            case -1:x=read();a[x]=n+3;break;
            case 2:x=read(),y=read();a[x]=a[y];break;
            case 3:x=read(),y=read();a[x]=-a[y];break;
        }
        for(int i=1;i<=n+3;i++)if(!vis[i])cut(i);
        for(int i=1;i<=n;i++)if(!root[i]){int f=a[i];if(f<0)f=-f;son[f].push_back(i);}
        for(int i=1;i<=n;i++)if(root[i])dfs(i);dfs(n+1);
        for(int i=1;i<=n;i++)if(root[i]){
            if(a[i]>0&&col[a[i]]==-1)ans+=siz[i];
            if(a[i]<0&&col[-a[i]]==1)ans+=siz[i];
        }ans+=siz[n+1];printf("%d\n",ans-1);
    }return 0;
}

T3

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9')f=(c!='-'),c=getchar();
    while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
    if(f)return x;return -x;
}
const int maxn=5e5+10;
int f[2005][2005],a[maxn],b[maxn],A[maxn],B[maxn],c,n,m,q;
void solve(){
    if(n>2000||m>2000){
        int mx=0,mn=2e9;
        for(int i=1;i<=n;i++)mx=max(mx,a[i]);
        for(int i=1;i<=m;i++)mn=min(mn,b[i]);
        printf("%d",b[1]>mx&&a[n]<mn);
        return;
    }
    f[0][0]=1;
    if(a[1]>b[1]&&a[n]>b[m]){
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
            f[i][j]=(a[i]>b[j])&&(f[i-1][j]||f[i][j-1]||f[i-1][j-1]);
    }else if(a[1]<b[1]&&a[n]<b[m]){
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
            f[i][j]=(a[i]<b[j])&&(f[i-1][j]||f[i][j-1]||f[i-1][j-1]);       
    }else f[n][m]=0;
    printf("%lld",f[n][m]);

}
signed main(){
    freopen("expand.in","r",stdin);
    freopen("expand.out","w",stdout);
    read();n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++)A[i]=a[i]=read();
    for(int i=1;i<=m;i++)B[i]=b[i]=read();
    solve();while(q--){
        for(int i=1;i<=n;i++)a[i]=A[i];
        for(int i=1;i<=m;i++)b[i]=B[i];
        int kx=read(),ky=read();
        for(int i=1;i<=kx;i++){int x=read(),v=read();a[x]=v;}
        for(int i=1;i<=ky;i++){int x=read(),v=read();b[x]=v;}
        solve();
    }return 0;
}

T4

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9')f=(c!='-'),c=getchar();
    while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
    if(f)return x;return -x;
}
const int maxn=2e5;
struct task{int x,y,v;}L[maxn];
int f[maxn],val[maxn],n,m,k,d;
signed main(){
    freopen("run.in","r",stdin);
    freopen("run.out","w",stdout);
    read();int T=read();
    while(T--){
        n=read(),m=read(),k=read(),d=read();
        for(int i=1;i<=m;i++)L[i]={read(),read(),read()};
        sort(L+1,L+1+m,[](task a,task b){return a.x<b.x;});
        for(int i=1;i<=n;i++)val[i]=f[i]=0;
        for(int i=1,j=1;i<=n;i++){
            while(j<=m&&L[j].x<=i)val[L[j].x-L[j].y+1]+=L[j].v,j++;
            f[i]=f[i-1];
            for(int p=i,sum=0;p>i-k&&p;p--){
                sum+=val[p];
                if(p==1)f[i]=max(f[i],sum-d*(i-p+1));
                else f[i]=max(f[i],f[p-2]+sum-d*(i-p+1));
            }
        }printf("%lld\n",f[n]);
    }return 0;
}