2019.4 余姚中学 被吊打记

点击量：885

$\TeX$ 版游记

（不好意思标题有点不恰当别人貌似不屑于吊打我）

Day -1

第一次坐软卧，感觉空间宽敞，设施也比较新。当然是多交钱了的

Day 0

早上 8 点到了余姚站，坐了十几分钟公交车到宾馆。误判了地图的比例尺所以本来在公交站台后面的酒店找了半天。

去的还是比较早的，好在刚有人退房，就住下了。在房间里充电到 9 点下去吃了早饭，顺便走到了学校门口，并沿路踩点了吃饭的地方。

然后基本上就在睡觉了。

下午 xls 过来想拼房，但是被迷迷糊糊的 Dew 拒绝了（成功甩锅。

晚上随便吃了点。本来买了「小猪佩奇注心饼干」打算 4 天吃 10 包的但是貌似第一天就吃了 4 包呢？？？

FWT 接着看没怎么看进去，看来不能在床上学习。

Day 1

正常操作，8:00-13:00 考试。

现在拿 SYZOJ 当考试评测机已经很普遍了吗？虽然评测速度还是要参考硬件，而且我还是很享受光标在 pdf 上选来选去的那个感觉…吧

开场看 T1，实际上是随机开题。T1 是给定一个无向图，给每条边赋一个方向，求这 $2^m$ 种方案中 DAG 的个数。

想了很有一段时间发现只会 10pts 的 $2^m$ 枚举…在纸上写了 T1 $O(2^m\cdot n)\ 10’$。

枚举+tarjan 应该挺好写。先扔了开 T2。

T2 如果枚举全排列的话是 $O(n!)$，$n=20$ 貌似跑不过去。于是准备 meet-in-middle，但是发现虽然上界很松但是状态数还是 $O(2^n)$ 级别的，信仰它能跑过去。

码码码，发现上面还有一维..好像是 $O(n^2\cdot 2^n)$，$n=22$ 的点就跑不过去了啊

然后又调了很久发现还有一堆锅。

准备打 $s_i=0$ 的部分分，考虑先把 $n\le 20$ 的表打出来，打到 $n=11$ 时发现没什么规律，扔了。然后顺手跑了一波 $n=20$，结果要用 $2 \mathrm s$。大力优化循环+判断卡到了 $0.6\mathrm s$ 就没管了。

到此感觉前两题都是计数 with $1000000007$ 十分毒瘤。

开 T3。怎么又是排列啊…今天两计数两排列好像都没怎么做过题啊..

然后打了个贪心直到对拍…才发现自己的错误。毕竟猜贪心这东西凭运气多一点吧。

但是最低档部分分还是 $n\le 20$，仍然没想到比 $O(n!)$ 更优的做法。而且没绑包，于是交上去就没管了。

摸了会鱼发现电脑上并没有扫雷？而且网很慢。

最后随便检查了一下文件输入输出就差不多了。

估分 $10+30+0\sim 100=40\sim 140$（当然那个波浪线当作左倾的吧 XD

结束之后发现是 $10+20+10=40$。和估分差得不远

T2 莫名 $n=20$ 挂了，结果听别人说才想起来这题是 $500\mathrm{ms}$…

$600\mathrm{ms}$ 扔了是梁静茹给的勇气吗！！！register 啥的还没加呢..

不过还好，没挂多少，T3 送了 $10$ 分，应该是规模小了。

中午吃了什么什么鱼，吨吨吨了三碗汤泡饭。

Dew 告诉我 T3 可以二分图顿时产生了熟悉的愧疚感——见 CF1139E 题解，并表示了 Dinic 优化连边+未知神操作可以艹掉这题orz。

然后去面基?纪中的宋老师增加了一点_点点信心，并对后来的日程也有了一些_{极其微小的}打算。

下午讲题貌似仍然一脸不可做，会了多一点的部分分，感觉还是有收获的，当然题题容斥的话会有点难受。

搬着凳子坐在教室的左上角，T3 正解大概也不是流。

之后是杂题选讲，或许是一些国外题目 USACO/POI/ROI/CF Gym 的搬运。有些题目会有点卡科技，但是还有一些题目思维比较重要然后才卡科技。

有一道三进制 mex 的题猜测是多项式，再根据 $k\le 12$ 猜了复杂度 $4^k\cdot k$，大概是 $2\times 10^8$，然后给奶中了 ppt 上给出的复杂度。实际上会有大概 $3^n$ 的“平移进制位”做法，但是都好神啊。

