2018.8.9 test
t1:Nim博弈中,先手必败当且仅当异或和为0(先记下来~)
我当然是没做这道题了。。。根据异或和的性质状压dp即可。
t2:思路很简单,但调试很操蛋
为了能够对拍我花了一晚上装VMware与noilinux,结果到现在才大致搞好
思路就是(离线)用单调栈求凸包,用树链剖分模拟蚂蚁的移动即可。
t3:树状数组求lis,然后就没了
据zyf描述其过程十分繁琐。

Ich bin 分界线


2018.8.13 test
t1:多项式求幂$O(nlog_2n)$,XZY使用“多项式快速幂”$O(nlong^2_2n)$成功A掉此题。
40分解法是枚举组合,使用(高超的)位运算技巧以及状压来去重。
t2:一开始的思路就不对,一直想着边双缩点,没有意识到双连通分量的本质是搜索树。
结果我的思考最终得出了这样的结论:我需要求出“边三连通分量”并缩点来统计答案(鬼知道这个怎么求)。
然后中午就被猜测“听起来这很像一个NPC问题”,下午老师讲课时说道“好像要求一个三连通分量才行…但是没人知道这个怎么求啊”
正解:求dfs树,讨论去掉两条树边还是一条树边一条非树边,统计答案。
t3:我要告分数欺诈…题目下面明明写了$O(n^2)$暴力有60分的…
dp递推算是比较好想,需要用到费马小定理求逆元,注意转移时的期望值与总值的转换。
至于正解….
告辞。

Ich bin 分界线


2018.8.14 test
毕姥爷出题,难度果然不同凡响,数据非常有梯度。
t1:令人根本摸不着头脑的题,直到讲题的时候才大致搞懂一点。
主题思路是计算胜率,然后按照胜率下注就行了。dp求胜率70分,组合数求胜率100分。
t2:毕姥爷写的solution一个字都看不懂,还是abs的讲解比较贴合我的水平。
考场上打了一个sb乱搞版线段树,证实了标记下放到底就算是随机数据也不如暴力。
正解其实很简单…依然是线段树,每个节点维护一个函数的k-1个系数,复杂度$O(knlong_2n+100n)$,然而我就是想不到…
t3:毕姥爷表示这道题很简单很简单…
让我们看看有多简单:
1. 162阶递推数列打表
2. 学会矩阵树定理(哦这证明过程比邻居家约翰大叔的院子里的毛毛虫还长)
3. 学会行列式求值(某本线性代数被放在了在600海里外的某个机房里)
4. 学会$Berlekamp-Massey$算法(全机房只有zyf会的冷门高深算法)
我还是不要学OI了…
一点改的欲望都没有。
怎么t3画风都这么奇怪的吗…

Ich bin 分界线


2018.8.15 test
我几乎写完了,被zyf弄没了。

Ich bin 分界线


2018.9.8 test
据说是多校联考,T1、T2普及组难度,T3湖南省选难度。
t1:完全背包。
t2:简单的树形dp。维护节点子树深度的最大值与(不严格)次大值,进而维护一个节点的顶上最长路径。
打完之后发现过不了大样例,完全没法调试。之后用abs的程序对拍发现是次大值没有更新好。改了就A了。
t3:一看数据范围就猜是找规律题,然后dp找规律失败。看了题解,发现我的状态和题解的状态很像,然而并不能正确转移。如果成功做出有机会拿40分。
正解的话貌似是打表然后用$Berlekamp-Massey$算法解出递推式,然后使用矩阵加速DP。
BM是不可能学的,这辈子都不可能学的。。。不过这道题提醒了我所有以“矩阵”为子串的算法我都不会,是时候学一波了。