CSP2019-S宝典

CSP2019-S宝典

CSP2019-S宝典

——(Memory\_of\_winter)

~~放图镇楼~~

模板

博客

博客模板链接

如平衡树，网络流，最短路，(mathrm{LCT})，(mathrm{LCA})，可并堆，(mathrm{tarjan})缩点，(mathrm{ODT})，(mathrm{KMP})，(mathrm{AC})自动机等

快读

namespace io {
    struct istream {
#define M (1 << 25)
        char buf[M], *ch = buf - 1;
        inline istream() { fread(buf, 1, M, stdin); }
        inline istream& operator >> (int &x) {
            while (isspace(*++ch));
            for (x = *ch & 15; isdigit(*++ch); ) x = x * 10 + (*ch & 15);
            return *this;
        }
#undef M
    } cin;
    struct ostream {
#define M (1 << 23)
        char buf[M], *ch = buf - 1;
        inline ostream& operator << (int x) {
            if (!x) { *++ch = '0'; return *this; }
            static int S[10], *top; top = S;
            while (x) { *++top = x % 10 ^ 48; x /= 10; }
            for (; top != S; --top) *++ch = *top;
            return *this;
        }
        inline ostream& operator << (const char x) {*++ch = x; return *this;}
        inline ~ostream() { fwrite(buf, 1, ch - buf + 1, stdout); }
#undef M
    } cout;
}

vim配置

~~如果考场没有(mathrm{vim})我也没办法，希望我(mathrm{dev})还用的习惯~~

source $VIMRUNTIME/vimrc_example.vim
se nu rnu ts=4 sw=4 ci si list lcs=tab:|- go=
" syntax on
" filetype plugin indent on
se guifont=Courier\_New:h14
colorscheme desert

map <F9> <ESC>:w<CR>:!g++ -o "%<" "%" -Wall -Wl,--stack=16777216<CR><CR>
map <C-F9> <ESC>:w<CR>:!g++ -o "%<" "%" -Wall -Wl,--stack=16777216 -std=c++11 -O2<CR><CR>
map <F10> <ESC>:!"%<"<CR><CR>
map <F11> <F9><F8>
map ya <ESC>gg<S-V>G"+y

imap <F9> <ESC>:w<CR>:!g++ -o "%<" "%" -Wall -Wl,--stack=16777216<CR><CR>
imap <C-F9> <ESC>:w<CR>:!g++ -o "%<" "%" -Wall -Wl,--stack=16777216 -std=c++11 -O2<CR><CR>
imap <F10> <ESC>:!"%<"<CR><CR>
imap <F11> <F9><F8>

imap <C-s> <TAB><BS><ESC>:w<CR>a
map <C-s> <ESC>:w<CR>

对拍

@echo off
:loop
gen.exe > in.in
S.exe < in.in > S.out
M.exe < in.in > M.out
fc S.out M.out
if not errorlevel 1 goto loop
pause

CSP2019-S注意事项

考前

记得看模板
注意休息，不要睡太晚
设个闹钟
考前不要太紧张

考时

先全面浏览题目，简单分配一下时间
注意看数据范围，有没有什么特殊性质，把可能的坑也注意一下
如果看不出正解，可以先把所有可以写的部分分计算一下，确定保底分和预计写的时间
不要太紧张，可以通过喝水等方式缓解压力
计算答案和中间变量的大小，记得取模和开(mathrm{long long})
注意变量名，不要有( exttt{time,y1})等
计算数组大小，不要开小，变量类型不要写错
注意测试极限数据和边界数据
有时间要写对拍
最后要跑一遍大样例，检查是否有注释未删除
最后留出(15 exttt{min})时间检查文件夹~~（不要建双层文件夹）~~和文件名

考后

(16)号下午泼一泼隔膜，调整心态，不要影响到第二天

把(Day1)出问题的地方重新复习一下

游记

不一定会有。如果有的话可能直接附在后面，也可能是链接。（如果写了的话预计考完后也会放一份游记的博客）

UPDATE：2019-11-17：游记链接

Day -2（UPDATE：2019-11-14）

完了，我写游记了，~~是不是要被禁赛了~~。

刚刚写完不一定会有游记，然后开始写，感觉自己打脸真/cy快。

经过(11,12,13)连续三天的期中考的摧残（原来教务处说不用考，然后变成非创新班的要考语数英和选考科目，幸好技术不用考，不然要考(6)门更自闭），人要没了。

