本文长文/高能预警
由于博主过于懒惰和菜鸡，打算把未来50天内的大多数训练题目全部放在此博文中，将会不定时更新
所有代码全部位于Onedrive共享文件夹内
DP
CF802K 树形DP
无意中做到了瑞士HC2 EPFL的题目，果然很SOI，很侧重思维性
题意：给定一棵树，可以从一个点开始在树上行走，每条边上有一个宝物价值为$w$，每个节点最多访问$k$次，求能够得到的最大价值
$f[x][1]$表示访问完以$x$节点为根的子树后返回到$x$的父节点所能得到的最大价值
$f[x][0]$表示访问完以$x$节点为根的子树后不返回$x$的父节点所能得到的最大价值
CF261D 结论+暴力
题意：给出数列$B$，请假定一个数列$A$，使得其长度为$n\times t$，使得$A$序列为若干个$B$组成，求出序列$A$的最长上升子序列数
表面上看十分不可做，无法把$A$序列求出来并计算LCS
但显然当$t\geq min(n,maxb)$时，答案是$a$中不同的个数
剩下的可以直接暴力
因为LCS的总增量一定小于等于$maxnb\times n$
CF285D DP+容斥+组合
题意：$n$个数的全排列$p_i$，对于每个全排列$p_i$，若$abs(p_i - 1)=1$，则位置$i$为好，询问$n$个数的全排列中存在多少个恰好$k$个好位置的排列
设$f[i][j][0/1][0/1]$表示前$i$位，存在至少$j$个位置满足条件的计数值，两个$0/1$分别表示数字$i$有没有使用过和数字$i+1$有没有使用过
每次转移判断该位置是否满足条件，如果不满足条件的话就添加一个空数字（可以直接乘上阶乘）
但这样的排列中还会存在一些大于$k$个好位置的排列，所求的为至少$k$个好位置
要得到最终的答案还需要一个trick
存在一个容斥原理的模型
$ans=f[n][k]-C(k+1,k)\times f[n][k+1] + C(k+2,k)\times f[n][k+2]……C(n,k)\times f[n][n]$
因为取模数较大为$1e9+7$，所以只能使用逆元处理
CF50D 二分+概率DP
题意：给定若干点和一个爆炸中心点的位置坐标，如果要想使得其爆炸失败（小于$k$个点爆炸）的概率满足不大于给定值$F/1000$，求出最小爆炸半径
很明显先二分答案之后概率DP检验
$f[i][j]$表示前$i$个坐标中存在$j$个爆炸的概率
只需要枚举是否爆炸进行状态方程的转移即可
时间复杂度$O(T\times n^2)$
线段树
CF482B 线段树+位运算
题意：给出序列的长度$n$和$m$次询问，对于每次询问给出$l_i,r_i,q_i$，满足$a[l_i]\& a[l_i+1]\& … \& a[r_i] = q_i$，请你求出原序列${ a_i }$
先按照题意给出的询问将原数组修改，之后再次询问一次看是否符合条件
注意线段树操作的时候要把极大值inf每一位都赋值为1（在这里WA了半小时）
CF833B DP+线段树优化
题意：给出长度为$n$的序列，可以将其划分为$k$段，最大化每段中出现的不同种类数字个数之和
用$f[i][j]$表示前$i$个书分为$j$段的最大价值
$f[i][j]=\max { f[k][j-1]+query(k+1,i) } (0\leq k < i)$
然后发现从$a[i]$上次出现的位置$lst[a[i]]$到当前位置中的这些$f$值都需要$+1$，那么可以第一重循环枚举$K$，之后每次重构线段树进行优化
时间复杂度$O(nk\log n)$
CF383C dfs序分层+线段树
题意：给出长度为$n$的序列，支持如下操作：
- 查询一个点权值
- 修改以这个点$x$为根的子树中所有节点的权值，奇数层+val，偶数层-val
先dfs将树中每个节点分层，之后记录两个权值，分别是对应的+/-答案
CF633H
题意：给出长度为$n$的序列，每次询问给出$l_i,r_i$，请求出$a[l_i]…a[r_i]$之间的斐波那契权值
其中斐波那契权值定义为：将子序列排序去重，$P(a)=a_1\times F(1) + a_2\times F(2) + … + a_i\times F(i)$，其中$F(i)$指斐波那契数列
莫队处理询问，线段树处理修改和答案
对于莫队，由于区间内的数和顺序和数量无关，所以可以看成集合进行操作
首先离散化并对每个数进行计数，只有数量在$0$和$1$之间变化时才进行线段树的答案修改操作，否则实际上对答案无影响
对于线段树，pushup可以使用矩阵完成
其中$[1][2]$是答案的矩阵，$[2][2]$是$fib$的矩阵
结果发现常数优秀的暴力可以水过去。。。。
树
CF686D 树的重心
题意：给出大小为$n$的树和$q$次询问，每次询问以$x$点为根的子树中重心的编号
当合并两棵树的时候，新的树的重心一定在原本的两个重心的路径上
CF191C 树上差分
题意：给出大小为$n$的树和$m$次操作，每次操作将路径上的边都染色一次，最后询问每条边被染色的次数
将$(x,y)$节点$+1$，$lca(x,y)$节点$-2$，最后统计前缀和即可
CF842C
题意：给出大小为$n$的树，每个节点的权值为$a[i]$，询问每个节点到根节点的路径上所有点权值的最大公约数$gcd$，其中你可以把路径上一个节点的权值变为$0$，使$gcd$最大化
经典
HDU1028 母函数/DP
本题母函数$(1+x+x^2+x^3+x^4+…)\times (1+x^2+x^4+x^6+…)\times (1+x^3+x^6+x^9+…)…$
DP方法
$f[i][j]$表示把自然数$i$划分为所有元素不大于$j$的方案数
$f[i][j]=f[i-j][j]+f[i][j-1]$
POJ2442 堆/优先队列
题意：给出$n$个长度为$m$的数列，一共$m$次让你每次从各个数列中选一个数相加成新的数列，让你求该数列的前$n$小的值
每次将前$i-1$行求出的$n$个最小值和第$i$行的前$n$小值求和放入优先队列
HDU1010 DFS+奇偶性剪枝
题意：给出迷宫入口出口，询问能否恰巧在$k$步的时候到达出口
常规DFS+剪枝
- 如果已经存在解
- 当前距离超过$k$
- 当前点到出口最小距离过长
- 当前点到出口最小距离的奇偶性与答案不符
POJ1742 多重背包可行性
常规多重背包三重循环
如果只需要检测可行性，只需要两重循环
每次对选取的次数进行限制即可
POJ2411 状压DP
题意：给出$n\times m$的矩形，用$1\times 2$的方块覆盖，不重叠并且要求完全覆盖，不能越界，询问完全覆盖的方案数
设计状态$f[i][S]$表示第$i$行状态为$S$时的方案数
对于横放，我们可以将两块砖都设计为$11$
对于竖放，为了防止冲突，将上面的设为$0$，下面的设置为$1$
之后逐格讨论状态即可，要手动移动循环变量
POJ2255 二叉树遍历
给定先序和中序遍历，求出后序遍历
直接递归即可
SGU199 LIS输出解
二维LIS，按指定域排序后，求出最长上升子序列
本文可以转载，但必须附上原文链接，否则你会终生找不到妹子！！！欢迎关注我的CSDN: ahyjjr