我来帮你们拉低分数线啦!

写在前面

本文记叙了我在2020年的CSP-J/S中的精彩表现。

对文中使用到的缩写/专业词汇的注释

本文中令 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生涯的回顾与总结

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小数问题。然而做题的时候却翻车了。我对快速排序的效率一直不熟(毕竟有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-14-34-4

前两道题还行,在题解的帮助下很快AC了。最后一题看似简单,要自己写还是很费劲的,我调了1h的错误,最后实在懒得复制粘贴样例了直接敲了个文件IO,一直到22:55才提交,结果CE??原来是gets出锅了,只好明天来手打。

Day 4 (2020-10-14)

昨天sb了,手写gets不知道写的smwy,今天稍微改了改就AC了。

下一道题是UVA512,看起来貌似挺复杂的。不过今天没时间了。

Day 6 (2020-10-16)

UVA512还行,就是很多坑点(尤其是翻译没有把输出格式讲清楚,差评),不过WA了两次(貌似都是因为格式)以后还是AC了。顺便写了一个简单的题解

明天有空来做UVA12412,大概扫了一眼是一道大模拟,和时间复杂度挺像的,但好像侧重点不一样(时间复杂度侧重于字符串,这道题应该侧重数据处理),希望能再增强写模拟题的能力(当然也希望这道题不要调的太痛苦)。

Day 8 (2020-10-18)

这UVA12412真tm毒瘤,还没写完

Day 9 (2020-10-19)

呼~写完了,然而交上去又是CE,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开刀,加油。

Day 13 (2020-10-23)

AC P3957 祭之

之前一直不会,居然是因为题目有一个小细节理解错了:往右跳的时候只能跳到格子上,中间的位置都是万丈深渊不能逗留的,所以只用空间复杂度 $O(n)$ 的dp,再用单调队列优化时间就行了。和我之前做的一道题P1725本质上没有什么不同,就是用单调队列的时候需要加一点小小的处理而已。

继续肝UVA题。

Day 14~Day 15 (2020-10-24~2020-10-25)

把之前WA掉的一道UVA单调栈板子切了。

总结了一下发现错误居然是:

  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)$ 搞定。

#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$ 增长情况进行容器调配即可。

代码即为:

#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$ 即可。

#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测样例,三刻钟差不多搞定了。具体看【赛后题解】

T3 实在不会,就打了个暴力。30分呢,说不定就是2=和1=的差距。

#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上,现在应该是在家里坐等双1=了。可以说是一个教训吧。

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 预计3= 未参加 / 该得的分都得到了 实力不足 J一等S二等
zjh 220 预计2= 50 预计2= J的T2没有写挂 J的T3不会表达式解析,T4没写出来,因而差了100分,S可能是因为暴力写挂了 双1=

至于为什么我的基础相对较好,个人觉得是因为疫情期间在洛谷刷了很多题,积累了不少经验,所以编码能力较强,简单的题目发挥稳定,难题的暴力基本都能写出来。唯一欠缺的就是一些考场技巧,不能拘泥于一道题不放,以后要注意了。

今年的CSP圆满结束了,我辜负了奇迹,但总算没有辜负自己。一年的努力没有白费 ,可以睡个好觉了。听说NOIP会很难,所以就去打个酱油就好了。

最近又听了几遍《膜你抄》以及许多融入OI元素的经典歌曲,忽然有些难过。学校里的那些同学,就算关系再好,终究无法理解信奥生的苦与乐。往后的路,还是要一个人走。这也是为什么我把自己的用户名改成了wandering_trader(即“流浪商人”)。它时时警醒着我:非淡泊无以明志,非宁静无以致远。在孤独中创造奇迹吧。

由于期中考砸了,接下来一直到寒假,我还会在洛谷上做题,但将成为一名潜水员,几乎不会出现在社区中了。从这个意义上看,我也算是暂退谷吧。

Ade,洛谷,等我回来。

完。

最近一次更新:2020年11月20日。