题解 P4621 [COCI2012-2013#6] BAKTERIJE

tzc_wk · 2021-08-06 16:23:09 · 题解

洛谷题面传送门

发篇正常点的题解。

首先对于这样的题暴力枚举肯定是不行的，因为最小时间显然可能达到 (4nm)^5\approx 10^{20}，就算数据很难卡到这个上界，构造出一些使你暴力超时的数据还是很容易的，因此考虑一些不基于暴力枚举的做法。不难发现，对于每个细菌而言，如果它的位置及方向已经确定了，那么它下一步所在的位置及面对的方向也已经确定了，也就是说，如果我们对于每个细菌，把位置及方向看作一个三元组 (x,y,d)，并且在一步可达的三元组之间连有向边，那么可以得到 k 个基环内向森林。而由于得到的图是基环内向森林，对于一个点，从它出发可以到达的点应是一个 \rho 形。而对于陷阱格 (x,y)，到达陷阱格即意味着在建好的图上到达 (x,y,0),(x,y,1),(x,y,2),(x,y,3) 中的一个点，因此题目可以转化为：

• 求最小的时间 t，满足对于全部全部 k 个基环内向森林的起点，走 t 步后到达的点都是 (x,y,0),(x,y,1),(x,y,2),(x,y,3) 中的一个

由于此题 k 很小，因此我们考虑暴力 4^k 枚举每个细菌的终点 (x,y,d_i)，那么问题可进一步转化为，最少需要多少时间 t，满足每个细菌走 t 步后到达的点都恰好是 (x,y,d_i)。我们对于每个细菌 i，预处理出以下四个量：

• tim_{i,d}$：对于终点 $(x,y,d)$，最少需要多少时间才能从细菌 $i$ 起点对应的三元组走到 $(x,y,d)

那么显然如果存在一个 (x,y,d_i) 无法从 i 的起点到达那么就不存在这样的 i，否则继续分类讨论：如果存在一个 (x,y,d_i) 不在细菌 i 的起点对应的环上，那么显然时间必须为 tim_{i,d_i}，因为错过这个点就无法再回来了，我们只需检验从所有细菌的起点开始走 T=tim_{i,d_i} 步是否能够到达对应的终点即可，如果都能那么就用 T 更新答案，否则不做处理。具体检验方法就是如果 typ_{i,d_i}=1，那么必须有 T\ge mn_i 且 T\equiv tim_{i,d_i}\pmod{len_i}，否则必须有 tim_{i,d_i}=T，存在 typ_{i,d_i}=0 的情况都判完了，剩余的就是 typ_{i,d_i} 都为 1 的情况了。对于每个细菌 i，显然它在 T 时刻到达 (x,y,d_i) 的充要条件是 T\ge mn_i 且 T\equiv tim_{i,d_i}\pmod{len_i}。我们如果只考虑后一个条件，那显然就是一个解同余方程组的问题，exCRT 合并即可，加了第一个条件，由于方程组的通解可以写成 T=T_0+kT' 的形式，因此我们对于每个细菌求出 k 最少需要是多少才能满足第一个限制，然后取个 \max 即可。

复杂度大概是 4^kk\log T+nmk，跑得飞快，最慢的一个点只用了 6ms

u1s1 这题上界是 10^{20}，但实测把 INF 开到 9\times 10^{18} 能过……

const int MAXN=50;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
int n,m,k,X,Y,id[1<<7];
int getid(int x,int y,int d){return d*n*m+(x-1)*m+y;}
pair<pii,int> getcor(int x){return mp(mp((x-1)%(n*m)/m+1,(x-1)%m+1),(x-1)/n/m);}
int a[7][MAXN+5][MAXN+5],st[7];
int getnxt(int t,int x,int y,int d){
    d=(d+a[t][x][y])&3;
    if(x+dx[d]<1||x+dx[d]>n||y+dy[d]<1||y+dy[d]>m)
        d^=2;
    return getid(x+dx[d],y+dy[d],d);
}
vector<int> rch[7];
int stk[MAXN*MAXN*4+5],tp=0,len[7];
bool vis[MAXN*MAXN*4+5];
void dfs(int t,int x){
    if(vis[x]){
        for(int i=1;i<=tp;i++) rch[t].pb(stk[i]);
        for(int i=1;i<=tp;i++) if(stk[i]==x) len[t]=tp-i+1;
        return;
    } vis[x]=1;pair<pii,int> p=getcor(x);stk[++tp]=x;
    dfs(t,getnxt(t,p.fi.fi,p.fi.se,p.se));
}
int need[7][5],typ[7][5];
ll gcd(ll x,ll y){return (!y)?x:gcd(y,x%y);}
void exgcd(ll x,ll y,ll &a,ll &b){
    if(!y) return a=1,b=0,void();exgcd(y,x%y,a,b);
    ll tmp=a;a=b;b=tmp-(x/y)*b;
}
ll smul(ll x,ll y,ll mod){
    x=(x%mod+mod)%mod;y=(y%mod+mod)%mod;ll res=0;
    for(;y;y>>=1,x=(x+x)%mod) if(y&1) res=(res+x)%mod;
    return res;
}
pair<ll,ll> combine(ll a1,ll b1,ll a2,ll b2){
    if(!~a1||!~a2) return mp(-1,-1);
    ll d=gcd(a1,a2);if((b2-b1)%d) return mp(-1,-1);
    ll t=(b2-b1)/d;ll k1,k2;exgcd(a1,a2,k1,k2);
    k1=smul(k1,t,a2/d);ll A=a1/d*a2;
    return mp(A,(smul(a1,k1,A)+b1)%A);
}
int main(){
    scanf("%d%d%d%d%d",&n,&m,&k,&X,&Y);
    id['U']=0;id['R']=1;id['D']=2;id['L']=3;
    for(int i=1;i<=k;i++){
        int x,y;char c;cin>>x>>y>>c;
        st[i]=getid(x,y,id[c]);
        for(int j=1;j<=n;j++) for(int l=1;l<=m;l++)
            scanf("%1d",&a[i][j][l]);
    }
    for(int i=1;i<=k;i++){
        memset(vis,0,sizeof(vis));tp=0;
        dfs(i,st[i]);
//      for(int x:rch[i]) printf("%d\n",x);
        for(int d=0;d<4;d++){
            int x=getid(X,Y,d),ps=-1;
            for(int j=0;j<rch[i].size();j++) if(rch[i][j]==x) ps=j;
            need[i][d]=ps;typ[i][d]=(ps>=rch[i].size()-len[i]); 
//          printf("%d %d %d %d %d\n",i,d,x,need[i][d],typ[i][d]);
        }
    } ll res=9e18;
    for(int i=0;i<(1<<(k<<1));i++){
        bool flg=1;
        for(int j=1;j<=k;j++){
            int x=i>>((j-1)<<1)&3;
            if(!~need[j][x]) flg=0;
        } if(!flg) continue;
        int tim=-1;
        for(int j=1;j<=k;j++){
            int x=i>>((j-1)<<1)&3;
            if(!typ[j][x]) tim=need[j][x];
        }
        if(~tim){
            for(int j=1;j<=k;j++){
                int x=i>>((j-1)<<1)&3;
                if(!typ[j][x]&&need[j][x]!=tim) flg=0;
                if(typ[j][x]&&(tim<rch[j].size()-len[j]||tim%len[j]!=need[j][x]%len[j]))
                    flg=0;
            } if(flg) chkmin(res,tim);
            continue;
        }
        pair<ll,ll> A=mp(1,0);
        for(int j=1;j<=k;j++){
            int x=i>>((j-1)<<1)&3;
            A=combine(A.fi,A.se,len[j],need[j][x]%len[j]);
        } if(!~A.fi) continue;ll tt=A.se;
        for(int j=1;j<=k;j++){
            int x=i>>((j-1)<<1)&3;
            if(A.se<need[j][x]) chkmax(tt,A.se+(need[j][x]-A.se+A.fi-1)/A.fi*A.fi);
        } chkmin(res,tt);
    } printf("%lld\n",(res==9e18)?-1:(res+1));
    return 0;
}