题解：P14014 [ICPC 2024 Nanjing R] 嘿，有看到我的袋鼠吗？

· · 题解

更好的阅读体验

袋鼠题。

考虑先暴力模拟一轮中每个袋鼠的运动。我们假设位于 (i, j) 的袋鼠，经过一轮之后到达 (i', j')，那么我们连边 (i, j) \to (i', j')，形成一个内基环树。

那么我们考虑一个格子在多少轮以前会有袋鼠。我们发现，一轮以后，每一个袋鼠都会向父亲跳一步。而到了最后，就只有一些袋鼠在环上一直跳。对于非环上的点 u，假设 u 子树内离 u 最远的叶子到 u 的距离为 d，那个点为 v，则 u 这个位置在 v 跳到 u 父亲之前都会有袋鼠，即在前 d+1 轮会有袋鼠。假设对于 u，有 tim_u = d+1。

当两个袋鼠到达同一个位置，可以认为是发生了合并，因为这两个袋鼠以后的运动轨迹都完全相同，可以让有袋鼠的格子数量 -1。那么我们考虑两个格子 x, y 合并的影响。我们发现，在 \min(tim_x, tim_y) 的时间内，这两个格子都会有袋鼠，合并的时间很好计算。所以我们可以存下所有合并事件发生的时间，再用 \max(tim_x, tim_y) 去更新当前格子有袋鼠的时间，因为虽然发生了合并，但是有袋鼠的最晚时间没有变。

那么这道题就做完了，复杂度 O(nmk)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 200006
#define fi first
#define se second
using namespace std;
using pii=pair<int,int>;
vector<int> mp[N],G[N];
vector<pii> v[N];
int n,m,k,cnt,tot,to[N],vis[N],ring[N],mxd[N],now[N],tmp[N],tim[N],ans[N];
char op[N],ch[N];
inline int id(int x,int y){return (x-1)*m+y;}
void find_ring(int u,int col)
{
    vis[u]=col;
    if(!vis[to[u]])find_ring(to[u],col);
    else if(vis[to[u]]==col) {
        int v=u;
        do {
            ring[v]=1,v=to[v];
        } while(v^u);
    }
}
void dfs(int u)
{
    mxd[u]=1;
    for(int v:G[u])if(!ring[v])
        dfs(v),mxd[u]=max(mxd[u],mxd[v]+1);
}
main()
{
    scanf("%lld%lld%lld%s",&n,&m,&k,op+1);
    for(int i=1;i<=n;i++)
        mp[i].resize(m+5),v[i].resize(m+5);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",ch+1);
        for(int j=1;j<=m;j++)mp[i][j]=ch[j]^48;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)if(mp[i][j])
            v[i][j]={i,j},cnt++;
    for(int l=1;l<=k;l++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)if(mp[i][j])
            {
                int &x=v[i][j].fi,&y=v[i][j].se;
                if(op[l]=='U'&&x>1&&mp[x-1][y])x--;
                else if(op[l]=='D'&&x<n&&mp[x+1][y])x++;
                else if(op[l]=='L'&&y>1&&mp[x][y-1])y--;
                else if(op[l]=='R'&&y<m&&mp[x][y+1])y++;
            }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)if(v[i][j].fi)
            to[id(i,j)]=id(v[i][j].fi,v[i][j].se),
            G[id(v[i][j].fi,v[i][j].se)].push_back(id(i,j));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(mp[i][j]&&!vis[id(i,j)])find_ring(id(i,j),id(i,j));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(ring[id(i,j)])dfs(id(i,j)),mxd[id(i,j)]=1e15;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)now[id(i,j)]=mxd[id(i,j)];
    for(int l=1;l<=k;l++)
    {
        memset(tmp,0,sizeof(tmp));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)if(mp[i][j])
            {
                int x=i,y=j;
                if(op[l]=='U'&&x>1&&mp[x-1][y])x--;
                else if(op[l]=='D'&&x<n&&mp[x+1][y])x++;
                else if(op[l]=='L'&&y>1&&mp[x][y-1])y--;
                else if(op[l]=='R'&&y<m&&mp[x][y+1])y++;
                int t=min(tmp[id(x,y)],now[id(i,j)]);
                for(int o=0;o<t;o++)tim[++tot]=o*k+l;
                tmp[id(x,y)]=max(tmp[id(x,y)],now[id(i,j)]);
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)now[id(i,j)]=tmp[id(i,j)];
    }
    sort(tim+1,tim+tot+1);
    for(int i=1;i<=cnt-tot-1;i++)ans[i]=-1;
    for(int i=1;i<=tot;i++)ans[cnt-i]=tim[i];
    for(int i=1;i<=n*m;i++)printf("%lld\n",ans[i]);
    return 0;
}