2020 CSP-J 赛后总结

这次考试纯属意外,心态炸了


我诅咒出题人没有肺泡,只有骨骼肌!(当场去世)


还是总结一下吧:

进入考场

我提前60分钟进入考场,找到座位后老师便让我出去等到考试前五分钟进入考场。比较有缘的是,我初赛时前面的人和后面的人都进入了第二轮,我们也是相邻而坐。我的同学ZC也来得很早,于是我们和一些其他学校的人攀谈起来。听说成都某外国语学校的光辉事迹——全校去考初赛为了补录名额,但在这里得到了成都某外国语学校的同学否认了。

开考

考试开始后,那个密码我的旁边的人一直输入输入不起,老师和我都过来看了,最后都不成。于是老师借了我的U盘拷到了他的电脑上(U盘是放在袋子里,放在教室前面的),于是浪费了10min。。。

T1

题目传送门

before做T1时,我浏览了一下所有的题,发现最后一题好像类似一个我们模拟赛(教练自己出题)时考的奇怪的贪心题。心情大好,一下子就用2进制把第一题A了。

贴上你们最爱的代码(考试时):

#include<bits/stdc++.h>
#define N 35
using namespace std;
int n,w;
bool a[N]={},sf=0;
void cf(int num){
    if(n==0)return ;
    if(n%2==1){
        w=num;
        a[num]=1;
    }
    n=n/2;
    cf(num+1);
}
int main(){
    freopen("power.in","r",stdin);
    freopen("power.out","w",stdout);
    cin>>n;
    cf(0);
    if(a[0]==1)cout<<-1;
    else{
        for(int i=w;i>=1;i--){
            if(a[i]==1)cout<<(1<<i)<<" ";
        }
    }
    return 0;
}

T2

题目传送门

我看到第二题,想到了大家都能想到的,每次加入一个数,然后sort一遍就可以了。但自己算了一下复杂度最多50分,所以开始想优化。开始想它每次都会插入一个数继续排序,于是就想到了每次插入一个后冒泡升上去(或者插入到指定位置,插入排序)+一个二分查找,但我觉得有点麻烦。后来,我看到了一个让我兴奋的东西,每人的分数<=600,伟大的桶排就出现了。桶排的思路也就是每次对应的桶++,然后倒序查找。

又是最美丽的代码(考试时):

#include<bits/stdc++.h>
using namespace std;
int n,w;
int tp[650];bool ok;
int xs,gs,maxn=0,yq;
int main(){
    freopen("live.in","r",stdin);
    freopen("live.out","w",stdout);
    cin>>n>>w;
    for(int i=1;i<=n;i=-~i){
        cin>>xs;
        maxn=max(maxn,xs);
        ++tp[xs];
        gs=0;yq=max(1,int(i*w/100));ok=0;
        for(int i=maxn;;i--){
            if(tp[i]!=0){
                int fj=tp[i];
                while(1){
                    if(fj==0)break;
                    --fj;
                    ++gs;
                    if(gs==yq){
                        cout<<i<<" ";
                        ok=1;
                        break;
                    }
                }   
            }
            if(ok) break;
        }
    }
    return 0;
} 

T3

题目传送门

第三题我的第一个思路就是二叉树优化,但是呢,好像代码很难写,我又去想另一个思路。我于是发现了好像可以用记忆化搜索,就是记录每一次的处理值,如果没有改变,那后面的也不会改变。但是在存的时候却不好存,看到时间只有一小时了,所以我果断暴力栈。。。

又是代码。。。

#include<bits/stdc++.h>
using namespace std;
char c[1000001];
bool x[100001];
stack<bool>n;
int s,q,fm;int sum,js;
char getch(){
    ++js;
    return c[js];
}
bool ans(){
    js=0;
    char ch=getch();
    while(ch!='\n'){
        if(ch>='a'&&ch<='z'){
            int num=0;ch=getch();
            while(ch<='9'&&ch>='0')num=(num<<3)+(num<<1)+ch-'0',ch=getch();
            n.push(x[num]);
        }
        if(ch=='!'){
            bool fj=n.top();
            n.pop();
            n.push(!fj);
        }
        if(ch=='|'){
            bool fj1=n.top();
            n.pop();
            bool fj2=n.top();
            n.pop();
            n.push(fj1|fj2);
        }
        if(ch=='&'){
            bool fj1=n.top();
            n.pop();
            bool fj2=n.top();
            n.pop();
            n.push(fj1&fj2);
        }
        ch=getch();
    }
    return n.top();
}

