CF1335F Robots on a Grid
比较简单的倍增但还是看了题解才会
题意
给出一个 \(n\times m\) 的网格，每个格子有颜色，\(0\) 黑 \(1\) 白，每个格子还有一个方向，表示这个格子上的机器人会向那个方向走，并保证不会走出格子
摆放机器人，它们同时开始运动，在任意时刻不能有两个机器人在同一个格子里
先最大化机器人个数，如果多种方案机器人个数相等，再最大化摆在黑格子里的机器人数量
首先，这个路线肯定是循环的，如果不循环，就会走到无限多个格子，不合理
然后，对于任意一个格子，从那里开始走到完成一个完整的循环，步数肯定小于等于 \(nm\)，显然它不能走了比 \(nm\) 还多的格子仍然不开始循环
而对于两个不同的循环，它们一定没有交点（就是一个相同的格子），如果有，肯定就不会行成两个循环了
如果有两个机器人分别走了至少 \(nm\) 步，那么它们肯定已经各子循环了一次或以上了
所以，如果它们不在同一个循环，显然不会相遇
如果在一个循环，且没有在 \(nm\) 步内相遇，说明这时它们已经“同步”了，就是会一直保持这一个距离不断的走，永不相遇
当然，如果在 \(nm\) 步之前就已经相遇，那么它们会一直一起走，不会有影响
至此，我们判断两个格子上的机器人是否会相遇的方法，就是看它们走了 \(nm\) 步以后，是不是在同一个格子
所以，假设我们在所有格子都摆上机器人，让他们走，一旦有几个相遇了，就说明我们要去掉这些机器人只剩下其中的一个
这时，给这 \(nm\) 个点编号 \(1\ldots nm\)，并用\(white_i,black_i\)表示的分别是有没有从白/黑格出发的机器人，\(nm\) 格后会走到这里
然后从 \(1\) 到 \(nm\) 统计答案，如果某个格子可以由黑色格子中的机器人走来，就保留黑色格子的那个，否则任意保留
就可以计算出答案了
对于走 \(nm\) 步那个操作，就要用倍增实现
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<‘0‘||c>‘9‘){if(c==‘-‘) y=0;c=std::getchar();}
while(c>=‘0‘&&c<=‘9‘){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
int black[1000006],white[1000005];
int nex[24][1000006];
int color[1000006];
char s[1000006];
int main(){int T=read();while(T--){
int n=read(),m=read();
for(reg int i=1;i<=n;i++){
std::scanf("%s",s+1);
for(reg int j=1;j<=m;j++) color[(i-1)*m+j]=s[j]==‘0‘?0:1;
}
for(reg int i=1;i<=n;i++){
std::scanf("%s",s+1);
for(reg int j=1;j<=m;j++){
int now=(i-1)*m+j;
if(s[j]==‘U‘) nex[0][now]=now-m;
else if(s[j]==‘D‘) nex[0][now]=now+m;
else if(s[j]==‘L‘) nex[0][now]=now-1;
else nex[0][now]=now+1;
}
}
n*=m;
for(reg int i=1;i<=20;i++)
for(reg int j=1;j<=n;j++) nex[i][j]=nex[i-1][nex[i-1][j]];
for(reg int j=1;j<=n;j++){
int to=j;
for(reg int i=20;~i;i--){//倒着循环，倍增传统套路，不过想想也能知道，要先走大的步数
if((1<<i)&n) to=nex[i][to];
}
color[j]?white[to]=1:black[to]=1;
}
int ans=0,black_num=0;
for(reg int i=1;i<=n;i++)
if(black[i]) black_num++,ans++,black[i]=white[i]=0;
else if(white[i]) ans++,black[i]=white[i]=0;
std::printf("%d %d\n",ans,black_num);
}
return 0;
}