[CF1335F] Robots on a Grid

题目链接

Solution

其实给定的图是一个基环树森林。

容易知道，对于每一个基环树，它最多能放的机器人数量就是它的环的长度。主要问题在于怎么找到一种放置方式使黑色节点最多。

我们可以任取环内一点开始 $dfs$，用 $1\sim r$ 循环染色，其中 $r$ 是环的长度。可以证明，在两个同色的节点处放置机器人是不合法的，因为充分长的时间后，它们会在环中该颜色的节点处相遇，换句话说，它们之间相差整数个周期（一个周期就是 $r$）；而在不同色的节点处的两个机器人，它们永远都不会差整数个周期，就永远不会相遇。

所以开一个 set，记录某颜色是否有黑色节点，最后数 set 的大小即可。

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 1000005;

int T, n, m;
char s[N];
vector<char> c, g;
vector<int> edge[N];

int fa[N];
int findfa(int x){ return fa[x] == x ? x : fa[x] = findfa(fa[x]); }
void unionn(int x, int y){
	if(findfa(x) == findfa(y))	return;
	fa[findfa(y)] = findfa(x);
}

inline int getNum(int x, int y){ return x * m + y; }

vector<bool> vis;
vector<int> dis;
int dfs(int x, int d){
	if(vis[x])	return d - dis[x];
	vis[x] = 1; dis[x] = d;
	if(g[x] == 'U')	return dfs(x-m, d+1);
	if(g[x] == 'D')	return dfs(x+m, d+1);
	if(g[x] == 'L')	return dfs(x-1, d+1);
	if(g[x] == 'R')	return dfs(x+1, d+1);
	return -233;
}

vector<bool> vis2;
set<int> col;
void dfs(int x, int color, int MOD){
	if(vis2[x])	return;
	vis2[x] = 1;
	if(c[x] == '0')	col.insert(color);
	for(auto nxt: edge[x])
		dfs(nxt, (color + 1) % MOD, MOD);
}

int main(){
	for(read(T); T; T--){
		read(n, m);
		for(int i = 0; i < n * m; i++){
			fa[i] = i;
			edge[i].clear();
		}
		vis.clear(); vis.resize(n * m, 0);
		vis2.clear(); vis2.resize(n * m, 0);
		dis.clear(); dis.resize(n * m, 0);
		c.resize(n * m), g.resize(n * m);
		for(int i = 0; i < n; i++){
			scanf("%s", s);
			for(int j = 0; j < m; j++)
				c[i*m+j] = s[j];
		}
		for(int i = 0; i < n; i++){
			scanf("%s", s);
			for(int j = 0; j < m; j++){
				g[i*m+j] = s[j];
				if(g[i*m+j] == 'U'){
					unionn(getNum(i-1, j), getNum(i, j));
					edge[getNum(i-1, j)].emplace_back(getNum(i, j));
				}
				if(g[i*m+j] == 'D'){
					unionn(getNum(i+1, j), getNum(i, j));
					edge[getNum(i+1, j)].emplace_back(getNum(i, j));
				}
				if(g[i*m+j] == 'L'){
					unionn(getNum(i, j-1), getNum(i, j));
					edge[getNum(i, j-1)].emplace_back(getNum(i, j));
				}
				if(g[i*m+j] == 'R'){
					unionn(getNum(i, j+1), getNum(i, j));
					edge[getNum(i, j+1)].emplace_back(getNum(i, j));
				}
			}
		}
		int ans0 = 0, ans1 = 0;
		for(int i = 0; i < n * m; i++){
			if(findfa(i) == i){
				int res = dfs(i, 0);
				ans0 += res;
				col.clear();
				dfs(i, 0, res);
				ans1 += col.size();
			}
		}
		printf("%d %d\n", ans0, ans1);
	}
	return 0;
}