CSP-J&S-2019 游记

ix35 · 2019-10-18 21:06:32 · 个人记录

初中最后一年OI，不过文化课上倒没掉什么链子，应该说上学期期末和第一次月考成绩还是比较好的，底气足一点。

Day \ \ -35

意识到了初赛的重要性，今年两个组报初赛的人都多的不得了，发觉这个比复赛还要凶险，于是开始认真复习初赛知识点，刷完了十年内的题目。

然而我初赛还是很菜的，一星期里总是在担心。

Day \ \ -30

初赛当天。

上午是S组，考场在交附，环境挺不错的，但是由于某些众所周知的原因服务器卡了，一开始20分钟不能登陆，最后是延时了20分钟，现场还不算太混乱。

下午是J组，考场在华师大，半小时做完后无聊，在草稿纸上默岳阳楼记，默完一节发现草稿纸要交，就不默了，开始背自己的答案。

今年初赛的难度，实在是非常简单，考完之后J和S的答案都出来了，自批了一下，J是100分，S是94分，比几次模拟考都要高（平时S大概是88分上下）...这成绩放在浙江估计也过了。

要说对考卷的分析，主要是完善程序太简单。

J组的阅读题有一道是a,b数组互指，还有一道是普通分治，都是些大水题。J组的完形题第一道递归水题是复读机就会做，另一道是基数排序模板也特别无聊。

S组的阅读题一道是问s删掉最长多少的子串还有t作为子序列，另一道听说是DSU，但是我不知道，反正题做出来了，就是数路径的方法，都是水题。S组的完形题有一道图论题，本来以为放这个位置好歹要拓扑排序+Priority_queue一类的东西，结果程序居然是个暴力；另外一道就比较搞笑了，中午刷洛谷的时候听人说初赛考状压DP，我还在考虑我们做的是不是一张卷子，然后发现两套卷子仅顺序不同，那就滑稽了，状压+DP=状压DP？总的来说水题为主，难度较低。

总体来说，最大的收获是知道了cin不能输入空串。

初赛是没问题了，不过这一天挺忙的，晚上的ABC比赛耽误了40分钟才发现，最后只做了前五题。

Day \ \ -15

这段时间跟着教练一直在做历年真题，但是我太菜了，除了2014年能AK以外基本都有一道题不会做，2017和2018有两道不会做的。

感觉NOIP2018真的有点难，赛道修建比较考代码能力，然后填数游戏就是个神仙题，到现在我也不能独立证出结论。好在近两年没有什么sb搜索题和sb图论题。最讨厌的就是华容道和斗地主这种了。

希望今年多出数论和树论。

（树论毒奶中了）

Day \ \ -4

期中考完了，文化课可以先扔一边了。

接下来就要做几件事：

熟悉一下NOI Linux系统（然而如果不出问题的话我还是选Windows）；
打一遍所有模板（数据结构，图论，分治，动态规划），高精度和省选不考的除外；
如果来得及就补一下前几次模拟赛的题（估计来不及）；
休息半天，准备AK普及，提高450+。

Linux下的编辑感觉真没有Windows方便，找不到怎么补全括号最烦了。另外某谷上几次比赛都太毒瘤了（省选模拟赛），之前几年的题（大搜索除外）和一套本省同年级神仙gyr的题做了一下。

Day \ \ -2

两天之内打了很多的板子（ST表，树状数组，线段树，左偏树。主席树，Kruskal重构树，SPFA负环，单调队列，单调栈，三分法，lucas定理，杜教筛，KMP，Manacher），有不少来不及打了只能看一遍（三种Tarjan是最虚的所以看了两遍，扩展BSGS，各种Trie）。

正常的题就来不及写了，就写了一些以前做过的数据结构综合题（Peaks之类的）。

Day \ \ 0

考前最后一天，休息，看一下考试的一些细节要求，颓洛谷和B站。

Day \ \ 1

Day1进考场先打了个Tarjan板子，还没打完就公布密码了。

拿到题先根据别人的经验仔细阅读了第一页，WTF题面里就有两道是树？

