一道很好的数学题。
首先不难想到每个细菌的移动路线是有循环节的,循环节外的时间最多就是每个格子的四个方向都走一遍,也就是 \(4\times N \times M\)。
可以预处理每个细菌分别通过四个方向第一次到达终点的时间 \(b_{i,0/1/2/3}\) 和再次回到当前状态的循环节长度 \(md_{i,0/1/2/3}\)。
要特别注意的是不同方向到达终点是不同的状态。
首先 \(4\times N \times M\) 以内的答案直接暴力算出来(有可能有病毒没有进入循环节)。
然后计算大于 \(4\times N \times M\) 的答案,假设已知了每个病毒最终到达终点面对的方向 \(face_i\),其实限制就是一个同余方程,设答案为 \(x\),对于每个病毒有限制:
\[x\equiv b_{i,face_i}(\bmod md_{i,face_i}) \]可以扩展中国剩余定理求解,每个病毒面对的方向可以搜索。
有一个细节,扩展中国剩余定理求解的答案必须大于等于所有的 \(b_{i,face_i}\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=60;
const int INF=1e18;
int as=INF;
int n,m,k,rx,ry;
int dx[10]={-1,0,1,0},dy[10]={0,1,0,-1};
int tun[10]={2,3,0,1};
int vis[N][N][4],b[N][4],md[N][4],rec[N][N];
int mp[N][N],x,y;
int ton[2*N*N*4];
int hp[4],cho[N],lim=0;
struct node{
int x,y;
char c;
}q[N];
bool out(int xx,int yy){
if(xx>n || xx<1 || yy>m || yy<1) return true;
return false;
}
int go(int xx,int yy,int st){
st+=mp[xx][yy];
st%=4;
if(!out(xx+dx[st],yy+dy[st])) return st;
else return tun[st];
}
void work(int now,int nx,int ny,char ch){
int st;
if(ch=='U') st=0;
else if(ch=='R') st=1;
else if(ch=='D') st=2;
else st=3;
int tim=0;
hp[0]=hp[1]=hp[2]=hp[3]=0;
int xf=INF;
while(tim<=n*m*4){
++tim;
if(nx==rx && ny==ry){
xf=min(xf,tim);
if(b[now][st]==INF) b[now][st]=tim;
else if(md[now][st]==INF) md[now][st]=tim-b[now][st];
ton[tim]++;
hp[st]=tim;
}
st=go(nx,ny,st);
nx+=dx[st],ny+=dy[st];
}
lim=max(lim,xf);
}
void init(){
cin>>n>>m>>k;
cin>>rx>>ry;
for(int i=0;i<N;i++){
for(int j=0;j<4;j++) b[i][j]=md[i][j]=INF;
}
for(int i=1;i<=k;i++){
cin>>q[i].x>>q[i].y>>q[i].c;
string s;
for(int j=1;j<=n;j++){
cin>>s,s=" "+s;
for(int k=1;k<=m;k++) mp[j][k]=(s[k]-'0');
}
work(i,q[i].x,q[i].y,q[i].c);
}
}
int exgcd(int a,int b){
if(b==0){
x=1,y=0;
return a;
}
else{
int as=exgcd(b,a%b);
int xx=x,yy=y;
x=yy,y=xx-(a/b)*yy;
return as;
}
}
int qmul(int af,int bf,int p){
int aa=0,x=af;
while(bf){
if(bf&1){
aa+=x;
aa%=p;
}
x*=2;
x%=p;
bf/=2;
}
return aa;
}
int excrt(){
int ans=b[1][cho[1]],lcm=md[1][cho[1]];
for(int i=2;i<=k;i++){
int aa=lcm,bb=md[i][cho[i]],cc=b[i][cho[i]]-ans;
cc=(cc%md[i][cho[i]]+md[i][cho[i]])%md[i][cho[i]];
int d=exgcd(aa,bb);
if(cc%d){
return INF;
}
ans=ans+lcm*qmul(x,cc/d,md[i][cho[i]]);
lcm/=d,lcm*=md[i][cho[i]];
ans=(ans%lcm+lcm)%lcm;
}
int af=ans;
if(lim>af){
int xx=(lim-af)/lcm;
af+=(xx*lcm);
if(af<lim) af+=lcm;
}
return af;
}
void dfs(int x){
if(x==k+1){
as=min(as,excrt());
return;
}
for(int i=0;i<4;i++){
if(b[x][i]==INF || md[x][i]==INF) continue;
cho[x]=i;
dfs(x+1);
}
}
signed main(){
init();
for(int i=1;i<=n*m*4;i++){
if(ton[i]==k){
cout<<i;
return 0;
}
}
dfs(1);
if(as==INF) cout<<-1;
else cout<<as;
return 0;
}
标签:P4621,10,md,int,题解,COCI2012,times,xx,face
From: https://www.cnblogs.com/wangwenhan/p/18533127