【NOIP2013模拟11.4A组】游乐场

本文主要是介绍【NOIP2013模拟11.4A组】游乐场，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

今天是个好日子，小A和他的小伙伴们一起去逛游乐园。这时，游乐园中忽然出现了一个伪装的吸血鬼，小A和他的小伙伴们都惊呆了！小伙伴们马上跑向了游乐园的四面八方。当“吸血鬼”回家吃饭的时候，小A才发现他已经和他的小伙伴们走散了。小A是个路痴，所以他只好站在原地等小伙伴们回来。

我们可以将游乐园视为一个N行M列的矩形，最上面一行为第1行，最左边一列为第1列。每个小伙伴手里都有一张神奇的地图，地图中对应着游乐园的每行每列都有一个写着0-9中某个数字的路标。小A的K位小伙伴们每一秒都会依次进行以下行动：

1. 读取他所在的位置上的路标X；

2. 顺时针旋转90度X次；

3. 如果他面对游乐园外，那就他会再转180度；

4. 移动到他面对的位置。

小A的视力很糟糕。只有当所有的小伙伴都同时出现在他所在的位置时，他才能和他的小伙伴们团聚。小A等得很心急，所以他求助于你。请你告诉他，他和小伙伴们团聚所需要的时间。

Input

输入的第一行包括正整数N、M和K。

输入的第二行包括正整数X和Y，代表小A的位置。

输入的其他行将分别描述K个小伙伴：

·两个正整数Xi，Yi，代表第i个小伙伴开始时所在的位置。字符Ci，代表该小伙伴开始时面对的方向（U为上，R为右，D为下，L为左）；

·由0-9（含）组成的N×M的地图，其中第x行第y列的数字表示该小伙伴地图上(x, y)的位置上的路标。

Output

唯一的一行输出小A和小伙伴们团聚所需要的时间。如果小A和他的小伙伴们永远不会团聚，请输出-1。

Sample Input

输入1：
3 3 1
2 2
1 1 R
010
000
000
输入2：
3 4 2
2 2
3 4 R
2327
6009
2112
3 2 R
1310
2101
1301
输入3：
4 4 3
4 3
1 1 U
1001
0240
3322
2327
1 3 L
9521
2390
3020
2421
2 2 D
3397
2013
1102
7302

Sample Output

输出1：
3
输出2：
8
输出3：
296

Data Constraint

对于30%的数据，如果小A和他的小伙伴们能够团聚，团聚的总秒数小于10^6；
对于70%的数据，3<=N, M<=40；
对于100%的数据，3<=N, M<=50，1<=K<=5如果小A和他的小伙伴们能够团聚，团聚的总秒数小于10^18。

Solution

首先对每个人进行模拟，会发现他会走成一个环。
因为有四个方向，所以到达目标点也会有最多四个状态。
对于每个这四个状态，记录从开头走到这里的时间ai，还有环的大小bi，如果状态不在环内，bi为0
只有5个人，4个状态，先枚举每个人选哪一个状态$5^4$
那么就会得到一个方程
设时间为t，x为未知数
$t=a1+b1*x1$
$t=a2+b2*x2$
$t=ai+bi*xi$
这就是一个典型的中国剩余定理的方程，可以套用公式得出最优解t
但是因为我不懂那个中国剩余定理的公式，所以我用的是扩展欧几里得的解法
每次只算两个方程
如方程1、2：
$a1+b1*x1=a2+b2*x2$
$b1*x1-b2*x2=a2-a1$
然后就变成了$ax+by=c$的形式，解这个方程
然后将x或y代入原方程中，得到这两个方程的最优解t’
然后将这两个方程合并，变成
$t=t'+lcm(b1,b2)*x$
为什么能变成这样？
因为t’相当于第一个满足原方程的时间，而lcm就是两个都走完环回到原点的最短时间，意义与原方程相同

就这么化简到只剩一个方程，即可得出解
还有b=0或两个b相等的特殊情况，特判即可

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 60
#define ll long long
#define min(a,b) ((a)<(b)?(a):(b))
#define fo(i,a,b) for(ll i=a;i<=b;i++)
#define INF 100000000000000001ll
using namespace std;
ll n,m,k,x1,y1,a[N][N],b[6][4],c[6][4],d[6],bz[N][N][4],ans=INF;
void hzj(ll &x,ll &y,ll &z)
{(z+=a[x][y])%=4;if(x==1&&z==0) z=2;if(y==1&&z==3) z=1;if(x==n&&z==2) z=0;if(y==m&&z==1) z=3;if(z==0) x--;if(z==1) y++;if(z==2) x++;if(z==3) y--;
}
void exgcd(ll a,ll b,ll &x,ll &y)
{if(b==0){x=1,y=0;return;}exgcd(b,a%b,x,y);ll t=x;x=y;y=t-a/b*y;
}
ll gcd(ll a,ll b)
{return b==0?a:gcd(b,a%b);
}
ll getans(ll b1,ll a1,ll b2,ll a2)
{ll a=b1,b=-b2,c=a2-a1,x=0,y=0;if(b1==0&&b2==0){if(a2==a1) return a2;else return INF;}if(b1==0){if(b>c&&c%b==0) return max(a1,a2);else return INF;}if(b2==0){if(c>a&&c%a==0) return max(a1,a2);else return INF;}if(b1==b2){if(abs(a2-a1)%b1==0) return max(a1,a2);else return INF;}ll g=gcd(a,b);if(c%g!=0) return INF;exgcd(a,b,x,y);c/=g;x*=c;b=abs(b);b/=g;if(x<0) x=(b+x%b);x%=b;return a1+b1*x;
}
void pd()
{ll q[6],w[6];fo(i,1,k) q[i]=b[i][d[i]],w[i]=c[i][d[i]];if(k==1){ans=min(ans,q[1]);return;}fo(i,1,k-1){q[i+1]=getans(w[i],q[i],w[i+1],q[i+1]);if(gcd(w[i],w[i+1])==0) w[i+1]=0;else w[i+1]=w[i]*w[i+1]/gcd(w[i],w[i+1]);}ans=min(ans,q[k]);
}
void dg(ll x)
{if(x>k) {pd();return;}fo(i,0,3) if(b[x][i]!=0) d[x]=i,dg(x+1);
}
int main()
{freopen("park.in","r",stdin);freopen("park.out","w",stdout);scanf("%lld%lld%lld",&n,&m,&k); scanf("%lld%lld\n",&x1,&y1);fo(l,1,k){char ch;ll x,y,z,lh,jy;scanf("%lld %lld %c\n",&x,&y,&ch);if(ch=='U') z=0;if(ch=='R') z=1;if(ch=='D') z=2;if(ch=='L') z=3;fo(i,1,n){fo(j,1,m) a[i][j]=getchar()-48;scanf("\n");}memset(bz,0,sizeof(bz));fo(i,0,3) b[l][i]=0;fo(i,1,2147483647)if(!bz[x][y][z]){bz[x][y][z]=i;if(x==x1&&y==y1) b[l][z]=i;hzj(x,y,z);}else{lh=i-bz[x][y][z];jy=bz[x][y][z];break;}fo(i,0,3) if(b[l][i]>=jy) c[l][i]=lh;else c[l][i]=0;}dg(1);if(ans==INF) ans=-1;printf("%lld",ans);
}

这篇关于【NOIP2013模拟11.4A组】游乐场的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---