ABC311 CDE Solution - By LaDeX - 帖子

用 DFS 找一个环。用一个 vis 数组加标记即可。

LL n, vis[N];
vector<LL> G[N];
 
LL T = 0;
 
 
LL vis2[N], tmp[N];
void Find(LL x){
	if (vis2[x]){
		cout << T << "\n";
		for (LL i = 1; i <= T; i ++)
			cout << tmp[i] << " ";
		exit(0);
	}
	vis2[x] = 1;
	++ T;
	tmp[T] = x;
	for (auto it : G[x]){
		if (vis[it] >= 2)
			Find(it);
	}
	return ;
}
 
void DFS(LL x){
	++ vis[x];
	if (vis[x] == 3){
		Find(x);
		exit(0);
	}
	for (auto it : G[x]){
		DFS(it);
	}
	return ;
}
 
int main(){
	Fcin;
	cin >> n;
	LL x;
	for (LL i = 1; i <= n; i ++){
		cin >> x;
		G[i].emplace_back(x);
	}
	for (LL i = 1; i <= n; i ++){
		memset(vis, 0, sizeof (vis));
		if (vis[i])
			continue;
		DFS(i);
	}
	return 0;
}

暴力广搜，水。

LL n, m;
char G[1000][1000];
bool vis[1000][1000], res[1000][1000];
 
int main(){
	Fcin;
	cin >> n >> m;
	for (LL i = 1; i <= n; i ++){
		for (LL j = 1; j <= m; j ++){
			cin >> G[i][j];
		}
	}
 
	queue<pair<LL, LL> > q;
	q.push(mkp(2, 2));
	vis[2][2] = res[2][2] = 1;
	while (!q.empty()){
		LL x = q.front().first, y = q.front().second; q.pop();
 
		LL t1 = x, t2 = y;
		while (t1 > 1 && G[t1 - 1][t2] == '.'){
			res[t1 - 1][t2] = 1;
			t1 --;
		}
		if (t1 != x || t2 != y){
			if (!vis[t1][t2]){
				vis[t1][t2] = 1;
				q.push(mkp(t1, t2));
			}
		}
 
		t1 = x, t2 = y;
		while (t1 < n && G[t1 + 1][t2] == '.'){
			res[t1 + 1][t2] = 1;
			t1 ++;
		}
		if (t1 != x || t2 != y){
			if (!vis[t1][t2]){
				vis[t1][t2] = 1;
				q.push(mkp(t1, t2));
			}
		}
 
		t1 = x, t2 = y;
		while (t2 > 1 && G[t1][t2 - 1] == '.'){
			res[t1][t2 - 1] = 1;
			t2 --;
		}
		if (t1 != x || t2 != y){
			if (!vis[t1][t2]){
				vis[t1][t2] = 1;
				q.push(mkp(t1, t2));
			}
		}
 
		t1 = x, t2 = y;
		while (t2 < m && G[t1][t2 + 1] == '.'){
			res[t1][t2 + 1] = 1;
			t2 ++;
		}
		if (t1 != x || t2 != y){
			if (!vis[t1][t2]){
				vis[t1][t2] = 1;
				q.push(mkp(t1, t2));
			}
		}
	}
	LL Ans = 0;
	for (LL i = 1; i <= n; i ++){
		for (LL j = 1; j <= m; j ++)
			Ans += res[i][j];
	}
	cout << Ans;
	return 0;
}

提供一种二分做法。

对于每个格子二分一下它向右下延伸，最大的合法正方形边长，则答案就为。

二分处理时，整个正方形有无洞口是可以用二维前缀和预处理得到的。

时间复杂度：


bool check(LL x, LL y, LL Len){
	return (Pre[x + Len - 1][y + Len - 1] - Pre[x - 1][y + Len - 1] - Pre[x + Len - 1][y - 1] + Pre[x - 1][y - 1]) == 0;
}

int main(){
	Fcin;
	cin >> H >> W >> n;
	LL x, y;
	for (LL i = 1; i <= n; i ++){
		cin >> x >> y;
		Pre[x][y] = 1;
	}
	for (LL i = 1; i <= H; i ++){
		for (LL j = 1; j <= W; j ++){
			Pre[i][j] += Pre[i][j - 1];
		}
		for (LL j = 1; j <= W; j ++){
			Pre[i][j] += Pre[i - 1][j];
		}
	}
	LL cnt = 0;
	for (LL i = 1; i <= H; i ++){
		for (LL j = 1; j <= W; j ++){
			LL L = 1, R = min(H - i + 1, W - j + 1), res = 0;
			while (L <= R){
				LL Mid = (L + R) >> 1;
				if (check(i, j, Mid))
					L = Mid + 1, res = Mid;
				else
					R = Mid - 1;
			}
			cnt += R;
		}
	}
	cout << cnt;

	return 0;
}