题解 P3843 【[TJOI2007]迷路】
又是鬼畜的学校考试题。。。
题目的样例太弱了，有手就能过，这导致了我的58分（自己懒得造数据。。。） 所以我们重新造一组数据，跟着数据来分析这道题
0 0 4
-1 Y
-2 X
1 Y
2 X
3 3 6
-1 X
2 Y
1 X
-2 Y
1 Y
-1 Y 也就是把题目样例改了一下，但这样就可以让我们注意到主人公的速度为1，而并非d
借助图我们来看看他们的运动轨迹
我们可以直接模拟时间，这样在每一秒钟内去计算两人的距离，然后去它和ans的min即可
但如果每次输入的d不是1或-1怎么办呢？就可以把它拆开，拆成d个项，就像这样
scanf("%d%c%c",&g[i].ad,&x,&g[i].az);
if(abs(g[i].ad)!=1){
int xx=g[i].ad/abs(g[i].ad);
int cc=abs(g[i].ad);//数据会改变，所以中途定义一个变量储存
for(int j=i;j<=i+cc-1;j++){
g[j].ad=xx;
g[j].az=g[i].az;
}
i+=cc-1;
am+=cc-1;//别忘了最后对am和i进行处理，因为你的项变多了
}全篇的AC代码如下
#include<bits/stdc++.h>
using namespace std;
int find(int a,int b){
int c=a%b;
while(c!=0){
a=b;
b=c;
c=a%b;
}
return b;
}
struct G{
int ad,bd;
char az,bz;
}g[10005];
int ax,ay,bx,by,am,bm,ft;//初始数据保留 ft就是最小公倍数，即枚举秒数
char x;
int main(){
double ans=0;
scanf("%d%d%d",&ax,&ay,&am);
for(int i=1;i<=am;i++){
scanf("%d%c%c",&g[i].ad,&x,&g[i].az);
if(abs(g[i].ad)!=1){
int xx=g[i].ad/abs(g[i].ad);
int cc=abs(g[i].ad);//数据会改变，所以中途定义一个变量储存
for(int j=i;j<=i+cc-1;j++){
g[j].ad=xx;
g[j].az=g[i].az;
}
i+=cc-1;
am+=cc-1;//别忘了最后对am和i进行处理，因为你的项变多了
}
}
scanf("%d%d%d",&bx,&by,&bm);//b的输入与a相同
for(int i=1;i<=bm;i++){
scanf("%d%c%c",&g[i].bd,&x,&g[i].bz);
if(abs(g[i].bd)!=1){
int xx=g[i].bd/abs(g[i].bd);
int cc=abs(g[i].bd);
for(int j=i;j<=i+cc-1;j++){
g[j].bd=xx;
g[j].bz=g[i].bz;
}
i+=cc-1;
bm+=cc-1;
}
}
ft=max(am,bm)/find(am,bm)*min(am,bm);//最小公倍数即模拟秒数；
ans=sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
for(int i=1;i<=ft;i++){
int ca=i%am,cb=i%bm;
if(ca==0) ca=am;
if(cb==0) cb=bm; //没有存g[0]，即模下来等于零就是第am/bm步
if(g[ca].az=='X') ax+=g[ca].ad;
else ay+=g[ca].ad;
if(g[cb].bz=='X') bx+=g[cb].bd;
else by+=g[cb].bd;
ans=min(ans,sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by)));//两点之间距离公式
}
printf("%.2lf",ans);//输出两位
return 0;
}