发布于 由itewqq

[思维][预处理][区间信息技巧] codeforces 1015E2 Stars Drawing (Hard Edition)

还是找星星，但是数据量升高了，不能用n^3复杂度的算法了

这里可以用六个预处理的矩阵来表示信息，前四个分别为上下左右到当前位置的连续的星个数，这样就不用每次到一个坐标都从新求了。后两个分别为两个标记矩阵，这里的思想很像之前有个AC自动机替换禁忌词的题目，因为那个题目禁忌词可能互相冲突，互相交错，互相包含，而这个里面的不同的星星也会出现这种情况，所以采用了类似的方法：在左端点标记+1，右端点标记-1，然后再把矩阵从左往右过一遍，h[i][j]=h[i][j]+h[i][j-1]，这样的话，就可以确定出来一个点有没有被星星覆盖到：如果他的h或v大于0就被覆盖了，否则就没有。所有的矩阵预处理都是n^2的复杂度，总共6*n^2大概。

 

#include 
#include 
#include
#include
#include
#include
#include

using namespace std;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
typedef long long LL;

char board[1005][1005];
int lft[maxn][maxn];
int rht[maxn][maxn];
int up[maxn][maxn];
int down[maxn][maxn];
int ab[maxn][maxn];
int h[maxn][maxn];
int v[maxn][maxn];
struct node
{
    int x,y,w;
    node(int x,int y,int w):x(x),y(y),w(w){}
};

vector ns;

int main()
{
    int n,m;
    scanf("%d %d\n",&n,&m);
    for (int i=1; i<=n; i++)
        gets(board[i]+1);
    for (int i=1;i<=n;i++)
    {
        for (int j=1; j<=m; j++)if(board[i][j]=='*')
        {
            lft[i][j]=lft[i][j-1]+1;
        }
        for (int j=m;j>0;j--)if(board[i][j]=='*')
        {
            rht[i][j]=rht[i][j+1]+1;
        }
    }
    for (int j=1;j<=m;j++)
    {
        for (int i=1;i<=n;i++)if(board[i][j]=='*')
        {
            up[i][j]=up[i-1][j]+1;
        }
        for (int i=n;i>0;i--)if(board[i][j]=='*')
        {
            down[i][j]=down[i+1][j]+1;
        }
    }
    int temp;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
    {
        temp=min(up[i][j],down[i][j]);
        temp=min(temp,min(lft[i][j],rht[i][j]));
        if(temp>1)
            ns.push_back(node(i,j,temp-1));
    }
    int len=ns.size();
    int x,y,w;
    for (int i=0;i

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。