牛客算法周周练全部题解

Phemia ·

更新时间:2024-09-21

· 788 次阅读

eg：感觉牛客算法周周练的题目还是挺好的，有一定的思维量，时间也很友好，大家都可以打一打。
传送门

A 相反数

题意：给出一个数字，将其翻转并与原数相加，输出这个数字。
题解：高精度都用不上，签到题。

//
//  main.cpp
//  acm
//
//  Created by Mac on 2020/3/26.
//  Copyright © 2020 Mac. All rights reserved.
//
#include "stdio.h"
#include "string.h"
#include "iostream"
#include "algorithm"
#include "math.h"
#include "queue"
#include "map"
#include "set"
#include "vector"
#include "stack"
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e9+7;
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int N=3e5+10;
const ll Mod=998244353;
ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int n;
int doit(int x){
    int res=0;
    while(x){
        res=res*10+x%10;
        x/=10;
    }
    return res;
}
int main(){
    scanf("%d",&n);
    printf("%d\n",n+doit(n));
    return 0;
}

C 完全平方数

题意：求区间[L,R]之内的完全平方数个数。
题解：范围是1e9，我们先预处理所有的完全平方数，然后使用二分查找即可，有一个坑点，就是0也是完全平方数。

//
//  main.cpp
//  acm
//
//  Created by Mac on 2020/3/26.
//  Copyright © 2020 Mac. All rights reserved.
//
#include "stdio.h"
#include "string.h"
#include "iostream"
#include "algorithm"
#include "math.h"
#include "queue"
#include "map"
#include "set"
#include "vector"
#include "stack"
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e9+7;
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int N=3e5+10;
const ll Mod=998244353;
ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int a[maxn],cnt;
int main(){
    for(int i=1;i*i<=mod-7;i++)a[i]=i*i,cnt=i;
    int T;
    scanf("%d",&T);
    while(T--){
        int l,r;
        scanf("%d%d",&l,&r);
        int pos1=lower_bound(a+1,a+1+cnt,l)-a;
        int pos2=lower_bound(a+1,a+1+cnt,r)-a;
        int ans;
        if(r==a[pos2])ans=pos2-pos1+1;
        else ans=pos2-pos1;
        if(l==0)ans++;
        printf("%d\n",ans);
    }
    return 0;
}

D 小H和游戏

题意：有一棵树，每次选择一个结点，其距离为2以内的点都会被标记一次，每次输出这个结点已经被标记的次数。
题解：一开始想的是dfs后来发现t飞了，发现并查集可以搞这道题，开一个数组d[N]，表示每个点被选择的次数，同时用一个数组F[N][2]，F[I][1]表示I的儿子选择的次数，F[I][2]表示I的孙子被选择的次数，之后并查集维护统计答案即可。

//
//  main.cpp
//  acm
//
//  Created by Mac on 2020/3/26.
//  Copyright © 2020 Mac. All rights reserved.
//
#include "stdio.h"
#include "string.h"
#include "iostream"
#include "algorithm"
#include "math.h"
#include "queue"
#include "map"
#include "set"
#include "vector"
#include "stack"
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e9+7;
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int N=7e5+50100;
const ll Mod=998244353;
ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int fa[N],f[N][3],d[N];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(!fa[u])fa[u]=v;
        else fa[v]=u;
    }
    while(m--){
        int x;
        scanf("%d",&x);
        d[x]++;
        int num=0;
        if(fa[x]){
            f[fa[x]][1]++;
            f[fa[x]][2]++;
            num=f[fa[x]][1];
            if(fa[fa[x]])f[fa[fa[x]]][2]++;
        }else num=d[x];
        printf("%d\n",d[fa[x]]+d[fa[fa[x]]]+f[x][2]+num);
    }
    return 0;
}

B Music Problem

题意：给出若干个数字，问其中部分和是不是3600的整数倍。
题解：两个思路。第一个思路是多重背包，显然，将所有的数字对3600取模，每个数字ai可以有若干个，问题就转换成了这么多数字能否恰好放满3600的问题。第二个思路是bitset，f[i]=1表示存在一种情况使得可以加到i，那么每次将整个bitset左移x位再或上去即可。

//
//  main.cpp
//  acm
//
//  Created by Mac on 2020/3/26.
//  Copyright © 2020 Mac. All rights reserved.
//
#include "stdio.h"
#include "string.h"
#include "iostream"
#include "algorithm"
#include "math.h"
#include "queue"
#include "map"
#include "set"
#include "vector"
#include "stack"
#include "bitset"
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e9+7;
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int N=7e5+5010;
const ll Mod=998244353;
ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int n;
bitsetf;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        f.reset();f[0]=1;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            x%=3600;
            f|=f<>3600;
        }
        if(f[3600])puts("YES");
        else puts("NO");
    }
    return 0;
}

E 水题（water）

题意：给出一个数列公式，判断x是否是其中一项，如果是求出第几项再进行m进制转换，如果不是输出x%min(13,m)+1皇后的问题的解。
题解：数列公式是斐波那契公式，然后这道题就成了水题，13皇后问题可以预处理一下得到。

#include
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int a[]={-1,1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596};
ll f[100];
ll x,m;
int main(){
	f[1]=f[2]=1;
	for(int i=3;i<=100;i++)f[i]=f[i-1]+f[i-2];
	scanf("%lld%lld",&x,&m);
	int flag=0;
	for(int i=1;i<=80;i++)if(f[i]==x)flag=1; 
	if(flag){
		ll ans=1e18,num=0,sum=0;
		for(int i=2;i<=100;i++){
			if(m%i)continue;
			num=sum=0;
			while(m%i==0)num++,m/=i;
			ll tmp=x;
			while(tmp)sum+=tmp/i,tmp/=i;
			ans=min(ans,sum/num);
		}
		printf("%lld\n",ans);
	}else printf("%d\n",a[x%min(13ll,m)+1]);
	return 0;
}

作者：小涵少年

牛客算法

1024 个赞