codeforces #620

这次div2的难度不算高，有手就行的那种吧
A.Two Rabbits
题意:a+b

B.Longest Palindrome
题意:给出n个长度为m的字符串，取出若干个进行拼接，求可以构成的最长回文串
思路：
step1.先找出两两配对可以构成回文串的字符串，打上标记
step2.对于没有打标记的字符串，若其本身是回文串，则任意取出一个放到到中间拼成最后的回文串

C.Air Conditioner
题意:屋子初始温度为m，有n个人依次进屋子，第i个人的允许温度范围是[Li,Ri]。在前后两个人到来的时间间隔内可以调节温度，每分钟只能增加或减少至多1度。
当第i个人到来的时刻，屋子的温度需要在[Li,Ri]的范围内。问是否能够通过调节温度使得所有人都满足条件
思路：
记第i个人的允许温度的上下限为 a[i].l 和 a[i].r
记第i个人到来的时间点，温度实际可达范围的上下限为 b[i].l 和 b[i].r
则第i个人满足条件的要求是 区间[a[i].l,a[i].r] 与 区间[b[i].l,b[i].r]有交集
若第i-1个人与第i个人到达时间差为k
则b[i]的递推关系式为：
b[i].l = max(a[i-1].l, b[i-1].l) - k
b[i].r = min(a[i-1].r, b[i-1].r) + k
按时间顺序依次遍历n个人，求出b[i]再与a[i]判交即可

D.Shortest and Longest LIS
题意:给出长度为n的数列中，所有前后相邻的两个数的大小关系。要求排列1~n这n个数，使得满足给出的大小关系。求出其中最长上升子序列(LIS)最大和最小的两种排列方式
思路：
贪心+构造
先说LIS最大的情况
排列思路是使得整体数字呈上升趋势，即在满足大小关系限制的前提下，小数尽可能放前面
而为了满足大小关系限制，需要找到数列中的“极小值点”
以>><><为例：

1.有两个极小值点，分别从前到后赋予1和2这两个最小的值
2.然后整个数列被分为了3段：
第一段[a1,a2,]单调减，分配剩余最小的2个数3~4
第二段a4,分配剩余最小的数5
第三段a6,分配剩余最小的数6
因此得到数列4 3 1 5 2 6

LIS最小的情况只要按从右到左的顺序分配即可

E.1-Trees and Queries
题意:给出一棵树，有若干次询问，每次询问由5个数组成 x,y,a,b,k
含义为在x节点和y节点间加一条边，然后判断从a节点到b节点是否能刚好走k步到达(边可以重复走)
询问之间互相独立
思路：
因为边可以重复走，重复一条边实际上相当于总步数+2，所以数量不重要，主要是判断奇偶性
一开始想法被加边成环给限制住了，打算分成3种情况讨论：

1.a到b的原始路径与环有至少两个交点
2.刚好只有一个交点
3.没有交点
但是这里求环以及求边长都是O(n)的复杂度，会超时

实际上路径的奇偶性的改变只与是否经过了新添加的(x,y)这条边有关
最后只有3种可能的情况：
1.没有经过xy,只要看a到b的路径长度
2.a->x->y->b,此时要知道a到x和y到b的长度
3.a->y->x->b,此时要知道a到y和x到b的长度

因此这题实际上只要求一下LCA就行了

F.Animal Observation (easy version)
题意：在一个n * m的矩阵中，每一行放一个2 * k的小矩形，最后求这些小矩形覆盖的所有数字之和的最大值是多少(重复覆盖的数只能被算一次)
这题有两个难度，区别只是k的大小不同
思路：
满脸都写着dp的亚子
记dp[i][j]为将第i行的矩形放在第j列，累计i行得到的最大值
可以得到朴素的递推关系式：
dp[i][j] = max(dp[i-1][l] + GetSum(l,j,k))
其中l的范围取[1,m],GetSum(l,j)为放在第i行第l列和第i行第j列的两个1*k的矩形覆盖到的数字之和
由于l和j的两个矩形可能有重叠，所以这个转移方程的需要暴力的枚举所有的l、j，这显然是不允许的

对于k较小的情况，可以将l分为两大类：
1.l位置的矩形与j位置的矩形相交(最多只有2k-1种情况)，由于情况较少，直接枚举出来求最值
2.l位置与j位置不相交，其实就是在[1,j-k]和[j+k,m]这连段区间内取最值，只要每次求dp的时候维护一下就行了

对于k较大的情况
如果重叠部分的数字是允许重复计算的话，那显然问题会简单许多，递推式变成：
dp[i][j] = sum[j,j+k-1] + max(dp[i-1][l]+sum[l][l-k+1])
记f[l]=dp[i-1][l]+sum[l][l-k+1], 这样只要维护f[]的最大值就行了
加了不能重复计算的条件后，对于与j有重叠的l，不能直接取f[l],而需要把重叠部分的数字减掉
当j=1时，l在[1,k-1]范围内的f都需要减掉部分数字，
其中f[1]要减去a[i][1]~a[i][k]
f[2]要减去a[i][2]~a[i][k]
以此类推
转换一下，a[i][1]被[1,1]这个区间段各减了一次
a[i][2]被[1,2]这个区间段各减了一次
......
a[i][k]被[1,k]这个区间段各减了一次
于是这就转换成了一个区间更新，求区间最值的问题，用带惰性标记的线段树即可
另外要注意的是，对每行扫描从j变化到j+1时，[j-k+1,j]这个区间内的f[]需要把a[i][j]补回来