晚上搬了一会题，一开始准备从内网 OJ 导入 GuOJ，但是出了点问题以为需要外网。后来才知道是 GuOJ 临时挂了。

22:35 有场 Div.3，感觉不是很影响睡眠+Unr 就打了。不过因为 Unr 打的也不是很认真，1h 才过掉 5 题。FG 还是有些难度的。

这时看见 ACoder 只写了 G，感觉这个策略不错。毕竟用 1h 时间刷 Div.3 A-E 五道难度不大的题除了对手速的训练以外并没有别的作用，况且 OI 中手速快也并没有特别大的增益。

Unr 场除了玩得开心还要对自己有所提升。

貌似写过的题很容易忘，当然如果考试进入状态或者做写过的题的时候进入状态估计回想起来会容易很多。

Day 2

前一天睡的有一点点晚，不过只困了一会。阳光明媚的春天怎么能犯困呢

吃了买好的面包就差不多过去了。前一天晚上疑似坏了的 OJ 能上了，Dew 重测之后就有了 80，被吊打一倍了2333。

开题发现有 4 道，前面两道题目一样，是因为 Subtask 需要的时限不同而 SYZOJ 目前并没有分包改时限的功能，分别放了 40 和 60 分。

所以还是顺着看 T1。给出 $m$ 棵一模一样的树，每个点有一个不同的颜色，有 $q$ 次操作，每次可以对区间 $[l,r]$ 中的每棵树“缩”一条链变成一个点。

强势缩点的话是 $O(nmq\log n)$ 的，只能过 10 分。抱着之后可能会用到对拍，就当时打了。不过打完是 10:00，耗时有点长。然后就直接点了 T3，忘记写暴力的初心了。

T3 是个类似区间 DP 的东西，用区间 DP，对于 $q$ 个询问，每个可以 $O(n^2)$ 求出解。仍然是 10 分。但是算了一下上界复杂度在 $2.4\times 10^8$，$3\mathrm s$ 的限制可以卡一卡。最终还是花了 $3.9\mathrm s$，不是很稳。

最后看的 T2，一开始感觉每个进制分别维护已经遍历过的和还没遍历的，貌似需要树状数组。后来发现前缀和预处理一下就可以了。但是还是调了很久，甚至把数据写在纸上调试，感觉有些得不偿失（貌似没有失去什么）。还好找到了“忘写乘法”的错误。

并没有想到更优的解法。感觉比前一天打的还要不好。

中午又吃了 KFC，大概放松了那么一点点。

xht37 跟我说 T3 实际上可以 $O(n^2)$ 倒着做所有情况，然后 $O(1)$ 用 $f[u][u]$ 回答所有询问，这样就可以过掉 30 分。

Dew 表示 T2 是个类欧，应该不可改；并在 T1 YY 出了 $O(n\log^3n)$ 的做法然而好像没调出来。

下午听题，T1 是个扫描线+LCT，听上去极其煞笔，应该可改，估计得先复习 LCT。

T2 类欧，套上原根会简单很多，然而不知道式子为什么要那样推。

T3 据说送分题，简单数据结构貌似就可以解决。

下午讲了几个有意思的题，跟着思考了一下，但是讲的时候很容易掉线。希望之后能多听一会，也许可以听懂。

好像有一些题是把状态放到平面上然后找斜率或者位置的性质，感觉可能是一种做题的方向。

还有一些题是对算法的理解。会把一些基础算法的步骤进行一些变形，然后适应到各种题上去。

虽然没有打挂什么题，但是还是很难受。看到自己每个题都只会最低档暴力有种被扼住喉咙的无力感。

打完暴力总是会忘记为什么要打暴力，以为打完暴力这题就结束了。这种心态要尽量调整回来，并相信自己有实力拿到更高等的部分分。

然后是建模。虽然题目描述是这样，并且可以通过一定手段模拟实现拿到一定部分分，但是这对揭开整个题目并没有什么帮助。需要考虑题目中的每个操作的意义是什么，可以转化为哪些已知的模型并用套路解决它。

任重道远。

Day 3

kls 出题。貌似由于前一天 OJ 有很多 Waiting 打算今天线下测评。

开题还是看 T1，感觉流挺可做的。但是最小的包 $V\le 2000,\ E\le 4000,\ \mathrm{maxflow}\le 2000$ 一脸 TLE。

不一会想了个贪心，可以用路径压缩做到 $O(n)$（不是很清楚这里有没有 $\alpha(n)$，但是没看到哪里可以按秩合并）。

