CSP2021

Daidly · 2021-10-24 12:40:54 · 个人记录

10.23

8:20 刚坐下，下载试题，写了个快读。
8:30 看题，T1 是个数学题，感觉还行。
8:45 写完 T1。
8:55 看完 T2 感觉很奇怪
9:00 想到一种 T2 O(q_1n+q_2\log n) 的算法，其中 q_{1,2} 表示操作 1,2 的个数，开始写（赛后发现有人写这种，能过）。
10:00 没调出来，准备写暴力，大概是比 O(q_1n\log n+q_2\log n) 快的算法，为什么快呢，我把直接排序改成了区间排序。具体而言，将值在修改区间内的排序：

if(opt==1){
    x=read(),v=read();
    pos=find(a[x],x);
    a[x]=v;
    if(v==b[pos].w){
        continue;
    }else if(v<b[pos].w){
        tmp=find1(v);
        b[pos].w=v;
        sort(b+tmp,b+pos+1,cmp);
    }else{
        tmp=find2(v);
        b[pos].w=v;
        sort(b+pos,b+tmp+1,cmp);
    }
}

T2 由于我写了两种算法（正解&暴力）但是正解写挂了，注释起来，一共有 250 行。

不算写挂的，光是有用的也有 100 行：

#include<bits/stdc++.h>
using namespace std;

int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}

const int MAXN=8005;
int n,q,a[MAXN];
struct node{
    int w,num;
}b[MAXN];

bool cmp(node x,node y){
    if(x.w==y.w)return x.num<y.num;
    return x.w<y.w;
}

