CVBB ACM Team

题意:大水题

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

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

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

题意:构造一个长度为$n(1 \leq n \leq 10^{9})$的$01$串，其中$1$的个数为$m(0 \leq m \leq n)$，要求含$1$的子串数量最多。

题解:$m$个$1$把字符串分割成$m+1$个全$0$串，答案即为子串总数减去这些全$0$串的子串总数。可以证明让这些全$0$串的长度尽量相等时答案最大。

题意:如图一个$n \times m(n,m\le500)$的方格图，一共有$(4 n m - 2n - 2m)$条边，起点在左上角，每条边只能经过一次，给出一个恰好经过$k$条边的方案。方案由不超过$3000$条指令组成，每条指令为执行一个长度不超过$3$的字符串$(L,R,D,U)$指定次数；或判定无解。

题解:显然$k>(4 n m - 2n - 2m)$则无解。否则，可以先把每一行走遍，然后把每一列走遍，最后再回到左上角，途上步数到了就exit(0)即可。写完代码看看循环边界可以发现这样的指令条数为$3(n-1)+3(m-1)+2=3(n+m)-4<3000$，符合题意。

for(int i = 1;i < n;i++) solve('R', m - 1), solve('L', m - 1), solve('D', 1);
for(int i = 1;i < m;i++) solve('R', 1), solve('U', n - 1), solve('D', n - 1);
solve('L', m - 1), solve('U', n - 1);

题意:给定一个$n \times m$的方格，每个点格子红蓝黄绿四种颜色，$q$次询问一个子矩阵，求其中最大的正方形使得这个正方形可以分成四个小正方形，且这四个小正方形的颜色左上、右上、左下、右下分别为全红、全绿、全红、全蓝。$(1 \leq n , m \leq 500, 1 \leq q \leq 3 \cdot 10^{5})$

题解:注意到如果某个子矩阵内有边长为$K$的符合条件的正方形，那么也存在边长比$K$小的符合条件的正方形，因此可以二分答案。首先对每种颜色求二位前缀和，以便求出每个位置是否有以该点为左上角的半边长为$k$的符合条件的矩阵，再对每个$k$求一个二位前缀和，二分半边长，对每一个需要验证的值$mid$判断$[x,y]与[xx-2 \times mid,yy-2 \times mid]$之间的矩形范围内是否有满足条件的点即可。

题意:在$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()+区间查询最大值即可。