BZOJ 5495
题意：求异或和前$k$大的区间的和。

类似超级钢琴做法，见bzoj 5495
那题查询最大值用的st表，这里是异或区间最大所以想到可持久化01Trie维护即可。

bzoj 3170
题意：给定一个树形图，求他的拓扑序个数。

如果看成拓扑图做那就凉了…据说拓扑图的拓扑序个数是NP的
我们发现这里是一个树形图，那么我们考虑分类讨论边的方向，树形DP
DP是合并思想，最暴力的想法就是，每个点存下一个序列，然后在父亲$u$合并儿子的答案。
具体就是$dp(u) \Leftarrow dp’(u), dp(v)$ ($dp’(u)$为只考虑当前枚举的$v$前的子树，类似DP求树直径方法)
但是显然不能记录那么多，我们考虑设$dp(u, i)$为$u$子树形成的拓扑序，$u$在$i$位置的方案数。这个状态可以让我们知道$u$前有几个数，$u$后有几个数。(以上思想是思考DP不要拘束于状态，而是去想怎么方便怎么做，之后再来看怎么压状态)
考虑$dp(u, i) \Leftarrow dp’(u, j), dp(v, k)$
那么先给出式子(先考虑$u$在$v$前的情况)
$$
dp(u,i)=\sum_{j=1}^{\min(\text{sz}[i], i)} C^{j-1}_{i-1} \cdot C^{\text{sz}[u]-j}_{\text{sz}[u]+\text{sz}[v]-i} \cdot dp’(u,j) \cdot \sum_{k=i-j+1}^{\text{sz}[v]}dp(v, k)
$$
这里是$dp(u, i) \Leftarrow dp’(u, j), dp(v, k)$，即一个序列合并的情况。
前$3$项是说，在$u$的前面的$i-1$个位置，选择$j-1$个位置出来，然后在$u$后面$\text{sz}[u]+\text{sz}[v]-i$个位置选$\text{sz}[u]-j$个位置出来，这些选的位置只有$dp’(u,j)$种填法(保证顺序)。然后其他空位置只能有$dp(v, k)$种填法。注意对于$v$合并后必须到$u$后面，所以对$k$有约束。
然后对于$u$在$v$后，就是$k$的约束不同。然后就可以DP了。
对于复杂度，我们先发现后面$v,k$的东西可以单独前缀和处理，然后前面的$i,j$在$\text{LCA}$处计算复杂度，是$O(n^2)$的。
具体就是，这里相当于枚举$v$前子树和$v$子树的节点，设这一对点为$(a,b)$，这对点当且仅当在$\text{LCA}$处被枚举，所以不会重复枚举，点对个数为$n^2$，类似此题分析的还有很多树形DP题。

Bzoj 2143
题意：见上。

这题暴力就是直接连边跑。
然而我们发现这里连边都是向一个区间连边，那么我们可以考虑线段树优化连边
对每行建线段树，线段树内部父亲连孩子一条边边权为0，然后要连边的话就递归下去找到几个区间连对应边权的边即可。

这题也可以DP。可以将每一步拆开来，设$dp(i,j,k)$为在$i,j$还能免费走$k$步的最小距离。
这里免费是之前交过费以后，类似CF某题

注意本题数组要开够，可以开到$10^7$

知识点
1、线段树优化连边
2、数组大小要算不要偷懒

Bzoj 2118

orz MashiroSky

这题我们设$\text{min}a_i=T$, 则我们只需要去考虑用$n$个数能够组成的数对$T$的模的情况。其他可以用$T$累加倍数得到。因为$T$的灵活性最高。
那么设$dis(i)$表示构成的一个数$k$，满足$k \mod T = i$, 且$k$是最小的满足这个条件的数。
那么对于询问$x$能否组成，进行分讨
$dis(i) \leq x$时，可以拼成
而反之则不能。
那么我们求出$dis(i)$的值就能解决这题了。
考虑最短路模型，设$[0,T)$为点，每个点$i$连到$(i + a_j) \mod T$, 边权为$a_j$，最短路一遍即为答案。
对于区间$[\text{Bmin}, \text{Bmax}]$的数，公式求一下即可

知识点：
1、同余最短路模型
2、最小数的运用

Loj 2652
题意：见上。

设$g(i,j)$为$i \to j$的路径条数，那么设$F(i)=g(S,i) \cdot g(i,T)$
可以发现第一个条件等价于$F(A)+F(B)=F(T)$的$A,B$
第二个条件即$A,B$不为前驱后缀关系

那么第一个条件用一个map优化，第二个条件我们可以求出最短路图，然后传递闭包，bitset优化

第一个条件和第二个条件的可能点的交集即为答案。

知识点：
1、Bitset空间

Codeforces 24D
给你一个$n×m$的棋盘，你初始在$(x,y)$，每一步等概率不动、向左、向下或向右走（如果向左走会越界则该步等概率不动、向右、向下走，向右会越界同理, 走到最后一行就结束, 问从开始到结束的期望步数

很容易设出方程$f[i][j]$表示从$(i,j)$走到最后一行的期望步数