然后把之前的流打了出来开始对拍，流还打错了一次。拍上之后造了一组极限数据跑了 $1.65\mathrm s$，有了前天的教训于是开始卡卡卡。

当然到最后发现是卡了读入…各种优化都没用。最后到网上 copy 了一个 fread 快读板子但是不会用..

看了 T2 和 T3，感觉秒了 T2 的 40 分，没写先扔了看 T3。

感觉可以建个图，但是发现边数是 $O(n^2)$ 的。然后想了个贪心没把自己叉掉，$O(nm^2)$ 看上去很可做，带上 $\log m$ 也应该能过。

然后拿着 $n\le 12$ 对拍，偶尔 bf 会被 $n=12,\ m=12$ 卡成狗，但是并没有出现 WA 的情况。就头铁交了上去。

此时期望最大得分 $100+40+100=240$，理论最小得分 $60+40+0=100​$。

拿着 T2 码码码..差不多 10 行写完了，但是不会阶乘以内的对拍并坚信自己的 40 分狗贪心是对的。

这时差不多 10:20，我已经没事干了。←当然这一定是考试爆炸的前兆

拿出了之前关掉流量开关的手机刷刷刷，然而并没有打发很多时间。

中间下发了大样例，发现三个贪心都基本能过。虽然觉得有点奇怪但是继续摸鱼。

然后想起来 T1 需要卡卡，但是没卡成功。一直以为找到了假的 fread 板子..偶尔帮跑得慢的 T3 重新生成数据，然后再玩玩扫雷，时间终于差不多了。

结束之后看到 3 个阿克的，每个题都有一些人 A 掉，感觉今天可能是自信场。最终是 $60+0+25=85​$。

T1 果然是被卡了，应该是读入问题；T2 莫名挂了，甚至挂在第一个点，导致整个包都跳过了。明明过了大样例的…T3 贪心是有问题的，不过听说小数据可以过掉很多。此外如果某个循环倒序枚举是可以过掉更多的包的…

中午吃了大概四碗饭。汤泡饭太好吃了！！！！回房间找到了真的 fread 果然过了。

下午去发现 T1 是一道放过一些 $O(n\log n)$，卡掉很多 $O(n)$ 的玄学题，思路大概差不多。

T2 构造+卷积。那个贪心是错的，可以用排序不等式等一些式子叉掉。而且貌似读题不规范，爆零两行泪了，图不需要连通，森林即可。

T3 我的贪心假了，有个结论被 Dew 整出来了，不过后来他可能哪里写挂了并没有得到很多分数。

杂题选讲感觉很卡科技啊…上来扔一个斯特林反演，给出的思考时间长达 1h，不得不摸鱼。然后剩下的题有一些目前看上去很热门的算法。持续掉线，考虑明天还听不听杂题选讲了。

晚上只吃了一两个大概 $5\mathrm{cm}^3$ 的面包，中午吃多了不是很饿。改了一个多小时昨天 T1，没改出来。貌似 LCT 维护这个东西会很麻烦，可以在明天的自闭时间继续梳理一下。

Day 4

早上大概 7:55 到了机房门口，发现没有开门。于是等到了差不多 8:01，咕咕咕。

开题看 T1，数论题。发现分别是 $n\le 10^6,\ n\le 10^9,\ n\le 10^{18},\ n\le 10^{24}$ 这样很多档部分分。看上去 $n\le 10^6\ O(n\log n+q)$ 一脸可做，但是感觉后面可能稍微想一下也有分，于是随便想了想。

毕竟 $n\le 10^6$ 是个 DAG 上 dp，实际上状态会非常少，大概不超过 $O(\log n)$ 层，于是考虑用 map 存一下状态，因为给出了质因数，所以准备枚举质因数进行转移。

然后好像并不能涉及到所有的约数，然后就由于没过样例被扔了。

T2 是个字符串题。感觉比较签到，然后多搞了一会。每次一交就会发现自己有一些错误然后改改改，最后差不多了才扔掉，不过多组数据还是很虚的。

当然最后看提交记录是 $40\to 60\to 80=80$。

T3 并没有思路，又是一个暴力不会打的题。毕竟只会 $O(n!)$ 给我 $n\le 20$ 并没有什么用┑(￣Д ￣)┍。

后来 yy 出来一个贪心，但是不会贪。用了贪心引出的一个结论，好像可以 $O(n\cdot 2^n)$，有 $5$ 分了..

