B3983

wosile · 2024-06-05 11:13:39 · 题解

UPD：修正笔误。

信息与未来真神吧？拿这种东西给小学生做？

我的做法可能偏复杂了。

观察到 n,m \le 10，对于每对括号，我们可以先对于其内部的字符串，计算出对于每一种初始位置，经过这个字符串后可能会到达哪里，以及可能会经过哪些位置。这两个信息可以用两个大小为 nm \times nm 的 \texttt{01} 矩阵 M_t,M_p 表示。也就是说，一段字符串 S 就可以转化成一个矩阵二元组 (M_t,M_p)。

对于单个字符 LRUD，我们可以提前把它们对应的这两个矩阵算出来。

方便起见，我们把全部 nm 个位置从 1 到 nm 编号，比如说，S(M_t,M_p) 中，M_p(x,y) 就代表从编号为 x 的位置开始，经过字符串 S 所代表的操作序列，有没有可能经过编号为 y 的位置。

当两段操作序列 S(M_t,M_p),T(N_t,N_p) 按顺序拼接在一起得到 ST(F_t,F_p) 时，假如我们从 x 号位置开始，我们会先经过 M_p(x,t)=1 的位置 t，然后到达 M_t(x,r)=1 的位置 r，然后再经过 N_p(r,z)=1 的位置 z，到达 N_t(r,y)=1 的位置 y。

由此并不显然有，F_t(x,y)=\bigcup\limits_{r=1}^{nm}(M_t(x,r)\cap N_t(r,y)) 和 F_p(x,y)=(\bigcup \limits_{r=1}^{nm}M_t(x,r)\cup N_p(r,y))\cup M_p(x,y)。

我们发现这个东西很像矩阵乘法。具体来讲，若乘法为 \text{and-or} 矩阵乘法，那么 F_t=M_t\times N_t，F_p=M_p \cup (M_t \times N_p)。显然是有结合律的，那不妨定义矩阵二元组的乘法如上，即 (M_t,M_p)(N_t,N_p)=(M_tN_t,M_tN_p\cap M_p)。

做这个乘法的复杂度是 O(n^3m^3) 的，但是我们可以通过 std::bitset 或者 unsigned long long 或者 __int128 之类的东西压位，可以做到 O(\frac{n^3m^3}{w})。

对于 \texttt{(S)k} 的情况，显然整个字符串对应的矩阵二元组就是 k 个 S(M_t,M_p) 相乘，即 (F_t,F_p)=(M_t,M_p)^k。这里可以用快速幂，当然不用也无所谓。

对于 \texttt{(S)*} 的情况，若把 M_t 看作一个邻接矩阵，则 F_t 相当于一个可达性矩阵，而 F_p(x,y) 则相当于“在这个图上从 x 号位置开始走能到达的所有点 t 中，是否有点满足 M_p(t,y)=1”。F_t 可以通过 Floyd-Warshall 传递闭包（这里也可以压位除掉一个 w）求出，F_p 可以一并求出。

然后全拼起来就做完了，总复杂度 O(\frac{n^3m^3|S|k}w)，其中 k 是括号后附带的数字，k \le 9。如果你有心情做矩阵快速幂可以做到 O(\frac{n^3m^3|S|\log k}w)，常数非常小。

这题既不入门，也不面试，但是它在入门与面试题库里面。综合算法难度，思维难度和代码难度，我觉得这应该是 B 题库最难的一题。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
char s[15][15],S[1005];
int n,m,N;
inline int id(int x,int y){
    return (x-1)*m+y;
}
inline int getx(int x){
    return (x-1)/m+1;
}
inline int gety(int x){
    return (x-1)%m+1;
}
struct command{
    command(){
        for(int i=1;i<=N;i++){
            to[i].reset();
            path[i].reset();
        }
    }
    bitset<105>to[105],path[105];
    void operator |=(command o){
        for(int i=1;i<=N;i++){
            to[i]|=o.to[i];
            path[i]|=o.path[i];
        }
    }
}com[505];
int cnt=0,readpos=0;
bitset<105>tr[105];
command concatenate(const command &x,const command &y){
    command z;
    for(int i=1;i<=N;i++)z.path[i]=x.path[i];
    for(int i=1;i<=N;i++)for(int j=1;j<=N;j++)if(x.to[i][j]){
        z.to[i]|=y.to[j],z.path[i]|=y.path[j];
    }
    return z;
}
command repeat(command &x,int k){
    for(int i=1;i<=N;i++)tr[i].reset();
    command ans;
    for(int i=1;i<=N;i++)ans.to[i][i]=1,ans.path[i][i]=1;
    if(k<1 || k>9){
        ans|=x;
        for(int i=1;i<=N;i++)for(int j=1;j<=N;j++){
            // Floyd 求最短路的时候我们有 dis[j][k] <--- dis[j][i]+dis[i][k]，这里也是一样的道理。
            if(ans.to[j][i]){
                ans.to[j]|=ans.to[i];
                ans.path[j]|=ans.path[i];
            }
        }
    }
    else{
        command tmp=x;
        while(k){
            // 快速幂
            if(k&1)ans=concatenate(ans,tmp);
            tmp=concatenate(tmp,tmp);
            k>>=1;
        }
    }
    return ans;
}
int Len;
void walk(command &x,int dir){
    for(int i=1;i<=N;i++)tr[i].reset();
    for(int i=1;i<=N;i++)for(int j=1;j<=N;j++)if(x.to[i][j]){
        int nx=getx(j)+dx[dir],ny=gety(j)+dy[dir];
        if(nx>=1 && nx<=n && ny>=1 && ny<=m && s[nx][ny]=='.')tr[i][j+dx[dir]*m+dy[dir]]=1;
        else tr[i][j]=1;
    }
    for(int i=1;i<=N;i++)x.to[i]=tr[i],x.path[i]|=tr[i];
}
void readCommand(command &x){
    for(int i=1;i<=N;i++){
        x.to[i][i]=x.path[i][i]=1;
    }
    while(readpos<Len && S[readpos]!=')'){
        char c=S[readpos];
        // LRUD 可以做到 N^2 而不是 N^3/w
        if(c=='L')walk(x,0);
        if(c=='R')walk(x,1);
        if(c=='U')walk(x,2);
        if(c=='D')walk(x,3);
        if(c=='('){
            ++readpos;
            command &f=com[++cnt];
            readCommand(f);
            ++readpos;
            char op=S[readpos];
            x=concatenate(x,repeat(f,op-48));
        }
        ++readpos;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    N=n*m;
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    scanf("%s",S);
    Len=strlen(S);
    readCommand(com[++cnt]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='#')putchar('#');
            else if(com[1].path[id(1,1)][id(i,j)])putchar('+');
            else putchar('.');
        }
        putchar('\n');
    }
    return 0;
}