安徽游记 II
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
咕掉了