BZOJ5217：[Lydsy2017省队十连测]航海舰队—

https://www.lydsy.com/JudgeOnline/problem.php?id=5217

Byteasar 组建了一支舰队！他们现在正在海洋上航行着。海洋可以抽象成一张n×m 的网格图，其中有些位置是“.”，表示这一格是海水，可以通过；有些位置是“#”，表示这一格是礁石，不可以通过；有些位置是“o”，表示这一格目前有一艘舰，且舰离开这一格之后，这一格将变为“.”。这些“o” 表示Byteasar 的舰队，他们每天可以往上下左右中的一个方向移动一格，但不能有任何一艘舰驶出地图。特别地，Byteasar 对阵形有所研究，所以他不希望在航行的过程中改变阵形，即任何时刻任何两艘舰的相对位置都不能发生变化。Byteasar 的舰队可以航行无限长的时间，每当一艘舰经过某个格子的时候，这个格子海底的矿藏都将被Byteasar 获得。请写一个程序，帮助Byteasar 计算他最多可以获得多少个格子海底的矿藏？

很妙……如果没有做过类似的题可能打死也不知道是道FFT题。

首先将最小的包含所有舰队的矩形拿出来，那么先不考虑能否到达，我们只需要将这个小矩形和大矩形匹配，就能知道我们舰队能够放在哪里。

于是想到暴力匹配，但是显然是过不了的。

想到BZOJ4259：残缺的字符串这道题，但是那是一维匹配，而我们要二维匹配。

所以一个想法就是降维，简单点说，就是第一行字符+第二行字符+……

设大矩形为a[]，小矩形（需要将大小填充等于大矩形）为b[]。

对于一个合法的匹配位置的左上角下标为p，则有对于所有的位置，都不能存在a[p+i]有礁石，b[i]有舰队这种情况。

于是令a中礁石=1，b中舰队=1，则就是f[i]=sigma(a[i+j]*b[j])=0，将a矩阵倒存，就有f[i]=sigma(a[n*m-i-j]*b[j])是一个卷积形式，于是FFT。

接下来考虑，对于所有的左上角，我们并不是都能到达的，所以从小矩阵最开始的左上角搜索找到所有合法的左上角。

最后就是一个点其下标为p，它能到达当其存在一个左上角p-i合法，且b[i]=1，于是令所有合法左上角=1，则f[i]=sigma(a[i-j]*b[j])>0，直接就是一个卷积，FFT求一遍就行了。

#include<map>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef double dl;

typedef pair<int,int>pii;

#define fi first

#define se second

const dl pi=acos(-1.0);

const dl eps=0.5;

const int M=;

const int N=M*M*;

struct complex{

    dl x,y;

    complex(dl xx=,dl yy=){

    x=xx;y=yy;

    }

    complex operator +(const complex &b)const{

    return complex(x+b.x,y+b.y);

    }

    complex operator -(const complex &b)const{

    return complex(x-b.x,y-b.y);

    }

    complex operator *(const complex &b)const{

    return complex(x*b.x-y*b.y,x*b.y+y*b.x);

    }

};

void FFT(complex a[],int n,int on){

    for(int i=,j=n>>;i<n-;i++){

    if(i<j)swap(a[i],a[j]);

    int k=n>>;

    while(j>=k){j-=k;k>>=;}

    if(j<k)j+=k;

    }

    for(int i=;i<=n;i<<=){

    complex res(cos(-*on*pi/i),sin(-*on*pi/i));

    for(int j=;j<n;j+=i){

        complex w(,);

        for(int k=j;k<j+i/;k++){

        complex u=a[k],t=w*a[k+i/];

        a[k]=u+t;a[k+i/]=u-t;

        w=w*res;

        }

    }

    }

    if(on==-)

    for(int i=;i<n;i++)a[i].x/=n;

}

bool vis[M][M];

int n,m;

int dx[]={,,,-};

int dy[]={,,-,};

char mp[M][M];

complex a[N],b[N];

queue<pii>q;

void bfs(int sx,int sy){

    q.push(pii(sx,sy));

    vis[sx][sy]=;

    while(!q.empty()){

    int x=q.front().fi,y=q.front().se;q.pop();

    a[(x-)*m+y-]=complex(,);

    for(int i=;i<;i++){

        int nx=x+dx[i],ny=y+dy[i];

        if(vis[nx][ny]){

        vis[nx][ny]=;

        q.push(pii(nx,ny));

        }

    }

    }

}

int main(){

    int x1=M,y1=M,x2=,y2=;

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%s",mp[i]+);

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

        if(mp[i][j]=='o')x1=min(x1,i),y1=min(y1,j),x2=max(x2,i),y2=max(y2,j);

        else if(mp[i][j]=='#')a[n*m-(i-)*m-j]=complex(,);

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

        if(mp[i][j]=='o')b[(i-x1)*m+j-y1]=complex(,);

    int len=;

    while(len<n*m)len<<=;

    FFT(a,len,);FFT(b,len,);

    for(int i=;i<len;i++)a[i]=a[i]*b[i];

    FFT(a,len,-);

    for(int i=;i<=n-(x2-x1);i++)

    for(int j=;j<=m-(y2-y1);j++)

        if(a[n*m-(i-)*m-j].x<eps)vis[i][j]=;

    for(int i=;i<len;i++)a[i]=complex(,);

    bfs(x1,y1);

    FFT(a,len,);

    for(int i=;i<len;i++)a[i]=a[i]*b[i];

    FFT(a,len,-);

    int ans=;

    for(int i=;i<n*m;i++)if(a[i].x>eps)ans++;

    printf("%d\n",ans);

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

BZOJ5217：[Lydsy2017省队十连测]航海舰队——题解

最新文章

热门文章