CVBB ACM Team

题意:大水题

题解:练习英语阅读和手速。

题意:长度为$n(n\le100000)$的序列中有一些位置确定，其它位置不确定，在不确定的位置上填上同一个数字，使得最大相邻差值最小。

题解:一开始写了很复杂的二分答案还WA了，结果发现并不需要。考虑与不确定位置相邻的确定的数字的最大值和最小值，令填上的数字为这两个数字的平均值一定是最优的，最后不要忘记考虑相邻的已确定的数字之间的差值对答案的影响。

题意:店里初始温度为$m$，有个空调每分钟可以升高$1°C$或降低$1°C$或不变，一共有$n$个客人，每个客人会在第$t_i$分钟到达，他要求到达时刻店里温度的范围为$[l_i,r_i]$，问能否让每个客人都满意。

题解:求出每个时刻可能的温度范围，如果和某个客人的要求交集为空，则无法满足，否则可以满足。更新范围时，两个客人间的间隔可以让$L$增加$R$减少对应的时间间隔，客人来时和客人的要求范围取交集。

题意:给出一个形如$<<>><<>>$的字符串，求出两个对应位置符合该字符串的$1$到$n$的排序，分别满足最长上升子序列最短和最长。

题解:我的构造方法太蠢，还卡了好久。巨佬的构造方法：最长只需对$1,2..n$中$>$的部分进行进行序列翻转，最短的只需对$n..2,1$中$<$的部分进行进行序列翻转。

题意:$n$个节点的树，$q$个询问，如果在$x$和$y$之间连一条边形成基环树，是否存在从$a$到$b$点的长度为$k$路径（可以重复经过点或边）。

题解:如果$a$到$b$的最短路大于$k$那么显然不存在。否则，只要存在一条长度奇偶性和$k$相同的路径就可以。奇偶可能不同的路径有以下几种：$a \rightarrow lca \rightarrow b$，$a \rightarrow x (\rightarrow_{cycle} x)\rightarrow_1 y \rightarrow b$，$a \rightarrow x (\rightarrow_{cycle} x) \rightarrow b$，$a \rightarrow y (\rightarrow_{cycle} y)\rightarrow_1 x \rightarrow b$，$a \rightarrow y (\rightarrow_{cycle} y) \rightarrow b$。

题意:在$n*m$的矩阵中，每行选择一个宽为$2$，长为$k$的矩形覆盖一些数字（重复的只算一次），当然最后一行只会覆盖一行，求数字之和的最大值。

题解:设$f_{i,j}$表示到第$i$行，这一行的选择的矩形左上角为$(i,j)$的最大值，那么有$$f_{i,j}=S_{i,j+k-1}-S_{i,j-1}+S_{i+1,j+k-1}-S_{i+1,j-1}+\max_{l}\begin{cases}f_{i-1,l}-(S_{i,l+k-1}-S_{i,j-1}) \qquad l\in [j-k+1,j]\\f_{i-1,l}-(S_{i,j+k-1}-S_{i,l-1}) \qquad l\in [j,j+k-1] \\f_{i-1,l} \qquad \text{otherwise}\end{cases}$$把大括号里面的下标类别相同的项进行合并，设$x_{i,j}=f_{i-1,j}-S_{i,j+k-1}$ , $y_{i,j}=f_{i-1,j}+S_{i,j-1}$，上式变成$$f_{i,j}=S_{i,j+k-1}-S_{i,j-1}+S_{i+1,j+k-1}-S_{i+1,j-1}+\max_{l}\begin{cases}x_{i,l}+S_{i,j-1} \qquad l\in [j-k+1,j] \\y_{i,l}-S_{i,j+k-1} \qquad l\in [j,j+k-1]\\f_{i-1,l} \qquad \text{otherwise}\end{cases}$$使用线段树维护$f,x,y$三个值即可，每次重新build()+区间查询最大值即可。