CSU--------2133: 中南大学2017年ACM暑期集训前期训练题集(基础题)

痛定思痛。 2022-06-15 12:13 168阅读 0赞

## K: Number Transformation ##

Submit Page      Time Limit: 1 Sec       Memory Limit: 128 Mb       Submitted: 36       Solved: 9

--------------------

## Description ##

In this problem, you are given a pair of integers A and B. You can transform any integer number A to B by adding x to A.This x is an integer number which is a prime below A.Now,your task is to find the minimum number of transformation required to transform S to another integer number T.

## Input ##

Input contains multiple test cases.Each test case contains a pair of integers S and T(0< S < T <= 1000) , one pair of integers per line.

## Output ##

For each pair of input integers S and T you should output the minimum number of transformation needed as Sample output in one line. If it's impossible ,then print 'No path!' without the quotes.

## Sample Input ##

5 7
    3 4

## Sample Output ##

Need 1 step(s)
    No path!

题意：输入2个数 a,b  给a加上一个比a小的素数 使得a等于b  问 最少需要多少步才能从a转化到b 如果不可能转化到b  则输出 No path!

有点要注意：

## A是一步变一次的，也就是说每次可以加的素数的范围是改变的 ##

## 比如当S=5，T=20的时候，S先加3=8，然后此时可以取的素数就不仅有2、3，还有5、7了。 ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int MAXN = 1050 ;
    struct Node
    {
        int num ,d ;
        Node() {};
        Node(int a,int b):num(a),d(b) {}//长见识了
    };
    bool prim[MAXN] ;
    bool mark[MAXN] ;
    int C , S ,T ;
    
    void isprim()
    {
        for(int i = 2 ; i < MAXN ; i ++)
            prim[i] = 1 ;
        for(int i = 2 ; i < MAXN ; i ++)
            if(prim[i])
                for(int j = 2 ; i * j < MAXN ; j ++)
                    prim[i * j] = 0 ;
    }
    
    int bfs(int source ,int destation)
    {
        queue<Node> Q;
        memset(mark,0,sizeof(mark)) ;
        Node a ;
        Q.push(Node(source,0));//长见识了
        mark[source] = 1 ;
        while(!Q.empty())
        {
            a = Q.front();
            Q.pop() ;
            //搜索比它小的素数
            for(int i = 2 ; i < a.num ; i ++)
            {
                //判断要加的数是不是素数
                if(!prim[i])continue ;
                int number = a.num + i ;
                //大于所要求的目标数，直接退出
                if(number > destation) break ;
                if(mark[number]) continue ;//number已经到达过就不用再次入队列
                mark[number] = 1 ;//否则标记它
                if(number == destation)
                    return a.d + 1;
                Q.push( Node(number,a.d+1));
            }
        }
        return -1 ;
    }
    
    int main()
    {
        isprim() ;
        while(scanf("%d %d",&S,&T)==2)
        {
            int d=bfs(S,T);
            if(d==-1) printf("No path!\n") ;
            else printf("Need %d step(s)\n",d) ;
        }
        return 0 ;
    }