CSP2021退役记

Hello,\ OI \,!

自从开学起，whk 一直不断，两三个星期里，OI 的时间严重不足，甚至少到仅能看看文章，而没时间打代码，就在这样的情况下，CSP 到来了。

大约八月初的时候，收到了可以报名的信息，很快地提交了信息，并于月底准时给西西弗捐完钱，之后的日子就如我上面所说的一样。

Day\ 1:

早上是 tg，我想着随便考，以我的能力还难以在 tg 组立足，抱着这样的心态，我来到了考场。

其他人来的很早，初三的还有几个初二的神仙。没一会就进考场了，走完一遍程序便开始发卷。

很好，前面的单选题做的还算得心应手，转到最恶心的读程序题。

计算几何，开幕雷击。我整个人傻掉了，凭感觉选了几个答案下去。第二题读了一下像是最大子序和，这道题做的还行，复杂度靠主定理轻松求得。第三道题，？？？字符串，我又傻掉了，再次乱选。考完才知道这是个叫 base64 的东西。

开始自闭，殊不知可怕的在后面。

魔法数字写起来还挺顺利的，第二题——四毛子？！神 tm 提高考这些？？？

这玩意一周前我还看过，然而忘的一干二净。长叹一口气，又只好瞎蒙几个下去。

果然我还是不配待在 tg。中午对完答案只剩下 56 分，岌岌可危。

相比之下，下午就显得轻松许多。单选题 20min 不到就做完了，转向读程序。

第一题一个很显然的 popcount+lowbit ，快速写完，甚至觉得轻松得有点诡异。

果然，我的预感是正确的，第二题，又 tm 出了 base64，虽然是弱化版的，但我还是不会啊！又只得蒙了几个。第三题一个像线性筛的东西，但是我记错复杂度了，也没看出他到底要求什么东西。

完善程序就很简单，可以说是送分。

出来感觉还行，想着 base64 和线性筛扣一点自己七八十应该稳了，可是我错了。

对完答案，我几乎崩溃，只有 68.5，base64 挂了大分，三道选择全错，线性筛也挂了很多。

晚上感觉很彷徨，原本的游记计划鸽掉了，whk 并颓废了一会冷静一下。后来 my 来问我成绩

目前来说，我的 tg 可能擦线过，而 pj 悬了，未来能否进复赛，只能看天命了。

洛谷的膜你赛错过了，准备找个时间补一补题。

Day\ 1.5:

噫！好了！我中了！

害，一直都忘了更新游记。

Day\ 2:

好极了，可以躲避 whk，还不用早起。

离高铁站最近，来的最晚/kel。

等高铁的时候，wt 哥哥居然在 whk ！！1

上车后，打了一下模板，主要还是颓废（

然后就到了。

然后坐地铁。

然后出了地铁后，我们直接错过了酒店，跑到马路另一边，又跑了回来。

广州真是个充满多样性的城市。

好冷。

早上超早就起来了，跑去麦当劳结果七点才开门，草草在便利店解决完毕。

今年 pj 还行，没有离谱 dp，能打的都打了。

T1 签到题考场上想了大概 15min，脑子突然卡住了，在 30min 的时候搞完了。中午午睡的时候突然把我的做法 hack 了（居然三个样例都过了 /fad），希望 CCF 脚造数据良心亿点 /fad。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,l,r;
int main(){
    freopen("candy.in","r",stdin);freopen("candy.out","w",stdout);
    scanf("%d%d%d",&n,&l,&r);
    if(r-l>=n)printf("%d",n-1);
    else printf("%d",r%n);
    fclose(stdin);fclose(stdout);   return 0;
} 

。 T2 sort 一眼看到操作 1 数量不超过 5000，中间调了一些奇奇怪怪的错误，花了 1h 切掉。

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

const int N=8e3+10;

int n,q,b[N];
struct node{
    int val,id;
}a[N];

inline bool cmp(node x,node y){return x.val==y.val?x.id<y.id:x.val<y.val;}

