KeBlog

12 天的培（kao）训（shi），坚持每日总结。

Day0 to Day4.

Day0

大清早的就出发了，地铁还是那么挤。
先从长沙坐到南京，高铁上干坐 6 个小时贼贼贼贼贼无聊。

中午幸好提前买了泡面，随便应付一下，坐了一上午不动也不会感觉饿。
%%% 在高铁上一餐吃 70rmb 的 lzk 。

到了南京还得等 1 小时转到芜湖，期间 UNO 现学现玩，
第一把就赢了，一定是传说中的新手的欧气附体，
但是这欧气来得快去的也飞快，后面再也没赢过 ，并且一度成为全场最富（一次拿了 20 张牌也是没谁了）。

再到动车上就累了，睡了一觉。

宾馆感觉一般但也还行，位置不错，旁边就是美食街，
逛一遍发现芜湖的物价似乎比长沙要便宜得多？
这里奶茶只有长沙一半多的价格还巨好喝，还有木桶饭最便宜 8rmb, 最贵也 16rmb, 吃得相当饱，提供的辣椒酱好评。

晚上宾馆自习，我的笔记本实在实在实在是太 tm 旧了 windows xp 实在实在实在是忍不了啊。
宾馆的 wifi 都连不上去我怎么怎么打（kan）代（dian）码（ying）啊？？？
还有我早已练就一身折腾本领，小事，关掉 XP 的沙雕代理轻松解决。
但是网络实在是 suo （也许是我电脑不行？），努力了一晚上都没能成功看上电影。

Day1

第一天考试，凄惨爆 0 。
考试的时候想不出题啊（我太菜了），比较心不在焉，
才发现打满暴力都是一种困难，水平不够。
%　一 % 成功拿满暴力的 CZZ, orz 。

第一题维护区间历史最小和，玄学转换到二维平面 KD-Tree, 这玩意前几天刚考但是没去学，
我发现冷门算法一考就会连续考几次。

第二题一脸不可做，题目名叫因式分解，我也就真的只会因式分解了。
讲题的时候满分做法爆搜？？？好吧正解还是要个 DP 的。

第三题式子题妙啊妙啊，这什么用 $ _{i=0}^{n-1} A^i = $ 把 $ A^n $ 换掉的清奇思路谁想得到啊。
还有把 f(i) O(1) 一路推到 f(n) 再用组合数的奇技淫巧把 k 到 n 的枚举换成 1 到 k 谁想得到啊。

还有吐槽一下这套题部分分好少，几乎只有两档：暴力 -> 正解。

然后就是晚上的 自由欢乐时光 认真自习。
终于成功把昨天的电影看了一半。
然后颓了一晚上也是没救了，没办法 T3 被卡常心态爆炸（这就是你颓废的理由？）。

Day2

成功拿到预期的暴力分 30，一大进步。

第一题图染色，考场上脑子不清醒，很快想到 $ O(n^2) $ 的建图方式后，
竟然完全没有想到怎么计数，最后 $ O(n^n) $ 枚举染色方案可还行。
于是 40' -> 10'

第二题又是一个计数，AC 自动机？我完全没想到，
我还以为是容斥，但是发现有有 5 种情况，容斥起来要 5 + 10 + 10 + 5 种情况加加减减，
没敢打，不过这次这题部分分给的挺全的，分了 10 个 subtask 还是不错的 ~~虽然我只拿了 20 ~~ 。

第三题玄学最短路，要用最短路树（我想到了但是没啥用），这玩意前几天 czz 才讲，
果然又应验了我昨天说的，一考就连续考几次
暴力都很难打啊这题，到最后只能 puts("-1") 了，然而 subtask 数据捆绑。

一考完就被 *** 拉去吃什么网红烤冷面（然而是热的），very nice but 量有点少。
然后 *** 就拉了一堆人去星巴克 666 ，讲真这是我第一次在星巴克喝咖啡，忍痛剁手。
晚上到宾馆就开始颓，终于看完了昨天的电影 壮哉我大火影 。

Day3

今天的题目巨难，听出题人说是因为他明天赶时间所以把明天的 毒瘤 题全放今天就有更多时间讲。

