好难过呀
不会做题了
A
签到
B
题意
现有一根木棒，长度为m，其中有n个断点形成n-1个区间，最多可以用k个木棒，问最小需要补的长度。
分析
显然尽可能的将长的区间用k个木棒，剩余下的花费即可。
C
打表找规律。。。
$2^n - 1$ $(n:1,2,3….)$比较特殊，剩下的都是可以得到的max。
D
题意
和顺子对子(2017 广西邀请赛)相似度 $99$%
给出n个数，每连续的三个数或者相同的三个数可以贡献 $+1$，问最大贡献。
分析
状压dp
朴素的想法：
- 对于每个x，可以和(x-2, x-1, x)，(x-
1,x,x+1),(x, x+1, x+2)形成一个合理的贡献，并且每种不会超过两个$(\le2)$。 - 所以可以得到定义 dp[i][a][b][c]:
前 i 种数字，(x-2, x-1, x)，(x-
1,x,x+1),(x, x+1, x+2)分别形成a，b，c个的最大贡献。 - 这样的复杂度是
优化：
- 显然对于第x种类型的a, 就是第x-1种类型b,第x种类型的b就是第x-1类型的c，故可以优化掉一维。
E
题意
给出两个长度为n的数组a，b，每次对于任意的数组a的一个位置i，可以将a[i+1] + a[i-1] - a[i]变成a[i]，问a数组是否可以转化为b数组。
分析
对于修改前的数组： a[i-1], a[i], a[i+1]。
差分：a[i]-a[i-1],a[i+1]-a[i]
修改后：
差分：
a[i+1]-a[i], a[i]-a[i-1]
故每次修改就是交换差分的位置。
F. Nearest Leaf
题意
给一棵树和每个节点的dfs序，问q次询问，每次询问一个节点u和dfs的区间[l,r]，问区间[l,r]中叶子节点距离节点u最近的距离是多少。$(n ,q\le 5·10^5)$
分析
考虑将询问离线，利用dfs序是连续的性质做。
- 离线所有询问，考虑从根节点出发dfs。
- 一开始询问就是整个树的所给区间中叶子节点中的最小值。
- dfs的过程，考虑从父亲节点u转移到儿子节点v的过程且当前被询问节点为v，v子树内的减少 $w(u,v)$ (u和v之间的边权)，v子树外的增加了 $w(u,v)$。
- 并且dfs序是连续，询问区间dfs序形成的连续区间。
- 故离线所有询问，一边dfs一边维护线段树的值(区间加，区间减，区间最值)。