CSP游记

· · 生活·游记

前话：这篇文章作者文笔不好，是个初三弱省蒟蒻。

初赛

J组准考证：AH-J00336
S组准考证：AH-S00143
考点：依旧是二中
离大谱，初赛考交互了？？考得一坨。

复赛

DAY -50

额，文化课作业怎么这么多，考前根本刷不到题。

DAY -7

没打你谷模拟赛，感觉质量不高，打的MX模拟赛。

8:34

开 T_{1}，发现只有数字才有用，把所有出现数字降序排序输出不就行了？一开始写了个堆，后来发现开个桶就行了，没那么麻烦。

8:51

开 T_{2}，发现是道数学题？一看数据范围，直接模拟也行？放弃推结论，直接模拟，不会有人行、列看反了吧？哈哈。

9:01

开 T_{3}，发现区间异或？想都不用想肯定要前缀异或维护一下。剩下的思路有点乱，想了很多种做法，觉得可行的大概有三个（现在已经记不清了，大概写下）：

  1. 容易发现当区间右端点固定时，左端点越后一定不劣，所以每个数往前模拟找异或值为 k 的区间，记录区间，找到不相交区间的数量。后来发现有点问题，遂放弃。
  2. 先找所有数字 k 出现的地方，将整个序列分成若干段，每段区间中我们往里面加隔板，整体思路是个dfs，但是这咋写？遂也放弃。
  3. 没事不会贪心，我还会DP，预处理下前缀异或数组，这道题是很明显的区间动规板子啊！具体的设 dp_{l,r} 表示 a_{l}，a_{l+1}，\ldots，a_{r} 中能选区间的最大值。以下我们定义 getval(l,r) 表示区间异或值。则很容易推导出转移方程：dp_{l,r}=max(dp_{l,r},getval(l,r),dp_{l,k}+dp_{k+1,r},getval(l,k)+getval(k+1,r))。初始化时，dp_{l,l}=getval(l,l)。求解目标就是 dp_{1,n}。
    时间复杂度:O(n^3)
$10:14$ 写完了，但是样例一直算不对，开调。很快调完了，那么现在开T4，还是优化T3的 $3$ 次方做法呢？这里做出一个非常错误的抉择——继续优化T3（因为我并不知道这不是正解，且优化的没啥效果，甚至还挂了 $5pts$，所以时间完全浪费了） $10:30$ 想到梦熊J组模拟赛 $T_{3}$ 的优化方法了，发现选定一个数后它的 $dp$ 值等同于前面从 $1$ 推到当前的 $dp$ 最大值加上从 $n$ 推到当前的 $dp$ 最大值，时间复杂度 $O(2 \times n^2)$ ？很快写完了，样例全过了。具体细节看代码的```solve2()```函数。 $10:44$ 开T4，很快想到一个```DP```错解，跟T3差不多的写法？但是，也懒得想了，所以按错解写了并且写了下性质分，赛后发现根本不对，且性质不知道怎么把组合数推成等差数列了？挂完了。 $12:10$ 考完且离开了学校，开你谷群，发现解法完全不一样？不管了，先休息。 **【S组】** 完蛋上午J组已经挂了。S组没必要写时间轴了QwQ。 解压包密码：```Ren5Jie4Di4Ling5%``` T1开局王炸，一开始写了贪心按所有人的满意程度排序，在用个桶标记乱搞？发现第三组数据不对，陷入沉思。这一思考就是两个半小时。发现一种```DP```做法（很好，赛后发现不是我一个人被骗到```DP```上了），式子非常难推，细节也多，但是没时间了，所以写了，但是调了很久。 留给后三题没多少时间了，发现 $T_{3}$ 考字符串？而且感觉这个换字符串有点像```KMP```？不懂，先写 $T_{2}$。嗯，标准的```Kruskal```有 $16$ 分？而且容易看出的一点是，后续的操作一定只在最小生成树上。但是我的板子一直不对？（后来赛后发现是我自己造的数据手推错了，太荒谬了），不管了，$T_{3}、T_{4}$ 我选择总司令，连性质来都不及看就结束了！ 结束后发现考的还没去年好，挂完了 ###### DAY ？？ 期望得分： ```J```：$100+100+60+30=290

