每天水水身体好...今天真的是水题啊

题目1 - BFS


题目大意:
给一个四位素数,每次改变一位成另一个素数,问几次可以变成目标素数。
思路:
BFS + 枚举...(还没什么改进)

代码在此

#include <iostream>
#include <queue>
#include <string.h> 
#define MaxSize 100010
using namespace std;

bool visit[MaxSize];
int A,B,ans;

typedef pair<int,int> p;    //A和操作数

bool is_su(int a){
    if(a == 1) return false;
    if(a == 2) return true;
    for(int i = 2;i * i <= a;i++){
        if(a % i == 0) return false;
    }
    return true;
}

void bfs(int a,int st){
    memset(visit,false,sizeof(visit));
    queue<p> que;
    while(que.size()) que.pop();
    que.push(p(a,st));
    visit[a] = 1;
    while(que.size()){
        p t = que.front();
        que.pop();
        if(t.first == B){
            cout<<t.second<<endl;
            return ;
        }
        for(int j = 0;j < 4;j++){
            if(j == 0){
                //个位 
                for(int i = 1;i <= 9;i++){
                    p node ;
                    int tmpa = (t.first / 10) * 10 + i;
                    if(is_su(tmpa) && !visit[tmpa]) {
                        node.first = tmpa;
                        node.second = t.second + 1;
                        visit[tmpa] = true;
                        que.push(node);
                    }
                }
            }
            else if(j == 1){
                //十位 
                for(int i = 0;i <= 9;i++){
                    p node ;
                    int tmpa = (t.first / 100) * 100 + i * 10 + t.first % 10;
                    if(is_su(tmpa) && !visit[tmpa]) {
                        node.first = tmpa;
                        node.second = t.second + 1;
                        visit[tmpa] = true;
                        que.push(node);
                    }
                }
            }
            else if(j == 2){
                //百位 
                for(int i = 0;i <= 9;i++){
                    p node;
                    int tmpa = (t.first / 1000) * 1000 + i*100 + t.first % 100;
                    if(is_su(tmpa) && !visit[tmpa]) {
                        node.first = tmpa;
                        node.second = t.second + 1;
                        visit[tmpa] = true;
                        que.push(node);
                    }
                }
            }
            if(j == 3){
                //千位 
                for(int i = 0;i <= 9;i++){
                    p node;
                    int tmpa = t.first % 10 + i * 1000;
                    if(is_su(tmpa) && !visit[tmpa]) {
                        node.first = tmpa;
                        node.second = t.second + 1;
                        visit[tmpa] = true;
                        que.push(node);
                    }
                }
            }
        }        
    } 
    cout<<"Impossible\n"<<endl;
    return;
}

int main()
{
    int n;cin>>n; 
    while(n--){
        cin>>A>>B;
        bfs(A,0);
    }    
    return 0;
} 

两道水题:)


敢问我怎么好意思把他贴出来...
贪心做嘛

代码在此

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#define MaxSize 101
using namespace std;
struct p{
    int first,second;
    p(int m,int n):first(m),second(n){
    };
    p(){
    };
};
p v[MaxSize];
bool cmp(p A,p B){
    return A.second <= B.second;
}
int main()
{
    int n;
    cin>>n;
    for(int i = 0;i < n;i++){
        int a,b;
        cin>>a>>b; 
        v[i] = p(a,b);
    }
    sort(v,v + n,cmp);
    int cnt = 1;
    int l = v[0].second;
    for(int i = 1;i < n;i++){
        if(v[i].first >= l){
            cnt ++ ;
            l = v[i].second;
        }
    }
    int pp;
    cin>>pp;
    cout<<cnt<<endl;
    return 0;
}


理清思路就行了,主要是想到会很好写!

代码在此

#include<iostream>
#include <string.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int l = s.length();
    int cnt = 0;
    for(int i = l;i >= 0;i --){
        if(s[i] == '1') cnt++;
    }
    if(cnt > 1) cout<<(l + 1) / 2<<endl;
    else cout<<l / 2<<endl;
    return 0;
}

端午快乐!我今晚一定不能熬夜辽~

Last modification:June 27th, 2020 at 06:31 pm
请赏我杯奶茶,让我快乐长肉