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$
期中考完了，文化课可以先扔一边了。
接下来就要做几件事：
1. 熟悉一下NOI Linux系统（然而如果不出问题的话我还是选Windows）；
2. 打一遍所有模板（数据结构，图论，分治，动态规划），高精度和省选不考的除外；
3. 如果来得及就补一下前几次模拟赛的题（估计来不及）；
4. 休息半天，准备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$位格雷码。
1. $p=1$，则结果与$q$相等（$q=1$则结果为$1$，$q=0$则结果为$0$）；
2. $p>1,\ \ q< (1<<(p-1))$，则最高位为$0$，递归$solve(p-1,q)$；
3. $p>1,\ \ q\ge (1<<(p-1))$，则最高位为$1$，同时后面要逆过来，可以推得后面的位是$solve(p-1,(1<<p)-1-q)$。
于是做完了。
```cpp
#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$，然后询问就是求桶里一个位置的值了。
```cpp
#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读入。
```cpp
#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$个操作，寻找最早的满足要求的花费掉。
```cpp
#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$，每天都完全背包即可。
```cpp
#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$的边，然后从超源跑最短路即可。
好像很烦的样子...不过程序好写，就是两遍最短路。
```cpp
#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提前丢了很多分，输在了起跑线上）。