S：60+16+?+?=76+?
实际得分:
J：100+100+55+12=267
S：50+0+0+4=54

赛后没几天NOI网站卡bug，能通过申诉看到得分了？发现J的 T_{4}性质果然写炸了，丢了 20 多分，哎。

而且S的 T_{2} 怎么别人标准板子都是 32 分，我一分没有？找了一晚上，最小生成树模板对的，函数也都对的，您猜哪里出问题了？——没开long long！这下真见祖宗了，搞不好就差这一点分就是二等了，哎。但是 T_{4} 怎么有 4 分？

总结

先放下我的考场代码： ::::info[J] :::success[T1]

#include<bits/stdc++.h>
#define int long long
#define N (int)(15)
using namespace std;
int b[N];
inline void read(int &num);
inline void solve();
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}
inline void solve(){
    string str;
    cin>>str;
    int slen=str.size();
    for(int i=0;i<slen;++i){
        char c=str[i];
        if(c>='0'&&c<='9'){
            ++b[c-'0'];
        }
    }
    for(int i=9;i>=0;--i){
        while(b[i]){
            cout<<i;
            --b[i];
        }
    }
}

:::

:::success[T2]

#include<bits/stdc++.h>
#define N (int)(1e3+5)
using namespace std;
int a[N],G[N][N];
inline void read(int &num);
inline void solve();
inline bool cmp(const int &A,const int &B);
signed main(){
    freopen("seat.in","r",stdin);
    freopen("seat.out","w",stdout);
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}
inline void read(int &num){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        f=(ch=='-')?-1:1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    num=x*f;
}
inline void solve(){
    int n,m;
    read(n);
    read(m);
    for(int i=1;i<=n*m;++i){
        read(a[i]);
    }
    int R=a[1],ct=0;
    sort(a+1,a+1+n*m,cmp);
    for(int j=1;j<=m;++j){
        if(j&1){
            for(int i=1;i<=n;++i){
                ++ct;
                if(a[ct]==R){
                    printf("%d %d",j,i);
                }
            }
        }else{
            for(int i=n;i>=1;--i){
                ++ct;
                if(a[ct]==R){
                    printf("%d %d",j,i);
                }
            }
        }
    }
}
inline bool cmp(const int &A,const int &B){
    return A>B;
}

::: :::success[T3]

