CSP-J2021 第二轮（复赛）游记

Harry_Meng · 2021-11-23 21:42:29 · 个人记录

CSP-J2021 第二轮（复赛）游记

前言

坐标：SD-jn

这里是我的初赛游记

Day -20

十一假期，模拟赛进行中，这几天的模拟赛思维题明显增多，所以我猜测这一次 CCF 可能考几道思维题（当时我思维题做得还不错）

Day -14~Day -1

说句实话，我所在的学校其实并不怎么重视竞赛，仅仅是凭借着中考的成绩优秀以及体育成绩特别好而有知名度，跟济南市其他的学校在竞赛这一点上没法比，但是由于我们学校这一次有 3 个人过了初赛（去年就一个人，复赛还是三等），终于，我们的信息老师给我们班主任说好了，让我们每天下午 4:45-5:55 去复习一个小时的 OI（别的学校的同学都整个下午的请假），不过虽然时间少，但聊胜于无吧，就抓紧时间搞搞 OI，尤其复习了 DP（结果复赛还没考！！！），即使这样我们班主任还说我状态很差，我真的不理解，OI 和 whk 之间本来就要有一些取舍，况且我成绩也没差到哪去啊？记得有一周有四个考试，我考了 3 个班里第二，1 个班里第三（第一名不是同一个人）。

最终决定，先不管别人怎么想了，先争取把 CSP-J 拿到省一，考完了回头再搞 whk。

于是每天跟我同学一起去机房搞 OI（顺便逃个跑操），刷了刷 pj 的知识点和历年真题，其实这一个小时过得很快，还要开机关机，真正搞 OI 的时间也就 50 分钟左右。

时间就这样不断地流逝着，终于在复赛前把之前的 T1和 T2 都敲了一遍，也写了写 T3 和 T4，感觉这次应该差不多能省一（只要没有心态爆炸）。rp++

Day 0

10 月 22 日，终于到达了日照，住在亚朵，去吃了个313羊庄，然后就去试机了，机子上的键盘好难用啊，按起来很别扭，rp-- ,有的机子直接蓝屏了，机房的老师还一直催我们快点试机，最后只打了个快读和文件输入输出就撤了。

回到酒店，先把以前的模拟题看了看，然后简单地打了几个板子就睡觉了。rp++

Day 1

早上起床，6:50，感觉状态还可以，不算很困，简单吃了早饭就直接去考场了。rp++

进考场时电脑上显示 8:10，看着还有 20min 我打了几个板子就趴了一会，结果 8:20 老师就发了密码说可以做题了，当时我还很疑惑（此处为伏笔）。

拿到题二话不说先开 T1，我天这题面怎么这么长，这是语文考试吧缓了缓心神，仔细读题，因为 n≤10^9，所以 Θ(n) 的算法肯定超时，由于当时比较紧张先打了个 Θ(r-l) 的算法，结果一看 r-l≤10^9 果断删了重写，想了一会，想出了 Θ(1) 的算法，过了样例之后也试图 hack 自己的代码，最终应该能 AC 了。估分 100pts。

T1 考场代码