int found(int v,int p){
    int l=1,r=n,mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(a[mid].val==v){
            if(a[mid].id==p)return mid;
            if(a[mid].id>p)r=mid-1;
            else l=mid+1;
        }else if(a[mid].val>v)r=mid-1;
        else l=mid+1;
    }
    return mid;
}

int main(){
    freopen("sort.in","r",stdin);freopen("sort.out","w",stdout);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)scanf("%d",&a[i].val),a[i].id=i,b[i]=a[i].val;
    sort(a+1,a+n+1,cmp);
    int op,x,y;
    while(q--){
        scanf("%d%d",&op,&x);
        if(op==1){
            scanf("%d",&y);
            if(b[x]==y)continue;
            int pos=found(b[x],x);
            if(b[x]<y){
                a[pos].val=b[x]=y;
                for(int i=pos;((a[i+1].val<a[i].val)||(a[i+1].val==a[i].val&&a[i].id>a[i+1].id))&&i<n;++i)swap(a[i],a[i+1]);
            }else {
                a[pos].val=b[x]=y;
                for(int i=pos;((a[i-1].val>a[i].val)||(a[i-1].val==a[i].val&&a[i].id<a[i-1].id))&&i>=2;--i)swap(a[i],a[i-1]);
            }
        }else printf("%d\n",found(b[x],x));
    }
    fclose(stdin);fclose(stdout);
    return 0;
} 

T3 模拟还不会做，跳过。

T4 马上就想到链表，可惜调了半天没调出来，遂改成队列，总共花了接近 1.5h。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=2e5+10;
int n,a[N],cnt;
queue<int>q[N];
int main(){ 
    freopen("fruit.in","r",stdin);freopen("fruit.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    a[0]=2;cnt=0;
    for(int i=1;i<=n;++i){
        if(a[i]!=a[i-1])q[++cnt].push(i);
        else q[cnt].push(i);
    }
    bool fl=true;
    while(fl){
        int lst=0;fl=false;
        for(int i=1;i<=cnt;++i){
            if(q[i].empty())continue;
            int x=q[i].front();
            if(a[x]==a[lst])continue;
            printf("%d ",x);q[i].pop();
            fl=true;
            lst=x;
        }
        if(fl)printf("\n");
    }   fclose(stdin);fclose(stdout);
    return 0;
} 

T3 只剩差不多半小时了，只好抓几个性质骗个分。

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e3+10;
int n,op[N],a[N],b[N],c[N],d[N],e[N];
bool vis[N];
char s[10];

int main(){
    freopen("network.in","r",stdin);freopen("network.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%s",s);vis[i]=1;getchar();
        op[i]=(s[0]=='S')?1:0;
        scanf("%d.%d.%d.%d:%d",&a[i],&b[i],&c[i],&d[i],&e[i]);
        if(a[i]>255||b[i]>255||c[i]>255||d[i]>255||e[i]>65535){
            printf("ERR\n");vis[i]=0;
            continue;
        }
        if(op[i]==1){
            bool fl=true;
            for(int j=1;j<i;++j){
                if(op[j]==0||!vis[j])continue;
                if(a[j]==a[i]&&b[j]==b[i]&&c[j]==c[i]&&d[j]==d[i]&&e[j]==e[i]){
                    fl=false;vis[i]=0;
                    break;
                }
            }
            if(!fl)printf("FAIL\n");
            else printf("OK\n");
        }else {
            int pos=0;
            for(int j=1;j<i;++j){
                if(op[j]==0||!vis[j])continue;
                if(a[j]==a[i]&&b[j]==b[i]&&c[j]==c[i]&&d[j]==d[i]&&e[j]==e[i]){
                    pos=j;
                    break;
                }
            }
            if(!pos)printf("FAIL\n");
            else printf("%d\n",pos);
        }
    }
    fclose(stdin);fclose(stdout);
    return 0;
} 

匆匆忙忙就搞完了，临近结束时突然冷得一批，全身都在抖。

luogu 估分：100+100+65+70=335

计蒜氪 估分：90+100+65+100=355