然后期望得分 $20+100+5=125$。

今天貌似投入的时间挺多的，也就是说没有自闭的垃圾时间。不过并没有更多的收获2333

感觉各种前后（3 道题）调整了一会，时间就差不多了。

出分 $0+80+0=80$，每天的分数在递增来着，排名就不一定了。

T1 T 了，好像并没有输出。貌似是 EOF 判错了。T2 fst，估计还是有什么细节。

T3 或许贪心错了或许枚举错了，不过好像是不可做题。但是难得看到 $n\le 5000$，应该是个 $O(n^2)$ 神仙题。

Dew 神神神，A 掉了 T2，然后 T1 据说期望 $O(T\log^2 n)$ 的复杂度卡成了上界 $O(T\sqrt n\log n)$？？神神神。并且 T3 整出了看上去很对的结论拿了 $45$。

中午余姚中学的老师把 ZJOI Day2 安排上了。

中午喝养生粥。

下午讲题没有咕咕咕好评。T1 怎么上来「容斥+高维前缀和」好方啊。T2 好像把每个包都讲了不过我瞎打的。T3 有好多神仙做法啊，好像我的结论是个错的，并且有好多神神神弄出了比较优秀的 DP 式子。

lsy（评论 1L） 讲题公开膜 Dew（评论 3L）太暴力了。

然后杂题选讲听懂了一个爆搜，剩下的又卡知识点了。不过有收获就行。（并且良心的 kls 把课件发了下来（是因为讲完了吗2333

晚上吃食堂。感觉食堂阿姨好热情啊[捂脸]，吃完了好像小卖部锁门了。下午忘记带杯子了不过撑过来了，晚上还能继续去机房苟一阵子。

然后开始改改改 T2，改了好久一阵子听说有牛客练习赛然后打算签到。结果签到半天签不上，好像是 spj 锅了，一开始以为不算错误次数不罚时，于是大力交了 10+ 发。最后错误改过来了，后来重测直接罚时 5h+？？？还好没认真打。

最后还是没把 T2 改过来，貌似我的解法需要用个栈存一下。

然后晚上去华润屯早餐了。

明天继续靠签到题苟活吧2333

Day 5

现在是 Day6，由于 intLSY 同学提前阿克没事干想来踩蒟蒻找优越感，于是就更了（就咕了一天怎么就催更了

摁了 6:45 的闹铃之后就睡过了orz，还好买了面包窝在房间吃吃吃。

开题，T1 是个数论方面的构造。想了一会没啥头绪，准备最后再打个暴力（下策

T2 给了一个幻方，但是是在 $\bmod m$ 意义下的。一开始没怎么理解好，后来发现只是一个矩阵，不是幻方。划划划一会没啥发现，又扔了。

开 T3，看到是个随机游走，每个点只能经过两次。看成每条边只能经过两次，那不是最后一定回到根节点了？？？样例不对啊…

鉴于此时已经 10:00（我也不知道摸了什么鱼就过了两个小时），于是打了看上去比较好写的 T3 暴力。大概调了十来分钟就差不多了。

然后再看 T2，还是画不出来什么有用的信息。这时发现 T1 只有一个输入，可以考虑打表，顺便防止 TLE。而且第二档暴力有 $20$，然后就开始打表，复杂度大概是 $O(k\log^2 k+nk\log^2 n)$（$k$ 是枚举上界）。于是 $n\le 30$ 跑了半个小时左右跑出来了，一个有梦想的人会在剩下的 40+min 内跑出 $n\le 50$ 吗？？？然后脑抽看了 T2……

由于有了 T1 打表防 TLE 的意识，又因为 T2 只有 $n\le 5,m\le 5$，于是我开始打 T2 的表。复杂度好像飙到了 $O(5^{17})$，当然我直接跑了 $n=5,m=5$，这个看上去出题人一定会造的数据如果跑不出来，前面的应该也没用。

等它跑的时候我又去看了看 T1，在 T1 继续真·暴力打表。研究了一下已经打出来的东西，发现总有一段是 $x-1,x-2,\cdots,x-k$，后面几段也满足了这个个规律。然后先把后面的按这个规律顺下来交上去，再慢慢看是否全部符合。

大概在 12:35 的时候乱输入 $n$，搞出了 $n=45$，发现输出了 $-1$，这时候就感觉这一段都是 $-1$，然后开始“二分”哪里是第一个输出 $-1$ 的位置。当然个数比较少，所以跟一个一个枚举检验没什么区别。最终找到了 $n=41\to ans=7567741$ 和 $n=42\to ans=-1$。高高兴兴地把 $42\sim 50$ 全部填上了 $-1$。

