相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_day1-statements.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_day1-solutions.pdf
解题报告
之前在BZOJ上看过这道题,然后当时嫌麻烦没有写
今天刚好考到,然后就被细节给搞死了_(:з」∠)_
一句话题解就是:用FFT做矩阵匹配
详细一点的话,大概就是:
先用FFT做一遍0/1矩阵匹配,求出能放阵型的位置
然后BFS出能到达的位置
最后再做一遍FFT求出每个点被覆盖了多少次
Code
#include<bits/stdc++.h>
#define LL long long
#define CP complex<double>
using namespace std;
const int N = 709;
const int M = 5000000;
const double EPS = 0.5;
const double PI = acos(-1);
char mp[N][N];
int n, m, vis[M], sfe[M];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
CP a[M], b[M], c[M];
inline void FFT(CP *arr, int len, int ty) {
static int pos[M], init = 0;
if (init != len) {
for (int i = 1; i < len; ++i) {
pos[i] = (pos[i >> 1] >> 1) | ((i & 1)? (len >> 1): 0);
}
init = len;
}
for (int i = 0; i < len; i++) {
if (pos[i] < i) {
swap(arr[i], arr[pos[i]]);
}
}
for (int i = 1; i < len; i <<= 1) {
CP wn(cos(PI / i), sin(PI / i) * ty);
for (int j = 0; j < len; j += i + i) {
CP w(1, 0);
for (int k = 0; k < i; k++, w *= wn) {
CP tmp = arr[j + i + k] * w;
arr[j + i + k] = arr[j + k] - tmp;
arr[j + k] = arr[j + k] + tmp;
}
}
}
if (ty == -1) {
for (int i = 0; i < len; i++) {
arr[i] /= len;
}
}
}
inline void BFS(int sx, int sy, int lx, int ly) {
vis[sy * n + sx] = 1;
queue<pair<int, int> > que;
for (que.push(make_pair(sx, sy)); !que.empty(); que.pop()) {
int x = que.front().first;
int y = que.front().second;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (0 <= nx && nx + lx - 1 < n && 0 <= ny && ny + ly - 1 < m && sfe[ny * n + nx] && !vis[ny * n + nx]) {
que.push(make_pair(nx, ny));
vis[ny * n + nx] = 1;
}
}
}
}
int main() {
freopen("sailing.in", "r", stdin);
freopen("sailing.out", "w", stdout);
cin >> m >> n;
int mnx = n, mny = m, mxx = 0, mxy = 0;
for (int j = 0; j < m; j++) {
scanf("%s", mp[j]);
for (int i = 0; i < n; i++) {
if (mp[j][i] == 'o') {
mnx = min(i, mnx);
mxx = max(i, mxx);
mny = min(j, mny);
mxy = max(j, mxy);
}
}
}
for (int j = 0; j < m; ++j) {
for (int i = 0; i < n; ++i) {
if (mp[j][i] == 'o') {
b[(j - mny) * n + i - mnx] = CP(1, 0);
} else if (mp[j][i] == '#') {
a[j * n + i] = CP(1, 0);
}
}
}
int cur = n * m, len = 1;
for (; len < cur * 2; len <<= 1);
for (int l = 0, r = cur - 1; l < r; ++l, --r) {
swap(b[l], b[r]);
}
FFT(a, len, 1);
FFT(b, len, 1);
for (int i = 0; i < len; i++) {
a[i] *= b[i];
}
FFT(a, len, -1);
for (int i = 0; i < cur; i++) {
if (a[i + cur - 1].real() < EPS) {
sfe[i] = 1;
}
}
BFS(mnx, mny, mxx - mnx + 1, mxy - mny + 1);
memset(b, 0, sizeof(b));
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
c[j * n + i] = vis[j * n + i]? CP(1, 0): CP(0, 0);
b[(j - mny) * n + i - mnx] = mp[j][i] == 'o'? CP(1, 0): CP(0, 0);
}
}
FFT(c, len, 1);
FFT(b, len, 1);
for (int i = 0; i < len; i++) {
c[i] *= b[i];
}
FFT(c, len, -1);
int ans = 0;
for (int i = 0; i < cur; i++) {
ans += c[i].real() > EPS;
}
printf("%d\n", ans);
return 0;
}
—————————— UPD 2017.6.30 ——————————
B站题号:4624