牛客算法周周练6 题解【B-E】

B 华华对月月的忠诚：
试着打了打表，发现只跟gcd(a,b)有关，所以直接输出gcd(a,b)就可以了。

但是作为题解要数学证明，我在别人的博客那发现了证明：

https://blog.nowcoder.net/n/69e53616e1444d399be566a360061220
大家想要看数学证明的可以去看看。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

char s[maxn];

ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}

int main(){
    ll a,b;
    scanf("%lld%lld%s",&a,&b,&s);
    printf("%lld",gcd(a,b));
    return 0;
}

C. Game
很基础的质因数分解，然后直到什么时候分解不了了就输出就好了。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

int a[maxn];

int check(int num){
    for(int i=2;i*i<=num;i++){
        if(num%i==0){
            return num/i;
        }
    }
    return 0;
}

int main(){
    int n;
    scanf("%d",&n);
    int flg=0;
    while(1){
        int tmp=check(n);
        if(tmp==0) break;
        n=tmp;
        flg++;
    }
    if(flg%2==1){
        printf("Johnson\n");
    }
    else{
        printf("Nancy\n");
    }
    return 0;
}

D 挖沟
超级明显的最小生成树题，有两种算法：普利姆和克鲁斯卡尔，复杂度分别是O(n²)和O(mlogm)。所以这次的是要用克鲁斯卡尔。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

int fa[maxn];

void init()
{
    for(int i = 0;i<=maxn;i++){
        fa[i]=i;
    }
}
int find(int x)
{
    return (fa[x] == x)?x:fa[x] = find(fa[x]);
}
void merge(int y,int x)
{
    int xx = find(x),yy = find(y);
    if(xx != yy) fa[xx] = yy;
}

struct Node{
    int x,y,val;
    Node(int x,int y,int val):x(x),y(y),val(val){
    }
    bool operator<(const Node& bb)const{
        return val>bb.val;
    }
};

int main(){
    init();
    int n,m;
    scanf("%d%d",&n,&m);
    priority_queue<Node> q;
    for(int i=1;i<=m;i++){
        int x,y,val;
        scanf("%d%d%d",&x,&y,&val);
        q.push(Node(x,y,val));
    }
    int ans=0;
    while(!q.empty()){
        int x=q.top().x;int y=q.top().y;int val=q.top().val;
        q.pop();
        int xx=find(x);int yy=find(y);
        if(xx!=yy){
            fa[yy]=xx;
            ans+=val;
        }
    }
    printf("%d\n",ans);
    return 0;
}

E 签到题
E是最有意思的题了，主要看大家是否看到这句话：保证数据随机生成。
一般看到这句话就意识到：暴力说不定能行。
然后试着暴力一发，A了。
正常的时间复杂度：如果随机的话，平均的L-R长度为1e5/2，有N次操作，那么应该是1e9的时间复杂度，但是随机嘛肯定会小点，所以暴力是能过的，脸黑的就再交一次。

牛客算法周周练6 题解【B-E】

全站热榜