Codeforces 1106E
题意：给定一个$n$长值域为$m$的序列，你要将其组成尽可能多的三元组$(a, b, c)$满足$a=b=c$或者$b=a+1,c=b+1$。
一开始读错题了。
先将所有数存在一个桶里，按数大小来DP。
显然对于一种方案$(a,b,c)$，他只会重复至多$2$次。
那么对于一个方案$(i,i+1,i+2)$，他最多只会有$2$个
那么设$dp(i,0/1/2,0/1/2)$为前$i$个数，第一个数是$i$的三元组个数，第二个数是$i$的三元组个数的最大个数。
转移
$$
dp(i,a,b)=\max_{0\leq c \leq 2}(dp(i-1,b,c)+c+(cnt-a-b-c) / 3)
$$
其中$cnt$为$i$数的个数。
后面$(cnt-a-b-c) / 3)$等价于将多余的$i$组成三元组$(i,i,i)$
hdu 5608
题意：给定$n$和函数$f, g$满足
$$
g(n)=n^2−3n+2\\
g(n)=\sum_{d|n} f(d)
$$
求
$$
\sum_{i=1}^n f(i) \mod 10^9+7
$$
显然$f * I = g$，杜教筛即可。
即
$$
S(n)=\sum_{i=1}^n g(i) - \sum_{i=2}^n S(\lfloor \frac nd \rfloor)
$$
将$g$每个项分离出来，用平方数列前缀和公式+等差数列公式即可求解。
对于前$n^{\frac 23}$的$f$，反演一下即可。即
$$
f(n)=\sum_{d|n} g(d) \mu(\frac nd)
$$
注意这个式子不是很常用。
LCT，也就是Link-Cut Tree的缩写。它是最常见的一种解决动态树问题的工具。不过说它是树也不准确，因为它维护的可以是一片森林。
将某一个儿子的连边划分为实边，而连向其他子树的边划分为虚边。
区别在于虚实是可以动态变化的，因此要使用更高级、更灵活的Splay来维护每一条由若干实边连接而成的实链。
LCT维护的对象其实是一个森林。
1、每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历Splay得到的每个点的深度序列严格递增。
2、每个节点包含且仅包含于一个Splay中
3、边分为实边和虚边，实边包含在Splay中，而虚边总是由一棵Splay指向另一个节点（指向该Splay中中序遍历最靠前的点在原树中的父亲）。
Bzoj 2730
题意：给一张无向图，让你加一些出口，使得任意点删除后图上任意点都能找到出口。
复习一波点双联通分量
考虑求出割点和双联通分量，然后对于每个双联通分量，我们考虑
若这个双联通分量有两个及以上割点，那么不需要建立出口
若这个双联通分量有一个割点，那么如果这个割点删了这个图就找不到出口了，要加一个出口
若这个双联通分量没有割点，即这个子图与其他子图不连通，要加两个出口
加出口即加在任意非割点的点上即可
BZOJ 1911
题意：有$n$个数$x_i$，将其分成连续的组，每组的分为$a\sum x_i + b\sum x_i +c$，求最大的总分。
设$dp(i)$为前$i$个分组的最大的总分。设$\operatorname{sum}(n)$为$\sum\limits_{i=1}^n x_i$
则
$$
dp(i)=\max(dp(j)+a[\operatorname{sum}(i)-\operatorname{sum}(j)]^2 + b[\operatorname{sum}(i)-\operatorname{sum}(j)] + c)
$$
则决策点可以表示为点$(\operatorname{sum}(j), dp(j)+a \cdot \operatorname{sum}(j)^2 - b \cdot \operatorname{sum}(j))$
这里要维护最大值，所以与之前的斜率优化不同，维护一个上凸包即可。
注意有负数时不要用叉积，符号不能确定！
知识点
1、有负数时不要用叉积，符号不能确定
3768 简单的数学题
题意：给定$n, p$，求
$$
\sum_{i=1}^n \sum_{i=1}^n ij\gcd(i,j) \mod p
$$
枚举约数
$$
\sum_{d=1}^n d\sum_{i=1}^n \sum_{i=1}^n ij [\gcd(i,j)=d]
$$
将后面的提取因数
$$
\sum_{d=1}^n d^3 \sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{i=1}^{\lfloor \frac nd \rfloor} ij [\gcd(i,j)=1]
$$
将布尔式化成$\mu$
$$
\sum_{d=1}^n d^3 \sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{i=1}^{\lfloor \frac nd \rfloor} ij \sum_{k|i,k|j}\mu(k)
$$
先枚举$k$
$$
\sum_{d=1}^n d^3 \sum_{k=1}^{\lfloor \frac nd \rfloor} k^2 \mu(k) (\sum_{i=1}^{\lfloor \frac n{kd} \rfloor} i)^2
$$
设$T=kd$
$$
\sum_{T=1}^n (\sum_{i=1}^{\lfloor \frac nT \rfloor} i)^2 \sum_{d|T}d^3 (\frac Td)^2 \mu(\frac Td) \\
\sum_{T=1}^n (\sum_{i=1}^{\lfloor \frac nT \rfloor} i)^2 T^2\sum_{d|T}d \mu(\frac Td)
$$
后面是个卷积形式，根据$\mu * id = \varphi$
$$
\sum_{T=1}^n (\sum_{i=1}^{\lfloor \frac nT \rfloor} i)^2 T^2 \varphi(T)
$$
现在要求$T^2 \varphi(T)$的前缀和。不妨先设$g=id^2$
$$
(f * g)(i)=\sum_{d|i} d^2 \varphi(d) \times id^2(\frac id) \\
= \sum_{d|i} d^2 \varphi(d) \times (\frac id)^2 \\
= \sum_{d|i} i^2\varphi(d) \\
= i^2\sum_{d|i} \varphi(d) \\
= i^3
$$
则
$$
g(1)S(n)=\sum_{i=1}^n(f * g)(n) - \sum_{i=2}^n g(i)S(\lfloor \frac ni \rfloor) \
S(n)=\sum_{i=1}^n i^3 - \sum_{i=2}^n i^2 S(\lfloor \frac ni \rfloor)
$$
再由两个公式
$$
1^3+2^3+ \dots + n^3 = (1+2+ \dots + n)^2 \\
1^2+2^2+ \dots + n^2 = \frac{n(n+1)(2n+1)}{6}
$$
即可完成求解
坑：
1、$n$要运算时一定要先模，否则$10^{10} \times 10^{10}$马上爆炸
2、$2n$也要模
知识点：
1、整除分块只有$\lfloor \frac nd \rfloor$部分相同，可以用来乘
2、Dirichlet卷积运用
3、LCM和那题没搞明白的东西
4、预处理逆元免除$\log$
Loj 2632
题意：见上。
做法($(c=容量, w=费用)$)：
将每天拆点拆成$x_i,y_i$($x$为脏餐巾点，$y$为干净餐巾点)
1、$S$到$x_i$：$(r_i, 0)$，补脏的 (用过的毛巾假设全丢掉，然后再从$S$补偿脏毛巾。以达到一个毛巾用$n$次有流量$n$)
2、$S$到$y_i$：$(∞, P)$，买入毛巾
3、$y_i$到$T$：$(r_i, 0)$，使用毛巾 (用过的毛巾假设全丢掉)
4、$x_i$到$y_{i+M}$：$(∞, F)$，快洗
5、$x_i$到$y_{i+N}$：$(∞, S)$，慢洗
6、$x_i$到$x_{i+1}$：$(∞, 0)$，存着脏毛巾
上述博客思路为：
1、先拆点，然后考虑快洗慢洗、不洗(存着脏毛巾)
2、发现错误(一个毛巾用两次只有流量$1$)，修改为舍弃流和补偿流
知识点：
1、资源调配问题，舍弃流和补偿流的方法
poj 3709
题意：给定一个数列 $a$， 分成若干段，每段至少有$k$个数， 将每段中的数减少至所有数都相同， 求最小的变化量
设$dp(i)$为前$i$个的最小变化量。
则
$$
dp(i)=\min_{i-j \leq k}(dp(j)+\operatorname{sum}(i)-\operatorname{sum}(j)-i \cdot a_{j+1} +j \cdot a_{j+1})
$$
显然可以斜率优化。决策表示为$(a_{j+1}, dp(j)-sum(j)+j \cdot a_{j+1})$，即可算斜率。
注意$i-j \leq k$的限制，我们可以考虑延迟加入决策(具体看代码)，预处理$[0,2k]$的答案。
知识点
对于这种有限制的斜率优化可以考虑延迟加入决策
Codeforces 1106E
题意：有 $k$ 个区间 $[s_j, t_j]$ 表示一段时间，每个区间有 $t_j, w_j$ 表示若选择这个区间则 $t_j$ 后才能选其他的区间，选择区间的权为 $w_j$ 。现在有一个人从 $1$ 时刻开始选区间，他会选当前能选的最大权的区间，若存在多个，选 $d_j$ 大的区间。现在有 $m$ 次机会，每次可以使得这个人在某一秒不能选区间。求当这 $m$ 次机会使用得最优时，这个人最小能选择区间权和。
正序DP不太好做。
考虑倒序DP，设$dp(i,j)$为$[i,n]$用了$j$次机会的最小权和。
则
$$
dp(i,j)=\min(dp(i+1,j-1),dp(i+1,j),dp(g, j))
$$
其中$g=\max\limits_{i \in {[s_j, t_j], j\in[1,k]}}(d_j)$
这个$g$可以用set维护。
具体就是将区间端点存起来，然后枚举时间线时看是否超出了，超出即删掉，如果有新的加入，就加入。
BZOJ 3930
题意：给定$n,K,H,L$，求
这个形式和在$[1,n],[1,m]$中的$gcd$类似，我们从$N=2$开始考虑。
显然
$$
f(k)=\sum_{d=1}^{\lfloor \frac nk \rfloor} \mu(d) \left \lfloor \frac n{kd} \right \rfloor^2
$$
扩展到高维也类似，所以可以得到
$$
f(k)= \sum_{d=1}^{\lfloor \frac Hk \rfloor} \mu(d) \left (\left \lfloor \frac H{kd} \right \rfloor - \left \lfloor \frac {L - 1}{kd} \right \rfloor \right )^n
$$
然而$\lfloor \frac Hk \rfloor$是$O(H)$级的，不能满足。
引理：
当所有数不全部相同时，$\gcd\left ( i_1, i_2, \dots, i_N \right ) \leq \max\left ( i_1, i_2, \dots, i_N \right ) - \min\left ( i_1, i_2, \dots, i_N \right )$
证明：设$d = \gcd\left ( i_1, i_2, \dots, i_N \right ), a = \min\left ( i_1, i_2, \dots, i_N \right ), b = \max\left ( i_1, i_2, \dots, i_N \right )$
显然$a = k_1d (k_1 \in \mathbb{Z}^+), b = k_2d (k_2 \in \mathbb{Z}^+, k_2 > k_1)$， 所以$b - a \geq d$，证毕。
所以$[H, L]$中的一个不全部相同的序列的$\gcd$不会超过$H - L$个，只用处理不全部相同的序列，所以可以得到
$$
f(k)= \sum_{d=1}^{\lfloor \frac Hk \rfloor - \lfloor \frac {L-1}k \rfloor} \mu(d) \left( \left (\left \lfloor \frac H{kd} \right \rfloor - \left \lfloor \frac {L - 1}{kd} \right \rfloor \right )^n - \left (\left \lfloor \frac H{kd} \right \rfloor - \left \lfloor \frac {L - 1}{kd} \right \rfloor \right )\right)+[L \leq k \leq H]
$$
注意需要加上$[L \leq k \leq H]$，因为这样就可以选$n$个$k$。
本题也可以直接杜教筛筛出$\mu(d)$的前缀和，但是我并不会……等学了杜教筛再来填坑吧。