先看T1，感觉是个大水题，没急着写，先去看了看后面两题。喜闻乐见的是T2长得像个数据结构，应该是套路题，T3是个非套路题，不过我当时想着应该有足够时间做出来吧。

先去写了下T1，刚开始觉得是个和异或有关的东西，但是没有一眼推出结论，只好老老实实写递归，没注意到longlong就看T2了。

T2一开始花了几分钟写出来一个暴力，结果没过样例，发现idea错了。然后恍惚了一会，顺眼看到第一题的(1<<64)，于是顺手开了个ull。

发现以前自己出题的时候出过类似T2的idea，所以立刻想了个差不多的算法，只是实现起来繁琐一点，花了一点时间写了个倍增+询问离线+计数数组。最后所有样例都过了，两题基本上稳了，时间过去了1个小时不到一点，开始看T3。

T3看到范围是2000开心了一会。贪心倒是很容易想：从小到大每个数字尽量到小的点上去，检验是否可以就行了。但是连个O(n^3)也口胡不出来，看了一下有n\leq 10的10分，先写掉了，然后再想正解，又想不出来就写了一个菊花图的部分分。然后时间就差不多了，Day1就这样在恍惚间过去了。

（结果后来发现菊花图写错了）

以下是我的CSP-S 2019 Day1题解（T3不会做）：

T1: Code

我的解法：

设solve(p,q)表示求第q个p位格雷码。

于是做完了。

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=75;
ull n,k;
int ans[MAXN];
void solve (ull p,ull q) {
    if (p==1) {ans[p]=q;return;}
    if (q<(1ull<<(p-1))) {
        ans[p]=0;
        solve(p-1,q);
    } else {
        ans[p]=1;
        solve(p-1,(1ull<<(p-1))+((1ull<<(p-1))-1)-q);
    }
    return;
}
int main () {
    freopen("code.in","r",stdin);
    freopen("code.out","w",stdout);
    cin >> n >> k;
    solve(n,k);
    for (int i=n;i>=1;i--) {cout << ans[i];}
    cout << endl;
    return 0;
}

T2: Brackets

我的解法：

记dep[i]表示i到根的路径中左括号的个数减右括号的个数，pre[i]表示i的祖先中第一个dep值比i小的。query(i,v)表示查询i到根节点中有多少个点dep值为v。

然后i这个点的答案设为dp[i]，那么：

dp[i]=dp[fa_i]+query(i,dep[i])-query(pre[i],dep[i])

表示首先考虑右端点不是i的，然后考虑右端点是i的，那么dep[i]必然是路径上最小的dep（否则不满足前缀的要求），所以要差分掉pre[i]上面的答案。

