CSP-J 2020 游记

发布于 2020-12-21  325 次阅读


食用前提示:本文搬自作者的洛谷博客。

只要走的方向正确,不管前方的路有多苦,不管多么崎岖不平,都比站在原地更接近幸福 ——《千与千寻》

Update On 2020.11.11:

J组自测结束了,在 Luogu 比赛区订正后居然达到了rk11,在这里留个纪念吧。

Day -X

打CSP-S模拟赛各种被吊打/kk(也不知道我一个没进S组的为什么执着于CSP-S),J组的话还可以(除了被 $xze$ 大佬$1.5h$ $AK$ 之后吊着打那一次),所以打J组基本上是冲着300+去的(再不高分我要退役了鸭、、)。

Day 0

到下午一直在打各种模板,训练了一下手速,记了一下自己dev的配置(准备考试的时候设置一下)。

然后是到杭州的酒店休息了一下(下午打S组的都在真正意义上“休息”,只有我们这些J组的不敢“休息”/kk),也是相对早睡了(如果10点多算早的话)。

Day 0.5

早起,然而没想到下午考试的why比我起得还早、、在酒店吃了个早饭,草草地乘上同学的车出发去学军海创园了、、不过考前能碰到SYXX的同学也确实是一件令人欣喜的事情。

Day 1

输入解压密码,一看T1发现不是去年J组有手就行的题目了,居然考察了
$2^n >2^{n-1}+...+2^1+2^0 $
这个性质(可能有别的做法),于是感觉今年题目普遍比去年偏难。然而还是简单题, $10 min$ 切掉。然而此时心里已经开始紧张了。

于是开始看T2,刚看题目发现是个暴力,果断上手(其实这里我有点冲动了,应该先看看数据范围的),样例错了一发以后发现要如果要简单直白地维护当前每个选手的得分的话,时间复杂度是 $O(n^2)$ 的,直接人傻掉,开始胡思乱想了,甚至来了一发优先队列、、然而并不行。这时候认真看了一遍数据范围,看到$a_i \le 600$,然后想到是计数,过了T2。然而此时已经过去大半个小时了。。

之后看T3,发现题目难懂,没有明显思路,于是先看T4。T4是很明显的DP,一看$n \le 1000$确定是二维。然后看到题目说只能向上向下向右走,看出把一列看成一个整体,做一个前缀和,应该可以优化到后面的DP。

然后想到一个$O(n^2m)$的DP,设$dp_{i,j}$表示在第 $i$ 列第 $j$ 行时候的值,转移方程就是枚举 $1\le j \le n$ ,$1 \le k \le n$,暴力转移,加上 $a_{i+1,j}$ 到 $a_{i+1,k}$ 的和即可。

部分代码(考场):

inline long long GetMax(long long x,long long y){
    if (x>y) return x;
    else return y;
}

inline long long GetDis(int line,int x,int y){
    if (x>y) return a[x][line]-a[y-1][line];
    else return a[y][line]-a[x-1][line];
}

...

for (int k=1;k<=n;k++)
    for (int j=1;j<=n;j++)
        f[i+1][k]=GetMax(f[i+1][k],f[i][j]+GetDis(i+1,j,k));

于是就是 $70pts$,用时$30min$,此时剩余$1.5h$。

T4有70分了,就去看T3,一开始以为是把后缀表达式转化成中缀会比较好做,然后码了一会儿自闭了。。再仔细看了一遍题面,发现有 “为了方便处理,给出后缀表达式” 这句话,然后就明白了应该是根据后缀表达式去做,之后不难想到是用栈去模拟,用了 $20 min$ 写了一个$O(n^2)$暴力,得分$30pts$,中间一度挂掉大样例,原因是 $x$ 的下标不一定是一位数(奇怪的错误增加了)。

最后一个半小时里面,先是试图去想了一下T4的正解,发现想不出来,应该是要加一些的玄学优化,于是放弃,去看T3。T3正解比较好想,毕竟 $ 1 \le |s| \le 10^6$,$1\le q,n \le 10^5$ 的提示还是给得挺明显的。不难想到是跑一遍初始化,建出一颗符号树,然后每次修改只需要修改相关的 $log n$ 个运算就可以了。但是码量很大,尝试了 $40min$以后 果断放弃,去检查去了。

于是,在忙碌而有序的尾声中,CSP-J 2020结束了,期望得分$100+100+30+70=300pts$,估计是一个基本分,但是至少也挺稳的了(后来民间数据测出来果然是300pts)。

后记

总体来说,这次题目的思维含量不高(真的不高,尤其是T4的DP几乎就是明摆着告诉你了,T3也是一道大码量题)(个人理解,不对请指出),出来以后也看到很多人都口胡了T3的正解,但是真正写出来的却很少。感觉这次CSP应该把T3和T4位置调换一下。不过这次的题目总体还是挺有难度的,考察的内容也挺细致,不失为一套好题。