第一题在 2 * n 的网格图上求一个生成树，我想到有个类似的题（求 2n 的网格图上放一颗树的方案数），
但是那道题我已经忘记怎么做了，而且那是计数，而这题是要求一个最优方案，
反正就是以为可做然而 Naive, 浪费了很多时间最后打了枚举生成树的大暴力。
考场上有一个线性计算当前方案的算法，枚举的时候加一点小剪枝，总复杂度应该是 $ O(6^n n) $ ， 预计 20' ，但是实际上还是只有 10' 。

第二题感觉是什么数据结构题，我按照一种贪心思路敲了线段树，
估摸着有 23' 就没管了，后来出题人放了三个大样例，我一测，第一个就 WA 了，改了一点细节后过掉了，
再测第二个，又 WA 了，然后 debug 了好久才意识到贪心的思路不对，这个时候离考试结束只有 5min, 弃疗。
然后和预计的一样，3' 。

第三题是在一个很奇怪的图上面求最短路为 x 的点对（怎么又是最短路），
大暴力就是跑出每个点对的最短路再统计嘛，这个图发现了一些性质，但是还是不会做，
想着应该不难打就去打 T2 了，然后 T2 打到结束前 5min 所以这题的暴力也没打， 0' 。

今天的部分分还是很少，T2 T3 的暴力都只有 3' ，难受。

中午去一个东北菜馆吃饭，菜上的k慢但是挺好吃，很有特色，
最抢眼的是收银台前面的冰箱，里面一条巨大的鱼（完整一条的可能比我还大？）。

下午有洛谷月赛，于是冠冕堂皇地不改题打月赛，洛谷月赛一如既往，除了签到题都只能打暴力。

晚上险些被查水表，我正在听歌教练突然敲门，我当时就以迅雷不及掩耳盗铃儿响叮当仁不让世界感受痛楚汉相争之势拔掉了耳机。
没错，拔掉了耳机，然后 tm 就变成外放了声音贼大，当时就感觉自己真是沙雕了我去，
然后我又以迅雷不及掩耳盗铃儿响叮当仁不让世界感受痛楚汉相争之势插上了耳机（被自己秀死了），这个时候教练已经差不多进来了，然后交代一些事，我耳机就插在笔记本上光明正大地摆桌上，有点小可怕，还好教练没有说什么。。。

从今天开始教练晚上要强制收电脑，于是 10:30 电脑被收后无所事事，
这时候大家都要睡了（比如柠檬 9:30 就交电脑睡了），可是万恶的 *** 以睡不着的名义把我拉过去打 UNO,
然后我只能被逼无奈地去打 UNO, 到 11:30 才睡可还行。

Day4

今天终于 A 了一题，今天终于 A 了一题，今天终于 A 了一题。
还有 % 一 % 全场 rank1 的柠檬。

第一题我手玩了一下得出了一个十分精简的结论，按照这个结论三四十行代码就能解决，
自己都不敢相信啊，今天终于有一道良心签到题了？
于是打出来后不停地调试，手造各种情况的数据都跑一遍，把之前的结论完善一些漏洞之后就交了，
交了之后还是有点慌，生怕哪里出锅。
最后还是成功 AC （四天来唯一一次）。

第二题刚开始看题还觉得可做，感觉像扫描线加线段树那种，
但是看到可能有一面墙回塌后就不这么觉得了。
而且我还看错了样例，这直接导致我误解题意，本来是先选点再有墙塌（考虑方案的时候不知道哪个墙会塌），
我看样例这样跑出来不对（其实是我手玩玩错了），就以为是先塌墙再选点（提前知道哪面墙会塌后考虑方案），
于是 blablabla 后交上去，预计至少有个二三十来分，结果只有大暴力 3' （还好大暴力的数据没卡掉我）。

第三题就感觉完全不可做了，最后暴力都没打， 0' 。
下午讲题的时候才发现这题 25' 的部分分贼容易，就是个排序加贪心。
另外 75' 正解好像是用 dp 做前面 25' 在对后面 75' 的求和用 dp 套 dp, 好巧啊之前朱哥才讲过。

A 了一题心里比较舒服，于是下午就颓了好久，打 Nazo 自力更生到 level 8 就不会了，
在网上找提示后玩到 level 11 后再次卡关。

另外碰到一件玄学的事，我那显示器一碰就断电，然后要不断地调那根线，
直到调到某个位置才可以打开，大概是因为接触不良，
然后一次又黑了，我调了贼久试遍了各种姿势还是然并卵，
没法子了，去找老师实在不行换个位置，
老师了解状况后过来随手一拨，真的是 随手一拨 ，那显示屏就开了，就开了，开了，了，
emm 不愧是金牌教练，真的 6 。