计算query可以离线，所有询问按照dfn排序，用一个桶记录当前dfs到的点到根的路径上所有点的dep，然后询问就是求桶里一个位置的值了。

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=500010;
struct Q {
    Q () {ps=v=fr=flg=0;}
    Q (int a,int b,int c,int d) {ps=a,v=b,fr=c,flg=d;}
    int ps,v,fr,flg;
}q[2*MAXN];
int n,x,eg,tot,cnt,cur,v[MAXN],dep[MAXN],bac[2*MAXN],hd[MAXN],ver[2*MAXN],nx[2*MAXN];
int f[MAXN][22],mn[MAXN][22],dfn[MAXN],pre[MAXN];
ll dp[MAXN],ans;
char c[MAXN];
bool cmp (Q a,Q b) {return dfn[a.ps]<dfn[b.ps];}
void add_edge (int x,int y) {
    ver[++eg]=y;
    nx[eg]=hd[x];
    hd[x]=eg;
    return;
}
void dfs1 (int x,int fa) {
    dep[x]=dep[fa]+v[x],dfn[x]=++cnt,f[x][0]=fa,mn[x][0]=dep[fa];
    for (int i=1;i<=20;i++) {
        f[x][i]=f[f[x][i-1]][i-1];
        mn[x][i]=min(mn[x][i-1],mn[f[x][i-1]][i-1]);
    }
    int pos=x;
    for (int i=20;i>=0;i--) {
        if (mn[pos][i]>=dep[x]) {pos=f[pos][i];}
    }
    pre[x]=f[pos][0];
    q[++tot]=Q(x,dep[x],x,1);
    q[++tot]=Q(pre[x],dep[x],x,-1);
    for (int i=hd[x];i;i=nx[i]) {
        if (ver[i]==fa) {continue;}
        dfs1(ver[i],x);
    }
    return;
}
void dfs2 (int x,int fa) {
    while (cur<=tot&&q[cur].ps==x) {
        dp[q[cur].fr]+=1ll*q[cur].flg*bac[q[cur].v];
        cur++;
    }
    bac[dep[x]]++;
    for (int i=hd[x];i;i=nx[i]) {
        if (ver[i]==fa) {continue;}
        dfs2(ver[i],x);
    }
    bac[dep[x]]--;
    return;
}
void dfs3 (int x,int fa) {
    dp[x]+=dp[fa];
    for (int i=hd[x];i;i=nx[i]) {
        if (ver[i]==fa) {continue;}
        dfs3(ver[i],x);
    }
    return;
}
int main () {
    freopen("brackets.in","r",stdin);
    freopen("brackets.out","w",stdout);
    scanf("%d",&n);
    scanf("%s",c+1);
    bac[MAXN-10]=1,dep[0]=MAXN-10;
    for (int i=1;i<=n;i++) {v[i]=(c[i]=='('?1:-1);}
    for (int i=2;i<=n;i++) {
        scanf("%d",&x);
        add_edge(i,x),add_edge(x,i);
    }
    dfs1(1,0);
    sort(q+1,q+tot+1,cmp);
    cur=1;
    while (cur<=tot&&q[cur].ps==0) {cur++;}
    dfs2(1,0);
    dfs3(1,0);
    for (int i=1;i<=n;i++) {ans^=(1ll*i*dp[i]);}
    printf("%lld\n",ans);
    return 0;
}

S-Day1期望得分：100+100+35=235

下午考PJ，得到密码前先打了个dij板子，后来手残删掉了（如果不删还可以省点时间）。

看了T1直接花了一分半钟切掉了，然后看T2，结果一点思路都没有：PJ的T2也能这么难吗？然后又看了T3和T4，发现T3好像很可做，但还是先看了T2。

盯着T2看了两分钟突然意识到可以枚举所有券，于是感觉自己花了几分钟才看出来一个sb题，自己也很sb啊。

然后T3几乎就立刻想出来了，每天独立做完全背包，贪心一下发现肯定是对的。

做完T3只过了大概20分钟，还有三个小时想T4，看了两分钟以后意识到了奇偶性的问题，其实就是要求长度分别为奇数和偶数的最短路了，接下来就很精彩了。

现场脑子抽掉了，没想到分层图/直接BFS等简单方法，联想到了“图论”和“奇偶性”这两个东西以后在大脑里就搜索到了一道叫做校园旅行的题（HNOI2019，黑题），依稀记得那道题是根据奇环缩边，于是这道题也狂想奇环这方面的事。

神奇的是我真想出来了，推了大概10分钟的结论发现：虽然奇环很多，但是只要建最短路树后只要枚举一条非树边的奇环即可，然后奇环数量就少了。

然后接着想怎么推一个点经过非树边到1的最短路，第一反应是在最短路树上DP，于是写了一下，发现大样例里有一行是错的，于是自己Hack了一下发现确实是错的——经过奇环的时候不一定走树边，所以实际上求完奇环后只要求所有端点的单源最短路，这样的话连到超级源点再跑带权的dij就可以了（考试前试机打的板子删了只好重写），然后就过了大样例。

最后1h太无聊了。

以下是我的CSP-J 2019题解：

T1: Number

我的解法：

~~利用stl-bitset的count功能~~

水题，可以用scanf+%s读入。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=12;
int n,ans;
char c[MAXN];
int main () {
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    scanf("%s",c+1);
    int n=strlen(c+1);
    for (int i=1;i<=n;i++) {
        if (c[i]=='1') {ans++;}
    }
    printf("%d\n",ans);
    return 0;
}

T2: Transfer

我的解法：

~~利用树套树减小常数，增大时间复杂度~~

