发现 $loj$ 真的好用……比 $luogu$ 不知道清爽到哪里去了，更何况 $loj$ 的题目也更多，而且提供数据和代码，更加开放。估计以后都会在 $loj$ 上多逛逛。( $bzoj$ 是真的丑，除非是做 $bzoj$ 的原创题不然我不会上 $bzoj$ 的) 。

顺便贴一下题目传送门：$loj$的传送门就戳我啦(～￣▽￣)～

概率 $\texttt{DP}$ ，设 $f_{i,j}$ 表示打了前 $i$ 张牌，还有 $j$ 轮没有打出牌的概率。我们枚举第 $i+1$ 张牌，分别讨论一下该牌打出与不打出的情况即可。

愉快的推式子吧(ﾉ≧∀≦)ﾉ！

设 $f_i$ 表示前 $i$ 根柱子完工后的最小代价。枚举一个小于 $i$ 的 $j$ ，表示为从 $j$ 向 $i$ 连了一座桥，中间的柱子当然全部推掉，计算一下就好：

*其中 $s$ 为 $w$ 的前缀和。

差不多搞懂了斜率优化吧……说实话网上的文章都写得很迷，还好找到了一个不错的文章：转送门戳我(￣▽￣)~* 。(为什么突然发现这道题和诗人小G很像呢)

这个 $\texttt{DP}$ 方程谁都会设：设 $f_i$ 表示前 $i$ 个玩具的最小费用，转移显然如下：

(其中 $sum$ 是前缀和)。这个复杂度是 $O(n^2)$ 的，过不去……

依旧是斜率优化的套路。

设 $f_i$ 表示前 $i$ 个士兵的最大贡献，转移显然是枚举一个 $j$ ，将 $j+1$ 到 $i$ 这些士兵组成特别行动队算贡献：

其中 $s_i$ 为战斗力的前缀和。这个方程是 $O(n^2)$ 的，需要优化。发现这个转移式貌似不满足单调队列优化的条件，于是将中间的式子拆开看看可不可以斜率优化。

发现数据范围很小，并且涉及到”集合”，很容易可以想到用状压 $\texttt{DP}$ 。

设 $f[i][j]$ 表示已经抛出了 $i$ 次宝物，获得的宝物集合为 $j$ 时的最优分值。那么转移的时候枚举每一个宝物，分两种情况即可——选当前宝物或者不选。注意选当前宝物的前提是必须满足前提，按照最优情况选取即可。注意最后将所有的宝物的贡献加上后还需要$/n$ ，因为题目要求的是”平均”。

这道题一共有两问，第一问瞎搞 $\texttt{DP}$ ，第二问如果直接 $\texttt{DP}$ 的话复杂度是 $O(n^4)$ 的过不去，这个时候需要用到决策单调性优化复杂度就可以降低至 $O(n^3)$ ，这样就过了。我们先来讨论一下第一问的做法。

时间的范围太大了，我们需要离散化一下。离散化后时间就控制在 $0$ 到 $2n$ 的范围内了。

首先可以发现最终的答案一定就是一段一段时间，每一段时间内的活动都是在同一个会场举行。我们可以预处理一个 $tot_{l,r}$ 表示完全在时间 $l,r$ 之内的活动有多少个。计算直接暴力，预处理的复杂度为 $O(n^3)$ 。

看懂了后发现 $\texttt{DDP}$ 其实不难呢……

其实主要思想就是将 $\texttt{DP}$ 转移式搞到矩阵上，然后如果是树形 $\texttt{DP}$ 的话就可以直接上树剖或者是 $LCT$ 进行维护，当然还可以用全局平衡二叉树(不费) 。如果只是线性的话可以直接用线段树等数据结构进行维护了。

注意这道模板树剖的复杂度是 $O(nlog^2n)$ ，而 $LCT$ 的复杂度为 $O(nlogn)$ ，于是窝选择了 $LCT$ ，跑的还挺快。

要是我不是 $\texttt{HN}​$ 的该多好，今年十二省联考两道傻逼题，一道异或粽子，一道十二响……

[十二省联考2019]异或粽子，可持久化 $trie​$ 树的板子题，比最大异或和还要板子些。相信 $60​$ 分入门者都会做，那么 $100​$ 分的话我们上可持久化 $trie​$ 树维护前缀异或和，嗯没错就像主席树那样。然后对于每个节点的可持久化 $trie​$ 树我们将其当成区间右端点，然后在此位置上的 $trie​$ 树中贪心寻找左端点即可。

要是我不是 $\texttt{HN}$ 的该多好，今年十二省联考两道傻逼题，一道异或粽子，一道十二响……

[十二省联考2019]春节十二响，启发式合并裸题。对于树中的一个节点 $u$ ，从其子树中选择一段的方式显然只能是从 $u$ 的所有子树中各选出一个节点。于是我们每一个节点开一个堆，存的就是其子树中(包括自己)的所有段的内存。

然后从下往上启发式合并即可，复杂度大约是 $O(nlogn)$ 。