晚上本来去吃必胜客的，但是没注意到今天周日，人巨多，排队等座位都要半个小时，
几经周折最后去了 KFC ，也还不错。
旁边一家奶茶店搞活动，把一个计时器按到刚好 10s 就能领两大杯奶茶，然而大概是我脸黑，按了 3 次都差的蛮远。 晚上又是 UNO, 和 tyr 无意间相互精准放炮，
连续两次 tyr （下家）只剩一张牌，我掐指一算，猜到了那张牌的颜色，
自信地打出一张其它颜色牌，结果和他数字相同。。。

NEXT

Day5 to Day8

12 天的培（kao）训（shi），坚持每日总结。

Day5 to Day8.

Day5

考试

Nice 大夫今天又 A 掉一题！

第一题是在 DAG 上 q 个询问，每次询问一个子图的路径数量（子图点数和 O(n) ），
我想了想部分分， DAG 上 DP 嘛，但是这样复杂度上界是 $ O(q m) $ ，
瓶颈在于边的枚举（菊花树卡爆），然而子图的点可能很少，
然后想到了更暴力的：邻接矩阵存图然后用枚举点代替枚举边，
事实上邻接矩阵存不下，那就开 set （map 也行）动态加，
这复杂度 $ O(q n^2 log(m)) $ 啊然而，然后我想了好久优化都没想出来，
最后想着得多骗点分，于是就把两个暴力结合在了一起：
每次询问比较 $ n^2 log(m) $ 和 $ m $ 哪个小就跑哪个。。。
看上去很鸡肋，然而我理性分析了一波复杂度卧槽好像是 $ O(q m log(m)) $ ，
应该能骗蛮多分，于是交了，然后 A 了。。。

第二题又是个计数，感觉像容斥，容斥之后怎么搞就有点迷，
于是写了个 dp ，手玩样例感觉没错，然而一测大样例就 WA 了，
于是手玩了几组数据，才发现 dp 错了，区间相交的情况没考虑好，
最后实在没思路，就打了个大暴力，有 30', 还不错（ 10 倍于前面两天的暴力分 3' ）。

第三题哇塞维护一棵树，一看就感觉是树剖 + 线段树或者 LCT 之类的数据结构题，
然而还是不会，又敲了一发大暴力 10' 走人。。。

讲题

下午讲题，一看 ppt 下面一行字：--Claris
woc 今天见到真人了，那位 bzoj 4000+ ac 的神仙！
第一题正解是按度数大小关系连边，出题人说数据难造所以有这种带 log 的算法卡过去了。
第二题果然是容斥，但是要通过一个奇妙的矩形构造转换为轮廓线 DP 。
第三题出题人说并不是数据结构题？blabla 讲了一堆奇妙的做法，
然而有 4 个人用动态 DP 搞过去了，出题人想到了这一点还特意去卡了但是没卡掉。

颓废

昨天没吃成必胜客来着，今天再次尝试，又剁一波手。
晚上真是诸事不利，tmd 这笔记本真的让人心累，
要啥没啥，网连续断了好几次，还真就不是网的问题，众人不断就我断，
什么 u 盘硬盘全没用，放我电脑上就读不到，
蓝牙更是做梦，键盘只能插线就算了还一老读不到，
还什么显像管出问题？动不动一些地方就全是红色的跟看恐怖片似的，
说优点倒也有，用个电脑火炉都省了，贼发热，那电风扇的声音时刻提醒你它还活着，
它要是太烫了还会自动关机，把你烤热了再降降温，贴心，
放歌听也很棒，我听快歌，它就一卡一卡的，一个字一个字给你放，根本不用怕听不清。
还能智能存储电量，充电线一拔就晓得要存储电量直接断电，不插上充电线不给开机，保证电池里的电永远满的。
别的什么还有一堆，懒得喷了，难受。

Day6

考试

前两天把 rp 用完了，今天全暴力都写挂。

第一题我一开始推出个错误的结论，然后一想可以离线排序询问再预处理 dist 根据询问不断删除，删除不好搞换成加边弄个并查集维护联通块，
然而代码打完后一跑样例， WA 了，手玩样例才发现结论错了，这时候已经 9:30 了，凉凉，后面两题还没看。
最后打了大暴力 10'。