当然我当时并没有想到 $n>50$ 的情况，不然都输出 $-1$说不定还能对

后来快结束的时候才想到，中间有一段 $10^5$ 数量级一下子就变成了 $7\times 10^6$ 数量级，这个上界可能设小了。但是再大的话预处理就凉了，所以暴力还是写的不优（不然就不是暴力了对吧）。最终抱憾 $20$ pts。

出场听说 Dew 用比较优秀的暴力打出了 $n\le 50$ 的表然后爆零了，好像是他看到自己暴力的 $n=1$ 输出了 $0$，又看到题目中 $x>0$ 的条件，然后改成了输出 $-1$。不过有 spj，输出 $1\sim 9$ 都是对的啊2333。不过貌似他打表找规律 A 掉了 T2，我到现在还没跑出来 $n=5,m=5$（（（

下午讲题时间疯狂变长最后才知道是把杂题宣讲给鸽了。

由于 ZJOI Day1 难度是 $2\to 3\to 1$，所以签到题放在了 T2，但是 T3 过掉的人最多…大家都喜欢硬核 DP 吗。。学不来学不来

吐槽 T1 的时候 Dew 指出了那个问题结果 zzt 上去就把 $1\le x$ 改成了 $0\le x$。

T2 有个看上去很严谨的证明，不想看了。但是这种核心代码只有 $4$ 行的题在听了之后不知道怎么再发挥它的价值呢…

期望 DP 这种东西好像看上去最可做了。但是要分 $5+$ 种情况讨论啊，不仅需要码力还需要一点脑子（我没有

然后还是提前讲完了。到机房发现洛谷月赛还有一个多小时可以打，然后先 T1 签到，T2 不是很想想了于是开始推部分分，发现奇数编号的点非常可做于是就都打了。但是获得了 $82$ 分的好成绩，好像是每个点 $5$ 分，$5$ 组数据，然后我没判就还过了几组偶数点。

T4 lxl 题，秒了暴力就看 T3，但是 T3 题面太长劝退了，回去想 T2 也并没有什么进展。最后 10 分钟看懂了 T3，不过只打了初始化部分就结束了。多给我一个小时应该可以多拿一点分甚至rk1？。

晚上回去整理了某比赛的 .md 题解，然后感觉对 Typora 有点审美疲劳了，就尝试了一下之前下好的 $\TeX$。弄了一会上瘾了，然后就一直查资料调调调，弄出了一个比较满意/美观的版本，也是游记咕咕咕的原因。

考虑游记写个 $\TeX$ 版本的发上来？？？

Day 6

昨天的面包没吃完，继续塞塞塞。

这场好像是真自闭场，但是分数甚至比前一天高。

有了昨天的经验，骗过一次人的伎俩不会再用第二次了，所以还是开了 T1。并且昨天 zzt 还说了“前面背景放一道题，后面不一定是它的加强版；前面放一道不可做题，后面说不定很可做”。

但是好像都不可做啊…一脸三道构造的样子。

T1 怎么又是数学题啊，暴力好像都不可打，给定奇质数 $p,q(q-p=\lambda,2\le \lambda\le 3\times 10^5)$，被这个 $\lambda$ 搞懵了。第一档暴力是 $p\le 10^3$，乘一下是 $10^9$，怎么都跑不过去啊..我的最优复杂度是 $O(n\log n)$ 来着..头铁还是打了个 $O(n\log n)$ 上去。

T2 给了一堆公式，后来才看懂那些 $\sum$ 是把哪些数加起来。当时写上去一个高斯消元，该过的（?）样例都过了。然后手动构造一些特殊排列被当场卡飞了，发现会有负系数，但是题目要求 $0\le p_i\le 1$。

然后就只考虑暴力了，$n\le 5$ 只有 $5!=120$ 个排列，每次随机生成 $m=5\le n$ 个排列，卡时到 $900\mathrm{ms}$，感觉比较稳。打算扩展到 $n\le 10$，发现 $n=8$ 就整不出来了。于是乎收回了远大的理想。

开 T3，虽然不像是构造，但是它没有给 $c_1$ 的初始值，并且 $c_i$ 还是变化的，所以还是需要这方面的构造。