#include<iostream>
#include<cstdio>
using namespace std;
int myn,myl,myr;
int myans=0;
int myread(){
    int x=0,f=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-'){
        ch=getchar();
    }
    if(ch=='-'){
        f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main(){
    freopen("candy.in","r",stdin);
    freopen("candy.out","w",stdout);
    myn=myread();
    myl=myread();
    myr=myread();
    if(myr-myl>=myn){
        myans=myn-1;
    }
    else{
        int mysl=myl/myn;
        int mysr=myr/myn;
        if(mysl==mysr){
            myans=myr%myn;
        }
        else{
            myans=myn-1;
        }
    }
    printf("%d",myans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

PS：当时担心变量名重复，在前面全加了个 my，然后就导致编译的时候好几次 CE。

解决了 T1，此时电脑时间是 8:45，直接开 T2。

T2 一看这什么玩意啊，搞插入排序，然后……这怎么搞啊？当时我的目标是 T2 拿 100pts 的，这么一看似乎只能拿 36 了，决定先想正解。正解的复杂度肯定是比较好分析的，应该是 Θ(5000×n)，但是这怎么搞啊，紧张得我连一个简单地 Θ(nq) 的 76 分暴力都没想出来，沉浸在自己以为的“正解”里，调了 20min 发现不对，此时时间已经过半，即 10:20，连忙写了个 Θ(n^2q) 暴力，然而过 n,q=1500 的大样例只跑了 2 秒？这么说我能拿 52 吗？

挣扎了许久，还是找不到思路太蒻了，只打了 36pts 暴力，希望 CCF 开了 O2 优化之后速度能快点。T2 估分[36,52]。

T2 考场代码

#include<iostream>
#include<cstdio>
using namespace std;
struct node{
    int x;
    int w;
}a[8500];
node b[8500];
int n,q;
int pd;
int s,v;
int myread(){
    int x=0,f=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-'){
        ch=getchar();
    }
    if(ch=='-'){
        f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main(){
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    n=myread();
    q=myread();
    for(int i=1;i<=n;i++){
        a[i].x=myread();
        a[i].w=i;
        b[i].x=a[i].x;
        b[i].w=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j>=2;j--){
            if(b[j].x<b[j-1].x){
                node t=b[j-1];
                b[j-1]=b[j];
                b[j]=t;
            }
            else if(b[j].x==b[j-1].x){
                if(b[j].w<b[j-1].w){
                    node t=b[j-1];
                    b[j-1]=b[j];
                    b[j]=t;
                }
            }
        }
    }
    while(q--){
        pd=myread();
        if(pd==1){
            s=myread();
            v=myread();
            a[a[s].w].x=v;
            for(int i=1;i<=n;i++){
                b[i]=a[i];
            }
            for(int i=1;i<=n;i++){
                for(int j=i;j>=2;j--){
                    if(b[j].x<b[j-1].x){
                        node t=b[j-1];
                        b[j-1]=b[j];
                        b[j]=t;
                    }
                    else if(b[j].x==b[j-1].x){
                        if(b[j].w<b[j-1].w){
                            node t=b[j-1];
                            b[j-1]=b[j];
                            b[j]=t;
                        }
                    }
                }
            }
        }
        else{
            s=myread();
            for(int i=1;i<=n;i++){
                if(b[i].w==s){
                    printf("%d\n",i);
                }
            }
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

中间还出了点 bug，写完 T2 时为 10:45。

没时间了，快开 T3。

这不是一个大模拟吗？

然后我眼瞎，把每个字符串的长度想成了 1000 （受数据范围影响），然后这样比较字符串复杂度 Θ(1000)，这么说我只能拿 15pts？炸了

因为符合性质 1，所以不用判断合法，样例还得自己造，后来才知道字符串长度不超过 25，彻底崩溃了……T3 估分[0,55]。

T3 考场代码

#include<iostream>
#include<cstdio>
using namespace std;
string s1[1005],s2[1005];
string zz[1005];
string pd[1005];
int n;
int c1=0,c2=0;
int dc=0,mc=0,sc=0;
int myread(){
    int x=0,f=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-'){
        ch=getchar();
    }
    if(ch=='-'){
        f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main(){
    freopen("network.in","r",stdin);
    freopen("network.out","w",stdout);
    n=myread();
    int l1=0,l2=0;
    for(int i=1;i<=n;i++){
        bool f=1;
        cin>>pd[i];
        if(pd[i]=="Server"){
            cin>>s1[++l1];
            zz[i]=s1[l1];
        }
        else{
            cin>>s2[++l2];
            zz[i]=s2[l2];
        }
        if(pd[i]=="Server"){
            string z=s1[l1];
            if(l1>1){

                for(int j=l1-1;j>=1;j--){
                    if(s1[l1]==s1[j]){
                        printf("FAIL");
                        printf("\n");
                        f=0;
                        break;

                    }
                }
            } 
            if(f==0){
                s1[l1]="cuowu";
                continue;
            }
            else{
                printf("OK");
                printf("\n");
                continue;
            }
        }
        else{
            string z=s2[l2];
            for(int j=1;j<=n;j++){
                if(z==zz[j]&&pd[j]=="Server"){
                    printf("%d\n",j);
                    f=0;
                    break;
                }
            }
            if(f==1){
                printf("FAIL");
                printf("\n");
            }
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

此时是 11:30，突然，监考老师说还剩 20min？？？我人懵了， 20min？不是 12:00 收卷吗？突然醒悟这个表慢！！！

迅速看 T4，打了个 10pts 的模拟，估分 10pts。

T4 考场代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
struct node{
    int x;
    int w;
};
node a[200005];
node b[200005];
int sum,cnt;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-'){
        ch=getchar();
    }
    if(ch=='-'){
        f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main(){
    freopen("fruit.in","r",stdin);
    freopen("fruit.out","w",stdout);
    n=read();
    sum=n;
    cnt=n;
    for(int i=1;i<=n;i++){
        a[i].x=read();
        a[i].w=i;
    }
    a[0].x=-1;
    while(n){
        sum=0;
        for(int i=1;i<=cnt;i++){
            if(a[i].x!=a[i-1].x){
                printf("%d ",a[i].w);
                n--;
            }
            else{
                b[++sum]=a[i];
            } 
        }
        memset(a,0,sizeof(a));
        for(int i=1;i<=cnt;i++){
            a[i]=b[i];
        }
        memset(b,0,sizeof(b));
        printf("\n"); 
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

然后跟同学玩了一下午。

Day 2

开始估分 突然发现 T4 模拟炸了，漏了一句 cnt=sum ，导致有爆零的风险，因为当时时间紧张没看见第一个样例，只测了第二个样例。

我的估分：100+[36,52]+55+[0,10]=[191,217]

洛谷：100+52+55+0=207

有道小图灵：100+36+55+10=201

Day 8

CCF 公布分数：100+52+55+10=217

看了数据才发现 T4 可以直接按顺序输出骗 10pts 的。

最终获得了山东省一等奖。

只可惜是个 4 级绿勾，T3 把大模拟打完就 5 级绿勾了啊……