int main(){
    //freopen("expr.in","r",stdin);
    ////////freopen("expr.out","w",stdout);
    char dick=getchar();
    while(dick!='\n'){
        ++sum;
        c[sum]=dick;
        dick=getchar();
    }
    c[sum+1]='\n';
    cin>>s;
    for(int i=1;i<=s;i=-~i)cin>>x[i];
    cin>>q;
    while(q--){
        cin>>fm;
        x[fm]=!x[fm];
        cout<<ans()<<endl;
        n.pop();
        x[fm]=!x[fm];
    } 
}

T4

题目传送门

第四题开始我一看是DP,看到上下左(并不是下左),哦嚯!我放弃了,所以怒写一个爆搜。写完之后发现还有30分钟,于是写了一个记忆化搜索,就开了3 1001 1001的数组,但我觉得好像这个数组会超,于是在最后写了一个

cout<<sizeof(jyh);

发现没有超,心里十分开心!满以为自己能考省一。

代码如下(考试源代码)

#include<bits/stdc++.h>
#define N 1002
using namespace std;
int jz[N][N],n,m;
long long jyh[3][N][N];
long long dfs(int x,int y,short syb/*0> 1^ 2\/*/){
    if(jyh[syb][x][y]!=-1e18)return jyh[syb][x][y];
    if(x==n&&y==m)return jz[x][y];
    long long maxn=-1e18;
    if(x==n){//x在最下面一行 
        maxn=max(dfs(x,y+1,0),maxn);// 向右走 
        if(syb==0)maxn=max(dfs(x-1,y,1),maxn);//下面边界,上一步是右可以向上走 
    }
    if(y==m)maxn=max(dfs(x+1,y,2),maxn);
    if(x==1){//如果在最上一行 
        if(y!=m){//如果y不在最后一列
            maxn=max(dfs(x,y+1,0),maxn);//向右走 
            if(syb==0)maxn=max(dfs(x+1,y,2),maxn);//shang面边界,上一步是右可以向下走
        }
    }
    if(x!=1&&x!=n&&y!=m){
        maxn=max(dfs(x,y+1,0),maxn);
        if(syb==0){
            maxn=max(dfs(x-1,y,1),maxn);
            maxn=max(dfs(x+1,y,2),maxn);
        }
        if(syb==1)maxn=max(dfs(x-1,y,1),maxn);
        if(syb==2)maxn=max(dfs(x+1,y,2),maxn);
    }
    jyh[syb][x][y]=maxn+jz[x][y];
    return maxn+jz[x][y];
}
int main(){
    //freopen("number.in","r",stdin);
    //freopen("number.out","w",stdout);
    for(int i=1;i<=1001;i=-~i)
        for(int j=1;j<=1001;j=-~j)
            jyh[0][i][j]=-1e18,jyh[1][i][j]=-1e18,jyh[2][i][j]=-1e18;
    cin>>n>>m;
    for(int i=1;i<=n;i=-~i)
        for(int j=1;j<=m;j=-~j)
            cin>>jz[i][j];
    cout<<dfs(1,1,0);
   cout<<sizeof(jyh);
}

民间数据

当民间数据出来时,我就把发下来的代码交了上去,结果100+95(莫名T了一个点)+35+0,最后一题爆0令我很惊奇!我查看了代码,当仔细浏览一遍时,我呆住了,我的最后一行写着大大的“cout<<sizeof(jyh)”,我小心翼翼得删掉了它,交到洛谷上去。

……

AC,你通过了此题……

这是我最大的遗憾。。。

总结

这次难度偏低,总体在DP难度之下,最主要是我的最后一题,唉,明年努力吧!

常记洛谷刷咕,AC不知何处。大佬皆姓周,误入黑题深处。呕吐,呕吐,写一行while(true)


发表于 2020-11-13 22:38:54 in 比赛