第二题题读到一半就感觉是二分，读完题后推了一下发现可以转换成这样一个模型：
二维平面上给定 n 个点，每次将一条平行于 y 轴的直线右边的点都向上平移 dy 单位并回答所有点的斜率 (y / x) 的最大值。
然后就有了 $ o(n^2) $ 的暴力做法，这玩意一脸可以优化的样子，然而想了好久没思路，就交了 60' 。

第三题网格图 DAG, 感觉像要 dp ？但是不会，就打了暴力，结果还打挂了 RE ，爆零。

讲题

第一题什么神仙 dp $ O(n^4) $ 过 100 可还行，我太菜了没搞懂这个 dp ，
但是出题人提到有枚举端点 + 组合数的做法，我想去看看，一看哇塞简单多了，
而且复杂度优秀的 $ O(n^3) $ ，下午按照这个作法改了一段时间就 A 了（期间没开 long long 一直爆炸）。

第二题好像是可以从我那个模型再转换一下后分块 + 凸包维护，感觉很神仙。

第三题有个神奇的结论：
用两个不同的顺序得到的 dfs 后序，u 可以到 v 当且仅当 v 的两个 dfs 序都比 u 的小。
然后就可以将点按一个 dfs 序排序后按颜色设状态 dp, 把 dp 数组扔进树状数组后得出答案。

颓废

晚饭兰州拉面，清真的店子就是讲究，还贼好吃。 晚上感觉屁事没干，教练发了一套题要我们做（考试的题都改不完啊），
实在不想做，反正明天收，晚上就几乎一直在颓，找歌听。

Day7

考试

100 % 纯暴力的一天。

第一题神仙计数题？好难啊感觉，于是想了想了 k 小于等于 3 会不会有什么规律可循，
发现 k = 1 的时候就是 $ 2^{n-1} $ ，就得到了 1 分的好成绩（这分给的真少）。
然后再手玩了一下 k = 2 和 k = 3 的情况，找到了一种计数方式，过了样例，就交了，
然并卵，k = 2 和 k = 3 的情况错了，只有 1' 。

第二题感觉是什么 set 启发式合并，但是合并之后只能暴力搞答案，
没思路，打了暴力，5 分的好成绩。

第三题我靠麻将小模拟大搜索题？感觉很复杂，而且到第三题也没什么时间了，
于是打了一发只有字牌的特殊情况，20 分的好成绩。

讲题

出题人说这个题目难度是 T1 >= T2 >= T3 。

T3 果然就是搜索，先算出最大答案（就是 9 ）统计面子搭子的数量再减答案。

T2 线段树合并，玄学，还不会。

T1 真有意思，标程生成函数加一大堆什么多项式的优化之类的，复杂，没懂。
但是有位大佬考试 27 分钟后就 A 了这题，出题人叫他上来讲讲，
然后他就开始秀操作：
“我的直觉告诉我 % n 等于 0 的方案和 % n 等于 x 的方案是一样的，然后就可以算出总方案数再除以 n 就可以......” ，
然后抄起笔写出一个式子，就是总方案数，
我靠这式子也贼好懂，全场都笑喷了，这大抵就是“爆踩标程”了吧，复杂度还更优秀。
出题人一脸懵逼，看了眼式子无奈的说了一句好吧那就这样吧。 做法就是考虑每个排列的贡献，枚举颜色的种类再用组合数和第二类斯特灵数算出这样的排列数再乘上贡献。 时间复杂度直接实现都是 $ O(k^2) $ （ k 只有 100 ，可见标程被爆踩），
把斯特灵数那部分的预处理用 NTT 优化复杂度就是 $ O(k logk) $ ，
听说还可以优化到 $ O(k) $ ，不会，但对这题来讲也没必要。

额外肝题

教练还额外发了一套题来着。
扫了遍题目，感觉第二题比较友好：
交换 i, j 枚举顺序后就把那个斯特灵数求和的部分设为函数 g ，
根据斯特灵数的递推，g 这玩意也是可以递推的，中间需要用到一排斯特灵数。
根据斯特灵数的容斥意义 NTT 预处理一排斯特灵数即可（卧槽这不就是上午 t3 吗）。
代码实现中，还没打完，随时准备被打脸。

今天晚上竟然没有颓。

Day8

咕掉了

NEXT

Day9 to END

12 天的培（kao）训（shi），坚持每日总结。

Day9 to Day12.

Day9

考试

炸了，今天出的题好诡异。

