题解：P13951 [ICPC 2023 Nanjing R] 酷，昨日四次重现

· · 题解

挺有意思的题。

对于一只袋鼠，为了淘汰更多的敌人，它必须要走到所有能走到的位置，即走遍它所在联通块内所有位置。如果走遍之后只剩它一个，它就可以贡献答案。显然这样是最优的。

分析一下时间复杂度：可能有 nm 只袋鼠，联通块大小为 nm，为了走遍联通块行走序列的长度为 nm，复杂度为 O((nm)^3)，显然会炸。

我们发现一个联通块可能会被搜索很多次，从这里下手优化。注意到对于一个联通块内所有袋鼠都会走遍这个联通块，那如果这个联通块内存在一只袋鼠能淘汰掉所有对手（把它叫做“胜利袋鼠”），那其他袋鼠可以先走到胜利袋鼠的位置，再重复走一遍胜利袋鼠的路径，也一定是一只胜利袋鼠。

如果这个联通块内的袋鼠不能淘汰掉所有对手（叫做“失败袋鼠”）呢？这等价于有另一个联通块的形状能完全覆盖这一个联通块。那对于这个联通块内其他袋鼠，都在大的联通块有一个对应的胜利袋鼠。它无法淘汰掉胜利袋鼠，所以它也是失败袋鼠。

最终，我们发现了一个性质：对于一个联通块内的袋鼠，要么全是胜利袋鼠，要么全是失败袋鼠。 因此对于每一个联通块只需要检验内部的一个袋鼠是否为胜利袋鼠即可。一个联通块对答案的贡献要么是 0 要么是联通块大小。

时间复杂度：最多检验 nm 只袋鼠，每只袋鼠走遍联通块的序列长度最多为 nm，复杂度 O((nm)^2)。我代码又臭又长，可以在下面品鉴一下。

:::info[AC 代码]

int n,m,k;
char a[N][N];
int col[N][N],cntcol=0;
vector<pii> p[N*N];
int num[N*N];
void dfs(int x,int y,int fx,int fy,int t){
    num[cntcol]++; 
    p[cntcol].pb(mkp(x-fx,y-fy));
    col[x][y]=t;
    up(i,0,3){
        int xx=x+dx[i],yy=y+dy[i];
        if(col[xx][yy]||a[xx][yy]=='O') continue;
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m) dfs(xx,yy,fx,fy,t);
    }
}
int ans=0;
bool check(int c){
    up(i,1,n){
        up(j,1,m){
            if(col[i][j]==0||col[i][j]==c) continue;
            bool cankill=0;
            For(s,p[c]){
                int xx=i+s._1,yy=j+s._2;
                if(a[xx][yy]=='O'||xx<1||xx>n||yy<1||yy>m){
                    cankill=1;
                    break;
                }
            }
            if(!cankill) return 0;
        }
    }
    return 1;
}
bool vis[N*N];
void Main(int cases){
    n=read(),m=read();
    up(i,1,n){
        up(j,1,m){
            cin>>a[i][j];
        }
    }
    cntcol=0;to0(col);ans=0;to0(num);to0(vis);
    up(i,1,n){
        up(j,1,m){
            if(!col[i][j]&&a[i][j]!='O'){
                cntcol++;
                p[cntcol].clear();
                dfs(i,j,i,j,cntcol);
            }
        } 
    }
    up(i,1,n){
        up(j,1,m){
            if(col[i][j]==0||vis[col[i][j]]) continue;
            vis[col[i][j]]=1;
            bool ok=check(col[i][j]);
            if(ok) ans+=num[col[i][j]];
        }
    }
    put(ans);
    return;
}

最后统计答案看似是 O((nm)^3) 的，但实际上完全跑不满，最慢的 #2 跑了 88 毫秒。 :::