中南高等学校2012年7月月赛Problem G: Number Transformation
中南大学2012年7月月赛Problem G: Number TransformationProblem G: Number Transformation/*题意 输入2个
中南大学2012年7月月赛Problem G: Number Transformation
Problem G: Number Transformation/*题意 输入2个数 a,b 给a加上一个比a小的素数 使得a等于b 问 最少需要多少步才能从a转化到b如果不可能转化到b 则输出 No path! 思路： 暴力必死 一开始我想用背包搞 搞不出来 后来用背包判断是否存在 如果存在再去暴力依旧超时 后来参考了大神的代码 终于恍悟 用优先队列去打表 从1到1000 分别做起始点 用优先队列 去找出到达比a大的点的最小步骤 优先队列用在这里漂亮极了 表打出来后 直接对应输出即可*/ /*注意：A的素数范围是动态增加的 这个地方很坑爹 题意没有描述清楚 即a变向b的过程 a增大那么a的素数也增多*/ #include<stdio.h>#include<math.h>#include<string.h>#include<queue>using namespace std;int prime[1005],vis[1100],cnt;int ans[1010][1010];struct haha{ int num; int step; friend bool operator <(struct haha a,struct haha b) { return a.step>b.step; }}q,temp; void get_prime(){ int i,j,n; double m; n=1002;cnt=0; m=sqrt(n+0.5); memset(vis,0,sizeof(vis)); for(i=2;i<=m;i++) if(!vis[i]) { for(j=i*i;j<=n;j+=i) vis[j]=1; } for(j=2;j<=n;j++) if(!vis[j]) { prime[cnt++]=j; }} void get_ans(int s){ int i,e; priority_queue<haha>que; q.num=s; q.step=0; ans[s][s]=0; que.push(q); while(!que.empty()) { temp=que.top(); que.pop(); q.step=temp.step+1; for(i=0;i<cnt&&prime[i]<temp.num;i++)///是temp.num 不是s { e=temp.num+prime[i]; if(e>1000) continue; if(ans[s][e]==-1||q.step<ans[s][e]) { ans[s][e]=q.step; q.num=e; que.push(q); } } }}int main(){ int a,b,i; get_prime(); memset(ans,-1,sizeof(ans)); for(i=2;i<=1000;i++) get_ans(i); while(scanf("%d %d",&a,&b)!=EOF) { if(ans[a][b]==-1) printf("No path!\n"); else printf("Need %d step(s)\n",ans[a][b]); } return 0;}
