2018~2019冬 广二避寒记
文章目录
【注意】最后更新于 January 31, 2021，文中内容可能已过时，请谨慎使用。
迎风迈出的步伐更艰难，即使走的不远，但踩得更深。一代人只能做一代人的事，完成这个时代赋予的使命就是英雄，大地也会将他的脚印铭记。
——乒乓帝国（句子迷上说是《孤杂记》..）
突然就得知了要去广二集训。
然后知道了这次出去可能要一直到 WC，差不多有 $50$ 天。这样一算这个学期我在武汉的时间可能和外出的时间一样多了。
毕竟是去广州，会暖和很多，也许看不到武汉的雪了。
Day 0
Railway
在站台上遇到了 Dew、ylh，感觉自己活尸化严重，都是我妈先看见的…
中午吃了泡面（有汤的那种），之前出去都比较近，在火车上不用吃饭，印象中上次吃方便面还是初三的时候在学校里吃的（桶装的泡面，愣是被我当成干拌面吃的）。
在火车上看看手机、看看《大卫·科波菲尔》，当然我现在在写博客。
途中看到了一幅非常………..ok我承认我词穷了。云很低，好像不比火车高多少，环绕在山的周围，山脚下是一些平房，在远处插入了几栋现代化的高楼大厦，有一种违和却奇妙的美感。
赶紧掏出手机，可毕竟只是手机，拍不出云那种虚无缥缈的立体感，匆忙中也没能选好角度，没拍到那几栋高楼大厦。
已经逝去了，经纬度也没有记下来，不能在回来的火车上再览其景，只能用粗浅的文字将其略微地记录下来罢。
Underground
进地铁前忘记上厕所了Orz
和 ylh 一起体验了一次换票出站上厕所。
然后是 huangbei 站：
人特别多，特别热。毕竟是来避寒的
Restaurant
和广二的教练谈了谈人生，建议我和 ylh 先系统地学知识点，不着急打套题，结果 dew 想先学知识点，我和 ylh 想在广二做题..
然后就是住宿的事，貌似准备先住两个星期三人间，等 ylh 回去了就去教练家里住（教练一个星期只回家一天）。今晚是先各自和家长住双人间。房号 1216.
Day 1
上午教练咕咕了，中午才来接我们。
然后让我们不着急打比赛，给我们三个人安排了个机房做题。
$5$ 道左偏树，派遣、罗马游戏和Joint Stacks比较轻松地做出来了；Sequence看了看题解，感觉还没完全搞懂，但A了；魔法猪学院用A*在广二的OJ和BZOJ上过了，暂时放弃可持久化左偏树，以后再学吧..
山、河、树（不只是路边那种）（当然也不是可持久化那种），游泳池，令人联想起 Angel Beats! 的食堂，各式各样的社团活动。
Day 2-3
把题目列表搞到了洛谷团队里.
搞了搞平衡树、启发式合并之类的，感觉自己啥都不会..
搞了个随机图片 。
Day 4
一天就写了[NOI2004]郁闷的出纳员和LCT模板…
然后搞了个stylus插件：洛谷犇犇、讨论隐藏。
果然整天待机房效率低.
Day 5
上午听隔壁机房的讲了下回文自动机、后缀数组、后缀自动机，但由于手头上的题还没搞完就没做相关的题目。
[NOI2005]维护数列做了好久..本来操作就多，取的子段还不能为空…
然后学了下LCT。
Day 6-7
就做了几道 LCT 的题…学了学虚树，还没做题。
然后这几天比赛挺多的，at+cf 还有洛谷比赛。感觉洛谷比赛都挺dl的…
然后今天看了几篇vfk的博客，感觉都写的挺好的。
里面提到了CFctr的自我修养，感觉以后出题时要牢记（虽然里面有些是只适用于CF的）：
准备一场CF包括：题目、比赛通知、题解。
你的题目必须是独一无二的。你不能从以前用过的题目中抄袭它的想法。PLEASE BE FAIR WITH THE COMMUNITY。（
空间限制必须是256MB，时间限制至少是出题人的java程序运行时间的两倍。
题面必须清晰好懂，没有语法错误。建议写得短短的……
题目背景中不要写数据范围，全部都要写在输入格式里。
请参考以前CF的题目描述的格式来写题目描述。如果你不知道怎么清晰地描述输入输出格式，请找与之类似的题目进行仿写。
题目描述中的数组下标最好从1开始。
你必须限制被你提到的所有的变量的范围。如果你提到一个字符串，你必须写明哪些字符可以出现在这个字符串内。
题目的tests中必须包括各种各样的数据，而且应该有各种各样的达到最小数据范围的数据和达到最大数据范围的数据。也就是说如果1 <= n <= 100000，那么数据中既应该有n = 1，也应该有n = 100000。
你应该写个暴力。
你应该拿标程与暴力对拍。
Div.2的题的pretests要很强，能让应该超时的程序在pretests上就TLE掉。但是你可以让这个点毫无意义。比如给n个数排序，你可以用n个1来确保选择排序不能过。
确保读错题的人不能过pretests。
建议添加极端数据，但是不必是所有极端数据。确保数组开小的人不能过pretests。
不要让时间复杂度很高但做了大量常数优化的人AC。
每道题至少2个样例。每道Div.2的题目的前两个样例必须有样例解释。
如果要使用long long，请确保不开long long的人不能过pretests。
哦对了，自定义域名总是炸，以后这个博客就用 ouuan.github.io 作为地址了。（正好避免了一年后域名到期的问题）
Day 8
今天好像啥都没干..估计是每天都没睡好导致白天效率低下..
好像看了好几篇淀粉质的教程，但就是不想写题..
和 memset0 讨论关于保留几位小数与精度限制的问题..感觉其他人总是不能轻松地理解保留几位小数是卡精度的…
翻译了CF的几道题，写了写题解。
继续yy自己口胡的题的优秀做法，依然没什么进展。
跟 Sooke 说了说自己出 CF 的想法，Sooke 表示想一起出，然后在还没想好一道题的情况下大谈怎么出 CF..
说实话出 div.2 的话会有些不甘，哪怕晚点也想出 div.1+div.2 的..
第一次用洗衣机，感觉洗衣机真有趣 
（好像暴露了我一周没洗衣服…）
（hexo 貌似不支持行内图片？）
Day 9
搞了个 随机生成图片 ，感觉自己自从用了 Hexo 日益由 OIer 变成码农了。
Day 10-11
这几天忙着搞比赛，博客可能咕咕咕了..准备比赛记大约会在比赛出来之后发QAQ.
Day ?-?
咕咕咕咕咕咕咕
Day 14
广二先是四楼停电，用了一上午笔记本，准备回酒店的时候门卫告诉我们电来了，然后回去一看发现四楼没电三楼有电。下午突然就又停电了，幸好我和 dew 都没有在写代码..
ylh 走了，然而住教练家被咕咕了，好像是因为又来了几个外省的。
新酒店..发几张图感受一下吧：
没错 p3 是 dew 在吊椅上
然而不敢对着 dew 拍…
wifi 特别神仙：
被夹在了一个没有 wifi 的世界里..
然后貌似明天还是什么时候开始要打比赛了，然后这篇游记就不会继续真的成“游记”了。
Day 15
今天是集训队爷 zjt 出的 集训队互测。
T1 一道带权带花树好题
的确是带权带花树裸题（求一般图最大权值匹配），然而不需要输出方案。
虽然说 OI 题名无正解，然而我还是百度了一下..然后学了一个半小时带花树，没学会！
然后再一看，$n\le20$ 不会做？
只好写了二分图的 $20$ 分滚粗..
然而发现一个严重的问题，这貌似是我第一次写二分图最大权值匹配..百度了一下，发现全是KM算法，没有一篇费用流？然后仔细想了好多遍，感觉费用流应该没问题，就写了。然而一开始写挂了（连图中的边时没判哪个点是起点），幸好后来发现了。
后来听说这题 std 是一个线代做法，由于不用输出方案码量非常小。具体可以参考2017年集训队论文。然而看不懂鸭…
这题不卡随机化乱搞.（嘤嘤嘤？）
T2 一道拉格朗日反演好题
看到 T1 真的是一般图最大权值匹配的我真的信了题名的鬼话..
一个 $01$ 序列，初始为空，有三种操作：
- 往末尾加个 $0$ .
- 删掉一个子序列，包含 $x$ 个 $0$ ，$y$ 个 $1$ ，然后往末尾加个 $1$ 。其中 $x\in A$ 。
- 删掉一个子序列，只包含 $x$ 个 $0$ ，然后往末尾加个 $1$ 。其中 $x\in B$ 。
$A$ 和 $B$ 还有操作总数 $n$ 是给你的，让你求 $n$ 次操作完成后序列长度为 $1$ 的方案数。
一开始还以为只用管 $01$ 分别的个数，后来才发现选的子序列位置不同也算不同的方案…
数据范围：いいよ,こいよ $114514$
不太会做，好像是转化成一个树上的 dp，然后再算一波式子，分治FFT/牛顿迭代？
不得不说样例十分lx：
10 10 10
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
362880
愉快地拿到了 $|A|=|B|=n$ 这档部分分。
T3 一道 Top cactus 好题
仙人掌上 $q$ 次询问求经过某个点的路径贡献之和。模 $998244353$。“不在简单环上的边数”为 $x$ 的路径贡献为 $v_x$ 。
部分分第一档，树，$n\le2000$ 。
woc我只会 $O(n^3)$ ..
冷静了一下，发现可以枚举路径树上差分..
愉快地拿到了这 $10$ 分。
正解好像是淀粉质+NTT。然后搬到圆方树上去。
总结
队爷出的题就是神仙..之前一直感觉多项式看起来没啥用？请julao们看到这句话别打我..感觉很有必要早点去学多项式全家桶了。
另外题名里的算法真的 $99%$ 不可信。
另外由于打比赛换了个机房，貌似机房里都是一些外省的？
OIer居然是可以有npy的！
Day 16
yww咕咕了，myh出的题。这场题面太赞了！题面，背景是自己看过的番，据说题意不清被吐槽的很厉害，但我貌似还是第一次碰见YNOI型题意瞬间理解。
这场还有个有趣的地方，T1 和 T3 的 subtask 一开始放反了，而且 T3 的变量 T1 都有，于是我比赛开始 $2h$ 才发现..（当然我发现的时候已经改回来了）
T1 青春野狼不做理性小魔女的梦
题意简述，题目背景太棒了，所以我要题面简述。
在咖啡厅，双叶不说话，只是推给了你一张纸，上面写着一个不定方程： $A_1x_1+A_2x_2+\cdots+A_kx_k\equiv1\mod m$，然而其中的一些 $A_i$ 被咖啡打湿了，需要给被打湿的 $A_i$ 们赋值（$A_i\in[0,m)$），使得不定方程有整数解；同时，双叶也不记得 $m$ 是多少了，所以要求 $m\in[1,n]$ 的方案数之和。$1\le k\le50,1\le n \le10^9$。
大约想到怎么做了，然而感觉无法实现（事实是正解要用杜教筛），会写的特别麻烦复杂度还不对，于是就只打了 $k\le5$, $n\le10$ 的暴力和没有数字被打湿的分。然而后面那档挂了，因为求区间内与某个数互质的数个数时没有容斥，最神奇的是拍半个多小时没拍出来…
T2 青春野狼不做姐控偶像的梦
和花给麻衣的信很有规律，她写的信是一个 $1$ ~ $n$ 的排列，一段连续的信能给麻衣鼓励，当且仅当它的值也连续（noi.ac的whzzt邀请赛里把这玩意定义为“广义排列”，意思就是一个区间， $max-min=r-l$ 且没有重复的数），麻衣想知道如果只保留一段连续的信，她能收到多少鼓励（就是多组区间询问）。
其实..就是 CF997E Good Subsegments..
千古神犇wxh log碾标算！lxctr myh n^2 送温暖！嗯，我拿了 $O(n^2)$ 的 $20$ 分…
做法参考 zzq的评论
T3 青春野狼不做小恶魔学妹的梦
这道题题面写的最好！（貌似也被吐槽的最惨）
对学长的思念，深埋于心底。
难以表达。
与学长的记忆分为 $n$ 个部分，两个不同的部分间可能会有一种关系，也可能没有。
可是我知道，它们藕断丝连，注定联通。
想忘掉，可是却越来越难忘，$m$ 种关系会带给我 $m^k$ 的思念。
我不知道我有多思念学长，能告诉我如果关系随意出现，思念的和吗？
我不想看到太大的数，只要告诉我它模 $998244353$ 的结果就好了。
题意简述：$n$ 个点组成联通无向图，求不同的方案边数的 $k$ 次方之和。
斯特林展开+大力推式子+NTT.
再见。
其它
myh 问班上的女生：你怎么3.5k写完仙人掌剖分的。
嗯，女生就是昨天的总结里的女生。yqyry
Day 17
今天没有比赛。
Day 16 ~ Day 17 的这晚貌似是来广二之后睡的最长的一次（$6$ 小时 $40$ 分），然后效率果然略高了一些（一天只搞了FFT/NTT/多项式求逆，高个鬼），比起之前整天几乎啥都不干还是好多了..（有种如果睡8小时能一天搞完多项式全家桶的错觉）
希望这周能把多项式常见的一些东西搞完吧..到时候应该会写一篇博客。
Day 18
颓颓颓。
T1
题意大约是求 $l_i\le ki+b\le r_i$ 的 $k,b$ 方案数。
最低档暴力在考试结束前 $10min$ 才想出来一个特别麻烦的解法..然后爆零了。
正解半平面交。
T2
线性同余找循环节海星。
T3
给几个团，团内点连相同权值边，问点之间两两距离之和。
以团内边权为点权求出团之间的最短路，然后 $dist(i,j)=\min\{d(x,y)|x\in S_i,y\in S_j\}$（$S_i$ 表示 $i$ 所在团的集合）。
具体实现要用到 FMT 里的一个小 trick ，然而题解里一笔带过，我看了一下午题解都没看明白…
其它
那位女生 $rank1$ 了…
然后今天才发现广二 OJ 外网是能上的..（当然注册不了账号QAQ）
Day 19
今天搬的 ACM 原题？CF 权限 gym Orz
题解给吉老师视频，太灵性了..
zjt 25（$rank$ $8$），myh 赛后五分钟提交 $15$ 快乐赛。
T1
dp，好像没啥不会的知识点，然而没做出来。
T2
把排列当成坐标放在平面上，分类讨论求上升块？表示完全没听懂，讲的时候 myh 在不停地提问。
黑科技听不懂，而这道题除了黑科技还要牛顿迭代…每场必有多项式的flag还是没倒.
T3
没听懂嘤嘤嘤。
Day 20
颓颓颓。
今天没比赛，然而只搞了多项式除法和任意模数NTT。
多项式除法一开始 $B(x)$ 模了 $x^m$ ，然而应该模 $x^{n-m+1}$ ，然后挂了半天。
任意模数NTT因为数组开小挂了半天…
看到洛咕有绘板，就把晚上的at咕咕了，搞了个py脚本。一开始妄想手动把图片转成数据，差点一晚没睡，后来main包发了个脚本，转的效果还挺不错的。
Day 21-23
基本上都在搞绘板，比赛记应该是永久咕咕了，绘板记这几天会写出来。
有一个小插曲，9102年第一个梗被我骗了点赞。
Day gugugu
绘板记咕咕了，这两天的比赛记咕咕了，今晚的CF不咕咕！猝死！！
Day 27
今天的T1非常有意思，$8$ 个 int 进行编码，编码长度至少是 $1000$ 个 int，随机打乱之后给你解码。标算是一个不确定性算法，所以这题是达到一定正确率就过，（然后我赛时第一次提交30，第二次提交20，脸黑选手zjt赛时90，赛后AC），然而有神仙想出了多点求值、快速插值的确定算法。
T2一看是几何题我就跳了..然而这题不怎么需要计算几何，而且有 $30$ 分挺好写的…..
T3是个树上dp，部分分有个“与一条蛇同构”，然后：
xswl
尝试着按myh的提交记录刷题，第一题是个字符串哈希，第一眼还以为是AC自动机..然后一发mapT飞，unordered就过了。第二题是个裸的单点、子树加，单点询问，竟然写错了3遍…..第三题是个数位dp，愉快地卡住了….再不好好学数位dp感觉会出事_(:з」∠)_
Day 28
T1是树上在线多组多路径询问颜色种类数和mex，一开始看到部分分还在想为什么没给树上莫队分，然后一想多条路径莫队复杂度肯定不对，看题解才知道正解树分块…bitset能在线搞定的事，为什么要离线排序呢？然后成功在赛后A掉了（广二膜你赛赛后首A_(:з」∠)_）大约就是预处理关键点之间的bitset，块内暴力跳，关键点之间已经预处理了。
T2是道神仙题..好像从某外国比赛搬的，赛时0A，通过分治时判断左右一样来保证复杂度，没太听懂。
T3：“点分治然后建虚树再点分治就好了！”（mdzz）“听说fzy有两个log做法？treap/Splay合并就行了！”（mdzz）
然后用bitset<0>水了点contribution，达成成就：contribution比friends多。
polygon真有意思！试着把一道题搞上去了。
Day 29-30
稍微学了下莫比乌斯反演和杜教筛，感觉挺有意思的QAQ。
比赛全场就我不会马拉车，然而三题暴力排名还不错…貌似只要打了点非无脑的暴力就能考的还行。（A题就jxd了
Day 31
今天比赛是zzq出的，上场 **Chinese round ** 既视感严重..
T1
树上有一些特殊点。
两两匹配特殊点使得距离之和最大。正解没听懂，然而直接扫一遍存为 $rk_{1..k}$ 然后输出 $(rk_i,rk_{i+\frac k 2})$ 就能过…
T2
“这是一道交互题”。
加了一些限制条件，不同排名的人在某些情况下可能不回答询问，对其排序。
并不是很难然而赛时没想到..
T3
QuickSort伪代码。
求 $cnt$ 次操作后排序成啥样了。又是只需要大小时转化为 $0/1$,$0/\pm1$ 的 trick.
然后，今天写了 $5$ 道莫比乌斯反演，100+600，感觉海星。
Day 32
改题日→出题日
Day 33
比赛的时候OJ挂了海星，最后修好了。
感受一下刚修好时的提交。这次题目时限又大，当时卡了好几页。
T1一开始时限是 $2s$，后来开成 $4s$ 了，然后一排人 $3.9s$…
T3一开始时限是 $6s$，myh NTT被卡常，赛后给自己开到 $12s$ 重测，$9s$ 过了…然后他成功 $rank1$。
Day 34
这个是我们刚来时就在画的，最近画好了，趁着迟到没人拍了一下。
上午被告知学校有考试，机房被占用了，让我们下午不要去机房，在打比赛的体育馆待着。于是很多人都提前跑了..我也下午就走了，走的时候看到一堆小学生模样的孩子和家长，听到了“XX考试的第二场和XX时间一样，不让考完第一场就跑”之类的话，听到了“二火”之类曾经熟悉的名词。我是为什么放弃了华一寄来到外初的呢..早就忘得一干二净了，只记得来外高是因为wqs的寥寥几句话：
还听到一个孩子说：“二中环境真好。”我以为他也会感叹二中有山有水，没想到他说的是——“二中有专门的清洁工”。
Day 35
改题日颓颓颓
Day 36
OrangeRabbit tql!!!
去机房的路上发现这个：
我们刚来的时候就看到有人在画井盖了，然而才发现这个QAQ
T2对自己 $20$ 分暴力过于自信，打了一个半小时表找不到规律后写了下 $20$ 分才发现是错的…
T1写了一个半小时比暴力跑的还慢的树剖..稍微想想就可以发现复杂度完全不比暴力优的，然而想到就打了..
最后没时间写T3暴力了，赛后听说T3数据特别水，随便写都能六七十分..
于是炸的特别惨。
晚上学了下淀粉质（讲题的时候myh认为机房里没人不会动态点分树…），看题解怎么都看不懂，只不过自己yy很快就写出来了，然而第一次交的时候前向星存边数组没开两倍..？
Day 37
今天又是zzq出的题，T1T2都是构造，其中T1没有输入..T1 rand跑了一个小时跑出来 $60$ 分（存种子提交），T2最低档爆搜不会..两个特殊性质subtask写了 $30$ 分。
T3 也是道思维好题，写了个 $O(n^3)$ 暴力 $30$ 分。
Day 38
好像是最后一个改题日..又颓过去了没什么好说的。
Day 39
Sooke跟我说他昨天做了这套题…然后告诉我不要看T3，会很惨。然而..
这次好像是我拿到 $80$ 分最快的一次，打完T1T2拍了一下就开始玩提答了。看了一会儿大约看懂了一点，然后试着百度了一下“lambda”，啥都没查到，然后继续搜“lambda 邱奇”，发现“邱奇数 百度百科”，然后继续搜“邱奇数”，搜到了这个。于是开始研究..前面 $6$ 个点有的是自己想的，有的是看懂之后写的，78是直接抄的。最后混到个15名..lx特别ba…只不过今天又来了几个人，感觉不抄的话二三十名好像也有，也海星啦…
Day 40
最后一天了呢..已经在布置THUWC了。
今天的题暴力档特别少..又是1h拿到了 $48$ 然后肝不出了…T3有很多人A，和之前D16T2有点像，是给一个排列问划分成若干个连续段的方案数，做法也比较类似，然而没想起来，也不会做…
这 $40$ 天好多想补的知识点也没补完..题也没怎么改..总体来说挺颓的…最后两天再稍微补一补，调整一下状态吧，考出应有的成绩就好。这篇博客大概就这样完结了，下次就是THUWC/WC游记了。
Day 41
本来应该结束了的..今天没去学校，10点的时候dew突然告诉我今天有场比赛？？一看是THUSCH2017原题，然后T1 dl线段树写了2h没调出来…只不过好像并不是膜你赛，广二OJ很早就有这几题了，今天的standing也只有6个人…
然后..窝竟然真的在WC前把kanon补完了..
评论正在加载中...如果评论较长时间无法加载，你可以 搜索对应的 issue 或者 新建一个 issue 。