自动搬运

查看原文

来自洛谷，原作者为

	tzc_wk **

搬运于2025-08-24 22:02:02，当前版本为作者最后更新于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$，预处理出以下四个量：

• $mn_i$：从该细菌起点对应的三元组开始，最少走多少步可以走到环上
• $len_i$：从该细菌起点对应的三元组开始，能够走到的 $\rho$ 字形的环长
• $typ_{i,d}$：对于终点 $(x,y,d)$，它在不在该细菌对应的起点能够走到的 $\rho$ 字形的环上
• $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;
}