早上的考试自闭，希望明天的“信心赛”真的是信心赛~~（一不小心就成了自闭赛）~~

开始写宝典，期待明天见到Mrsrz（毕竟到了(mathrm{zhzx})半学期多，除了一试见了一次，其他都没见过）。

这应该是我第二次写游记，不知道后面几天还会不会继续写~~（看我后面泼隔膜泼的程度）~~，估计是最后一次认真比赛了，后面要回去准备文化课了，所以说应该也是最后一次写游记。

到高中后信息学习状态一直起不来，看到题目根本想不出来方法，还没有去年(mathrm{NOIP})时候状态好，估计成绩还没那次好。希望今年(mathrm{CSP})可以(rp++)，至少不要犯大的错误。为(16,17)号的考试努力。

经过提醒，突然发现我写的是CSP2019-J，/jk，然后赶紧改过来（肯定是因为我太菜了），幸好我在报名的时候没写错

(mathrm{FSB})来机房动员经典语句：

(mathrm{dp})的模板多看看
变量名取的中文一点
要跳出题目看题目，从出题人的角度，任何题目都有缺陷
你们就是每个都低于(400)分，只要拍拍胸脯，问心无愧就是好的。~~我：(mathrm{FSB})，我得到了(0)分，这就是我的水平，我拍拍胸脯，问心无愧~~

Day -1（UPDATE：2019-11-15）

上午信心赛：

T1：[CF24A]Ring road

T2：[CF254C]Anagram

T3：[CF852E]Casinos and travel

感觉是近年来最良心的一次，终于可以正常的得到(300)分啦！终于不是自闭赛啦！

( exttt{T1})最简单然后结束后发现是代码最长的。。。后面两题代码好短啊！( exttt{T3})原来是用来给我们练习树形(mathrm{DP})的，然后没几个人写(mathrm{DP})，全写结论去了。

今天这么顺，明后两天估计要凉凉。

在车上得知蛟川出了一些奇妙的事情，可能不能和(Mrsrz)一起住。开始各种慌，慌自己“无家可归”。到了宾馆，在门口等了(20 exttt{min}+)，然后听老师说可以和(Mrsrz)住一起，瞬间感觉好多了。

我们房间在(21)楼，房间正对面是一个差不多可以直通一楼的东西。害怕自己明天自闭一不小心就下去了。整了下东西，边看(Mrsrz)泼雀，一边在群里问有没有人一起吃饭。

(17:50)左右，和(daklqw,Weng\_weijie,Mrsrz,YuHaoXiang)吃晚饭，绕着宾馆套了无数圈，最后由(daklqw)拍板找到一个火锅店，吃得倒是很饱。

晚上到(8:45)（也就是我写这句话的时候）还没有开始看模板，明天要慌慌慌了。过会加油看。

今天几乎没有颓过，估计是觉得最后一次考试要认真点吧。

祝我明天能有一个好成绩！

Day 1（UPDATE：2019-11-16）

今天是考试第一天。昨天晚上居然没有泼隔膜，应该是我出来比赛以来第一次晚上没有泼隔膜，睡得挺好。

早饭居然是在小卖部？？？？居然只有一张抵(10)元的票子？？？严重差评。奠定了自闭的一天的基础。

到了文渊中学，厕所也是差评，考点在地下车库，一般般吧。

开始比赛，密码是Ren2Zhen0Si1Kao9，为什么今年的这么正经。

开场先配(mathrm{vim})，咦？为什么改不了字体？为什么显示什么Courier_New中包含1（记不太清了）？改了(10 exttt{min}+)，算了算了，不改了，就默认吧。。。（考试后发现我写的是se guifont=Courier\_New:14，应该是se guifont=Courier\_New:h14）。果然不好好看(mathrm{vim})配置是不对的。

看( exttt{T1})，是格雷码，看了一下。嗯，简单，写了一会然后写挂了，然后发现有个地方想错，随手调了一下，应该就过了。

接下来是( exttt{T2})，好像有点不可写，先写个读入吧。去看( exttt{T3})，好像可以写的样子，不然至少(60)分应该可以拿的（(flag)）。突然发现这题是多测，还记得昨天车上，某人说：“(mathrm{CSP})绝对不会有多测的！”今天立马打脸。

