我被卡卡卡卡卡卡了

常规
1

数字转换

提交(Submit)

中文 切换语言(Change Language)

时间：0.2s 空间：32M

题目描述： 给你两个数s,t, 每次从小于s的质因子中挑选一个数加给s（ s 变化后影响可选质因子），问最少加几次能到达t

输入格式： 第一行输入一个整数T，表示测试组数 接下来T行每行两个整数s,t

输出格式： 对于每组测试数据输出一个最小步数，如果无法到达，输出-1 具体格式见样例输出 #### 样例输入： 2 6 12 6 13

样例输出： Case 1: 2 Case 2: -1

约定： T<=500,1<=s<=100,1<=t<=1000

提示：

5 个赞
2

一下是本蒟蒻丑陋的代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int x,step;
};
int dx[1145];
queue<node> q;
int m,ans=0,t,n,s=0,sum=0,vis[1145],a[1145],b[1145];
int cnt=0;
void df(){
    a[0]=a[1]=1;
    for(int i=2;i<=1001;i++){
        if(a[i]==0){
            for(int j=2*i;j<=1001;j+=i){
                a[j]=1;
            }
        }
    }
}
void f(int x,int i){
    i=1;
    if(x%2==0){
        dx[i]=2;
        i++;
    }
    for(int j=i;j<=cnt;j++){
        if(b[j]>x) break;
        if(x%b[j]==0){
            dx[i++]=b[j];
        }
    }
    sum=i;
    if(i==1) sum=0;
}
void bfs(){
    while(!q.empty()){
        f(q.front().x,0);
        for(int i=1;i<=sum;i++){
            int tx=q.front().x+dx[i];
            if(tx>=1&&tx<=m&&vis[tx]==0){
                if(tx==m){
                    cout<<"Case "<<s<<": "<<q.front().step+1<<endl;
                    return ;
                }
                q.push( node{tx,q.front().step+1} );
                vis[tx]=1;
            }
        }
        q.pop();
    }
    cout<<"Case "<<s<<": "<<-1<<endl;
}
signed main(){
    df();
    for(int i=1;i<=1005;i++){
        if(a[i]==0){
            b[++cnt]=i;
        }
    }
    cin>>t;
    for(s=1;s<=t;s++){
    	memset(dx,0,sizeof dx);
    	memset(vis,0,sizeof vis);
        cin>>n>>m;
        while(!q.empty()){q.pop();}
        q.push(node{n,0});
        vis[n]=1;
        bfs();
    }
}
5 个赞
3

主要代码

struct node{
    int x,step;
    bool friend operator <(node a,node b){
        return a.step>b.step;
    }
};
bool vis[10010];
int p[10010];
int s,t,k,ans;
void divide(int n){
    k=0;
    int m=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            p[++k]=i;
            while(n%i==0) n=n/i;
        }
    }
    if(n>1&&m!=n) p[++k]=n;//这里要注意考虑m!=n的情况，之前没注意到这个WA了好多次
}
void BFS(){
    priority_queue<node> qu;
    node e1;
    e1.x=s,e1.step=0;
    vis[s]=1;
    qu.push(e1);
    //int ans=INF;
    bool flag=false;
    while(!qu.empty()){
        e1=qu.top();qu.pop();
        node e2;
        if(e1.x==t){
            flag=true;
            ans=min(ans,e1.step);
            continue;
        }
        memset(p,0,sizeof(p));
        divide(e1.x);//注意每次转换后的b就是下一个a
        for(int i=1;i<=k;i++){
            e2.x=e1.x+p[i];
            e2.step=e1.step+1;
            if(e2.x<=t&&!vis[e2.x]){
                vis[e2.x]=1;
                qu.push(e2);
            }
        }
    }
    if(flag) printf("%d\n",ans);
    else printf("-1\n");
}
int main(){
    int n,kase=0;
    scanf("%d",&n);
    while(n--){
        ans=INF;
        memset(vis,0,sizeof(vis));
        scanf("%d %d",&s,&t);
        printf("Case %d: ",++kase);
        if(s==t){
            printf("0\n");
            continue;
        }
        if(s>t) {
            printf("-1\n");
            continue;
        }
        BFS();
    }
3 个赞
4

求解决方案

3 个赞
5

行，你能删掉吗？

1 个赞