[CF1335F] Robots on a Grid - 倍增

Description

给定 \(n \times m\) 的棋盘，每个格子有一个颜色和方向。如果一个机器人此时在某个格子中，那么下一时刻他会移动的这个格子的方向所指向的相邻的格子中。若干个机器人在棋盘上无限地走下去，请找出一种放置机器人的方案，需要保证任意时刻不会有两个机器人同时出现在同一个格子中，在最大化机器人总数的前提下，最大化初态下位于黑色格子上的机器人总数。

Solution

很显然我们需要对每一个“连通块”分别考虑，这个连通块一定包含一个环以及若干个内向链。

暴力找环用并查集维护当然可以，但是有点麻烦。

考虑到在足够长的时间后，所有机器人一定都会走到环上去，因此我们只需要给出一个足够大的 \(M\)，求出 \(M\) 时间后，每个初态位置可以到达的位置，这些位置的并集的大小就是答案。

考虑倍增，令 \(f[i][j]\) 表示点 \(i\) 走了 \(2^j\) 步后的位置，常规处理即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;

int n,m,f[N][22],buc[N];
char col[N],dir[N];

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>col+(i-1)*m+1;
    for(int i=1;i<=n;i++) cin>>dir+(i-1)*m+1;
    for(int i=1;i<=n*m;i++) 
    {
        if(dir[i]==‘U‘) f[i][0]=i-m;
        if(dir[i]==‘D‘) f[i][0]=i+m;
        if(dir[i]==‘L‘) f[i][0]=i-1;
        if(dir[i]==‘R‘) f[i][0]=i+1;
    }
    for(int j=1;j<=20;j++) for(int i=1;i<=n*m;i++) 
    {
        f[i][j]=f[f[i][j-1]][j-1];
    }
    for(int i=1;i<=n*m;i++) buc[i]=0;
    for(int i=1;i<=n*m;i++) buc[f[i][20]]=1;
    int ans=0,ans2=0;
    for(int i=1;i<=n*m;i++) if(buc[i]) ans++;
    for(int i=1;i<=n*m;i++) buc[i]=0;
    for(int i=1;i<=n*m;i++) if(col[i]==‘0‘) buc[f[i][20]]=1;
    for(int i=1;i<=n*m;i++) if(buc[i]) ans2++;
    cout<<ans<<" "<<ans2<<endl;
}

signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

[CF1335F] Robots on a Grid - 倍增

原文：https://www.cnblogs.com/mollnn/p/13971698.html