相关链接
题目传送门: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