Baka's Blog

「雅礼集训 2018 Day7」C 考虑一个乱走的过程，可以发现在某个点，除了最后一步（停止），每一步的期望长度都是所在的点到所有点距离的平均数。 那么考虑记录每个点走了多少次。热动分析一下发现所有同色点的期望次数都是一样的。 那么搞一个DP，令$f_{i,0/1}$表示有$i$个$1$，$0/1$

[SDOI2019]世界地图 只需要把前缀后缀的MST合并。考虑加入边的过程，只会删掉原来的环上的边。也就是说明只需要维护一些环即可。进一步的，可以把环上的链缩起来。 想法很简单，之后代码就不会写了。。网上冲浪后学习到了实现技巧： 直接暴力Kruskal合并两棵树。之后只需要在新树上缩掉一些边即可。

树上的数 首先，枚举数字，再枚举目的地，贪心。先考虑一下菊花图怎么做： 对于菊花图把边的选择顺序写出来，发现可以串成一条链。对于一次移动，可以发现限制是两条边必须一前一后的移动。那么用一些数据结构维护这个东西就可以了。 考虑一般情况，对于一次$x \rightarrow y$的移动，有这样的限制：$

[JSOI2019]神经网络 一条合法的哈密顿路，由两部分组成：每棵树拆成一些独立的链，把链串起来。 考虑如何把树拆成链。令$f_{x,i,0/1/2}$，表示$x$子树内划分为$i$条，并且有$0/1/2$个链连上来。对于子树$y$，是从$y$连上来，对于当前考虑的$x$，是连到$x$的。那么就可

上古时代的题啊。。都没地方交。。找到题面了，口胡一下： T1 有一支n个人的队伍要过一座限重为W的桥，我们规定这支队伍过桥时只能分组过，即当一组全部过去后，下一组才能接着过。给定每个队员的重量wi和过桥时间ti，一组人的过桥时间为花费时间最多的人的时间。问如何分组使得总的过桥时间最短。 对于100

CF1336E2 Chiori and Doll Picking 求一个线性基出来，求一下线性基可以表出多少数就好了。那么有一种简单暴力：直接枚举。加上折半搜索就可以过弱化版，不加折半搜索的复杂度是$O(2^r)$的。 还可以构造另一种算法：考虑令$f_{i,j}=f_{i-1,j}+f_{i-1,

[SDOI2017]切树游戏 orz rqy。首先可以知道，维护每种值的方案即可。令$F_x$为$x$为根的子树的集合幂级数，只需要用$\prod (F_y+1)$更新即可。 那么无脑FWT一下。之后考虑动态化。那么就维护轻儿子和重链。令$H_x$表示$x$轻儿子合并后的东西，那么有$F_x=H_x

[十二省联考2019]皮配 题目描述太长是真的难受… 洛谷题解里有个很有意思的简化版题意：豆子有黄色绿色，圆粒皱粒。豆子有重量，每种性状的豆子有重量和上限。同时有一些豆子钦定不能有某种性状。告诉了有多少豆荚，每个豆荚里每个豆子，豆荚里豆子颜色要一样，求方案。 那么就有一种DP的想法：因为两对相对性状

金融风暴 先orz Claris 好像是很经典的做法。考虑一行左边两个点的答案更新右边的某个点。不难发现是有决策单调性的。右边更新左边同理。那么把每个点的初始距离设置为上方/下方最近的点，并对每一行分分治即可。至于查询用二维ST表就可以。 1 2 3 4 5 6 7 8 9 10 11 12 13

CF590E Birthday 首先字符串的包含关系可以直接AC自动机。需要找出每个串能匹配到的所有子串。根据下文中提到的东西，只需要找出每个位置为结尾，能匹配到的最长串，即$fail_x$能匹配到的串即可（传递性）。 之后，得到偏序关系。要求的就是它的最长反链，也就是最小链覆盖。注意Dilwort