\(\mathcal{Description}\)

Link.

给一个 \(n\times n\) 的网格图，每个点是空格或障碍。\(q\) 次询问，每次给定两个坐标 \((r_1,c_1),(r_2,c_2)\)，问最大的正方形边长 \(k\)，满足 \(k\) 是奇数，且中心点在 \((r_1,c_1)\) 的正方形能够移动成为中心点在 \((r_2,c_2)\) 的正方形。

\(n\le1000\)，\(q\le3\times10^5\)。

\(\mathcal{Solution}\)

这题咋黑了呢 owo？

令障碍为 \(1\)，空格为 \(0\)，则一个正方形合法等价于子矩阵和为 \(0\)，单次判断用前缀和做到 \(\mathcal O(1)\)。然后整体二分即可。

复杂度 \(\mathcal O((n^2+q)\log n)\)。

\(\mathcal{Code}\)

#include <queue>

#include <cstdio>

#include <vector>

typedef std::pair<int, int> pii;

const int MAXN = 1000, MAXQ = 3e5;

const int MOVE[4][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

int n, q, sum[MAXN + 5][MAXN + 5];

int ans[MAXQ + 5], color[MAXN + 5][MAXN + 5];

std::vector<pii> arrived;

struct Query { int r1, c1, r2, c2, id; };

std::vector<Query> qrys;

inline int rint () {

	int x = 0; char s = getchar ();

	for ( ; s < '0' || '9' < s; s = getchar () );

	for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );

	return x;

}

inline void wint ( const int x ) {

	if ( 9 < x ) wint ( x / 10 );

	putchar ( x % 10 ^ '0' );

}

inline bool legal ( const int r, const int c, const int rad ) {

	int r1 = r - rad, c1 = c - rad, r2 = r + rad - 1, c2 = c + rad - 1;

	return 0 <= r1 && 0 <= c1 && r2 <= n && c2 <= n

		&& ! ( sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1] );

}

inline void paint ( const int sr, const int sc, const int rad, const int c ) {

	static std::queue<pii> que;

	que.push ( { sr, sc } ), color[sr][sc] = c;

	arrived.push_back ( { sr, sc } );

	while ( ! que.empty () ) {

		pii p = que.front (); que.pop ();

		for ( int w = 0, tx, ty; w < 4; ++ w ) {

			tx = p.first + MOVE[w][0], ty = p.second + MOVE[w][1];

			if ( ! color[tx][ty] && legal ( tx, ty, rad ) ) {

				que.push ( { tx, ty } ), color[tx][ty] = c;

				arrived.push_back ( { tx, ty } );

			}

		}

	}

}

inline void solve ( std::vector<Query>& curq, const int al, const int ar ) {

	if ( curq.empty () ) return ;

	if ( al == ar ) {

		for ( auto q: curq ) ans[q.id] = al ? ( al << 1 ) - 1 : 0;

		return ;

	}

	int amid = al + ar + 1 >> 1, col = 0;

	for ( int i = amid, ei = n - amid + 1; i <= ei; ++ i ) {

		for ( int j = amid, ej = n - amid + 1; j <= ej; ++ j ) {

			if ( ! color[i][j] && legal ( i, j, amid ) ) {

				paint ( i, j, amid, ++ col );

			}

		}

	}

	std::vector<Query> vecL, vecR;

	for ( auto q: curq ) {

		if ( color[q.r1][q.c1] && color[q.r1][q.c1] == color[q.r2][q.c2] ) vecR.push_back ( q );

		else vecL.push_back ( q );

	}

	for ( pii c: arrived ) color[c.first][c.second] = 0;

	arrived.clear ();

	solve ( vecL, al, amid - 1 ), solve ( vecR, amid, ar );

}

int main () {

	n = rint ();

	char tmp[MAXN + 5];

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

		scanf ( "%s", tmp + 1 );

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

			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + ( tmp[j] == '#' );

		}

	}

	q = rint ();

	for ( int i = 1, r1, c1, r2, c2; i <= q; ++ i ) {

		r1 = rint (), c1 = rint (), r2 = rint (), c2 = rint ();

		qrys.push_back ( { r1, c1, r2, c2, i } );

	}

	solve ( qrys, 0, n + 1 >> 1 );

	for ( int i = 1; i <= q; ++ i ) wint ( ans[i] ), putchar ( '\n' );

	return 0;

}

巴特西

Solution -「CERC 2016」「洛谷 P3684」机棚障碍

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章