$$
\begin{align}
f[i][1]&=\frac{1}{3}(f[i][1]+f[i][2]+f[i+1][1])+1, j=1\\
f[i][m]&=\frac{1}{3}(f[i][m]+f[i][m-1]+f[i+1][m])+1, j=m \\
f[i][j]&=\frac{1}{4}(f[i][j]+f[i][j-1]+f[i][j+1]+f[i+1][j])+1, 2 \leq j \leq n - 1\\
\end{align}
$$

初始化$f[n][j]=0$

那么我们发现这个方程是有后效性的。

其实行与行之间还是有无后效性的，但是列之间不满足。

考虑整理化简。我们将$f[i+1][]$看作常数，那么可以列一个方程组解出所有的$f[i][]$

即化成$a \cdot f[i][j] +b \cdot f[i][j - 1] + c \cdot f[i][j +1]=d+e \cdot f[i + 1][]$的形式

那么我们可以高斯消元解出来。

我们发现这里的每列最多三个有值，那么我们可以用特殊方法来求值，这里用倒三角的矩阵好做点，比直接求出简化阶梯矩阵好求，具体看代码

然后注意特判$m=1$即可，也可以直接输出$2n-1$，具体可以从高斯消元来推导，然后递推式转成封闭形式

BZOJ 5290
题意：见上。
一开始没看见必须选边…
然后发现是树形DP然后打……
之后发现我写假了
我们直接设$dp(u,i,j)$为$u$到根经过$i$条绿边，$j$条红边的最小代价
那么转移即
$$
dp[u][i][j] = \min(dp[lc[u]][i][j] + dp[rc[u]][i][ + 1], dp[lc[u]][i + 1][j] + dp[rc[u]][i][j])
$$

然后这题一个精髓是卡空间方法，我们维护一个dfn，然后每次存两个孩子的值即可，具体可看代码。

知识点
1、dfn卡空间方法

Spoj GSS 系列….

BZOJ 1492
题意：金券交易所可以对$A 、B$两种金券进行交易。
接下来的$N$天内，第$i$天$A、B$分别具有单位价值$A_i,B_i$,每一天用户进行若干次如下操作:
1、卖出所有的金券
2、用所有的钱买入等价值的金券，买入的$A、 B$两种金券的比例为$\text{Rate}_i$
初始时用户拥有$S$元钱，问$N$天后用户最多拥有多少钱?

可以证明每次一定全卖或者全买，不严谨证明是有利可图就尽量做，否则就不做。

具体证明即设有$S$元钱，我们设卖出单位收益为$p$, 不卖单位收益为$q$，卖出比例$x$, 则收益为$S \cdot x \cdot p + S \cdot (1 - x) \cdot q=S(x(p-q)+ q)​$
当$p-q \geq 0$时，取$x=1$有最大值
当$p-q \leq 0$时，取$x=0$有最大值
所以得证。

那么设$f(i)$为前$i$天的最大收益。
则
$$
f(i)=\max_\limits{1 \leq j \leq i-1}(f(i-1),A_ix_j+B_iy_j)
$$
其中$x_j, y_j$为最多能买到的$A,B$劵数量。
由
$$
\begin{cases}
f(j)=x_iA_j+y_iB_j \\
\frac{x_j}{y_j}=\text{Rate}_j
\end{cases}
$$
可算出$x_i, y_j$的值。
那么考虑斜率优化，我们可以得到
$$
y_j=-\frac{A_i}{B_i}x_j+\frac{f(i)}{B_i}
$$
但是这里$x​$和斜率都不单调怎么办？
考虑动态维护上凸包。可以用平衡树来维护，即每次插入一个决策点，如果这个决策点和它$x​$最近两个点连后形成下凸，则不用加这个决策点，否则向左找到一个最远的能形成凸包的，右边同理，然后将这两个点之间所有决策点删除，插入这个决策点，形成新的上凸包。可以用Splay来维护，也可以用Set

因为一个位置的决策集合是它前面的点，所以我们可以考虑CDQ分治。具体步骤为

若$l=r$则返回。
把左区间按编号把$≤mid$的分到左边，大于$mid$的分到右边。
分治左区间CDQ(l,mid)。
此时左区间横坐标有序，右区间斜率有序，所以用单调队列斜率优化DP。
分治右区间CDQ(mid+1,r)。
按$x$归并排序。

即左边构造好上凸包，用来更新右边的答案

模板及讲解

定义

$Prufer$数列是无根树的一种数列。在组合数学中，$Prufer$数列由有一个对于顶点标过号的树转化来的数列，点数为n的树转化来的$Prufer$数列长度为$n-2$。它可以通过简单的迭代方法计算出来。

将树转换为$prufer$序列

总体的思路是迭代删点，直到原图中只剩下两个点。对于一棵树$T$,我们已经将每次找到树中标号最小的叶子结点，将这个叶子结点以及与它相邻的边删去，将与叶子结点相连的点加入数列中。重复上一步，直到原图中只剩下两个点。

将$prufer$序列转换为树

将结点列一个集合$A=(1，2，\dots ,n)$在集合$A$中找出一个没有在$prufer$数列中出现的最小的值，将这个值在集合$A$中删去，并且将这个值和$prufer$数列中的第一个数连起一条边，并划去$prufer$数列中的第一个值，重复此步，直到集合$A$中只剩下两个数字，将以这两个数字为编号的结点连起一条边。