~~不知道，下一个~~
by 1saunoya @ 2019-07-05 21:25:36
菱形内的计数(diamond)
首先将在读入时将菱形转成正方形，统计矩形的个数。
有$(n+1)*(n+1)$个格点，用$d[i][j]$表示第i行第j列的格点到第1行第j列的格点之间有多少条竖线，f[i][j]表示第i行第j条横线（被抹去的也算）的距离上一条没被抹去横线的位置。
接着扫描$i,j，h$为矩形的高，初值为-1。若第i行第j根横线没被抹去，且$d[i][j]-d[i-f[i][j]]=f[i][j]$即当前横线到上一根横线的左边有封闭的竖线，那么表示这可能是一个矩形的开始，此时矩形的高$h$赋为$f[i][j]$。若$h>-1$，且$h[i][j]-h[i-h][j]>0$即当前扫描到的段左边有若干条竖线（矩形内不为空）；或$f[i][j]!=h$（矩形内不为空或不是矩形）；或当前扫描到的横线被抹去，$h$赋为$-1$。若$h>-1$且$d[i][j+1]-d[i-h][j+1]=h$，即横线右边线段有封闭的竖线，那么答案$+1。$
by Smallbasic @ 2019-07-05 22:13:15
原谅我太菜只能直接复制题解
by Smallbasic @ 2019-07-05 22:13:38
整套比赛的题解在这里：
## 偷懒的小X(lazy)
本题要求的是一个字典序最大的堆。首先将所有数字排序，根据堆的定义，堆的根权最小，左右子树都是一个堆，所以将最小的数放在根，接着因为在数组中左子树根排在右子树根前，所以将剩下的数大的一半分给左子树的堆，小的一半分给右子树的堆，利用分治递归解决即可。
## 渡河(river)
本题若只有1个询问，由于在同一个数字内走动是自由的，利用Flood Fill，每次寻找当前渡河次数能到的范围，直到范围到达边界为止位置。
40%-60%的数据可以这样解决。
同理，从外到内Flood Fill也是可以的，由于是8连的连通块，所以一个不在边界上的连通块必然被另一个连通块包围，而每个连通块所需步数一样，题目也可以理解为进入尽量少的连通块。所以顺序扫描i, j，Flood Fill所有没被填充过的连通块，由于询问不会在1上，进入这个连通块所需要的次数即包围它的连通块（必然已经被Flood Fill过）的次数（若这个连通块为1）或包围它的连通块的次数+1（若这个连通块为0）。
## 菱形内的计数(diamond)
首先将在读入时将菱形转成正方形，统计矩形的个数。
有$(n+1)*(n+1)$个格点，用$d[i][j]$表示第i行第j列的格点到第1行第j列的格点之间有多少条竖线，$f[i][j]$表示第i行第j条横线（被抹去的也算）的距离上一条没被抹去横线的位置。
接着扫描i,j，h为矩形的高，初值为-1。若第i行第j根横线没被抹去，且$d[i][j]-d[i-f[i][j]]=f[i][j]$即当前横线到上一根横线的左边有封闭的竖线，那么表示这可能是一个矩形的开始，此时矩形的高h赋为$f[i][j]$。若$h>-1$，且$h[i][j]-h[i-h][j]>0$即当前扫描到的段左边有若干条竖线（矩形内不为空）；或$f[i][j]!=h$（矩形内不为空或不是矩形）；或当前扫描到的横线被抹去，h赋为-1。若$h>-1$且$d[i][j+1]-d[i-h][j+1]=h$，即横线右边线段有封闭的竖线，那么答案$+1$。
## 电缆建设(cable)
本题即为平面图上的MST，特殊的是只有两排点。
普通的MST算法可以拿到40%的分数。但是由于图的特殊性，有以下推论：
1、MST中不会有线段相交,若AD与BC相交，无论AB有不经过AD、BC路径相连还是CD有不经过AD、BC路径，改连AC，BD会使得生成树权和更小。
2、若有点A(x1,y1),B(x1,y2),C(x2,y3)，且y1<y2<y3，那么边AC不可能在MST里。由于线段不交叉，B、C上方的点不可能与下方的点有连接，所以在MST中，不考虑B、C以下点的情况下，B、C要么同时属于MST中的一棵树中（B C连通），要么分别属于两棵树（B C不连通）。在BC连通的情况下，连接BA与连接AC同样将树扩展到了A及以上，由于ABC为钝角三角形，AB<AC，所以连BA只会使结果更优。在BC不连通的情况下，单连AC会使树不连通，再连AB或BC等价于连AB与BC，但是权更大。
所以这种情况AC是不可能连边。
这样就可以构出一张边数最多为2(m+n)条的新图，使用Kruskal时间复杂度
$O((n+m)log(n+m))$期望得分为70-100。
但是这题时间复杂度最低，写起来最简单的方法是DP。
用$f[i][j][0..1]$表示左边第i个点（下简称为点i）与右边第j个点（下简称为点j）以下的点已经处理完毕（即不可能再有边连到这2个点以下的点），且点i与点j连通/不连通。$f[i][j]$可以从$f[i-1][j]$或$f[i][j-1]$转移，$f[i][j]$从$f[i-1][j]$转移方程为（从$f[i][j-1]$基本相同，a为左边点坐标，$dist(i,j)$为点i到点j的距离）：
$f[i][j][1]=min(f[i-1][j][1]+a[i]-a[i-1],f[i-1][j][1]+dist(i,j),f[i-1][j][0]+a[i]-a[i-1]+dist(i,j))$
$f[i][j][0]=min(f[i-1][j][1],f[i-1][j][0]+a[i]-a[i-1])$
由于新图中只有$i$, $j$相邻才可能连边，所以维护$i$, $j$相邻，这样最多只会用到$n+m$个状态。状态中i与j都可以滚动，时间复杂度$O(n+m)$。
by Smallbasic @ 2019-07-05 22:19:20
最后一题第一个方程：
$f[i][j][1]=min(f[i-1][j][1]+a[i]-a[i-1], f[i-1][j][1]+dist(i,j),f[i-1][j][0]+a[i]-a[i-1]+dist(i,j))$
by Smallbasic @ 2019-07-05 22:20:46
好吧长度太小打不下。。。
by Smallbasic @ 2019-07-05 22:21:15
@[Smallbasic](/space/show?uid=98096) 谢谢巨佬（话说这是什么比赛？）
by brealid @ 2019-07-06 20:39:06
不知道
by Smallbasic @ 2019-07-06 20:49:45
好像是以前的orz教主模拟赛第二场
by Smallbasic @ 2019-07-06 20:50:25
luogu上没有吧，是一个学校自己出的
by Smallbasic @ 2019-07-06 20:50:48