【题解】CF1015E Stars Drawing

原题链接:点这里这里

解法

其实这题应该要缩短时间限制,不然感觉暴力都可以卡过去。

这里提供一个 $O(nm \cdot\log \min(n,m))$ 的做法。

首先 E1 的暴力做法比较好实现:

  • 枚举每一个 $‘*‘$ 的位置,并且尽可能向四个方向扩展,标记每一个扩展的位置。
  • 如果出现没有标记过的 $‘*‘$,输出 $-1$,否则输出刚刚扩展的方案。

这个想法的时间复杂度是三次方级别的,我们应将其优化。

如何快速定位每个位置的最大扩展长度

我们可以先只考虑一行或一列的情况。

如果我们把 $‘*‘$ 的值视作 $1$,其余视作 $0$,那么一段区间的价值和就是区间中 $‘*‘$ 的数量。

所以,如果区间 $[l,r]$ 内全是 $‘*‘$ 而没有 $‘.‘$,那么该区间的价值和为 $r-l+1$。

而我们扩展的时候,需要保证的是这个「星星图案」内没有 $‘.‘$ 。

若从 $(i,j)$ 扩展长度 $k$,那么需要保证第 $i$ 行的第 $j-k~ \sim j+k$ 列位置全部为 $‘*‘$,第 $j$ 列同理。

上述条件,等价于第 $i$ 行的 $‘*‘$ 总数为 $j+k-(j-k)+1=2k+1$。

如果不理解,可以看如下例子:

...*...
...*...
...*...
*******
...*...
...*...
...*...

这是一个大小为 $3$ 的「星星图案」。

其中有「星星图案」的行、列的区间 $‘*‘$ 数均为 $2\times3+1=7$。

而如下这个图没有长度为 $3$「星星图案」。

...*...
.......
...*...
*******
...*...
...*...
...*...

原因是若以 $(4,4)$ 为中心扩展 $3$ 格,那么第 $4$ 列的区间和为 $6$,与 $7$ 不相等。

静态维护区间和,我们就可以使用前缀和

只不过这是一个二维图案,我们需要分别对它进行行、列的前缀和。

如何优化时间复杂度

可以发现,如果以某点为中心,可以向外扩展 $k+1$ 个单位,那么它也绝对可以向外扩展 $k$ 个单位。

因此,扩展的长度相对条件具有单调性,我们可以二分查找

如何快速判断无解

如果我们一个一个标记每个 $‘*‘$ 的位置是否访问过,那复杂度就退化了。

但是我们有足够的复杂度可以在最后时刻一次性访问每个位置,判断它是否被访问过。

所以,将整个区间进行标记,可以是用差分,最后用前缀和求得答案。

注意一个「星星图案」的行、列都要标记。

有人会有所担心行、列若分别标记一次,中心会被标记两次,影响答案。

其实并不会,因为最后只有行、列的差分数组前缀和均为 $0$,才代表这个位置没有访问过。因此访问次数我们并不需要在意。

以下是代码,不理解的地方可以参考注释

#include <bits/stdc++.h>
#define INF 1e9
#define eps 1e-6
typedef long long ll;
using namespace std;

int n, m, suml[1010][1010], sumu[1010][1010], l, r;
int addl[1010][1010], addw[1010][1010], sl[1010][1010], sw[1010][1010];
int ss, ans1[1000010], ans2[1000010], ans3[1000010];
bool vis[1010][1010];
char s[1010][1010];

bool check(int i, int j, int x){    // 判断是否全为 *
    if(sumu[i + x][j] - sumu[i - x - 1][j] != x + x + 1) return 0;
    if(suml[i][j + x] - suml[i][j - x - 1] != x + x + 1) return 0;
    return 1;
}

int main(){

    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        scanf("%s", s[i] + 1);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)    // 行和列分别前缀和
            suml[i][j] = suml[i][j - 1] + (s[i][j] == *);
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            sumu[j][i] = sumu[j - 1][i] + (s[j][i] == *);
            
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            // 扩展范围不能超出边界
            l = 0, r = min(i - 1, min(n - i, min(j - 1, m - j)));
            while(l < r){
                int mid = (l + r + 1) >> 1;
                if(check(i, j, mid)) l = mid;
                else r = mid - 1;
            }
            if(l != 0){    // 记录答案、标记差分数组
                ans1[++ss] = i, ans2[ss] = j, ans3[ss] = l;
                addl[i - l][j]++, addl[i + l + 1][j]--;
                addw[i][j - l]++, addw[i][j + l + 1]--;
            }
        }
    for(int i = 1; i <= n; i++)    // 将差分数组进行前缀和得到访问记录
        for(int j = 1; j <= m; j++)
            sw[i][j] = sw[i][j - 1] + addw[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            sl[i][j] = sl[i - 1][j] + addl[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            if(sw[i][j] == 0 && sl[i][j] == 0 && s[i][j] == *){    // 没有访问过的 * 需要输出 -1
                puts("-1");
                return 0;
            }
        }
    cout << ss << endl;    // 输出答案
    for(int i = 1; i <= ss; i++)
        printf("%d %d %d\n", ans1[i], ans2[i], ans3[i]);

    return 0;
}

【题解】CF1015E Stars Drawing

上一篇:delphi xe 10.3 利用Git组群开发,Git服务器安装,Git 拉取,提交,推送相关设置操作


下一篇:acwing 143. 最大异或对