CSP 2020 游记
WanderingTrader
2020-10-11 23:13:25
~~我来帮你们拉低分数线啦！~~
## 写在前面
本文记叙了我在2020年的CSP-J/S中的~~精彩~~表现。
[对文中使用到的缩写/专业词汇的注释](/paste/3p1qqhpt)
本文中令 Day 1=2020/10/11，即2020 CSP-J/S初赛日。
## 正文
### Day -2 (2020-10-08)
洛谷膜你赛：12分。
本来以为自己凉了。
查看提交记录惊奇的发现：原来是因为字符串里多打了一个`\`导致从该位置开始后面几乎全错。
重新编辑了一下再提交，70分。
看到难度是“介于J和S之间”，心里稍微有了点底，毕竟真正的考试是笔试而不是上机。J组初赛应该没啥问题了，S组初赛希望能多一点rp分。这一年果然没白学。
### Day 0 (2020-10-10)
又做了几套模拟题。写完了[OI in 2020](/blog/Steven371/dui-yi-nian-oi-sheng-ya-di-hui-gu-zong-jie)
### Day 1 (2020-10-11)
考点：上海市民办上宝中学
S组一上来，我感觉不大对劲。怎么这么多人？我们学校考点的都是同校生，怎么S组有二十几个？什么情况？不管了，和几个老朋友打个照面，就开始看紫书（话说初赛前看紫书有个啥用）。
拿到试卷以后浏览了一下前面15道选择，还是那么简单（smg），至少没有高中难度的数学题（比如2018年那个线段期望长度）
现对一些较复杂的题目写一下解析（对题目的问法做了一些改动，将选择题改成了解答题）：
---
3.现有一段 $8$ 分钟的视频文件，它的播放速度是每秒 $24$ 帧图像，每帧图像是一幅分辨率为 $2048\times1024$ 像素的 $32$ 位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？
解：
$8min=480s.$
$480\times24=11520$ 帧图像
每帧图像占 $2048\times1024\times32$ 位内存，即 $2^{11}\times2^{10}\times2^5=2^{26}\text{bit}=2^{23}\text B=2^{13}\text{KB}=2^3\text{MB}=2^{-7}\text{GB}$
$2^{-7}\text{GB}\times11520=90\text{GB}$，选B.
---
8.二分图是指能将定点划分成两个部分，每部分的定点建没有边相连的简单无向图。那么，$24$ 个顶点的二分图 **至多** 有多少条边？
解：
设两个集合分别放 $x,24-x$ 个顶点
那么最优情况是两集合各任取一结点，都连边，共 $x(24-x)=24x-x^2$ 条边。
所以所求即为 $\max\{-x^2+24x|x\in[1,24]\}$，用配方法可知 $x=12$ 时有最优解 $144$，选A.
---
10.一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数 $n(n<60)$ 为多少？
解：
由于选项中的 $n$ 均处在 $(20,60)$ 之间，可以枚举这个区间内模7余4的数字，看看是否满足剩下两个条件：
$25,32,39,46,53.$
经计算，$53$ 符合条件，选C.
---
15道选择题很快搞定了，接下来是阅读程序——我最怕的题型。第一大题貌似还行，就是自己模拟一下就好了。结果我第一小题不知怎么了忘记了n=1000的情况，选了T.其他的都没啥难度，10分钟差不多搞定了。
第二题貌似比较复杂，不过静观程序12~18行，神似以前见过的一个东西——手写快速排序。再结合~~上下文~~前后的程序，容易看出此题解决的是[k小数问题](/problem/P1923)。然而做题的时候却翻车了。我对快速排序的效率一直不熟（毕竟有`sort`了就没太关注），只知道 $O(n)$ 最快，$O(n\log n)$ 平均和 $O(n^2)$ 最慢，对于特殊情况（比如题目中出现的单调递增和单调递减）并不了解，更别提它的变种k小数问题了。4道选择题全错，由于CCF自己出锅了，所以最终错3道题，7.5分白白溜走了。
第三题一看到 $99$ 行的代码，顿时一种~~喜感~~恐慌油然而生。不过当我看到那个class里面写的其实就是STL的map和queue时，我逐渐镇定下来了。稍微浏览了一下代码，脑子里灵光一闪：中途相遇法优化的广度优先搜索（其实就是双向BFS了）。那么后面的题目都好做了，但是最后一道选择题我也不太会，最终蒙错了，4分走掉。
完善程序也还行，但第一大题的第一小题不知道为什么选D，按性价比排序应该是A啊？总之3分走掉。
第二大题完全不会，直接猜蒙凑吧，5道题蒙错了4个……12分走掉。
最终我的S组预计是67分。希望可以进复赛。
下午的J组简直就是炸鱼塘。我们学校有57个人参加，让我大吃了一惊。我们学校什么时候有这么多OIer了？打听了一下发现，他们多半是C++学到一半来参赛练手的。好吧，反正多几个菜鸡是好事情（smg）。
J组我也懒得写题解了，毕竟确实不难。除了阅读程序第三道那个dfs，我456三题直接放弃乱填一通并完美避开正确答案，其他的都没啥难度。最终我预计是87分，过初赛是稳了，感觉心情还不错。唯一遗憾的是洛谷上的同学没有和我一个考场的，不能像北京的谷民一样见面了。
晚上赶作业赶到23:30，没开电脑就睡了。
### Day 2 (2020-10-12)
晚上被爸妈拖到22:30才开电脑。
准备到复赛前专门做UVA的模拟（对应紫书4,5章的例题和习题）。
### Day 3 (2020-10-13)
今天语文老师发慈悲了，没布置语文作业，所以我7:50写完了作业，8:20就开机了。
做了3道UVA的模拟，分别是紫书例题[4-1](/problem/UVA1339)，[4-3](/problem/UVA133)，[4-4](/problem/UVA213)
前两道题还行，~~在题解的帮助下~~很快AC了。最后一题看似简单，要自己写还是很费劲的，我调了1h的错误，最后实在懒得复制粘贴样例了直接敲了个文件IO，一直到22:55才提交，结果[CE](record/39767594)？？原来是`gets`出锅了，只好明天来手打。
### Day 4 (2020-10-14)
昨天sb了，手写gets不知道写的smwy，今天稍微改了改就AC了。
下一道题是[UVA512](/problem/UVA512)，看起来貌似挺复杂的。不过今天没时间了。
### Day 6 (2020-10-16)
UVA512还行，就是很多坑点（尤其是翻译没有把输出格式讲清楚，差评），不过WA了两次（貌似都是因为格式）以后还是AC了。顺便写了一个简单的[题解](/blog/Steven371/solution-uva512)
明天有空来做[UVA12412](/problem/UVA12412)，大概扫了一眼是一道大模拟，和[时间复杂度](/problem/P3952)挺像的，但好像侧重点不一样（时间复杂度侧重于字符串，这道题应该侧重数据处理），希望能再增强写模拟题的能力（当然也希望这道题不要调的太痛苦）。
### Day 8 (2020-10-18)
这UVA12412真tm毒瘤，还没写完
### Day 9 (2020-10-19)
呼~写完了，然而交上去又是[CE](/record/40131176)，rank也重名了？涨芝士了。
改好以后获得了WA的好成绩。经过了时间复杂度的洗礼，我的模拟又㕛叒叕写挂了。
明天要出分数了，有亿点紧张。
### Day 10 (2020-10-20)
我自己的分数没有锅，pj多估了1.5->85.5，tg估的完全正确->67，反正都是碾压分数线15+，没啥大不了的。上海真是一个超级弱省。身在这样一个弱省我不知是该哭还是该笑。
下面对本校和我关系比较不错的同学的得分做一下整理（分数从高到低）：
|姓名缩写+人物背景简单描述|J组得分|S组得分|个人评价
|:-:|:-:|:-:|:-:
|srt，我|85.5|67|发挥正常
|pjt，一个据他自己说刚学二分和dfs的人|67|66|后生可畏，S组的rp分针不戳，不过基础看起来很扎实，有望J组2=
|zmh，一个蒟蒻（虽然这么说自己同学不太好）|63|未参加|骗分能力绝对很强，希望他复赛rp++
|zjh，一个号称是巨佬的人|61|57|初赛大概发挥失常了，压线过J组可还行
|入档线|61|47.5|分数这么低把一个S组49分的菜鸡都放过了
那么就好好准备复赛和noip（今年noip和csp分开了）吧。同时我还得负责帮助pjt和zmh准备复赛，祝他俩也rp++。
今年我希望能1=，一雪去年0分的耻辱。
### Day 11 (2020-10-21)
UVA12412 提交n遍还是WA，决定放弃。
复赛前还是好好复习dp吧，毕竟J组T2的模拟应该不至于像这题这么毒瘤，T4完全靠rp，那么最重要的分水岭就是T3的dp了，要好好准备
明天先拿[P3957](/problem/P3957)开刀，加油。
### Day 13 (2020-10-23)
AC P3957 祭之
之前一直不会，居然是因为题目有一个小细节理解错了：往右跳的时候只能跳到格子上，中间的位置都是~~万丈深渊~~不能逗留的，所以只用空间复杂度 $O(n)$ 的dp，再用单调队列优化时间就行了。和我之前做的一道题[P1725](/problem/P1725)本质上没有什么不同，就是用单调队列的时候需要加一点小小的处理而已。
继续肝UVA题。
### Day 14~Day 15 (2020-10-24~2020-10-25)
把之前WA掉的一道UVA单调栈板子[题](/problem/UVA1619)切了。
总结了一下发现错误居然是：
1. 翻译没有给输入输出格式，导致漏了多组数据之间的换行.
2. 有两个连续的if，由于处理的变量是相同的，所以第二个if应为else if.
## 坑 UVA真坑
刚刚做完跳房子，复习了一下单调队列和单调栈，做了一些题目，也做了一些杂题。马上要期中考试了，心态爆炸。
### Day 16~Day 26 (2020-10-26~2020-11-05)
忙复习期中考试，几乎没搞OI.
### Day 27 (2020-11-06)
CSP 2020 前最后一天了，打了一些模板，重做了去年的T3T4，感觉特慌。
复习模板（是指比较难的，像快排/堆这种的就不算）的时候发现，本来会写的代码总是漏点东西（连dijkstra都能写挂），一遍AC的只有Kruskal模板和欧拉筛，毕竟印象很深刻，写过很多次了。
希望明天比赛能正常发挥吧。
这里先估个分：J组 250，S组 100.
不过考前还是要再念几遍
# 一定要写文件！一定要写文件！别忘了去年是怎么爆零的！
祝我&所有学OI的朋友们 rp++.
### Day 28 (2020-11-07)
两个组都比想象的难一点。
考点：上海市七宝中学（居然和cz是一个考点，我都没发现）
J组：
来考场先敲了个dijkstra模板（然而并没有用上），算是热热身吧。
解压密码是四个拼音，中间插入一些奇怪的字符。
把四个拼音连起来是：他山之石
看到T1的标题捏了把汗，好像是某年NOI的题目。难道CSP-J已经可以和NOI匹敌了？（滑稽）还好题目内容只是要求二进制拆分，一个 $O(1)$ 搞定。
```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
freopen("power.in","r",stdin);
freopen("power.out","w",stdout);
int n;
scanf("%d",&n);
if(n&1) printf("-1");
else for(int i=30;i;--i) if(n&(1<<i)) printf("%d ",1<<i);
printf("\n");
return 0;
}
```
代码很好懂，不解释了。
看到T2以后，遵循~~教员的指导~~教练的指点先简化题意，对每一个 $i(1\le i\le n)$ ，求出当前第 $k_i$ 大的值。其中 $k_i=\max\{1,\left\lfloor i\times w\% \right\rfloor\}$。
首先暴力肯定是可以的。用一个优先队列，每次弹出对应的数目即可。
考场上愣是忘记了两个优先队列的写法。但是想到了 multiset.
$\because1\le w\le99$
$\therefore 0<w\%<1$
$\therefore i$ 每增加 $1$， $\left\lfloor i\times w\% \right\rfloor$ 增加 $0$ 或 $1$
$\therefore$ 用两个multiset S和T，每次根据 $\left\lfloor i\times w\% \right\rfloor$ 增长情况进行容器调配即可。
代码即为：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int num[maxn];
multiset <int> S,T;
multiset <int> ::iterator it;
int main()
{
freopen("live.in","r",stdin);
freopen("live.out","w",stdout);
int n,w,a;
scanf("%d%d",&n,&w);
for(int i=1;i<=n;++i) num[i]=max(1,i*w/100);
for(int i=1;i<=n;++i)
{
scanf("%d",&a);
if(a>*T.rbegin()) S.insert(a);
else T.insert(a);
if(S.size()>num[i])
{
T.insert(*S.begin());
S.erase(S.begin());
}
else if(S.size()<num[i])
{
S.insert(*T.rbegin());
it=T.end();
T.erase(--it);
}
printf("%d ",*S.begin());
}
printf("\n");
return 0;
}
```
实测RE了，这才想起来，一开始T集合是空的，执行rbegin会RE，所以一开始插入一个 $-\inf$ 即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int inf=1e7;
int num[maxn];
multiset <int> S,T;
multiset <int> ::iterator it;
int main()
{
freopen("live.in","r",stdin);
freopen("live.out","w",stdout);
int n,w,a;
scanf("%d%d",&n,&w);
for(int i=1;i<=n;++i) num[i]=max(1,i*w/100);
T.insert(-inf);
for(int i=1;i<=n;++i)
{
scanf("%d",&a);
if(a>*T.rbegin()) S.insert(a);
else T.insert(a);
if(S.size()>num[i])
{
T.insert(*S.begin());
S.erase(S.begin());
}
else if(S.size()<num[i])
{
S.insert(*T.rbegin());
it=T.end();
T.erase(--it);
}
printf("%d ",*S.begin());
}
printf("\n");
return 0;
}
```
考完试发现其实一个桶排就搞定了。我\*\*。不过幸好还是AC了。
现在才9：15，时间还很充裕。T3乍一看不会，就先跳过看T4了。
T4乍一看一个dp，然后10min转移方程+10min编码+10min想出优化+10min编码+5min测样例，三刻钟差不多搞定了。具体看[【赛后题解】](/blog/Steven371/solution-p7074)
T3 实在不会，就打了个暴力。30分呢，说不定就是2=和1=的差距。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int maxlen=1e6+5;
char expr[maxlen];
int n,q,x,len;
int stpcnt=-1,stpos[maxlen],stp[maxn];
bool a[maxn];
vector <stack <bool> > ss;
void get(char* s)
{
char* tmp=s;
char c=getchar();
while(c!='\n'&&c!='\r') {if(c!=' ')*(tmp++)=c;c=getchar();}
}
int getint(char* s,int& pos)
{
int x=0;
while(isdigit(s[pos])) {x=x*10+s[pos]-'0';++pos;};--pos;
return x;
}
void solve()
{
stack <bool> s;
for(int i=0;i<len;++i)
if(expr[i]=='x')
{
int tmp=i,x=getint(expr,++i);
if(!stp[x]){stp[x]=++stpcnt;ss.push_back(s);stpos[stpcnt]=tmp;}
s.push(a[x]);
}
else
{
int u=s.top(),v;s.pop();
if(expr[i]=='!') s.push(!u);
else if(expr[i]=='&')
{
v=s.top();s.pop();
s.push(u&&v);
}
else
{
v=s.top();s.pop();
s.push(u||v);
}
}
}
void getans()
{
stack <bool> s=ss[stp[x]];
for(int i=stpos[stp[x]];i<len;++i)
if(expr[i]=='x')
s.push(a[getint(expr,++i)]);
else
{
int u=s.top(),v;s.pop();
if(expr[i]=='!') s.push(!u);
else if(expr[i]=='&')
{
v=s.top();s.pop();
s.push(u&&v);
}
else
{
v=s.top();s.pop();
s.push(u||v);
}
}
printf("%d\n",s.top());
}
int main()
{
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
get(expr);
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",a+i);
scanf("%d",&q);
len=strlen(expr);
solve();
while(q--)
{
scanf("%d",&x);
a[x]=!a[x];
getans();
a[x]=!a[x];
}
return 0;
}
```
这里加了一点小优化：对每一个变量，算出它第一次出现的位置，这样之前的结果直接拿上来用，不用重算了。希望可以多骗10分。
预计分数：$100+100+30+100=330.$ 希望1=.
---
S组：
来考场又敲了一遍dijkstra模板，依然没用上（我太南了）。
上午考完J组以后已经虚了（smg），精神不是很好。
解压密码又是四个拼音和一些奇怪的字符。拼音连起来是：可以攻玉。
上下午密码连在一起，他山之石可以攻玉，想暗示什么呢？
看到题目我就蒙圈了：咋都不会啊。看着T1还有点思路就先下手了。不想一下手就是3.5h。
写了一个又臭又长的代码（但是没有破一百行）。总算是三个样例都答案正确了。但样例三用了3.5s的时间，肯定是TLE了。大概70~80分的样子。另外三道题几乎没思路，也就输出样例结束了。
预计分数：$70+0+0+0=70.$ 希望混个2=.
### Day 29 (2020-11-08)
把考场代码下载下来到洛谷上实测了一下。
J组完全没问题，330.
S组T1居然直接AC了？不可思议。
希望rp分多一点。
静待出成绩。
### Day 36 (2020-11-15)
AC了S组T2.现在后悔死了。
就算比赛的时候有了一点疏漏，没考虑到 $k=64$，那也有90分呢。加上T1的70分，160在SH可以1=了。
如果比赛的时候我没有死磕在T1上，现在应该是在家里坐等蓝钩了。可以说是一个教训吧。
### Day 41 (2020-11-20)
分数陆陆续续都出来了，现在汇总如下：
|人名|J2分数|J2奖项|S2分数|S2奖项|优点|不足|明年的期望
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:
|srt（我）|330|1=|80|2=|基础较好，J发挥正常|S考场上失策了一直在做T1，不过由于基础不错，T1没有挂分|J满分S一等
|pjt|60|3=|20|没奖|S组策略正确|J的T2写挂了，因此分数很低。由于基础不牢，因此S只拿到了T4的20分|双1=
|zmh|120|2=|未参加|/|该得的分 都得到了|实力不足|双1=
|zjh|145|2=|50|3=|分数比上两位 好看一点点|J的T2用的暴力排序，T3不会表达式解析，T4没写出来，因而差了很多分，S可能是因为暴力写挂了|双1=
至于为什么我的基础相对较好，个人觉得是因为疫情期间在洛谷刷了很多题，积累了不少经验，所以编码能力较强，简单的题目发挥稳定，难题的暴力基本都能写出来。唯一欠缺的就是一些考场技巧，不能拘泥于一道题不放，以后要注意了。
今年的CSP圆满结束了，我辜负了奇迹，但总算没有辜负自己。一年的努力没有白费 ~~，可以睡个好觉了~~。听说NOIP会很难，所以就去打个酱油就好了。
最近又听了几遍《膜你抄》以及许多融入OI元素的经典歌曲，忽然有些难过。学校里的那些同学，就算关系再好，终究无法理解信奥生的苦与乐。往后的路，还是要一个人走。这也是为什么我把自己的用户名改成了`wandering_trader`（流浪商人）。它时时警醒着我：修行的路上必然是孤独的。在孤独中创造奇迹吧。
由于期中考砸了，接下来从NOIP结束一直到寒假，我还会在洛谷上做题，但将成为一名潜水员，几乎不会出现在社区中了。从这个意义上看，我也算是暂退谷吧。
Ade，洛谷，等我回来。
（完）