个人感觉就是在比赛的时候应该多看看题面和数据范围,尤其是后者,有时候你想了30分钟都不一定有看到一句话的题面/数据范围有用。找到正确的窍门和要点才是解题的关键。

Update On 2020.11.8:

贴上我的源代码:

T1:

#include<bits/stdc++.h>
using namespace std;
const int LogN=25;

int n,a[LogN],x,cnt;
bool flag[LogN];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
} 

int main(){
    freopen("power.in","r",stdin);
    freopen("power.out","w",stdout);
    n=read();
    x=1,cnt=0;
    while (x<=n){
        x=x<<1;
        a[++cnt]=x;
    }
    for (int i=cnt;i;i--)
        if (n>=a[i]) n-=a[i],flag[i]=true;
    if (n!=0) printf("-1\n");
    else {
        bool flag_first=false;
        for (int i=cnt;i;i--)
            if (flag[i]){
                if (!flag_first) printf("%d",a[i]);
                else printf(" %d",a[i]);
                flag_first=true;
            }
    }
    return 0;
}

T2:

#include<bits/stdc++.h>
using namespace std;
const int N=100005,MaxVal=605;

int n,w,Num,sum;
int a[N],f[MaxVal];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
} 

int main(){
    freopen("live.in","r",stdin);
    freopen("live.out","w",stdout);
    n=read(),w=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    for (int i=1;i<=n;i++){
        Num=max(1,(int)(i*1.0*w/100.0));
        f[a[i]]++;
        sum=0;
        for (int j=600;j>=0;j--){
            sum+=f[j];
            if (sum>=Num){
                if (i==1) printf("%d",j);
                else printf(" %d",j);
                break;
            }
        }
    }
    return 0;
}

T3-30pts:

#include<bits/stdc++.h>
using namespace std;
const int LEN=100005;

int n,Q,Len;
bool val[LEN],sta[LEN];
char s[LEN];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
} 

inline void GetAns(){
    int i=1,t=0,index;
    char ch;
    while (i<=Len){
        if (s[i]=='x'){
            i++;
            index=0;
            while (isdigit(s[i])){
                index=index*10+s[i]-'0';
                i++;
            }
            sta[++t]=val[index];
        }
        else if (s[i]=='&'){
            sta[t-1]=sta[t-1]&sta[t];
            t--;
        }
        else if (s[i]=='|'){
            sta[t-1]=sta[t-1]|sta[t];
            t--;
        }
        else if (s[i]=='!')
            sta[t]=1^sta[t];
        i++;
    }
}

void sub_task1(){
    while (Q--){
        int x=read();
        val[x]=1^val[x];
        GetAns();
        printf("%d\n",sta[1]);
        val[x]=1^val[x];
    }
}

void sub_task2(){
    while (Q--){
        printf("0\n");
    }
}

int main(){
    freopen("expr.in","r",stdin);
    freopen("expr.out","w",stdout);
    char ch=getchar();
    while (ch!='\n'){
        s[++Len]=ch;
        ch=getchar();
    }
    n=read();
    for (int i=1;i<=n;i++)
        val[i]=read();
    Q=read();
    sub_task1();
    return 0;
}

T3-100pts:

#include<bits/stdc++.h>
#define lid tree[id].lson
#define rid tree[id].rson
using namespace std;
const int N=2000005;

struct Node{
    int lson,rson,opt;
    int val,num;
    //opt表示运算符,opt=-1表示这是数,0表示!,1表示&,2表示|
    //num表示这个数在原来x数组中的下标 
}tree[N<<2];

int n,cnt=0,len=0,Q,x,t;
int val[N],sta[N];
bool effect[N];     //effect数组记录一个值取反是否会影响答案
char s[N];

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline void dfs(int id){
    if (tree[id].opt==-1){      //这个位置上是一个数 
        effect[tree[id].num]=1; //此时这个数就会影响答案了
        return;
    }
    if (!tree[id].opt) dfs(lid);    //非运算,把取反的操作数默认放到左子树
    else if (tree[id].opt==1){
        //只有在左儿子、右儿子都是0的情况下,取反才不会发生任何改变
        if (tree[lid].val+tree[rid].val==2)
            dfs(lid),dfs(rid);
        else if (tree[lid].val) dfs(rid);
        else if (tree[rid].val) dfs(lid);
    }
    else {
        //同理,只有在左儿子、右儿子都是1的情况下,取反才不会发生任何改变
        if (tree[lid].val+tree[rid].val==0)
            dfs(lid),dfs(rid);
        else if (!tree[lid].val) dfs(rid);
        else if (!tree[rid].val) dfs(lid);
    }
}