有 $30$ 分是 $k\le 2$，猜了个结论，推了一下应该是对的。在位置 $i$ 的贡献为$\frac{sum1_i+c\times mus1_i}{sum2_i+c\times mus2_i}$，根据数学课上学的“糖水定理”，当 $\frac{sum1_i}{sum2_i}\le \frac {mus1_i}{mus2_i}$ 时，$c$ 应该尽可能大，如果不管其他因素，取 $c=1$；否则，$c$ 尽可能小。

根据这个可以知道 $\{c\}$ 一定是一段连续的 $1$ 和一段连续的 $0$ 拼起来的。

11:00 左右打完了上述暴力，期望得分 $0\sim 10+20+30=50\sim 60$。

当然还有很多基于 T2 的时间优化，但是对于常数的优化并不能对瓶颈在指数的算法构成一些优化。

最后 $0+0+30$，这时候才看到 T2 的输出是要先输出排列个数 $m$ 的，应该是为了方便 spj，但是我好像没怎么仔细看输出格式orz…而且之前貌似没怎么犯过这种错误，只能当教训了。但是一共 $60$ 就挂 $30$ 比例也太高了点..

中午看到牛客有两场比赛，都签了个到。并没有中奖，但是好像知道了 01 背包的 mex 求法。

下午讲题吐槽的人变少了。可能是自闭场无槽可吐？？？

T1 是据说的送温暖题，不过还要推好一阵子。另外 slides 上的题解部分莫名消失了？不过就算有估计也看不太懂。

T2 是基于 $n$ 维凸包的题，中午考完了给 lbw 口胡，当场秒出 $n$ 维凸包 %%%。当然也许 $5000$ 个式子高斯消元能跑出来 $n\le 10$。讲解用了向量推导，从二维平面上的 $\lambda\vec a+(1-\lambda\vec b)$ 的中点一定在 $\vec a-\vec b$ 所在位置的线段上。剩下高维的不会了。

神仙 T3，防 AK 题？题目给出了一个分式但是并没有想到分数规划，不过知道是分数规划也不一定写得出后面的点。

后来听 sjzez 的神仙吐槽说样例输出 $0.666666668$ 一眼二分2333

及时补锅，++rp。

Day 7

前一天晚上睡得比较早，稍微清醒了一点。

早上还是吃楼下的面，不过在某团上发现了优惠价（大概优惠了 ￥0.2）。但是拌面体验并没有汤面好。

然后还是惯例 7:57 到机房考试。

开场看 T1，想了一共三个假算法，每次都是打到一半发现有问题。

想到了优秀的 $O(n\max\{a_i\})$ dp，然后看到 $v$ 是最大的数，$v\le 10^3,n\le 10^6$。我一想啊，$10^9$ 复杂度好像有点为难？？然后用了一会想到了去重，复杂度变成了 $O(\min^2(n,v))$，可以做到 $10^6$ 级别。

虽然经历了 $100\to 30$ 的从假到真和从高到低的大起大落，但是总比只写第一个包的 $10$ 分强很多了。

T1 写来写去磨磨唧唧了两个半小时，开 T2，看到又是个数学构造，不过 $n\le 500000$，也许会有其他想法。

然后瞎写了 $O(n\log n)$ 复杂度的一个构造，并写了一个指数复杂度（dfs 复杂度）的暴力，但是构造出来的答案总是比暴力小。不过还好通过比对答案大小发现错了不然又要少一行环长 $m$ 的输出。看来以后看到 spj 要注意输出格式，毕竟我写 spj 的时候应该也会让做题人输出答案长度来避免判断 EOF 这种麻烦吧。

然后写了个 checker 判断是否相邻两个元素的 $\gcd>1$。发现错了，赶紧改改改，过了一会终于能把 $n\le 10$ 大小全部跑对了，也都合法。毕竟不能比暴力差啊2333

然后 $n=21$ 的暴力疯狂跑不出来，T2 就扔了。

T3 看上去是个字符串，然后考虑 SAM 过掉第二个包。但是发现字符集大小高达 $440$——$\frac{n(n+1)}2=100000\to n\approx440$，然后不知道怎么做了，暴力 $O(n^4)$ 匹配甚至能跑出 $n=500$ 的数据，不过貌似这个区间枚举上界真的很小。

_{在开黑群里说了一下这个问题，Dew 说用 map?也许能解决。（没有真的开黑）}我没写过 map?的 SAM，算了算空间也不是很稳就弃了。

没挂分。T2 得了最稳的 $n\le 10$ 的 $10$ 分，虽然可能的最高得分是 $100$。然而比赛中乱搞 AC 的事情好像没有发生在我身上过。