#include<bits/stdc++.h>
#define int long long
#define N (int)(5e5+5)
using namespace std;
int a[N],ans,n,k;
int Xor[N];
//int dp[N][N];
int bck[N];
int fro[N];
inline void read(int &num);
inline void solve();
inline void solve2();
inline int getval(int l,int r);
signed main(){
    freopen("xor.in","r",stdin);
    freopen("xor.out","w",stdout);
    int T=1;
    while(T--){
        solve2();
    }
    return 0;
}
inline void read(int &num){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        f=(ch=='-')?-1:1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    num=x*f;
}
/*
inline void solve(){
    read(n);
    read(k);
    for(int i=1;i<=n;++i){
        read(a[i]);
        Xor[i]=Xor[i-1]^a[i];
    }
    for(int i=1;i<=n;++i){
        dp[i][i]=getval(i,i);
    }
    for(int step=0;step<=n-1;++step){
        for(int l=1;l<=n-step;++l){
            int r=l+step;
            dp[l][r]=max(dp[l][r],getval(l,r));
            for(int k=l;k<r;++k){
                dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]);
                dp[l][r]=max(dp[l][r],getval(l,k)+getval(k+1,r));
            }
        }
    }
    printf("%lld\n",dp[1][n]);
}
*/
inline void solve2(){
    bool flag=true;
    read(n);
    read(k);
    for(int i=1;i<=n;++i){
        read(a[i]);
        if(a[i]>1)flag=false;
        Xor[i]=Xor[i-1]^a[i];
    }
    if(flag&&n>=(int)(1e4)){
        if(k>1){
            puts("0");
        }else{
            int ct_0=0,ct_1=0;
            for(int i=1;i<=n;++i){
                if(a[i]==0){
                    ++ct_0;
                }else if(a[i]==1){
                    ++ct_1;
                }
            }
            if(k==1){
                printf("%lld\n",ct_1);
            }else{
                printf("%lld\n",ct_0);
            }
        }
    }
    fro[1]=getval(1,1);
    for(int step=0;step<=n-1;++step){
        int r=1+step;
        for(int k=1;k<r;++k){
            fro[r]=max(fro[r],fro[k]+getval(k+1,r));
        }
    }
    bck[n]=getval(n,n);
    for(int step=0;step<=n-1;++step){
        int l=n-step;
        for(int k=n;k>l;--k){
            bck[l]=max(bck[l],bck[k]+getval(l,k-1));
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        ans=max(ans,max(fro[i]+bck[i+1],fro[i-1]+bck[i]));
    }
    printf("%lld\n",ans);
}
inline int getval(int l,int r){
    int t=Xor[r]^Xor[l-1];
    return t==k?1ll:0ll;
}

::: :::success[T4]

#include<bits/stdc++.h>
#define int long long
#define MOD 998244353
#define N (int)(5e3+5)
using namespace std;
int a[N],ans,n,k;
int sum[N];
int dp[N][N];
inline void read(int &num);
inline void solve();
inline void solve2();
inline int getval(int l,int r);
signed main(){
    freopen("polygon.in","r",stdin);
    freopen("polygon.out","w",stdout);
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}
inline void read(int &num){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        f=(ch=='-')?-1:1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    num=x*f;
}
inline void solve(){
    read(n);
    bool flag=true;
    for(int i=1;i<=n;++i){
        read(a[i]);
        if(a[i]!=1)flag=false;
    }
    if(flag){
        n-=2;
        printf("%lld\n",(1+n)*n/2);
        return ;
    }
    sort(a+1,a+1+n);
    if(n<=3){
        if(a[1]+a[2]>a[3]){
            puts("1");
        }else{
            puts("0");
        }
        return ;
    }
    for(int i=1;i<=n;++i){
        sum[i]=sum[i-1]+a[i];
        dp[1][i]=(sum[i]>a[i]*2)?1:0;
    }
    for(int i=1;i<=n-2;++i){
        dp[i][i+2]+=(sum[i+2]-sum[i-1]>a[i+2]*2)?1:0;
    }
    for(int step=2;step<=n-2;++step){
        for(int l=1;l<=n-step;++l){
            int r=l+step;
            if(sum[r]-sum[l-1]>a[r]*2){
                dp[l][r]++;
            }
            for(int k=l;k<r;++k){
                dp[l][r]+=max(dp[l][k]+dp[k+1][r],dp[l][k-1]+dp[k][r]);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        ans=max(ans,dp[1][i]);
    }
    printf("%lld\n",ans%MOD);
}

::: ::::

::::info[S] :::success[T1]

#include<bits/stdc++.h>
#define N (int)(40)
using namespace std;
int w[(int)(1e5+5)][4],n,T;
int dp[N][N][N][N];
int f1[(int)(1e5+5)];
int f2[205][205][205];
inline void read(int &num);
inline void solve();
inline int dfs(int i,int j,int k);
signed main(){
    freopen("club.in","r",stdin);
    freopen("club.out","w",stdout);
    read(T);
    while(T--){
        solve();
    }
    return 0;
}
inline void read(int &num){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        f=(ch=='-')?-1:1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    num=x*f;
}
inline void solve(){
    bool flag1=true;
    bool flag2=true;
    read(n);
    int ans=0;
    memset(dp,0,sizeof(dp));
    memset(w,0,sizeof(w));
    memset(f1,0,sizeof(f1));
    memset(f2,0,sizeof(f2));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=3;++j){
            read(w[i][j]);
        }
        if(w[i][2]!=0){
            flag1=false;
        }
        if(w[i][3]!=0){
            flag2=false;
            flag1=false;
        }
    }
    if(flag1){
        for(int i=1;i<=n;++i){
            f1[i]=w[i][1];
        }
        sort(f1+1,f1+1+n);
        int ans=0;
        for(int i=n;i>=n/2+1;--i){
            ans+=f1[i];
        }
        printf("%d\n",ans);
        return ;
    }else if(flag2){
        for(int i=1;i<=n;++i){
            f2[i][0][1]=max(f2[i-1][0][1],w[i][2]);
            f2[i][1][0]=max(f2[i-1][1][0],w[i][1]);
        }
        for(int i=1;i<=n;++i){
            for(int a=0;a<=n;++a){
                if(a>n/2)break;
                for(int b=0;b<=n-a;++b){
                    if(b>n/2)break;
                    if(a>=1)f2[i][a][b]=max(f2[i][a][b],f2[i-1][a-1][b]+w[i][1]);
                    if(b>=1)f2[i][a][b]=max(f2[i][a][b],f2[i-1][a][b-1]+w[i][2]);
                }
            }
        }
        for(int x=1;x<=n;++x){
            for(int y=1;y<=n;++y){
                ans=max(ans,f2[n][x][y]);
            }
        }
        printf("%d\n",ans);
        return ;
    }
    for(int i=1;i<=n;++i){
        dp[i][0][0][1]=max(dp[i-1][0][0][1],w[i][3]);
        dp[i][0][1][0]=max(dp[i-1][0][1][0],w[i][2]);
        dp[i][1][0][0]=max(dp[i-1][0][0][1],w[i][1]);
    }
    for(int i=1;i<=n;++i){
        for(int a=0;a<=n;++a){
            if(a>n/2)break;
            for(int b=0;b<=n-a;++b){
                if(b>n/2)break;
                for(int c=0;c<=n-a-b;++c){
                    if(c>n/2)break;
                    if(a>=1)dp[i][a][b][c]=max(dp[i][a][b][c],dp[i-1][a-1][b][c]+w[i][1]);
                    if(b>=1)dp[i][a][b][c]=max(dp[i][a][b][c],dp[i-1][a][b-1][c]+w[i][2]);
                    if(c>=1)dp[i][a][b][c]=max(dp[i][a][b][c],dp[i-1][a][b][c-1]+w[i][3]);
                }
            }
        }
    }
    for(int x=0;x<=n;++x){
        for(int y=0;y<=n;++y){
            for(int z=0;z<=n;++z){
                ans=max(ans,dp[n][x][y][z]);
            }
        }
    }
    printf("%d\n",ans);
}

::: :::success[T2]

#include<bits/stdc++.h>
#define N (int)(1e4+5)
#define M (int)(1e6+5)
using namespace std;
typedef struct Edge{
    int to,next,w;
    int from;
}Edge;
Edge e[M<<1];
int ans[N];
int cnt;
int n,m,k;
int fa[N];
inline void unionn(int x,int y);
inline void addEdge(int u,int v,int w);
inline void read(int &num);
inline int find(int x);
inline void solve();
inline void Kus();
inline bool cmp(const Edge &A,const Edge &B);
signed main(){
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}
inline void read(int &num){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        f=(ch=='-')?-1:1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    num=x*f;
}
inline void solve(){
    read(n);
    read(m);
    read(k);
    for(int i=1;i<=n;++i)fa[i]=i;
    for(int i=1;i<=m;++i){
        int x,y,z;
        read(x);
        read(y);
        read(z);
        addEdge(x,y,z);
        addEdge(y,x,z);
    }
    Kus();
    sort(ans+1,ans+1+ans[0]);
    int cost=0;
    for(int i=1;i<=ans[0]-k;++i){
        cost+=ans[i];
    }
    printf("%d\n",cost);
}
inline void addEdge(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].from=u;
}
inline void unionn(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)fa[fx]=fy;
}
inline int find(int x){
    return (fa[x]==x)?x:fa[x]=find(fa[x]);
}
inline void Kus(){
    sort(e+1,e+1+cnt,cmp);
    for(int i=1;i<=cnt;++i){
        int u=e[i].from;
        int v=e[i].to;
        if(find(v)!=find(u)){
            unionn(u,v);
            ans[++ans[0]]=e[i].w;
            if(ans[0]==n-1){
                return ;
            }
        }else{
            continue;
        }
    }
}
inline bool cmp(const Edge &A,const Edge &B){
    return A.w<B.w;
}

