NOIP模拟赛（二）
赛时开题顺序并不太对。一直在看 T3，发现写不出来的时候瞅了一眼 T1 感觉是个结论就写了。但是写的。。。。没过脑子吧，然后寄了。希望今后吸取经验，再三仔细思考。
还有一方面是，赛时过了大样例，一高兴就去写别的题的暴力了。嗯。。。所以告诉我们过了大样例也得再考虑一下。。。
这是赛时的码，警钟橛烂。仔细看看就能看出来问题。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int T,n;
int a1,a2,a3;
struct node{int x,y,z;}a[N];
bool cmp1(node xx,node yy){return xx.x<yy.x;}
bool cmp2(node xx,node yy){return xx.y<yy.y;}
bool cmp3(node xx,node yy){return xx.z<yy.z;}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
}
sort(a+1,a+n+1,cmp1);
int flag=1,t=a[1].x;
for(int i=1;i<=n;i++) if(a[i].x%t!=0){flag=0;break;}
a1=(flag)?a[1].x:1;
sort(a+1,a+n+1,cmp2);
flag=1,t=a[1].y;
for(int i=1;i<=n;i++) if(a[i].y%t!=0){flag=0;break;}
a2=(flag)?a[1].y:1;
sort(a+1,a+n+1,cmp3);
flag=1,t=a[1].z;
for(int i=1;i<=n;i++) if(a[i].z%t!=0){flag=0;break;}
a3=(flag)?a[1].z:1;
printf("%d %d %d\n",a1,a2,a3);
}
int main(){
scanf("%d",&T);
while(T--) solve();
}
因为你一直减减减。发现就是求 gcd，终将会汇聚到那里。gcd 为 1 就一直减到 1。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int T,n;
int a1,a2,a3;
void solve(){
scanf("%d%d%d%d",&n,&a1,&a2,&a3);
for(int i=2;i<=n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a1=__gcd(a1,x);
a2=__gcd(a2,y);
a3=__gcd(a3,z);
}
printf("%d %d %d\n",a1,a2,a3);
}
int main(){
scanf("%d",&T);
while(T--) solve();
}
没长脑子导致的，我破大防！
因为最后没时间了所以赛时没写这道。但看出来是张图，似乎可以跑 dij。
然后正解就是 dij。
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=2e3+10;
db inf=1e12;
int n;
int x[N],y[N];
int vis[N];
db d[N][N],dis[N],zj[N];
db A,B,C,D,U;
db get(int x,int y,int xx,int yy){
return (sqrt(1.0*(x-xx)*(x-xx)+1.0*(y-yy)*(y-yy)));
}
void dij(){
for(int i=0;i<=n;i++) dis[i]=inf;
dis[1]=0;
for(int i=2;i<=n;i++)
if(zj[i]+d[1][i]<=U) dis[i]=min(dis[i],A+B+d[1][i]*D+(d[1][i]+zj[i])*C);
vis[1]=1;
for(int t=1;t<=n;t++){
int x=0;
for(int i=1;i<=n;i++) if(!vis[i]&&dis[i]<dis[x]) x=i;
if(!x) break;
vis[x]=1;
for(int i=1;i<=n;i++){
if(i==x) continue;
if(zj[i]+d[x][i]<=U){
db w=A+B+d[x][i]*D+(zj[i]+d[x][i]-zj[x])*C;//从 x 到 i 的代价，zj[x] 是因为原有电量。
if(dis[i]>dis[x]+w) dis[i]=dis[x]+w;
}
}
}
}
int main(){
scanf("%d%lf%lf%lf%lf%lf",&n,&A,&B,&C,&D,&U);
for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++){
zj[i]=inf;
for(int j=1;j<=n;j++){
if(i==j) continue;
d[i][j]=get(x[i],y[i],x[j],y[j]);
zj[i]=min(zj[i],d[i][j]);
}
}
dij();
printf("%.6lf",dis[n]);
}
首先预处理两点的距离、到达一个点最近的点。然后按照题意，要满足 “在到达充电桩时剩余的电量至少可以前往最近的一个充电桩”，所以需要判断 zj[i]+d[x][i]<=U 来决定是否能够转移。
这里可以不用优先队列优化。一方面时间充裕，另一方面连边的话比较麻烦，直接枚举就行。