对于每一个1，暴力枚举前面45个操作，寻找最早的满足要求的花费掉。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int n,f[MAXN],v[MAXN],t[MAXN],vis[MAXN],ans;
int main () {
    freopen("transfer.in","r",stdin);
    freopen("transfer.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%d%d%d",&f[i],&v[i],&t[i]);
        if (f[i]==0) {ans+=v[i];}
        else {
            int flag=0;
            for (int j=max(1,i-46);j<=i-1;j++) {
                if (f[j]==0&&!vis[j]&&v[j]>=v[i]&&t[i]-t[j]<=45) {
                    vis[j]=1;
                    flag=1;
                    break;
                }
            }
            if (!flag) {ans+=v[i];}
        }
    }
    printf("%d\n",ans);
    return 0;
}

T3: Souvenir

我的解法：

考虑第一天买第三天卖相当于是第二天先卖了，然后同一天又买进来，第三题再卖出去。也就是说，存在一种最优策略，今天买的东西一定明天卖。

所以每一天就独立了，对于第i天的第j件商品，可以花费p_{ij}的价格赚到p_{(i+1)j}-p_{ij}的差价，每个商品都可以买无限个，再加上金币数量始终不超过10^4，每天都完全背包即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=10010,MAXM=110;
int t,n,m,dp[MAXN],pri[MAXM][MAXM],wl[MAXM],vl[MAXM];
int main () {
    freopen("souvenir.in","r",stdin);
    freopen("souvenir.out","w",stdout);
    scanf("%d%d%d",&t,&n,&m);
    for (int i=1;i<=t;i++) {
        for (int j=1;j<=n;j++) {
            scanf("%d",&pri[i][j]);
        }
        if (i>=2) {
            memset(dp,0,sizeof(dp));
            for (int j=1;j<=n;j++) {
                wl[j]=pri[i-1][j],vl[j]=pri[i][j]-pri[i-1][j];
                for (int k=wl[j];k<=m;k++) {
                    dp[k]=max(dp[k],dp[k-wl[j]]+vl[j]);
                }
            }
            int tmp=0;
            for (int j=1;j<=m;j++) {tmp=max(tmp,dp[j]+m);}
            m=tmp;
        }
    }
    printf("%d\n",m);
    return 0;
}

T4: Work

我的解法：

好像跟网上其他人的解法很不一样呢...

题目其实是要求，有没有一种从1到u的路径，恰好经过L条边。

考虑到每条边可以重复经过，所以如果存在a条边的路径，那么a+2k\ \ (k\in N)的路径也存在。于是首先可以确定，如果1到i的最短路记为dis[i]，则如果dis[u]\ge L且dis[u]\equiv L\mod 2，那么答案是肯定的。

接下来考虑dis[u]\ne L\mod 2的情况，也就是到1的路径中改变了一次奇偶性的情况。也就是路径中的某一段有两种奇偶性不同的通过方法，那么将两条路径拼起来就得到了一个奇环，所以如果这种情况可行，必然经过了最短路以外的一个奇环。

然而奇环本身不容易统计，所以考虑换一个角度。先可以建出1为根的最短路树，那么树上当然没有环，奇环只能在非树边中产生，而且我们有如下结论：

必然可以只通过只有一条非树边的奇环，且只需要通过这样的一条奇环达到改变奇偶性的最短路。

结论容易用反证法证明（考场上看出来了也就懒得证），如果只有一个奇环是经过两个非树边的，那么这两个非树边分别与其他树边构成的环中必然有一个奇环。

于是，只要枚举经过哪个奇环即可，而通过奇环其实就是通过奇环中的那个非树边（不一定要绕圈），所以我们可以从任一个点出发必经过一条指定边的最短路。

如果奇环中非树边为(u,v)，那么u通过这条边的最短路显然是dis[v]+1，于是其他点如果要从u到达这条边，最短路也就是dis(x,u)+dis[v]+1了，有很多这样的u，不能分别跑最短路，所以建一个超级源点，把所有非树边的端点向超源连权值为上面那个dis[v]+1的边，然后从超源跑最短路即可。