第一题一道博弈论，题意好迷，没太看懂就去做后面的题了，
到后面离考试只有 5min 了再回来看 T1, 暴力都好难打，
于是信仰一波 std::cout << 0 << std::endl ，水到了 12' 。

第二题是给出将数组 a 变换到 b 的方式，要求用 b 求 a ，
式子里面有按位或、异或、bicount 什么的，莫非是 FWT ?
于是推式子，如果真的是 FWT 的话求出 a 到 b 的变换应该可以推出 b 到 a 的逆变换。
于是乎我花了一个小时搞来搞去，重新推了一遍 FWT （这个式子真的 6 没办法套用常用的位运算卷积），
果然可以从 a 用分治 3 个 for $ O(n log(n)) $ 变换到 b 。
但是和普通的 FWT 最不一样的就是这玩意不能“蝴蝶变换”，仅从 x, y 两个数推不到新的 x, y 。
woc 那我怎么解方程求逆变换？当时有点绝望了开始怀疑 FWT 做不了，
又去看了看 T3 ，不可做啊似乎，于是决定爆肝 T2 。
我就手玩小数据，推推式子再找找规律，搞了大概 1h 发现把 b 做一遍异或逆变换再乘二再把 b[0] 减去原来的 b[0] 好像就是 a ！
我还证明了它在 n 小于 8 的正确性，然后手玩了 n = 8 时的情况，错了。。。
再次绝望，想了好久大概又过了 30min 吧突然发现之前手玩算错了，我靠重新手玩，完全符合规律。
好嗨哟，感觉人生达到了高潮
快速敲完 KET （ kewth 变换可还行）交了上去，结果最后爆 long long 了，爆 long long 了， long long 了，了。。。
100' -> 60'

第三题交互题，实在没思路就想着能不能卡掉他的交互器来玄学 AC ，
（以下玄学操作，请勿模仿） 为此我研究了大约 40min 的 syzoj 交互原理。
考场上的提交得不到反馈，我就去同样用 syzoj 的 LOJ 上试着提交一下尝试尝试。
然后第一波提交， CE 。。。
改了一下再次提交， wating, wating, wating....
woc 无限 wating? 感觉不对经，看了看 LOJ 的评测记录，然后。。。
woc 自我 CE 代码后的所有评测全是 wating 不动，当时就懵逼了 loj 被我卡爆了？
事实证明只是 loj 卡了一下，过个 3min 的样子就恢复了。。。
我还读了下下发的交互器，于是我搞懂了这玩意的交互原理，
但是实际的交互程序是另一个程序，下发的交互器只是和你的代码一起编译后和交互程序交互，
看了看交互器最后 AC 的输出，然后在 solve 函数里打了份一样的就 exit(0) ，交了。
结果。。。没过，实际评测的交互器和下发的交互器完全不同。。。（但是确实可以卡，后面会说）

讲题

今天的讲题真欢乐，一位大佬屡次上台嘲讽出题人。

T1 就是 dp 啊，加个启发式合并状态，如果不把时间浪费在 T3 说不定能想出来的。

T2 不想说了，心累，在变换过程中做除法就不会爆 long long ， AC 。

T3 随机分治？感觉挺 6 但是没懂。
但是我还是通过奇技淫巧 AC 了。。。

爆掉这辣鸡交互

我还真不信这交互器天衣无缝，再次看交互器，
交了几个错误的程序，发现我能得到的信息只有交互程序给出的信息，
再蠢也不会把重要信息放提示信息里头嘛，感觉似乎没办法了。
又交了一次， CE 了。。。
这时转机出现了，我看了眼编译信息， woc nice 大夫 g++ 给的编译信息真详细：

/sandbox/1/a.cpp:5:6: error: 'QCNT' was not declared in this scope
out,QCNT,'\n';
  ^
/sandbox/1/a.cpp:5:6: note: suggested alternative:
In file included from /sandbox/1/a.cpp:2:0:
/sandbox/1/c.h:74:5: note:   'lkjjhkfdlhgkjdfgf5454::QCNT'
int QCNT;

note 那一排暴露啦，这命名空间 lkjjhkfdlhgkjdfgf5454 也是没谁了（另外还发现了源码的位置 /sandbox/ ）。
但是出题人以为套一个乱七八糟的 namespace 就没事了？
然而还是被我发现了哈，于是通过这个 namespace 直接获取了交互器里存的答案，
成功 AC ，辣鸡交互器。