T1 有 40+ 人通过了，T2 有 20+ 人，和以往的画风并不一样。构造题挺看运气和经验这个波动大我可以接受。但是貌似 T1 更签到啊？？？

最终得分是 $30+10+10=50$，在人人 $220$ 的这场比赛里真的显得太渺小了。自闭场大众分=暴力分，我挂分；自信场大众分=100×水题数量，我 A 不掉。

我好菜啊

得到了 ZJOI Day2 的狗牌，外省无人权选手前来报道。

中午又吃鱼了，居然把汤泡饭吃腻了。Dew 说 T1 的 $v$ 是输入的最大数，所以第二个包 $n\le 10^3$，白想了。

xht37 说如果下午自走棋 zzq 没来就在机房自闭，但是来了。发现 zzq 不是很会玩白板，并对白板高度延迟进行了吐槽。

T1 套线性基随便讲讲就没了？甚至倾情演绎线性基求法。并给出了这题的加强版，需要用 FWT 和 FWT 的定义进行优化。FWT 看上去没怎么考，但是思路也许会很重要。

T2 的构造貌似也很弱智，但是还是需要想一会的。而且构造方法貌似很清新脱俗。把一些链连起来就可以了。

讲完前两个题之后是“命题人写了 3h 就写完了的 T3”，需要发现一定规律然后分类讨论。不可做题。当然 $n,k\le 10^{17}$ 怎么看都不像是个字符串题啊2333

晚上走了 1km 左右去万达觅食，最终找到了牛排+自助，并不是牛排自助。把返程票买了。