int main(){
    freopen("expr.in","r",stdin);
    freopen("expr.out","w",stdout);
    char ch=getchar();
    while (ch!='\n'){
        s[++len]=ch;
        ch=getchar();
    }
    n=read();
    for (int i=1;i<=n;i++)
        val[i]=read(); 
    for (int i=1;i<=len;i++){
        if (s[i]=='x'){
            int x=0;
            while (s[i+1]<='9'&&s[i+1]>='0'){
                x=x*10+s[i+1]-'0';
                i++;
            }
            cnt++;
            tree[cnt].val=val[x];
            tree[cnt].num=x;
            tree[cnt].opt=-1;
            sta[++t]=cnt;
        }
        else if (s[i]=='!'){
            cnt++;
            tree[cnt].val=!tree[sta[t]].val;
            tree[cnt].lson=sta[t--];
            tree[cnt].opt=0;
            sta[++t]=cnt;
        }
    else if (s[i]=='&'){
            cnt++;
            tree[cnt].val=tree[sta[t]].val&tree[sta[t-1]].val;
            tree[cnt].opt=1;
            tree[cnt].lson=sta[t--];
            tree[cnt].rson=sta[t--];
            sta[++t]=cnt;
        }
    else if (s[i]=='|'){
            cnt++;
            tree[cnt].val=tree[sta[t]].val|tree[sta[t-1]].val;
            tree[cnt].opt=2;
            tree[cnt].lson=sta[t--];
            tree[cnt].rson=sta[t--];
            sta[++t]=cnt;
        }
    }
    dfs(cnt);
    int ans=tree[cnt].val;  //不作任何改变的答案
    Q=read();
    while (Q--){
        x=read();
        if (effect[x]) printf("%d\n",1^ans);
        else printf("%d\n",ans);
    }
    return 0;
}

T4-70pts:

//注意开long long!(10^6*10^4) 
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
const long long inf=100000000000000005;

int n,m;
long long a[N][N],f[N][N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline long long GetMax(long long x,long long y){
    if (x>y) return x;
    else return y;
}

inline long long GetDis(int line,int x,int y){
    if (x>y) return a[x][line]-a[y-1][line];
    else return a[y][line]-a[x-1][line];
}

void sub_task1(){
    //设f[i][j]表示当前在第i列第j行的最大值
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            f[i][j]=-inf;
    for (int i=1;i<=n;i++) f[1][i]=GetDis(1,1,i);
    for (int i=1;i<=m-1;i++){
        for (int k=1;k<=n;k++)
            for (int j=1;j<=n;j++)
                f[i+1][k]=GetMax(f[i+1][k],f[i][j]+GetDis(i+1,j,k));
    }
//  for (int i=1;i<=n;i++){
//      for (int j=1;j<=m;j++)
//          printf("%lld ",f[j][i]);
//      printf("\n");
//  }
    printf("%lld\n",f[m][n]);
}

void sub_task2(){
    //设f[i][j]表示当前在第i列第j行的最大值
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            f[i][j]=-inf;
    for (int i=1;i<=n;i++) f[1][i]=GetDis(1,1,i);
    for (int i=1;i<=m-1;i++){
        for (int k=1;k<=n;k++)
            for (int j=1;j<=n;j++)
                f[i+1][k]=GetMax(f[i+1][k],f[i][j]+GetDis(i+1,j,k));
    }
//  for (int i=1;i<=n;i++){
//      for (int j=1;j<=m;j++)
//          printf("%lld ",f[j][i]);
//      printf("\n");
//  }
    printf("%lld\n",f[m][n]);
}

int main(){
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    n=read(),m=read();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            a[i][j]=read()+a[i-1][j];
    if (n<=300) sub_task1();
    else sub_task2();
    return 0;
}

T4-100pts:

//注意开long long!(10^6*10^4) 
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
const long long inf=100000000000000005;

int n,m;
long long a[N][N],f[N][N],dp1[N],dp2[N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

void sub_task2(){
    f[1][1]=a[1][1];
    for (int i=2;i<=n;i++)
        f[i][1]=f[i-1][1]+a[i][1];
    for (int j=2;j<=m;j++){
        dp1[1]=f[1][j-1]+a[1][j];
        dp2[n]=f[n][j-1]+a[n][j];
        for (int i=2;i<=n;i++)
            dp1[i]=max(dp1[i-1],f[i][j-1])+a[i][j];
        for (int i=n-1;i;i--) 
            dp2[i]=max(dp2[i+1],f[i][j-1])+a[i][j];
        for (int i=1;i<=n;i++)
            f[i][j]=max(dp1[i],dp2[i]);
    }
    printf("%lld\n",f[n][m]);
}

int main(){
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    n=read(),m=read();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            a[i][j]=read();
    sub_task2();
    return 0;
}

我们无法选择过去,但我们可以改变未来。