看了看提交记录，我是第二个玄学 AC 的，第一个的 AC 代码提交时还没有那 sb namespace ，
所以说，我是第一个发现这鬼畜 namespace 并通过它 AC 的 :)
然后从我 AC 后就陆续有人玄学 AC, 代码我都看了一遍，大同小异，全是用这 sb namespace 过的（变量名、注释都跟我的长一个样），
开创先河哈。

后面再改改就是 65B 全场最短 AC 代码。

后来又看了看，还有一名大佬用另一种方式爆掉了这辣鸡交互器。
比我 6 多了，竟然直接搞到了交互器判 AC 的方式给写 solve 函数上了， %%% 。

声明：
交互器确实是可以做到无法被爆破的，
我今天成功爆掉交互主要原因是交互的封装方式漏洞百出，
把交互的主要部分直接给 include 进来了，
正确的方式是将交互的关键部分写在真正处理交互的通过输入输出交互的程序里面。
去看看 loj 的交互题，把附加文件下下来，
那附加文件就是封装了一下和交互器的交互方式，你不用都没关系。

Day10

考试

第一题乍一看要动态维护逆序对？感觉不太可做，后面直接交了暴力， 30 分。

第二题字符串，感觉像是贪心，但是有一些情况不好判断，
最后打了字符串做状态的暴力 DP ，我估摸着复杂度是 $ O(n^3) $ ，
于是就只开了 30' 的部分分的数据的大小的数组 n = 100 ，交了，果然是 30' ，
然而我把数组开到 2000 （ 60' 的范围）后就过了 60' ，这。。。
60' -> 30' 论复杂度分析的重要性。

第三题式子题，乍一看似乎可做，然后简化简化简化，简化成了这样一个题意：

在正整数范围内解方程 x * phi(x) = 2m ，m 已知。

我一看这么简洁的式子，枚举一下 2m 的因子应该差不多了，
一看数据范围： $ m ^{18} $ ，第一档暴力 10' 范围： $ m ^9 $ 。。。
还多组数据，一共 100000 组。。。
连暴力都过不去啊我去。
最后实在没思路，就预处理了一部分 phi 再暴力去搞，结果爆零。。。

讲题

第一题其实真的容易，根本不要动态维护逆序对，
题目要求的只是使逆序对最小的一个循环的位置，
考虑一个数从最左边被扔到最右边后对逆序对数量的影响，其实是不会变的，
维护这个影响的数列，那么就是要求一个最小前缀和的位置，
每次修改就是交换两段区间，虽然逆序对数量会改变，但是根本不用管，相对的影响还是不变的，
那这玩意一个平衡树搞上去就好了。

第二题我似乎摸到正解的前一半了，
贪心把能直接求的字母搞出来后对于剩下的求一个字典序最大后缀好像是，
那这玩意一个后缀数组搞上去就好了。
然而似乎还是要考虑一些情况，还没改出来。

第三题数论神仙题（我竟然以为 T3 可做），
正解复杂度 $ O(log(m)) $ ，神仙做法，
什么二次剩余什么欧拉定理什么质因数玄学分解都用上了，
好难，出题人讲了两遍都没听懂。

Day11

倒计时两天。

考试

第一题平面图上随机游走求到 n 的期望路径？
30' 高斯消元暴力分比较容易想到，其他的就没思路了，想着先去打后面的题。
最后回来打 T1 的时候连高斯消元都没打出来（我太菜了）。。其实是改昨天的题去了

第二题博弈题？乍一看似乎可做，然后简化简化简化，简化成了这样一个题意：

给定数列 a, b, c, 选 a 中的 x 个数替换成任意数使得 $ i: a_{i-1} + b_{i-1} a_i a_{i-1} + c_{i-1} $ 求最小的 x 。

然后这玩意 $ O(n^2) $ DP 嘛 $ O(n) $ 状态 $ O(n) $ 转移，
我以为可以得 10' + 20' + 30' 三个子任务的分，
结果 subtask2 的数据范围比 subtask3 大，但是是一个特殊情况，判掉就好了，我没打。。。
60' -> 40'

第三题没思路，暴力枚举行枚举列枚举每个位置 24k 纯暴力，拿到了 40' 的好成绩。

讲题