诶？我好想( exttt{T2})会了？似乎就是一个拿栈保存一下前面的右括号，然后(mathrm{dfs})，对每个点统计一下以这个点为结尾的合法串个数，前缀和一下就好了。回去花了不到半个小时把( exttt{T2})写了。嗯？大样例( exttt{RE})了？一看(mathrm{vim})配置，我把开栈写成了--static？？？怎么配置出错这么多。。

弄完配置发现没过大样例，调一调发现一个右括号好像不止加一个，改了一下过了大样例我就放在一边。

看起来时间还挺充裕的，难道今年(Day;1)和去年难度差不多？不会人人(300)吧？开始写( exttt{T3})，写写写，写了(30 exttt{min}+)。我写完了！一测数据，全部炸裂。突然感觉( exttt{T2})有点慌，时间看起来很够的样子，回去写对拍。一拍，(n=500)的数据一拍一个( exttt{WA})。怎么这么多错误，不会我暴力写挂了吧？看了一下，好像没问题？？？跑了个小数据，手模了一下，诶我的程序挂了诶！赶紧调，发现栈加元素的时候值写挂了。调掉。嗯？怎么还锅？然后发现我改的时候又加了一个锅。汗。

然后拍上啦（我也不知道到底过了没有）！去看了一眼( exttt{T1})，输出了(n=5)的数据，看了一下没问题。时间也到了(10:30)。赶紧回去调( exttt{T3})，今天最不幸的事情发生了。(11:00)，因为我前面程序开栈都是(10^9)。然后我内存没了？？？大概每三次编译只有一次可以成功的样子？（内存没了？肯定是因为今天太热了^[1]）。就有点慌。到了(11:50)左右，彻底无法编译了。感觉今天自己要垫底了，心态爆炸，向监考老师反映了一下，让我重启，彻底没有时间写暴力，( exttt{T3})爆零，最后还申请延长了(5 exttt{min})，然后并没有干什么。

预计(100+100+0=200)，不知道挂了没有。

出来发现，绝大部分人( exttt{T3})打的都是(10)分暴力，也没有被拉太多，但肯定是低于大多数的人的分数。内心有点崩溃，出来的时候袋子刚好发完，我也没拿。

中午和昨天的人吃饭，在路上看到一家饭店叫“梁大妈妈菜”（居然(D)梁大的妈妈菜？？？）

下午和(Mrsrz)以及(Weng\_weijie)一起玩(mathrm{Minecraft})（其实有点不想玩了），后面心态又好了点。晚上还是一样的人出去吃饭。回来后，(8:15)应(Mrsrz)的要求，泡了碗泡面，边吃边写这游记。我居然写了(1 exttt{h})？期间被(Mrsrz)怒(D)若干次“你好了没有啊？怎么写这么慢啊？”

希望明天可以发挥的比今天好吧，加油

Day 2（UPDATE：2019-11-17）

第二天，今天考完试直接走，早上整东西退房。

到考场，昨天晚上没看信息的东西，感觉有点慌？密码是@zhuajin1SHIJIAN7，看起来今天时间不够（笑）？打(mathrm{vim})配置，这次没有出问题，害怕内存又不够了，就没有手写开栈，打算遇到题手动再打一遍。

打开题目，( exttt{T1})看起来还行？仔细想了想好像不是很能写，看了下数据范围猜测复杂度(O(n^2m))。然后就去看( exttt{T2})，莫名感觉好像暴力很好写的样子（(flag)）？接着去看( exttt{T3})，这个暴力肯定是可以写的，(55 exttt{pts})应该是稳的，就放了放，去想( exttt{T1})。

大概(9:30)的时候，我还没有得分，有点慌。突然( exttt{T1})有点想法，先求出只满足条件一的方案数，求出其中不满足条件二的部分减去。可以知道最多只有一种菜超过了一半，枚举哪一种菜超过了一半，做一个背包。写了个(O(n^2m))的，写完一测样例，发现我在写背包的时候没有考虑到总共做了几道菜，然后只得又加了一个循环。对于每一种菜，记录总共做了(i)道菜，其中(j)种是这种菜的方案数，复杂度(O(n^3m))，可以拿到(84 exttt{pts})的分数。后面想想也不会优化，就放着了。

