P4621

Feyn · 2022-07-14 09:23:13 · 题解

link & 博客园食用

题意

有一个矩形区域被划分成了许多小方格，这些方格中有一个是陷阱。这个区域内有一些细菌，这些细菌有初始方向，它们会沿着各自的初始方向去到相邻的格子（特别地，假如当前方向会导致它们冲出矩形那么细菌会转身），每到一个新的格子，细菌就会按照格子中的数值旋转一定的角度从而改变自己的方向。显然很有可能这些细菌有一个时刻会进入陷阱中，但是一般来说为了防止打草惊蛇这些陷阱不会发作，进入陷阱的细菌会照常改变方向然后离开。陷阱发挥作用当且仅当所有细菌同时进入陷阱，题目中问的就是陷阱第一次发作的时间。

解法

很显然的是细菌所到达的格子会循环往复。因为细菌的状态由所在位置和当前方向决定，当前状态会产生唯一的一个新状态，而状态是有限的，所以肯定会产生循环。那么就可以推断出每一个细菌的路径一定是分为两个阶段，第一个阶段从初始状态走到一个状态 A ，第二个阶段就是从 A 通过一些时间重新回到 A ，这样循环往复。也可以像第一篇题解那样理解，把每一个状态抽象成一个节点，那么每个节点的出度都是一，所以肯定会形成一片内向基环树森林。

既然如此可以分两类情况。对于第一阶段大可以直接枚举时间然后判断是否合法，因为可以想见可能的时间一定不多。对于第二个阶段，假设第一次到达某个状态的时间为 t_0，每次循环的时间是 c，那么每次到达这个点的时间都可以表示为 t=t_0+kc(k\in N) ，换句话说就是 t\equiv t_0\pmod c ，注意这里的 t 应该不小于 t_0 。每个陷阱会对应四种状态（也就是四种方向），所以所有细菌就可能会有 K^4 种掉入陷阱的方式。这个数量也不多，可以枚举之后解同余方程组即可。

另外就是理论上这道题要用 __int128 来存储，但造出这样的数据似乎并不是很容易，于是只用龙龙就可以存的下了。

代码有注释，蒟蒻代码能力有限请大佬轻喷。

#include<bits/stdc++.h>
//#define feyn
#define int long long
const int N=60;
using namespace std;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w>='0'&&w<='9'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}
inline int min(int s1,int s2){
    return s1<s2?s1:s2;
}

int m,n,num,x,y,data[N][4],cnt[N],st[N];

int c[N][N],vis[N][N][4];
int f[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//方向数组 
inline bool check(int a,int b){
    return a<1||b<1||a>m||b>n;//是否跳出边界 
}
void solve(int wh){
    memset(vis,0,sizeof(vis));
    int a,b,now;read(a);read(b);
    char w[N];scanf("%s",w);
    switch(w[0]){
        case 'U':now=0;break;
        case 'R':now=1;break;
        case 'D':now=2;break;
        case 'L':now=3;break;
    }
    for(int i=1;i<=m;i++){
        scanf("%s",w);
        for(int j=1;j<=n;j++)c[i][j]=w[j-1]-'0';
    }//处理输入 

    int an=0;
    while(true){
        an++;
        if(vis[a][b][now]){cnt[wh]=an-vis[a][b][now];st[wh]=vis[a][b][now];return;}
        //如果一个状态已经被访问过了，那么两次访问的时间差就会是循环长度 
        vis[a][b][now]=an;if(a==x&&b==y)data[wh][now]=an;//记录第一次进入陷阱的时间 
        now=(now+c[a][b])%4;//按照题意改变方向 
        if(check(a+f[now][0],b+f[now][1]))now=(now+2)%4;//如果走出矩阵了 
        a+=f[now][0],b+=f[now][1];//移动到下一个格子 
    }
}

inline bool able(int wh,int t){
    for(int i=0;i<4;i++){
        if(data[wh][i]==0)continue;
        if(data[wh][i]<st[wh]){if(data[wh][i]==t)return true;}
        else if(t>=data[wh][i]&&t%cnt[wh]==data[wh][i]%cnt[wh])return true;
    }
    return false;
}

int limit,ans=1e18,a[10],b[10];

struct node{int x,y,g;};
inline node exgcd(int a,int b){
    if(b==0)return (node){1,0,a};
    node an=exgcd(b,a%b);
    return (node){an.y,an.x-a/b*an.y,an.g};
}//扩展欧几里得的板子 
void work(){
    int M=b[1],x0=a[1];
    for(int i=2;i<=num;i++){
        node an=exgcd(M,b[i]);
        int c=a[i]-x0,bg=b[i]/an.g;
        if(c%an.g)return;
        int x=an.x*(c/an.g)%bg;
        x0+=x*M;M*=bg;
        x0=(x0%M+M)%M;
    }//扩展中国剩余定理的板子 
    while(x0<limit)x0+=M;//要保证最后的答案大于等于limit 
    ans=min(ans,x0);return;//更新答案 
}
void dfs(int wh){
    if(wh>num){work();return;}
    for(int i=0;i<4;i++){
        if(data[wh][i]<st[wh])continue;//没进入循环的状态只会出现一次，不能加入同余方程 
        a[wh]=data[wh][i]%cnt[wh];
        b[wh]=cnt[wh];//记录余数和模数 
        dfs(wh+1);
    }
}

signed main(){

    #ifdef feyn
    freopen("in.txt","r",stdin);
    #endif

    read(m);read(n);read(num);
    read(x);read(y);
    for(int i=1;i<=num;i++)solve(i);
    for(int i=1;i<=num;i++){
        bool ok=true;
        for(int j=0;j<4;j++){
            limit=max(limit,st[i]);
            if(data[i][j])ok=false;
        }
        if(ok){printf("-1");return 0;}//如果有细菌根本到不了陷阱 
    }
    //limit是所有细菌中进入循环的最晚细菌的时间 

    //处理第一阶段的答案，枚举加验证 
    for(int i=0;i<=limit;i++){
        bool ok=true;
        for(int j=1;j<=num;j++){
            if(able(j,i)==false){ok=false;break;}//如果有细菌到不了 
        }
        if(ok){printf("%lld",i);return 0;}//假如存在小于limit的答案直接输出 
    }

    dfs(1);//枚举状态 
    printf("%lld",ans);

    return 0;
}