记录
hdxrie
·
·
个人记录
对于要把两种物品分开，或者是将某个物品划分成两份，划分有代价，要代价最小，可以将代价变为容量，求最小割：
[NOI2010]海拔
[ZJOI2009]狼和羊的故事
二分图思想比较好的题：
最小路径覆盖问题
分层图：
[CTSC1999]家园
孤岛营救问题
汽车加油行驶问题
最大点权独立集：
骑士共存问题
考察建模能力的题：
[ZJOI2010]贪吃的老鼠
[HNOI2013]切糕
费用流好题：
[CQOI2012]交换棋子
原来最大流的模板太丑了，居然过不了下面这个题，然后优化了模板：
[SDOI2014]LIS
求树的带权重心题目
[ZJOI2015]幻想乡战略游戏
对于位运算，由于每个二进制位互不影响，遇到位运算的题可以对每一位分别考虑：
洛谷树
T33808 XOR最小生成树
二进制位太多可以考虑压位
[NOI2017]整数
二进制状压枚举真子集
for(int S0=(S-1)&S;S0;S0=(S0-1)&S)
考虑某个操作只对树上的一条链的某个信息有同样的影响，可以考虑树上差分：
运输计划，[JLOI2014]松鼠的新家
在树上，一个点a与其他所有点的LCA在a到根的路径上，那么对于求两个点的LCA的深度，可以将其中一个点到根的路径上的点都加1，那么另一个点到根的路径上的点权和就是他们的LCA的深度：
[LNOI2014]LCA
对偶图：
P4001 [BJOI2006]狼抓兔子：特殊图的最小割，特殊之处在于边不会相交，那么求最小割可以转对偶图求最短路，对偶图的起点为原图源点与汇点连边所形成的平面，终点为无限区域。
P4675 [BalticOI 2016 day1]Park，NOIP模拟20180708屋漏偏逢连夜雨：如果两个物体之间无法通过，则视作它们之间连了一条边。
对偶图上的连通对应原图的不连通。
利用并查集快速查询可操作区间：
[COCI2010-2011#5] SLIKA
P4145上帝造题的七分钟2 / 花神游历各国
[NOI2017]蔬菜
Kruskal重构树：
一般用于需要用到kruskal求最小生成树的中途连通情况的题
[ONTAK2010]Peaks加强版
T33035 迷宫
[POI2018]Powódź
DFS序：
对于子树查询，可以用DFS序来维护，因为一个子树的节点在DFS序上是连续的一段：
[ONTAK2010]Peaks加强版
平方的期望不等于期望的平方,因此要单独求出平方的期望
BZOJ4318 OSU!
期望的线性性
（一般用这个思想的都是状态数是有限个的情况）
利用期望的线性性，可以考虑把大的期望拆分成小的期望。这道题首先看到期望被染黑的格子数，等价于有多少个格子期望被染黑，等价于每个格子最后被染黑的概率累加。
BZOJ2969 矩形粉刷
原本是累加每一种情况的时间复杂度×其发生概率，考虑期望的线性性，实际上就是累加每一个点期望被计算多少次。
bzoj3451|Tyvj1953 Normal
通过推公式可以发现神奇规律：
[Lydsy1711月赛]摘苹果
原本是期望DP，因为乘了一个n!，变成了组合数。不会这道题，看了题解发现思想挺巧妙，原本是跟二叉树的形态有关，不过这样并不好思考，事实上答案与一条边被经过的次数有关，为了保证方便确定边，保证不重不漏，我们就把点i到其父亲的这条边和点i绑定，这样就会方便很多，有时候要学会换一个角度思考：
[HAOI2018]苹果树
对于有多种条件，只需要有一个条件满足，这个情况就成立，这是“或”的关系，但是概率中一般求“与”比较容易，所以有时候可以考虑求发生相反情况（也就是“与”的情况）的概率减去总概率
[SHOI2014]概率充电器：维护一个点不会被充电的概率太麻烦，因为是一个树的结构，可以考虑维护其父亲不会给它充电的概率和其子树不会给它充电的概率。
期望好题
[HDU4035]Maze
比较好的题解
感觉难在推公式，而且不好想到化成统一形式，然后回代求出统一形式的系数的递推式。
似乎一般树上的期望，都是将父亲和儿子分开考虑，而且一般在DP转移时会保留父亲有关的东西。
完全K叉树：
T33586 K叉树：
fa[x]=\left\lfloor\frac{x+k-2}{k}\right\rfloor
deep[x]=\left\lfloor log_k^{x\cdot(k-1)}\right\rfloor(k≠1)
令next为KMP处理字符串的时候对应的失配下一位，那么一个前缀的最小循环节=i-next[i]
T33639 最小周期
[Lydsy1712月赛]字符串的周期
利用最小表示法减少数值相同状态数
[Lydsy1712月赛]字符串的周期
树形DP好题：
网络测试
KMP的特殊匹配套路
BZOJ4641 基因改造：
匹配条件：匹配位置的字符上一次出现位置与其距离要求相同。那么可以把每个位置的权值当作该字符上一次出现的位置与其的距离，然后跑KMP，要注意很多细节。
[CEOI2011]Matching：
对于一个没有相同数字的序列，当我们知道一个位置前面有多少个比它小的数后，可以唯一确定这个序列排序后，第几个位置的数字排第几，然后就可以利用这个方法进行KMP，实际上还可以维护当前位置在它前面且刚好比它大的数的位置，以及在它前面且刚好比它小的数的位置，这样也可以用KMP，而且复杂度更优秀。
AC自动机DP
[JSOI2007]文本生成器：
一般AC自动机上DP，大部分都用f[i][j]表示当前在节点j,且串长为i时的情况，有时再加一维表示这个状态里面包含了哪些东西，而且AC自动机的DP会经常让你用矩阵乘法优化
BZOJ1444[JSOI2009]有趣的游戏：
考虑建出AC自动机进行概率DP，求出到达某个自动机上节点的概率，但是因为转移有环，考虑用高斯消元，不过因为数据范围很小，建出邻接矩阵求矩阵快速幂也能得出答案。
一个字符串加上某个数字后变成另一个字符的匹配方式
[SDOI2008]Sandy的卡片：由于无论怎么加，相邻两个字符的差值不变，可以用差值来做。
求一个字符串有多少种子串
利用后缀数组求出height，用所有子串个数减去所有height之和就是答案。
也可以用后缀自动机求个数。
一道比较好的题：[SDOI2016]生成魔咒
求一个字符串两两后缀的lcp之和
用后缀数组求出height后，可以用单调栈O(n)扫一遍。
[AHOI2013]差异
BZOJ3879 SvT
剩余系的一个性质
如果a,m互质，那么k×a{\ \rm mod\ }m，在k\in[0,m-1]时，可以取遍[0,m-1]的值。
我们用反证法证明:
假设存在k_1,k_2使得k_1a=t_1m+w,k_2a=t_2m+w，且k_1≠k_2,0≤k_1,k_2<m，那么相减得到(k_1-k_2)a=(t_1-t_2)m，又因为a,m互质，那么(k_1-k_2)一定为m的倍数，又因为k_1,k_2小于m，所以k_1-k_2不可能为m的倍数，所以k×a{\ \rm mod\ }m，在k\in[0,m-1]时，余数肯定两两不同，也就是说可以取遍[0,m-1]的值。
若p,q互质，则可以得到下面这个公式：
\sum_{i=1}^{q-1}\left\lfloor\frac{i×p}{q}\right\rfloor=\sum_{i=1}^{q-1}\frac{i×p-i×p{\ \rm mod\ }q}{q}=\frac{(p-1)(q-1)}{2}
利用FWT原理的好题
[UOJ310]黎明前的巧克力
关于集合幂级数的式子：
\hat{f_S}=\sum_{T\subseteq2^U}f_T(-1)^{|S\cap T|}
FWT的和等于和的FWT：
FWT(A)+FWT(B)=FWT(A+B)
求0~2^n-1的每个数的二进制位有几个1
从Imagine在[WC2018]州区划分的讲解中学到的技巧。
以前写的都是复杂度为n2^n的代码，下面写一个复杂度为2^n的代码：
for(int i=1;i<(1<<n);i++)
size[i]=size[i&(i-1)]+1;
有时候可能还需要求出所有为1的二进制位代表的某种权值的一些运算操作（代码以求和为例），那么也可以优化掉枚举二进制位：
for(int i=1;i<S;i++)
val[i]=val[i&-i]+val[i&(i-1)];
这几个优化实质就是DP，每次从去掉最低非零位的位置转移过来。
FWT技巧
[WC2018]州区划分：
第一次列出的DP转移虽然是或卷积形式，但是如果直接套用FWT无法转移。不过可以发现转移肯定是由小集合转移到大集合，所以可以写成dp[i][S]表示集合大小为i，集合为S的状态，然后从小到大转移。
HDU6057 Kanade's convolution：
由于卷积有判断条件，不能直接套FWT，因为判断条件与集合大小有关，依然可以像上面那题一样，按照集合大小分一下，然后就可以套用FWT了。
位运算的一个公式
HDU6057 Kanade's convolution：i\ {\rm and}\ j=i\ {\rm or}\ j-i\ {\rm xor}\ j
找到一篇对FFT的讲解十分优美的博客
[FFT] 快速傅里叶变换学习笔记
NTT
对于模一个数的计数问题只能用NTT。
乘法取模
这里讲模数为64bit的情况：
一般遇到这种模数都是写手写快速乘，复杂度为log级，事实上根据2009国家集训队论文骆可强《论程序底层优化的一些方法与技巧》中的方法，可以改为O(1)的复杂度：
#define LL long long
LL quick_mul(LL a,LL b)
{
LL d=(LL)floor(a*(double)b/mod+0.5);
LL ret=a*b-d*mod;
if(ret<0)ret+=mod;
return ret;
}
首先它使用浮点运算来得到\frac{a×b}{mod}的值，关键在于第二句，显然a×b-d×mod中的两个乘法都是可能会溢出的，不过没关系，因为我们可以预见其差是一个64bit可容纳的正整数，那么溢出部分的差仅可能为0或者1，最后一句符号的特判用来处理溢出部分差为1的情况。容易注意到，我们计算 \frac{a×b}{mod}时使用了浮点运算，误差是不可避免的，故建议不要对太大的mod使用这个算法。
原根
[SDOI2015]序列统计：利用了原根的一些特殊性质：
对于一个素数p，他的一个原根g的0~p-2次幂在模p意义下可以取遍1~p-1的所有值。
求原根可以先找出p-1的所有质因数，然后从2开始枚举，如果对任意的p-1的质因数p[i]，x的\frac{p-1}{p[i]}次幂模p都不等于1，则x是p的一个原根。
多项式题目感想
好像用到FFT,FWT,NTT的题，一般都是列出DP转移方程，或者可以根据题目列出计算公式，然后进行一些十分奇妙的变换后就可以发现是一个卷积形式，不排除有其它情况，目前遇到的题大概都是这样。
查询一段区间里有多少种不同的值
用last[i]表示与第i个位置的数相同的上一个位置，没有则为0，那么一个区间里的答案就显而易见了：\sum\limits_{i=l}^r[last[i]<l]
数列与一个数的差值绝对值之和或差值平方和
给你一个数列，要求你求出一个数a，使得\sum\limits_{i=1}^nabs(num[i]-a)最小，a就是数列的中位数。
给你一个数列，要求你求出一个数a，使得\sum\limits_{i=1}^n(num[i]-a)^2最小，a就是数列的平均数。
第二个的证明：
记f(x)=(x-a_1)^2+(x-a_2)^2+(x-a_3)^2+\cdots+(x-a_n)^2
f(x)=nx^2-2x(a_1+a_2+a_3+\cdots+a_n)+(a_1^2+a_2^2+a_3^2+\cdots+a_n^2)
可以看出f(x)是一个开口向上的二次函数，根据求对称轴公式：\frac{-b}{2a}可以得到，当x=\frac{a_1+a_2+a_3+\cdots+a_n}{n}时，f(x)有最小值。
一个很巧妙的DP
[NOI2018雅礼集训Round 2] Divide
题解
一个很巧妙的状压DP
[NOI2018雅礼集训Round 1 Day 1] 树
求i×a/b(i≤n)向下取整的和
题目：P4433 [COCI2009-2010#1] ALADIN
20180713day11质数问题
原本以为这个性质没什么用，但是模拟题考到，那还是再记录一下。
讲解
一般的分块
对于一般比较简单的分块，都是与区间某种数值的个数有关，有的是维护某个块里的信息，有的是维护第i块到第j块的信息，还有的维护第i块到第j个位置的信息，例如：求区间某个数有几个，出现次数最多的数，交换两个数值位置维护一些信息（一般维护时需要的信息是某个数值的个数或者小于等于某个值的数的个数）
当然也有其它的一些不同的，与题目本身的一些维护性质有关，例如：哈希冲突等。
状态树
[国家集训队]跳跳棋：两种状态在状态树上的路径长度就是需要求的变换步数。
矩阵的结合律
CF750E New Year and Old Subsequence：利用矩阵的结合律使用线段树维护。
比较好的树形DP
[JLOI2015]战争调度
注意复习小球放盒子的方案数问题分析
分治递归
P1228 地毯填补问题
BSGS
1111\cdots=\frac{10^x-1}{9}
部分测试题目
是一个$\rm Pólya$定理的直接应用，所以这里只介绍莫比乌斯反演的方法，部分思想依然类似于$\rm Pólya$定理：
首先，我们破环为链，先不管旋转操作的影响，那方案数就是所有排列方案，但是若考虑旋转，对于之前的排列，我们会算重复，则应该除掉那些重复状态。考虑一种排列会算重复几次，观察例子：$123123$，重复状态有$312312,231231$，$2451$的重复状态有$1245,5124,4512$，如果再多弄几个例子，会发现重复状态个数为该状态的最短循环节的长度那么多次，如$123123$循环节为$123$，$2451$的循环节为本身，而且循环节长度肯定是$n$的约数，那我们令$f(x)$表示循环节长度为$x$的方案数，答案则为：
$$\sum_{d|n}\frac{f(d)}{d}$$
下面就是莫比乌斯反演的套路了：
再令$g(x)$为循环节长度为$x$的约数的方案数，则有：
$$g(x)=\sum_{d|x}f(d)$$
反演一下就可以求了，但是反演后需要求$\mu$，还有一种方法可以避免求$\mu$，就是直接从公式中提出我们需要的东西，这也是一种求解莫比乌斯反演的题的方法：
$$f(x)=g(x)-\sum_{d|x}[d≠x]f(d)$$
时间复杂度还是$n{\rm log}n$。
考虑如何快速求$g(x)$，事实上$g(x)=k^x$，可以发现这样正好算完了循环长度为$x$的约数的所有情况，这样对于每一次询问，$n{\rm log}n$的预处理，$\sqrt n$的查询，可以过掉此题。
还有更优的做法，以后再补。
$Simple$:
$$\sum\limits_{i=l}^r\sum\limits_{j=1}^i\frac{i\ {\rm mod\ }j}{j}$$
容易想到：
$$\sum\limits_{i=l}^r\sum\limits_{j=1}^i\frac{i}{j}-\left\lfloor\frac{i}{j}\right\rfloor$$
令$a^{-1}$为在模一个质数下的逆元，那么公式可以变成下面这种形式：
$$\sum\limits_{i=l}^ri\sum\limits_{j=1}^ij^{-1}-\sum\limits_{i=l}^r\sum\limits_{j=1}^i\left\lfloor\frac{i}{j}\right\rfloor$$
前半部分直接逆元前缀和，后面部分除法分块，但是过不了所有测试点，需要对后半部分进行优化。
直接计算已经不能再优了，但是我们还有另外一种思考方向，就是求出我们需要求的状态与前一个状态的差值，也就是差分：
令$f(i)=\sum\limits_{j=1}^i\left\lfloor\frac{i}{j}\right\rfloor
作差：
f(i+1)-f(i)=\sum\limits_{j=1}^{i+1}\left\lfloor\frac{i+1}{j}\right\rfloor-\sum\limits_{j=1}^i\left\lfloor\frac{i}{j}\right\rfloor
观察上式可以发现对于每一个j，作差后只有0,1两种取值，更美妙的是只有当j为i+1的约数的时候作差才为1，而一个数的约数个数是可以线性筛的，这样就成功的降低了复杂度。
令d(x)表示x的约数个数:
f(i)=f(i-1)+d(i)
直接对d(x)求两次前缀和就行了。
还有类似问题：
\prod_{i=l}^r\prod_{j=1}^i\left(\frac{i}{j}\right)^{\left\lfloor\frac{i}{j}\right\rfloor}
用类似的方法求解，令f(i)=\prod\limits_{j=1}^i\left(\frac{i}{j}\right)^{\left\lfloor\frac{i}{j}\right\rfloor}
作商:
\frac{f(i+1)}{f(i)}=\left(\frac{i+1}{i}\right)^{\sum_{j=1}^i\left\lfloor\frac{i}{j}\right\rfloor}\prod_{j|i+1}\frac{i+1}{j}
**环形DP**
类似于[APIO2007]动物园，首先破环为链，但是DP到跨过破开的地方时需要知道开头的状态，虽然可以直接开一维记录状态，但是空间很大，可以枚举每一种开头分别DP，这样就能解决空间问题。
**求使树上某个点集连通的最少边数**
先对原树求出每个点在$dfs$序中的标号，对于原树的一个点集（在树上不一定连
通）。令$v$表示按$dfs$序排序后相邻两个点间的距离之和（第一个点与最后一个点也算相邻），那么使它们连通的必要的边数为$\frac{v}{2}$，连通后的图里面有$\frac{v}{2}+1$个点。
**邻接矩阵倍增**
20181003测验 买零食：
虽然矩阵快速幂很明显，但是有一个比较致命的细节问题，就是如果直接对邻接矩阵进行快速幂，那么路径是严格走那么多次的，如果这样做就会在这道题上出问题，因为对于从环上伸出链的情况如果不这样处理，这时候会出现走的次数多反而路程更短的情况，使得按二进制从高位到低位考虑会出错，这时候考虑对每一个点加上自环（若有自环则不管），因为这样就能使得矩阵变成走的次数不超过那么多次的时候能走的最远距离，就成功将中途的最大值保留了下来。
**K进制下的无限循环小数转成10进制下的分数**
20181004测验 进制转换：
假设在$k$进制下有一个无限循环小数，其循环节长度为$p$，令$x$表示将循环节看成$k$进制下的整数再转化为$10$进制后的值，其不循环部分长度为$q$，令$y$表示将不循环部分看成$k$进制下的整数再转化为$10$进制后的值，那么在$10$进制下，其分数形式为：
$$\frac{x}{(k^p-1)\times k^q}+\frac{y}{k^q}$$
举例解释：
$10$进制下的无限循环小数$0.4(230769)$，其中括号部分为循环节：
那么循环节长度$p=6$，看成$10$进制整数为$x=230769$，非循环部分长度为$q=1$，看成$10$进制整数为$y=4$。
那么$10$进制下的分数形式为:$$\frac{230769}{(10^6-1)\times 10}+\frac{4}{10}=\frac{4230765}{9999990}=\frac{11}{26}$$
其它进制下的无限循环小数同理。
证明：
在考虑如何将一个循环小数转成分数之前，先讲解一下如何将一个$10$进制下的分数转为$k$进制下的小数：
首先整数部分的转换很简单，那么我们默认这个分数小于$1$，这个时候我们可以知道在$k$进制下这个小数的样子一定是$0.{\rm xxxxxx\cdots}$，但是我们不知道${\rm x}$部分具体长什么样，所以我们可以考虑一位一位的提出小数部分，但是直接提不好算，我们可以将每一位小数提到整数部分，那么我们计算整数部分就行了，这样就变得很方便了。
例如将$\frac{3}{7}$转化成$5$进制下的小数：
先将十分位提到整数部分$\frac{3\times 5}{7}=\frac{15}{7}$，现在的整数部分则为$\left\lfloor\frac{15}{7}\right\rfloor=2$，所以十分位上应该为$2$，将十分位消去$\frac{15}{7}-\frac{7\times 2}{7}=\frac{1}{7}$，现在百分位变到了十分位的位置，我们只需要再将现在的十分位移到整数部分，那么整数部分就变成了我们要求的百分位，那么百分位为$\left\lfloor\frac{1\times 5}{7}\right\rfloor=0$，去掉百分位（即现在的整数部分）$\frac{5}{7}-\frac{7\times 0}{7}=\frac{5}{7}$，后面依次类推，则可以得出转换为$5$进制下的小数后为：$0.(203241)$（括号部分为循环节）。
由于循环小数是循环的，也就是说我们在对每一个分数位提取的时候，它的分数形式是一个循环，还是以上面的为例：从左到右依次为每一个小数位提取时的分数形式：$\frac{3}{7},\frac{1}{7},\frac{5}{7},\frac{4}{7},\frac{6}{7},\frac{2}{7},\frac{3}{7},\frac{1}{7}\cdots$可以看到每$6$位一次循环。
令$p$表示循环节长度，如果我们不一位一位的提取，而是一次直接提取$p$位，那分数形式就会全部一样了，以上面为例：直接提取$6$位小数，则整数部分为$\left\lfloor\frac{3\times 5^6}{7}\right\rfloor=6696$，将$6696$转为$5$进制为$203241$（之前一位一位提取不用转进制是因为向下取整后一定小于进制），然后$\frac{3\times 5^6}{7}-\frac{7\times 6696}{7}=\frac{3}{7}$，可以看到又变成原来的样子了，那么假设该无限循环小数是$k$进制的，且由$\frac{x}{y}$得出，且循环节长度为$p$，且循环节转换为$10$进制后值为$v$，那么可以得到下面这个等式：
$$\frac{x\times k^p}{y}-\left\lfloor\frac{x\times k^p}{y}\right\rfloor=\frac{x}{y}$$
因为$\left\lfloor\frac{x\times k^p}{y}\right\rfloor=v$可以直接计算，所以公式移项变形后为：
$$\frac{x}{y}=\frac{v}{k^p-1}$$
这样我们就成功得到了任意进制下的无限循环小数转$10$进制分数的公式。
但是还不够，如果遇到一开始所举例的情况$0.4(230769)$，循环节没有包含所有小数部分，上面那个公式并不能完美解决，实际上我们直接拆开$0.4(230769)=0.4+\frac{0.(230769)}{10}$，我们只需要计算$0.(230769)$的分数形式，剩下的直接通分合并就行，这样就有了我们一开始所提出的公式（公式里的各个字母的含义见开头）：
$$\frac{x}{(k^p-1)\times k^q}+\frac{y}{k^q}$$
**无限背包计数问题**
一般的背包问题是求最优值，而背包问题还有另一种问题，就是求可行的方案数。
例$1$：给你一些数字，每种数字有无限个，问你组合成某个给定值有多少种方案，一般这种给的数字个数比较少，容易定义${\rm dp}$状态$f[i][j]$表示用前$i$种数字，组合成$j$的方案数，那么转移也就如下了：
$$f[i][j]=f[i-1][j]\text{(不选)}+f[i][j-v[i]]\text{(选)}$$
例$2$：给你一些数字，每种数字有无限个，问你在某个数值范围内有多少数是可以被用给定数字组合出来的，一般这种给的数字也很少，那么定义${\rm dp}$状态$f[i]$表示$i$能否被组成，那么转移如下：
$$f[i]=f[i-v[1]]{\ \rm or\ }f[i-v[2]]{\ \rm or\ }\cdots {\ \rm or\ }f[i-v[j]]$$
然后统计给定范围内有多少可以组合就行，但是若范围很大怎么办，例如
P2371 [国家集训队]墨墨的等式 这道题，这时候就需要运用一点数学技巧：
假如$a$是所给数中的一个数，若我们知道了在模$a$意义下的哪些余数可以被除$a$以外的其它数在模$a$的意义下所组合出来，且组合出来的最小值是多少，那么我们就可以知道所询问的范围内，那些模$a$的余数和你可以表示出来的余数相等的数中有哪些可以表示出来。
也就是说我们现在想要知道哪些余数可以被表示且表示的最小值是多少，这个不好构造${\rm dp}$，但是若我们把状态看成点，边看成加上某个数后的变化，且将边权赋为加的那个数，这样我们成功将模型转换到了最短路上面，那么当$a$取最小的那个数，点数最少，这样从$0$那个点开始跑最短路就可以了。
**单调队列优化多重背包**
许多资料上面都讲的是转二进制位的，这里讲解一下通过单调队列优化的复杂度为$O(nV)$的解法：
令$f[i][j]$表示对容量为$j$的背包，处理完前$i$种物品后，背包内物品可达到的最大总价值，$cnt[i]=min\left(tot[i],\left\lfloor\frac{j}{v[i]}\right\rfloor\right)$，那么原始的$\rm dp$转移方程如下：
$$f[i][j]=max\{f[i-1][j-k\times v[i]]+k\times w[i]\}(0\leq k\leq cnt[i])$$
那如何快速求出$f[i][j]$？
若我们观察一下转移的位置，可以发现转移过来的地方在模$v[i]$的意义下和$j$同余，也就是说，如果令$a=\left\lfloor\frac{j}{v[i]}\right\rfloor,b=j{\ \rm mod\ }v[i]$，那么转移方程就变成了下面这个样子：
$$f[i][j]=max\{f[i-1][(a-k)\times v[i]+b]+k\times w[i]\}(0\leq k\leq cnt[i])$$
虽然可以将同一模数的装到一个队列中，但是不同的$j$从同一个位置转移所用的$k$不一样，导致$k\times w[i]$每次需要改变，若我们每一次的转移能与当前所处位置无关，只与转移位置有关且能方便维护，那么就能够优化了。
令$k'=a-k$，那么$k\times w[i]=(a-k')\times w[i]=a\times w[i]-k'\times w[i]
可以发现，若我们将a\times w[i]提出，那每次转移只与k'有关，可以看成当前位置与转移位置的距离，这样\rm dp转移方程就变成了下面这个样子：
f[i][j]=max\{f[i-1][k'\times v[i]+b]-k'\times w[i]\}+a\times w[i](a-k\leq k'\leq k)
这样在每一种余数中做一次\rm dp，用单调队列优化一下，每一次就变成了O(V)。
树上所有点到某个点的信息统计
[HNOI2015]开店和蚂蚁开会
两者都是每次询问其他所有点的点权乘上到指定点的路径长度的和是多少，开店只是没有点权，所以当做1就好了。
开店可以用点分树做，还有一种主席树的做法，但是点分树更方便，而且空间复杂度有保证。主席树的做法是通过一个公式发现我们实际上需要维护的东西，我们默认1号点为根，令dis[i]表示点i到根节点的距离，令val[i]表示点i的点权，令size[i]表示以i点为根的子树里的点权和，令len[i]表示点i到其父亲那条边的权值，那么对于查询点u，我们的答案是如下公式：
ans=\sum_{i=1}^ndis[i]\times val[i]+\sum_{i=1}^ndis[u]\times val[i]-2\times \sum_{i=u\text{以及它的所有祖先}}size[i]\times len[i]
前面两部分很好维护，对于后面的部分我们直接用树剖来维护，但是开店这道题对点有编号，每次查询编号在某段区间里的点到规定点的答案，我们用了线段树维护，但是要查询区间，可以想到用主席树，但是这道题似乎用点分树更方便。
不过蚂蚁开会那道题用点分树就特别麻烦了，主要是因为涉及到点权与边权的修改，但是这道题没有查询一段区间的要求，所以这道题直接用上面的公式然后树剖维护反而更加方便。
总之，上面的公式还是比较有用的。
方案数转期望
禁书目录
出题人的题解和原题面
直接求想要的方案数不好算，但是我们发现，如果我们把要求的方案数除上总方案数，就变成了求随机排列后的序列里期望能看到多少种不同的颜色，那我们算出期望，再乘上总方案数就是答案。
根据期望的线性性，可以转成每一栋楼可以被看见的概率之和，然后发现就能很方便的计算期望，那么方案数也就能计算了。
两个数异或后二进制位1的个数的奇偶性讨论
假设其中一个数的二进制位为1的个数是x，另一个数的为y，那么这两个数异或起来后二进制位为1的个数为x+y-2a，其中a为这两个数有多个二进制位同时为1。
可以发现，若x和y同时为奇数或同时为偶数，那么异或后二进制位为1的个数为偶数。若x和y一奇一偶，那么异或后的个数为奇数。
交换一对数使得逆序对减少的最多
目前保证所有数两两不同。
「LibreOJ Round #6」花火
首先知道，交换的两个数必定也是一个逆序对，并且交换一对数减少的逆序对个数为位置在这两个数之间且权值也在这两个数之间的数的个数乘2+1。
假设改数列为h_i，那么我们想要找一个点对，使得i<j,h_i>h_j，并且要让k最多，其中k为i<k<j,h_j<h_k<h_i的数的数量。
如果我们将每一个数看成点(i,h_i)，我们相当于求一个左上角为(i,h_i)，右下角为(j,h_j)的矩形并且使得包含的点最多，但是枚举矩形的复杂度依然很高，我们考虑一个点会对那些矩形造成贡献。
首先可以知道要让解最优，对于一个矩形，其左上角必定没有点，其右下角也没有点，所以可以知道左上角集合和右下角集合必定单调，对于一个点x，令l为左上角集合中h_l>h_x，且l最小的点，令r为右下角集合中h_r<h_x，且r最大的点，那么这个点会对左上角为[l,x-1]，右下角为[x+1,r]的矩形产生贡献，但是我们不可能一个一个去加，如果我们把矩形看成点，即(i,j)表示左上角为点i，右下角为点j的矩形的话，那么一个点对矩形的贡献就转化成了对在平面中以(l,r)为左上角，(x-1,x+1)为右下角的矩形里的点都加1，直接上扫描线就完了，那么交换的点对为平面中点权最大的点，且点权乘2+1即为减少的逆序对个数。
二分图最小字典序匹配
爆瓶子-Nowcoder
对于每一行，先建出二分图，求一次最大匹配，这时不一定是字典序最小的，考虑贪心的修改，我们从前往后枚举位置，对于每一个位置，再从小到大枚举有哪些点能够与它匹配，对于一个能够匹配的点，如果它的匹配位置在你当前位置的后面，且它的值小于当前位置匹配的那个点的值，尝试能否将这两对匹配交换一下，如果能交换，则交换后去枚举下一个位置，否则继续枚举权值，直到剩下的权值都大于当前位置匹配的点的权值，这个时候再去枚举下一个位置。
如何判断能否交换：
假如说位置a与x配对，位置b与y配对，其中a<b,x>y，但是a与y也有边相连，我们考虑能不能改成a与y配对，b与x配对，这样就能使得字典序减小，于是我们删掉这两个配对方案，再强制使a与y配对，然后再用匈牙利算法判断b与x能不能配对，但是注意传入参数a，对于深搜中途，如果遇到某个点的配对点编号小于a，这个时候不能去更改，因为前面的配对方案已经是最优，再去修改反而会使得字典序变大，如果这种情况下，依然能够使a与y配对，则能交换。
求解一元n次方程的有理数根
我们只用考虑有理数根，所以可以把方程改写为f(x)=g(x)\times\prod(b_ix+c_i)的样子，其中g(x)是一个关于x的多项式，包含了所有的非有理数根，剩下的部分就表示了所有的有理数根。令g(x)的常数项为w，最高次项的系数为r，则原方程的最高次项的系数a_n=r\prod b_i，常数项a_0=w\prod c_i，所以对于一个有理数解\frac{-c_i}{b_i}，c_i为a_0的因子，b_i为a_n的因子。
两两枚举因子，判断是否合法就行，注意还要枚举负因子。
注意，如果a_0=0那么还有一个解为x=0，由于系数可能为0，所以我们需要人为的把系数不为0的最低次项作为方程的首项，最高次项作为方程的末项，再用上面的枚举因子的方法做。
[HAOI2016]字符合并
很明显的区间\rm DP，主要是如何表示状态和转移，首先需要发现一个性质，就是对于一个已知的长度，缩完所有序列后的长度是固定的，并且缩完后剩下的序列的每一位的来源是没有交集的，根据这个性质就能实现\rm DP，状压合并完成后的状态。
[九省联考2018]一双木棋
对轮廓线\rm DP有了一些新的认识，以前一直局限于插头\rm DP。
NOIP模拟 补兵
不好想的\rm DP题，容易往贪心上面想。
读完题应该能知道，如果没有单独砍的次数限制，一定是将数列砍成阶梯型，这样才能最大化收益，但是由于每一个时间段只能砍一次，数列自己又在每一时刻减少一层，导致不能够把所有的都砍成阶梯状，所以我们得用一个正确的方法分配一下怎么砍，使得收益尽量大。
假如说如果次数不限，那么我们可以确定收益最大且砍的次数最少的最终序列，这个确实没想到，然后由于次数有限制，所以我们可以记录一下最终序列的每一个值是由原序列的哪个值得到的，这样就可以知道得到这个数最少需要砍多少次，然后求一个方案，使得原序列的数尽量多的变成最终序列的数，这个就需要用\rm DP来做了。
考虑定义\rm DP状态f[i][j]表示，考虑到第i个时间段，下一次会自动砍掉i这个数，你还剩下j次可以自己分配，现在的问题是要不要i这个数，如果要就需要消耗cost[i]次，即f[i][j]从f[i-1][j+cost[i]]+1转移过来，不要则从f[i-1][j-1]转移，答案中途取最大就行。
NOIP模拟题
题目质量都很高，都没有考什么难的算法，基本上都是思维题。
比较神奇的题
期望：
BZOJ1426 收集邮票
LOJ6191「美团 CodeM 复赛」配对游戏
BZOJ5197 [CERC2017]Gambling Guide:对于这种初始只有一个点的dp值确定、其它点的dp值与其相邻的点有关的图上dp，考虑使用类似最短路的方式转移。
堆：
CodeVS 2057 生日聚会
随机数据：
HDU6348 序列计数
DP:
[ZJOI2008]生日聚会:维护的是当前位置的所有后缀信息。
线段树：
noi.ac 二叉交换树
不是很懂的题
BZOJ4310 跳蚤：感觉网上写的跟题目描述完全不一样啊，而且这个题目到底想要表达什么意思啊。
最值反演(MinMax容斥)。。。还没学，不会
LOJ2542「PKUWC2018」随机游走
HDU4624 Endless Spin
待完成：
BZOJ3881 [COCI2015]Divljak AC自动机+树链的并+DFS序+树状数组