BZOJ5217: [Lydsy2017省队十连测]航海舰队
? 解题记录 ? ? BZOJ ? ? FFT|NTT ?    2018-09-20 14:56:12    894    0    0

## Description

Byteasar 组建了一支舰队！他们现在正在海洋上航行着。海洋可以抽象成一张n×m 的网格图，其中有些位置是“
.”，表示这一格是海水，可以通过；有些位置是“#”，表示这一格是礁石，不可以通过；有些位置是“o”，表

，帮助Byteasar 计算他最多可以获得多少个格子海底的矿藏？

4 5
....#
.o#.o
.o..o
..o..

12

## 注意为了避免舰队穿过右边版面到左边的情况，要把这些位置开头的舰队放置方案清零。

```#include<cstdio>
#include<cstring>
#include<algorithm>
#include<complex>
#include<cmath>
#define LL long long
using namespace std;
const double Pi = acos(-1);
const int maxn = 1e6 + 5;

struct E {
#define T double
T real, imag; E(){}
E(T x, T y) {real = x, imag = y;}
E operator + (const E &A) const {
return (E){real + A.real, imag + A.imag};
}
E operator - (const E &A) const {
return (E){real - A.real, imag - A.imag};
}
E operator * (const E &A) const {
return (E){real * A.real - imag * A.imag, real * A.imag + imag * A.real};
}
};

char mp[705][705], ship[705][705];
char s[maxn << 1], t[maxn << 1];
int n, m, cnt;
E sn[maxn << 1], tn[maxn << 1], tmp[maxn << 1];
E sn2[maxn << 1], tn2[maxn << 1], tn3[maxn << 1];
double sum;
int ans[maxn << 1], vis[705][705];
int omnx = 0x3f3f3f3f, omny = 0x3f3f3f3f, omxx, omxy;

namespace match {
int n, m, lt[705][705], acc[705][705];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
void dfs(int x, int y) {
int nx, ny;
acc[x][y] = 1;
for(register int i = 0; i < 4; ++i) {
nx = x + dx[i];
ny = y + dy[i];
if(!lt[nx][ny]) continue;
if(acc[nx][ny]) continue;
dfs(nx, ny);
}
}
namespace FFT {
int RL[maxn << 1], N, mxp;
void init(int n) {
for(N = 1, mxp = 0; N < n; N <<= 1, ++mxp);
for(register int i = 1; i <= N; ++i)
RL[i] = (RL[i >> 1] >> 1) | ((i & 1) << mxp - 1);
return ;
}
void FFT(E * A, int type) {
for(register int i = 0; i < N; ++i)
if(i < RL[i]) swap(A[i], A[RL[i]]);
E Wn, w, x, y;
for(register int i = 1; i < N; i <<= 1) {
Wn = E(cos(Pi / i), sin(Pi / i) * type);
for(register int j = 0, p = i << 1; j < N; j += p) {
w = E(1, 0);
for(register int k = 0; k < i; ++k, w = w * Wn) {
x = A[j + k], y = w * A[j + k + i];
A[j + k] = (x + y), A[j + k + i] = (x - y);
}
}
}
}
void calc(E * sn2, E * tn, E * sn, E * tn2, int n, int m) {
init(n + m);
FFT(sn2, 1), FFT(tn, 1), FFT(tn2, 1), FFT(sn, 1);
for(register int i = 0; i <= N; ++i)
sn2[i] = sn2[i] * tn[i] - E(2, 0) * tn2[i] * sn[i];
FFT(sn2, -1);
for(register int i = 0; i <= N; ++i)
sn2[i].real /= N;
}
void mul(E * A, E * B, int n, int m) {
init(n + m);
FFT(A, 1), FFT(B, 1);
for(register int i = 0; i <= N; ++i)
A[i] = A[i] * B[i];
FFT(A, -1);
for(register int i = 0; i <= N; ++i)
A[i].real /= N;
}
}
int work() {
n = strlen(s) - 1, m = strlen(t) - 1;
int u;
for(register int i = 0; i <= n; ++i) {
u = n - i;
sn[u].real = s[i] == '#' ? 1 : 2;
sn2[u].real = sn[u].real * sn[u].real;
}
for(register int i = 0; i <= m; ++i) {
if(t[i] == '?') tn[i].real = 0;
else tn[i].real = 2;
tn2[i].real = tn[i].real * tn[i].real;
tn3[i].real = tn[i].real * tn2[i].real;
sum += tn3[i].real;
}
memcpy(tmp, tn, sizeof(tn));
FFT::calc(sn2, tmp, sn, tn2, n + 1, n + 1);
reverse(sn2, sn2 + n + 1);
for(register int i = 0; i <= n; ++i) {
ans[i] = !(((int)(sn2[i].real + sum + 0.5)) != 0);
}
int tot = 0;
for(register int i = 0; i < ::n; ++i) {
for(register int j = 0; j < ::m; ++j) {
++tot;
if(i < ::n - (omxx - omnx) && j < ::m - (omxy - omny))
{lt[i][j] = ans[tot - 1]; continue;}
lt[i][j] = 0;
}
}
memset(tmp, 0, sizeof(tmp));
dfs(omnx, omny), tot = 0;
for(register int i = 0; i < ::n; ++i)
for(register int j = 0; j < ::m; ++j) {
if(!acc[i][j]) ans[tot] = 0;
tmp[tot].real = ans[tot], ++tot;
}
FFT::mul(tmp, tn, n - m + 1, m + 1);
return 0;
}
}

int main() {
//freopen("sailing.in", "r", stdin);
//freopen("sailing.out", "w", stdout);
scanf("%d%d", &n, &m);
for(register int i = 0; i < n; ++i)
scanf("%s", mp[i]);
for(register int i = 0; i < n; ++i)
for(register int j = 0; j < m; ++j) {
if(mp[i][j] == 'o') {
omnx = min(omnx, i);
omxx = max(omxx, i);
omny = min(omny, j);
omxy = max(omxy, j);
}
}
for(register int j = omny; j < m; ++j) {
if(mp[omnx][j] == 'o') t[cnt] = '.';
else t[cnt] = '?';
++cnt;
}
for(register int i = omnx + 1; i < omxx; ++i)
for(register int j = 0; j < m; ++j) {
if(mp[i][j] == 'o') t[cnt] = '.';
else t[cnt] = '?';
++cnt;
}
for(register int j = 0; j < m; ++j) {
if(mp[omxx][j] == 'o') t[cnt] = '.';
else t[cnt] = '?';
++cnt;
}
t[cnt] = 0, cnt = 0;
for(register int i = 0; i < n; ++i)
for(register int j = 0; j < m; ++j) {
mp[i][j] = mp[i][j] == 'o' ? '.' : mp[i][j];
s[cnt] = mp[i][j], ++cnt;
}
s[cnt] = 0;
match::work();
int tot = 0, lans = 0;
for(register int i = 0; i < n; ++i)
for(register int j = 0; j < m; ++j)
if((int)(tmp[tot++].real)) ++lans;
printf("%d", lans);
return 0;
}
```

894 人读过

0 条评论