这时候大概(10:10)，赶紧打了一个( exttt{T3})的暴力，拿了(55 exttt{pts})。(10:30)，去看( exttt{T2})，写个两个假算法，然后感觉从后往前考虑，取最短的可行的段作为一段似乎可以，然后继续写，复杂度(O(n^3))，写完样例一二都过了，心中还是有一点兴奋的，然后样例三就挂了。已经(11:20)了，赶紧写了个(O(2^n))的暴力，拍了组小数据，然后发现我在判断把后面一部分变成一段是否可以上有问题，但是我还不会写，自闭了。

大概(84+12+55=151)，总分(200+151=351)，考试出来后突然想起( exttt{T2})应该把暴力的范围开大，这样如果数据有梯度也可以多得一点分，不过考试已经结束了。

出考场后，发现人人(230+)。退役了。这次(mathrm{CSP})准备不是很充足，状态也没有去年好，出发前就估计这是我最后一次认真参加信息竞赛了，明天应该就是只是参加比赛而不准备了。现在结果真实放在眼前，有一点不舍吧，毕竟是从五年级开始学的，和各个同学关系也特别好；但是我也知道我无法沿着这条路一直走下去，今后也不需要担心是应该学信息还是文化课了，也算是为我指明了一条路吧。以后还是会怀念和竞赛的同学们一起学习的时光，祝愿他们都可以得到他们满意的结果。

(skip2004)似乎(AK)了(mathrm{CSP})？无敌啊。

问了下同学，( exttt{T1})只需要改为对每种菜，记录这种菜的道数减去其他菜的道数就可以到(O(n^2m))了。( exttt{T2})大部分人写的(O(n^2))的(mathrm{DP})，( exttt{T3})写一个线段树合并。( exttt{T2}, exttt{T3})我都没有去搞懂，毕竟不学信息了嘛。

想想这一次比赛，感觉我什么也没有做，隔膜也没怎么泼，信息学也没有什么成绩。要回去补文化课了。

这篇游记应该是我最后和信息学的关联了，写完这篇游记就专心投入文化课了。以后应该只有在选修课的时候才可以见到我了，也许会写一点题，博客也可能会发一些题解，但是肯定不会完全尽心了。(mathrm{AFO})啦！

在出分了以后这篇游记可能还会更新一下，不过都是以后的事了……

Day3（UPDATE：2019-11-18）

还是没法完全忘记信息学。

正式进入文化课学习了，发现期中考我参加的学科试卷就讲完了，我没参加的学科试卷都没讲完。。。

才停课三周，其中还有一周是期中考，一些科目就已经有点跟不上了，习惯了机房的生活，在教室总是有点不舒服。怀念在机房无所顾忌没有担忧的生活。每天对着电脑，想写代码就写，不想写的时候也可以颓废；没有什么明确的任务；可以随时和同学聊天……然而这一切都已经过去了。

今天下午体活课前，还是没忍住，去了趟机房，借用(little\_gift)的电脑在洛谷和校内(mathrm{OJ})上发了(mathrm{AFO})的消息，宣告着今后信息学最多只能成为我的兴趣爱好，而再也不可能为之奋斗了。听说(little\_gift)因为(mathrm{MLE})可能有点爆炸，希望他不会有事。我花了(5 exttt{min})做完这些事就离开机房回了教室，毕竟这再也不会容纳我了。

从去年(mathrm{PKUWC})结束就开始讲什么“明年(mathrm{NOIP})后就退役”。然后，因为升学的几次提前招生的失利，我有差不多一个学期没有再碰(mathrm{OI})。而后在得知(mathrm{NOIP})取消后，同学们笑我：“这下你退役不了了。”我也是一笑了之。我知道我很难再有好的状态来参加竞赛了。

一个多学期的生疏和由于升学考失利而导致的分班问题，是本来就不拔尖的我连恢复到以前的水平也做不到。

我终于能有较为完整的假期了！我终于不用假期里天天早起坐车赶去蛟川了……但是，当这结果真摆在眼前的时候，我还是想选择这忙碌却又充实，与同学们一起玩闹的时光。

明明自己对一切事都看得很开，而且这也不会是我最后一次来到这个机房，但我总还是有一些伤感，一丝想哭的冲动。上一次这样大概是初中毕业晚会吧。

晚上回到家，看到洛谷上征集游记，就发了一下。这一篇是在晚上晚自习时候写完，然后回家后更新的。

我热爱过信息学，我为之努力过，我无怨无悔！致无悔的青春！

我名字：(Memory;of;winter)，被同学们戏称为“冬天的内存”，只要是冬天，我就有无尽的内存，笑 ↩︎