第一题解方程线性代数 blabla, 但是看了看 Rank1 的代码，
发现就是一个矩阵乘法，卧槽 $ O(n^3) $ 过 3000 ？
经 *** 分析，平面图上的边数是 $ O(n) $ （最大是 3n - 6 ），
所以高斯消元里的矩阵的点数是 $ O(n）$ 的，
然后就可以根据之前 pics 讲过的方法 $ O(n) $ 做矩阵乘法（ n * n 的矩阵与列向量相乘），
做 n 遍，复杂度 $ O(n^2) $ 。

第二题似乎是最难的，我挂到 40' 都能是全场 rank1 。。。
难点主要在简化题意上，简化后出题人说这就是个普及题了（ woc 我是不是不适合学信息），
DP 可以优化，设一些坐标搞到平面上后将转移用线段树维护优化到 $ O(log(n)) $ ，
但是把所有点对应到平面后，还有种更简单的做法就是求出最长下降子序列 x, 答案就是 n - x 。
这个结论的证明折腾了一下午，还是很妙的。

第三题暴力优化 dfs 可以水 90 分？
正解先枚举行再筛选列将单调性用桶存起来再转移大概是，正在改。

爆肝 Splay

这三天都在爆肝 Splay, 突然又对 Splay 的翻转操作有了更深的理解，
也发现 Splay 真不是那么万能的，许多操作用 Splay 做会多一些不必要的麻烦，
尤其是维护不对称信息还要带区间翻转的时候，似乎根本做不了？
硬要做的话就必须强制让维护的信息对称，
比如要是维护最大前缀和，要支持区间翻转就得还同时维护个最大后缀和。
不说了，去他的信仰，正在学无旋 Treap 。

Day12

最后一天。

考试

第一题已看完题 woc 这不就解方程嘛，手动消消元什么的就行了，
出题人这么良心？于是就开始打，打完后测了测样例， woc 过了。
再把大样例下下来一看， woc 出题人这么良心每道题 5 组大样例？
全都测了一遍，全过了，交了，这个时候考试开始 59min 12s 。。。
但是还是很荒，担心会写炸，然后就对着代码检查检查改了几个细节，
改着改着又测了测时间， woc 要跑 0.9s+ ，这不会被卡常吧？
又慌了起来，但是出题人说不会卡常，还下发了 io 模板，
套上 io 模板后再测 0.2s+ ，松了口气，最后交了一次，
这时候考试开始 101min 15s 。。。
考完后看了下，其实我第一次交就 AC 了，白折腾这么久。。。

第二题神奇题，打了个暴力，期望 60' ，
感觉可以把状态放平面上通过单调性什么之类的优化，
但是没有具体的优化方案（我的计算几何真的是一片空白），
结果最后暴力挂了？只有 10' 啊后面 50' 全 WA 了我一脸懵逼。
还在找错。

第三题哇神仙题，一看就不可做的那种，打完暴力后挣扎了一下，
得到了 30' 的好成绩。

讲题

今天又被爆踩了，T1 A 了一片，拉不开差距。

第二题果然是计算几何神仙题，什么凸包二分三分，什么半平面交，什么李超线段树。
完全不会，只能等我计算几何基础打好后再来重做这题了。

第三题出题人说打表找规律题？反正我是没看出什么规律，
然后出题人证明了一些结论，有这些结论就能 50 行内解决这题了，
正在试图独立证明这些结论。。。

爆肝 Treap

写完暴力自闭之后就滚去学无旋 Treap 了， 看懂后感觉这 split + merge 的操作很 6 。
然后自己写了写，过程中学到一个新操作： 空指针调用成员函数
woc 发现直接用空指针调函数就只要在函数里判一判，调用端省了无数个 if ，

方便死了，然后上午打完下午交了文艺平衡树，
woc 全部 RE ???
把数据下下来，本地跑了一下， AC 。。。
woc 玄学本地 AC 提交 RE ？
改了细节再交，还是全 RE ，
那到洛谷 IDE 上测一下？一测， AC 。。。
woc 玄学洛谷 IDE AC 提交 RE ？

然后 各种测试

最后肝到晚上，终于认识到空指针调成员函数是多么不安全的行为。。。

emm 最后发现 Treap 无论是速度还是码量上都没好到哪去（难道是我实现太烂？），
对于文艺平衡树来说，无旋 Treap 略慢，代码还略长，只是空间消耗略少。

THE END

安徽芜湖 12 天，每天都很充实，虽然也有遗憾。

HNOI 2019, RP ++.