回来的路上咵了很多废话/流水账，比较消食(x。

22:35 有场 CF Edu，一开始网络问题卡了 3min，然后发现魔改的快速输出有问题，然后改成 printf 把 A 过了。B 半天不知道怎么做，只好瞎贪心，过了样例交上去 A 了（Edu 的 AC 总是暗藏玄机）。C 题降智好题，求个 $\gcd$ 就完事了。

然后开始写 D，快读愈发不好用了，然后一边骂人一边改成 scanf。

写了个贪心。然后交上去 WA on 5，发现一个地方没讨论完全，加上去之后 WA on 9，然后持续自闭。

造了组数据能 hack 掉大部分贪心：

4 -2
11 -10 11 -12

到 23:50 意识到后面题还没开。打开 E 瞄了半天发现是个交互，

为什么不写 This is an interactive problem. 啊啊啊

感觉随便代几个值然后模意义下高斯消元就可以了。码码码，码完了构造了 $a_0=0,a_i=1(1\le i\le 10)$ 的特殊数据，没跑过。

到最后都没调出来，可能是逆元乘来乘去给爆 int 了没及时转。

0:22 的时候 debug 把 Code::Blocks 玩坏了，然后电脑出了点故障。强制重启之后 .cbp 文件损坏了，main.cpp 也打不开。看来还是 Linux 稳一些。

最终以 +,+,+1,-3 的好成绩结束了本场 Edu（撒花

预测是 -92

这一周以来的比赛貌似都打得不好，有一些题不愿意想，还有一些题本来会写但是没看出来或者打挂了，然后方向错了没及时 return 等等问题。多少都在这场 Edu 中体现了一点。

晚上聊天的时候也说了给自己压力不能太大。其实我也不知道是给自己压力大了还是小了，有时候会有做事不专注，总会偏移原来的方向。做一些有意义的事也就算了，但是很多时候对于无意义的事情的投入就显得冗余且累赘了。

所以做事情的话一定要记住本来是准备干什么的，不能偏离它太远。

大概要掉到 Expert 了，不过还会有机会上来的。

Day 8

早上终于点了三两面条。吃的时候并没有觉得很多，不过看上去的确比二两多一些。

昨天晚上在 U 群看到了 zzq 在问交互库怎么给，所以今天是有交互题的。

开题，T1 是个跟与或异或有关的题，进行一堆操作并查询区间和。每次看到这种题都会有 FWT 的感觉，推了一会发现不能 dp。

题目写了签到题，但是里面一定有猫腻，扔了。

继续看 T2，是个交互。用“下发”的 "dwa.h" 库，实现函数 vector<int> work(int n)。但是并没有附加文件，好了，现在不仅没有大样例，连交互库都不给了2333

过了一会交互库发下来了，考虑了一会，发现给定的限制和最低得分的限制不一样。后来发现 $t$ 是询问组数限制，另一个是询问总个数限制，一组询问可以问 $70$ 次。

一开始准备递归二分，建成了“线段树”的形式。后来发现修改一条链要询问 $\log n$ 组，这样就直接达到上界了，相当于 $10$ 分暴力。

然后就先放下去看了 T3。又是一道数据结构，但是比较奇怪，询问区间权值从 $k$ 开始连续的最长子序列。yy 了一下感觉可以 $O(n^2)$ 时空复杂度跑出 $30$ 分。

然后写写写样例过了，就交上去了。中间有个地方没判上界，想着跑出来了应该有 break，就没管。因为下标是 $0$ 开始，所以数组开的 b[5000][5000]。

T2 把树稍微改造了一下，成了个归并排序。但是归并的过程也无法同时比较很多元素，因此在最后几层是需要 $O(n)$ 次询问的，这样的话就又被卡到 $1000000+$ 了。既然是维护最小值，那我存一下次小值直接更新就好了啊，这样就可以做到 $\frac{2n\log n}{70}$ 了。

过了一会发现这个也假了。因为最小值次小值都是迭代的，我如果要维护次小值，就要维护第三小值，这个做法是不可行的。

最终还是打了归并，同一层一起查询可能可以尽可能降低复杂度？

然后写写写又发现维护信息冗余了。这时候 11:20，于是把 T1 题目中用来解释操作的暴力 copy 上去了，拿到了 20 的暴力。

然后就潜心写交互。在 12:30 的时候写完了，带交互库测了一下 RE 了。改的时候发现最后一段和其他段不一样，前面的段是按 $2$ 的幂分的，所以后面如果也是 $2$ 的幂的话会越界。

改完大概是在 $12:56$。测了发现交互库返回 Wrong Answer，错的还有点远，索性弃疗了。

这场难得的奋斗到了最后几分钟，但是没有实质上的成果，不过还是比较满足的，至少良心上过得去了。

出分是 $20+0+0=20$。T3 的两个细节是会冲突的，当枚举到 $n$ 的时候会越界，也就自然不会 break。xht37 用更简单的方式实现了这个东西并 $O(n^2)$ 跑出了 $n\le 50000$ 的数据，我的暴力打的总是没有他优美。

或许我的暴力只是暴力，别人的暴力是把每档部分分当作一个简单问题来思考。这就是总有人说“省选暴力进队”和“WC/CTSC/APIO 暴力 Au”的原因吧。

大众分 $180$，有四个阿克。每个题都有 $10$ 人左右过掉。

中午喝粥，点的配菜好像有点多了。

讲题的时候听上去感觉 T1 并不难，也不难想。因为按位操作除了 FWT，枚举子集，乱搞以外就只有 trie 了。省选的时候 xor 题想到了 trie，这会又给忘了。非常自闭。

T2 是模拟快速排序，只需要比较很少的次数就可以了。基准数被叫做 pivot，因为数据随机，所以直接比较就可以了。

T3 结合弹飞绵羊可以套上 LCT，把序列的操作转化到树上去，能做到一个 $\log$ 的复杂度。

这两天的题都没有超纲，甚至没有难的知识点，因此是比较可改的。

总结/后记

总结得失，那就先说失吧。

8 天，最高得分 $85$，最低得分 $20$。没有 AC，没有爆零。

每天上午平均两个小时没有做题，有时候在看之前的题目，有时候在乱写乱画，或者在手机上看一些消息。总感觉进入不了状态，非常浪费时间和环境。

做题的时候不愿意深入思考，得过且过。对于一道题应该搜刮所有与之有关的算法，再进行分析；每道题的每个子任务也可以当一道题想，这样应该会对算法的理解也加深很多。

建模，或者说是转化。有些题本来看上去非常麻烦，只能打暴力。但是实际上找出它的本质或等价条件，解决与其等价的问题，就会相对简单一些。这 8 场中有至少 3 道题都是这样的。

有些题的形态是要画出来才能知道有什么性质的。比如区间填数就可以用二分图匹配来做，对于有式子影响的题目，要多推式子。

注意读题。

不过还是有收获的，

比如在做题策略上，一个题一个题的开，写完第一题的大部分再写第二题这样。在 5h 的比赛中，这种时间分配要相对稳定一些。

还有这些令人闻风丧胆，实际上并不超纲/不卡知识点的题目。

最后就是知道了哪些知识点是现在的热门，哪里的题目质量比较高。

要变得越来越强啊

结束了？

结束了。

你好，ZJOI2019 Day2。