Codeforces Round 634 (Div. 3) F题题解

题意

给你一个 $n\times m$ 的矩阵，每个格子上有颜色， $0$ 代表黑， $1$ 代表白。每个格子上还有方向，在这个格子上的机器人会向格子方向的方向走，并且题目保证机器人不会走出矩阵。

你需要完成以下几个任务：

在格子上摆放尽可能多的机器人，他们同时开始无尽地运动，并且任何时刻都不能有两个机器人在同一个格子
首先最大化机器人的个数，如果有多种方案机器人个数相等，再最大化初始时摆在黑格内的机器人

首先，题目中提到的无尽，则代表每个机器人走的路线都是循环的。

对于每个机器人，它走的路径最长也就是 $n*m$ 。我们考虑在 $n * m$ 步内机器人的相遇情况

如果有两个机器人在不在同一个循环里，毫不相干。则它们肯定不会相遇

如果有两个机器人在同一个循环里，并且在 $n\times m$ 的步数里没有相遇，则他们也会以这样的节奏继续走下去，也不会相遇；反之如果相遇了的话，他们会在同样的格子里一直走下去。

所以我们想判断两个机器人是否会相遇，只需要看在 $n\times m$ 的步数里两个机器人是否在一起就行了

我们用一维 $color$ 数组表示每个位置的颜色，用 $white$ 和 $black$ 数组表示机器人的初始位置的颜色

对于走 $n\times m$ ，我们可以使用倍增，最后统计答案。

const ll MAXN=1e6+10;
ll a[MAXN],color[MAXN],black[MAXN],white[MAXN],mult[21][MAXN];
ll t,n,m;
char ch[MAXN];
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>ch+1;
			for(int j=1;j<=m;j++){
				if(ch[j]=='0')color[(i-1)*m+j]=0;//黑色
				else color[(i-1)*m+j]=1;//白色
			}
		}
		for(int i=1;i<=n;i++){
			cin>>(ch+1);
			for(int j=1;j<=m;j++){
				ll pos=(i-1)*m+j; //在数组上的位置
				if(ch[j]=='U')mult[0][pos]=pos-m;//上
				if(ch[j]=='D')mult[0][pos]=pos+m;//下
				if(ch[j]=='L')mult[0][pos]=pos-1;//左
				if(ch[j]=='R')mult[0][pos]=pos+1;//右
			}
		}
		ll matrix=n*m;//最大路径
		for(int i=1;i<=20;i++){
			for(int j=1;j<=matrix;j++){
				mult[i][j]=mult[i-1][mult[i-1][j]];//倍增
			}
		}
		for(int j=1;j<=matrix;j++){
			ll pos=j;
			for(int i=20;i;i--){
				if((1<<i)&matrix)pos=mult[i][pos];
			}
			if(color[j])white[pos]=1;//是白
			else black[pos]=1;//是黑
		}
		ll res=0,bla=0;
		for(int i=1;i<=matrix;i++){
			if(black[i]){
				res++;
				bla++;//是黑色的++
				black[i]=0;
				white[i]=0;
			}
			else if(white[i]){
				res++;
				black[i]=0;
				white[i]=0;
			}
		}
		cout<<res<<' '<<bla<<endl;
	}
	return 0;
}

第一次在自己博客里发题解，感觉就是给菜鸡一样的自己看的，以后会继续尝试div3f题的qaq/kk

还是希望大佬能支持/kel

Oak_limy 的博客