CVBB ACM Team

A

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

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

题意:如图一个$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 \times m$个点，相邻点之间移动时间为$1$，每个点有一种颜色，最多有$k$种颜色，相同颜色的点可以耗费时间$1$传送到达，$q$次询问求任意两点间最短路。$(1 \leq n, m \leq 1000,1 \leq k \leq min(40 , n \cdot m))$

题解:两点间最短路要么直接走曼哈顿距离，要么经过至少一次传送。前者直接计算即可，后者一定可以被分解成$x$到颜色为$c$的点$a$，$a$传送到颜色为$c$的点$b$，点$b$到点$y$，而$k$很小所以我们可以枚举颜色$c$。bfs求出每个点到每个颜色的最短距离，答案即为$dis_{x,c}+1+dis_{y,c}$。bfs的实现过程需要注意，除了普通的四个方向走，也可以使用传送，但要注意每个颜色只用考虑一次传送，因为后面传送的耗费时间一定更长不用考虑，而且这样才能保证$O(nmk)$的复杂度。