本文长文/高能预警
由于博主过于懒惰和菜鸡，打算把未来50天内的大多数训练题目全部放在此博文中，将会不定时更新
所有代码全部位于Onedrive共享文件夹内
DP
CF802K 树形DP
无意中做到了瑞士HC2 EPFL的题目，果然很SOI，很侧重思维性
题意：给定一棵树，可以从一个点开始在树上行走，每条边上有一个宝物价值为w，每个节点最多访问k次，求能够得到的最大价值
f[x][1]表示访问完以x节点为根的子树后返回到x的父节点所能得到的最大价值
f[x][0]表示访问完以x节点为根的子树后不返回x的父节点所能得到的最大价值
CF261D 结论+暴力
题意：给出数列B，请假定一个数列A，使得其长度为n×t，使得A序列为若干个B组成，求出序列A的最长上升子序列数
表面上看十分不可做，无法把A序列求出来并计算LCS
但显然当t≥min(n,maxb)时，答案是a中不同的个数
剩下的可以直接暴力
因为LCS的总增量一定小于等于maxnb×n
CF285D DP+容斥+组合
题意：n个数的全排列pi，对于每个全排列pi，若abs(pi−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)×f[n][k+1]+C(k+2,k)×f[n][k+2]……C(n,k)×f[n][n]
因为取模数较大为1e9+7，所以只能使用逆元处理
CF50D 二分+概率DP
题意：给定若干点和一个爆炸中心点的位置坐标，如果要想使得其爆炸失败（小于k个点爆炸）的概率满足不大于给定值F/1000，求出最小爆炸半径
很明显先二分答案之后概率DP检验
f[i][j]表示前i个坐标中存在j个爆炸的概率
只需要枚举是否爆炸进行状态方程的转移即可
时间复杂度O(T×n2)
线段树
CF482B 线段树+位运算
题意：给出序列的长度n和m次询问，对于每次询问给出li,ri,qi，满足a[li]&a[li+1]&…&a[ri]=qi，请你求出原序列ai
先按照题意给出的询问将原数组修改，之后再次询问一次看是否符合条件
注意线段树操作的时候要把极大值inf每一位都赋值为1（在这里WA了半小时）
CF833B DP+线段树优化
题意：给出长度为n的序列，可以将其划分为k段，最大化每段中出现的不同种类数字个数之和
用f[i][j]表示前i个书分为j段的最大价值
f[i][j]=maxf[k][j−1]+query(k+1,i)(0≤k<i)
然后发现从a[i]上次出现的位置lst[a[i]]到当前位置中的这些f值都需要+1，那么可以第一重循环枚举K，之后每次重构线段树进行优化
时间复杂度O(nklogn)
CF383C dfs序分层+线段树
题意：给出长度为n的序列，支持如下操作：
- 查询一个点权值
- 修改以这个点x为根的子树中所有节点的权值，奇数层+val，偶数层-val
先dfs将树中每个节点分层，之后记录两个权值，分别是对应的+/-答案
CF633H
题意：给出长度为n的序列，每次询问给出li,ri，请求出a[li]…a[ri]之间的斐波那契权值
其中斐波那契权值定义为：将子序列排序去重，P(a)=a1×F(1)+a2×F(2)+…+ai×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+x2+x3+x4+…)×(1+x2+x4+x6+…)×(1+x3+x6+x9+…)…
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×m的矩形，用1×2的方块覆盖，不重叠并且要求完全覆盖，不能越界，询问完全覆盖的方案数
设计状态f[i][S]表示第i行状态为S时的方案数
对于横放，我们可以将两块砖都设计为11
对于竖放，为了防止冲突，将上面的设为0，下面的设置为1
之后逐格讨论状态即可，要手动移动循环变量
POJ2255 二叉树遍历
给定先序和中序遍历，求出后序遍历
直接递归即可
SGU199 LIS输出解
二维LIS，按指定域排序后，求出最长上升子序列
本文可以转载，但必须附上原文链接，否则你会终生找不到妹子！！！欢迎关注我的CSDN: ahyjjr