::: :::success[T3]

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline void read(int &num);
inline void solve();
signed main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    freopen("replace.in","r",stdin);
    freopen("replace.out","w",stdout);
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}
inline void read(int &num){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        f=(ch=='-')?-1:1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    num=x*f;
}
inline void solve(){
    int n,m;
    read(n);
    read(m);
    for(int i=1;i<=m;++i){
        puts("0");
    }
}

::: :::success[T4]

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline void read(int &num);
inline void solve();
signed main(){
    freopen("employ.in","r",stdin);
    freopen("employ.out","w",stdout);
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}
inline void read(int &num){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        f=(ch=='-')?-1:1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    num=x*f;
}
inline void solve(){
    printf("0\n");
}

/*
#include<bits/stdc++.h>
#define N (int)(25)
using namespace std;
int w[N][4],n,T;
int dp[N][N][N][N];
inline void read(int &num);
inline void solve();
inline int dfs(int i,int j,int k);
signed main(){
    //::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    freopen("club3.in","r",stdin);
    freopen("club.out","w",stdout);
    read(T);
    while(T--){
        solve();
    }
    return 0;
}
inline void read(int &num){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        f=(ch=='-')?-1:1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    num=x*f;
}
inline void solve(){
    read(n);
    int ans=0;
    memset(dp,0,sizeof(dp));
    memset(w,0,sizeof(w));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=3;++j){
            read(w[i][j]);
        }
    }
    dp[0][0][1]=max(dp[i-1][0][0][1],w[i][3]);
    dp[0][1][0]=max(dp[i-1][0][1][0],w[i][2]);
    dp[1][0][0]=max(dp[i-1][0][0][1],w[i][1]);
    for(int i=1;i<=n;++i){
        for(int a=0;a<n;++a){
            if(a>=n/2)break;
            for(int b=0;b<n-a;++b){
                if(b>=n/2)break;
                for(int c=0;c<n-a-b;++c){
                    if(c>=n/2)break;
                    dp[i][a][b][c]=max(dp[i][a][b][c],dp[i-1][a-1][b][c]+w[i][1]);
                    dp[i][a][b][c]=max(dp[i][a][b][c],dp[i-1][a][b-1][c]+w[i][2]);
                    dp[i][a][b][c]=max(dp[i][a][b][c],dp[i-1][a][b][c-1]+w[i][3]);
                }
            }
        }
    }
    for(int x=0;x<=n;++x){
        for(int y=0;y<=n;++y){
            for(int z=0;z<=n;++z){
                ans=max(ans,dp[n][x][y][z]);
            }
        }
    }
    printf("%d\n",ans);
}

*/

::: ::::

太荒谬了这次，完全没发挥好，丢了非常多分，尤其是JT3、ST1、ST2放去年我是能写出来的，但是学的越多反而被带偏到别的错解上去了，666。

不管怎么说，马上中考了，也该退役了。考不上重高，估计高中也不会再打CSP了。 纪念我的OI生涯。

于马鞍山