好像很烦的样子...不过程序好写，就是两遍最短路。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=200010;
int n,m,qu,eg,eg2,x,y,hd2[MAXN],ver2[2*MAXN],nx2[2*MAXN],dis[MAXN],vis[MAXN];
int hd[MAXN],ver[4*MAXN],nx[4*MAXN],edge[4*MAXN],dis2[MAXN],vis2[MAXN];
priority_queue < pair<int,int> > q;
priority_queue < pair<int,int> > q2;
void add_edge (int x,int y,int z) {
    ver[++eg]=y;
    nx[eg]=hd[x],edge[eg]=z;
    hd[x]=eg;
    return;
}
void add_edge2 (int x,int y) {
    ver2[++eg2]=y;
    nx2[eg2]=hd2[x];
    hd2[x]=eg2;
    return;
}
int main () {
    freopen("work.in","r",stdin);
    freopen("work.out","w",stdout);
    memset(dis,0x3f,sizeof(dis));
    memset(dis2,0x3f,sizeof(dis2));
    scanf("%d%d%d",&n,&m,&qu);
    for (int i=1;i<=m;i++) {
        scanf("%d%d",&x,&y);
        add_edge2(x,y),add_edge2(y,x); 
    }
    q.push(make_pair(0,1));
    dis[1]=0;
    while (!q.empty()) {
        pair <int,int> a=q.top();
        q.pop();
        if (vis[a.second]) {continue;}
        vis[a.second]=1;
        for (int i=hd2[a.second];i;i=nx2[i]) {
            if (dis[ver2[i]]>dis[a.second]+1) {
                dis[ver2[i]]=dis[a.second]+1;
                q.push(make_pair(-dis[ver2[i]],ver2[i]));
            }
        }
    }
    for (int i=1;i<=n;i++) {
        for (int j=hd2[i];j;j=nx2[j]) {
            add_edge(i,ver2[j],1);
            if ((dis[i]&1)==(dis[ver2[j]]&1)) {
                add_edge(i,n+1,dis[ver2[j]]+1);
                add_edge(n+1,i,dis[ver2[j]]+1);
            }
        }
    }
    q2.push(make_pair(0,n+1));
    dis2[n+1]=0;
    while (!q2.empty()) {
        pair <int,int> a=q2.top();
        q2.pop();
        if (vis2[a.second]) {continue;}
        vis2[a.second]=1;
        for (int i=hd[a.second];i;i=nx[i]) {
            if (dis2[ver[i]]>dis2[a.second]+edge[i]) {
                dis2[ver[i]]=dis2[a.second]+edge[i];
                q2.push(make_pair(-dis2[ver[i]],ver[i]));
            }
        }
    }
    for (int i=1;i<=qu;i++) {
        scanf("%d%d",&x,&y);
        if (dis[x]%2==y%2) {
            if (dis[x]<=y) {printf("Yes\n");}
            else {printf("No\n");}
        } else {
            if (dis2[x]<=y) {printf("Yes\n");}
            else {printf("No\n");}
        }
    }
    return 0;
}

J期望得分：100+100+100+100=400

Day \ \ 2

解压以后先看T1：呀今年T1怎么不是水题，还是Yazid的题，那肯定做不出来的呀。

然后看T2：早上刚看的1D/1D的动态规划怎么套不上去？

再看T3：哈哈哈哈哈哈哈哈哈哈哈。

然后花了一个半小时做了T3，回去水了前两道题的部分分。由于T1有Yazid，也就没想正解。

~~不要想着D2翻盘，因为你根本不知道盘是什么。~~

只做出来T3，但好像写错了，就不写题解了。

S-Day2期望得分：64+64+100=228。

选手程序跟几个网站数据出来了。

洛谷：

J 400

S 423

OI题库：

J 400

S 363

牛客：

J 400

S 378

遗憾：一心以为T6满分结果连几个部分分也懒得去打（保险没了），T4是个大水题没做满分。

今年就这么结束了...三个网站前五题总分一模一样（338），第六题就很秀了，各个地方得分都不一样，最坏打算就是只拿十几分了...

S真实成绩：100+100+10+64+64+25=363

J真实成绩：100+100+100+100=400

初中OI生涯大概就这样了吧，两个月后也许能混个WC，省队希望不大了（CSP提前丢了很多分，输在了起跑线上）。