0902练习

· · 个人记录

A [HNOI/AHOI2018]道路

记忆化搜索,枚举当前哪里不修，暴力向下递归。有树高限制保证复杂度正确

code

B CF321D

hdhd讲的装呀枚举。通过规律找独立和有关的量，把独立的单独算，减小枚举量。

code

C

没写听直通车说很恶心 谷谷谷谷

upd

A题并不是那道题

真正的题面

因为是练习，所以看错题了也没发现

后来交到oj上过不了才发现题不一样。。。

真正的题面：把上面的A改成二叉树不变，选路任意选n条的的答案

然后这样就大概有两种做法 第一种出题人是给的正解wqs二分，不会。。德福写的这个可以看他博客

第二种是中天城给的方法

f[x][i][j][k]表示在x子树中选k条，在x到根的路径上选i，j条公路和铁路的最小代价

然后猜一波最后一维是个凸的，写个闵可夫斯基和合并dp数组就行了

可以理性分析，复杂度是O(n\times maxdep^3)

常熟很小，比O(n\times maxdep\times log)的wqs二分快不少。。。

空间很大，要套三层vector加滚动，用完就clear然后和空vector交换这样省空间

code

upd \times 2

因为太 懒 菜了，0903的比赛只补了一道题，干脆放到这里

题面

两种做法:一种是直接多项式去搞他，后一行等于前一行\times (bx+a)，往前推就多项式求逆。可以进行一个简单的卡常，就是先求出第一行，后面就不用多项式求逆了。

第二种是考虑p行的每一个数对你当前的这个数的贡献。具体可见这里

感觉第二种好写，狮子也不难推。于是就写的第二种。没想到我高估了自己。。。柿子推错字比了好久草

code