中午慌忙干完了饭，睡了 20min 又起来了，简直睡了个寂寞，tg 考场上困的要死，只会 t1 和 t3 暴力，其他交了个随机数就在那罚坐了 4h。

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

const int N=1e5+10;

int n,m1,m2;
struct node {
    int id,x,y;
} a[N];

priority_queue< int,vector<int>,greater<int> >q1,q2;

bool cmp(node a,node b) {
    return a.x<b.x;
}

int main() {
    scanf("%d%d%d",&n,&m1,&m2);
    if(n>=m1+m2)printf("%d\n",m1+m2);
    else {
        for(int i=1; i<=m1+m2; ++i)scanf("%d%d",&a[i].x,&a[i].y),a[i].id=(i<=m1)?1:2;
        sort(a+1,a+m1+m2+1,cmp);
        int ans=0;
        for(int k=1; k<=n; ++k) {
            int cur=0,cnt1=0,cnt2=0;
            while(!q1.empty())q1.pop();
            while(!q2.empty())q2.pop();
            for(int i=1; i<=m1+m2; ++i) {
                if(a[i].id==1) {
                    if(!q1.empty()&&a[i].x>=q1.top())q1.pop(),q1.push(a[i].y),++cur;
                    else if(cnt1<k)q1.push(a[i].y),++cur,++cnt1;
                } else {
                    if(!q2.empty()&&a[i].x>=q2.top())q2.pop(),q2.push(a[i].y),++cur;
                    else if(cnt2<n-k)q2.push(a[i].y),++cur,++cnt2;
                }
            }
            ans=max(ans,cur);
            if(ans==m1+m2)break;
        }
        printf("%d\n",ans);
    }
    return 0;
}

//T3

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

const int N=5e5+10;
int t,n;
bool fl;
deque<int>q;
struct node {
    int id,val;
} a[N];

void dfs(int x) {
    if(x>n*2) {
        fl=true;
        return;
    }
    if(x<=n) {
        int now=q.front();
        a[x].val=now;
        a[x].id=1;
        q.pop_front();
        dfs(x+1);
        if(fl)return;
        q.push_front(now);
        now=q.back();
        a[x].val=now;
        a[x].id=2;
        q.pop_back();
        dfs(x+1);
        if(fl)return;
        a[x].val=a[x].id=0;
        q.push_back(now);
    } else {
        int now;
        if(q.front()==a[n*2-x+1].val) {
            now=q.front();
            a[x].val=now;
            a[x].id=1;
            q.pop_front();
            dfs(x+1);
            if(fl)return;
            q.push_front(now);
            a[x].val=a[x].id=0;
        }
        if(q.back()==a[n*2-x+1].val) {
            now=q.back();
            a[x].val=now;
            a[x].id=2;
            q.pop_back();
            dfs(x+1);
            if(fl)return;
            q.push_back(now);
            a[x].val=a[x].id=0;
        }
    }
}

int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        if(n<=10) {
            while(!q.empty())q.pop_back();
            for(int i=1,x; i<=n*2; ++i)scanf("%d",&x),q.push_back(x);
            fl=false;
            dfs(1);
            if(fl) {
                for(int i=1; i<=n*2; ++i)printf("%c",a[i].id==1?'L':'R');
                printf("\n");
            } else printf("-1\n");
        } else printf("-1\n");
    }
    return 0;
}

luogu 估分：40+0+28+0=68

希望真正成绩出来了不要锅吧。

听说 lsz 和 hkf 都炸掉，希望再接再厉，明年双报。

说来说去，也到了尾声，两年多的时间就这样过去了，希望我最终能交出一份满意的答卷吧。至此，正式进入文化课模式，明年见。

\color{Black}2147483648

长风破浪会有时，直挂云帆济沧海。

后记

突然收到信息说出分了，赶忙去查了一下。

PJ:70+100+65+80=315

不出意料 T1 假做法果然挂了分。

TG:50+0+44+0=94

出乎意料，比估分高，骗分很给力

OVER