int find(int x,int numm){
    int l=1,r=n,mid,ans=0,ansl=0,ansr=0;
    while(l<=r){
        mid=l+r>>1;
        if(b[mid].w>=x)ansl=mid,r=mid-1;
        else l=mid+1;
    }
    l=1,r=n;
    while(l<=r){
        mid=l+r>>1;
        if(b[mid].w>x)ansr=mid,r=mid-1;
        else l=mid+1;
    }
    if(ansr)ansr--;
    else ansr=n;
    l=ansl,r=ansr;
    while(l<=r){
        mid=l+r>>1;
        if(b[mid].num<=numm)ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

int find1(int x){
    int l=1,r=n,mid,ans=1;
    while(l<=r){
        mid=l+r>>1;
        if(b[mid].w<x)ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

int find2(int x){
    int l=1,r=n,mid,ans=n;
    while(l<=r){
        mid=l+r>>1;
        if(b[mid].w>x)ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans;
}

int main(){
    //freopen("sort.in","r",stdin);
    //freopen("sort.out","w",stdout);
    n=read(),q=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        b[i].w=a[i];
        b[i].num=i;
    }
    sort(b+1,b+n+1,cmp);
    int opt,x,v,pos,tmp;
    while(q--){
        opt=read();
        if(opt==1){
            x=read(),v=read();
            pos=find(a[x],x);
            a[x]=v;
            if(v==b[pos].w){
                continue;
            }else if(v<b[pos].w){
                tmp=find1(v);
                b[pos].w=v;
                sort(b+tmp,b+pos+1,cmp);
            }else{
                tmp=find2(v);
                b[pos].w=v;
                sort(b+pos,b+tmp+1,cmp);
            }
        }else{
            x=read();
            cout<<find(a[x],x)<<endl;
        }
    }
    return 0;
}
/*
3 4
3 2 1
2 3
1 3 2
2 2
2 3
*/
/*
#include<bits/stdc++.h>
using namespace std;

int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}

const int MAXN=8005;
int n,q,a[MAXN];
struct node{
    int w,num;
}b[MAXN];

bool cmp(node x,node y){
    return x.w<y.w;
}

int find(int x,int numm){
    int l=1,r=n,mid,ans=0,ansl=0,ansr=0;
    while(l<=r){
        mid=l+r>>1;
        if(b[mid].w>=x)ansl=mid,r=mid-1;
        else l=mid+1;
    }
    l=1,r=n;
    while(l<=r){
        mid=l+r>>1;
        if(b[mid].w>x)ansr=mid,r=mid-1;
        else l=mid+1;
    }
    if(ansr)ansr--;
    else ansr=n;
    l=ansl,r=ansr;
    while(l<=r){
        mid=l+r>>1;
        if(b[mid].num<=numm)ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

int main(){
    freopen("sort.in","r",stdin);
    //freopen("sort.out","w",stdout);
    n=read(),q=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        b[i].w=a[i];
        b[i].num=i;
    }
    sort(b+1,b+n+1,cmp);
    int opt,x,v,pos,tmp;
    q=10;
    while(q--){
        opt=read();
        if(opt==1){
            x=read(),v=read();
            pos=find(a[x],x);
            tmp=pos;
            if(v==b[pos].w)continue;
            else if(v<b[pos].w){
                for(int i=pos;i>=1;--i){
                    if(b[i].w==v){
                        if(b[i].num<x){
                            tmp=i+1;
                            break;
                        }
                    }else if(b[i].w<v){
                        tmp=i+1;
                        break;
                    }
                }
                //[tmp,pos-1]->[tmp+1,pos]
                for(int i=pos-1;i>=tmp;--i){
                    b[i+1].w=b[i].w;
                    b[i+1].num=b[i].num;
                }
                b[tmp+1].w=v;
                b[tmp+1].num=x;
            }else{
                for(int i=pos;i<=n;++i){
                    if(b[i].w==v){
                        if(b[i].num>x){
                            tmp=i-1;
                            break;
                        }
                    }else if(b[i].w>v){
                        tmp=i;
                        break;
                    }
                }
                //[pos+1,tmp]->[pos,tmp-1]
                for(int i=pos;i<=tmp-1;++i){
                    b[i].w=b[i+1].w;
                    b[i].num=b[i+1].num;
                }
                b[tmp-1].w=v;
                b[tmp-1].num=x;
            }
            a[x]=v;
        }else{
            x=read();
            cout<<find(a[x],x)<<endl;
        }
    }
    return 0;
}
*/
/*
10 10
877332633 234569527 229171089 600324455 1458624 887548760 574229391 234569527 202374341 849045846
2 7
1 2 234569527
1 4 600324455
2 6
2 9
2 6
2 3
1 5 246345024
1 6 856960762
2 7

*/

10:32 写完 T2，浪费了大把时间，也为接下来的爆蛋打下基础。
10:42 看完 T3，感觉不难，细节很多。
10:50 写完 T3，测样例 2 挂了。
10:55 测样例 4 时用 fc 测时不知道为什么挂，翻到 network4.ans 的第 325 行发现没问题啊，就没管。
11:10 开始写 T4。
11:40 写了个暴力，不知道复杂度，样例都过了，反正没时间了。。。
然后就是提交。

中午睡觉。

2:15 才坐到电脑前，妈的 dev 下载到 2:26 下载不下来，换电脑，rp--。
2:35 才开始看题。
2:45 读完 T1 简单写了一下，发现不太会。
3:00 发现 T1 读错题了，忽略了“先到先得”，还以为是一个很难的 dp，此时跑去看 T2。
3:10 想写 T2 15 分的暴力。
3:30 写完挂了，没调出来，去看 T1。
4:00 写完了 T1 的暴力，复杂度比 O(n^2) 大，但是似乎比 O(n^3) 小。
4:00-5:00 心态不太好输了啊，T2 样例没复制，一直手动输入，结果发现是 ( 一直打成了 <（这两个都在键盘中间，只是一个上一个下）。

代码里写的是 (。

我自己也知道是 (。

输入时输入的是 <。

。。。。。。

要是有这 1h T1 肯定冲出来了。

中间抽空看了一下 T4 的题意，感觉不可做。

5:10 弃疗 T2，看 T3，发现有 28 暴力，写。
5:30 写完暴力，过了小样例。
5:30 意识到 T1 离散化线段树是个做法，开始莽。
5:48 写完离散化线段树，样例挂了，心态很崩。。。
6:02 想最后去冲一下 T2 暴力分。
6:20 很遗憾，人没了。
6:30 匆匆忙忙把我那个 T1 不知道是什么的暴力和 T2 的没调出来代码（只过了样例 1，样例 2 多输出 2）和 T3 的暴力 T4 的随机数交上去了。
6:40 出考场，心态炸裂，全程不想说话，想睡觉。

晚上吃完饭回家去测 pj 和 tg。

洛谷的 pj 挂成狗。

100+92+65+30=287

很离谱。

T2 的稍微优化是有作用的，同学的直接 sort 只有 76。

T3 挂了，有可能是这个原因：link，但还是似乎有数据能卡掉我 T3，考场上也没时间检查了。

T4 只有 30，而且 30 的很离谱：

别人的 30：

我的 30：

jsk 还比洛谷少，只有 100+76+65+0=241，而且 T3 也是这几个点挂了：

我感觉 T3 用的可能是同样的数据？

优化并没有起作用。

T4 boom 0 了，但是考场上大样例都过了。。。

T4：可能是没注意格式吧。

看官方结果吧，可能在 [241,322] 之间？

然后测 tg，先去 InfOJ 上测的：

40+10+28+0=78

垫底喽，不知道官方数据几分。

洛谷上也有了，m1 和 m2 差的较大可以把我卡掉一些分......

T2 还是 10 分，可能 T2 用的可能是同样的数据？

后面发现我 T1 调挂的线段树好像可以过？

妈的浪费时间在 T2 暴力上了还挂了，白扔 100 分。

反正爆蛋了，几乎没有给自己留下充足的思考时间，全在调暴力，浪费时间在调代码上，蓝勾没了。

S 组考试：

先读清楚题意再写！留下充足的思考时间！

提高代码能能力！提高调试能力！

合理分配时间！出考场才发现就花了 20 分钟打暴力的 T3 不是很难，合理分配时间是可以冲出来的！

从臆想中的 100+15+100+0 掉到了爆蛋哈哈哈不愧是我正式赛没有一次发挥好！

草普及 T4 n^2 暴力都能有 70，我是输在了没对拍上吗，垃圾样例