牛客算法周周练6题解

A.青蛙过河

题解：n个石墩，m片荷叶。
①若n=0，每片荷叶上只能放一只青蛙，最后从岸上直接跳到对面一只青蛙（最大的），然后再从大到小跳，最多可以有 m+1 只青蛙过河。
②若n=1，那么我们可以在这个石墩上放n+1只青蛙，然后转变为①状态，此时一共有2*（m+1）个青蛙可以过河。
③n>1，每多一个石墩就可以利用原来的k−1个石墩把它们的青蛙全部放到这上面来，这样就增加了一倍数量，答案为（m+1)*(2^n)
附代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;cin>>n>>m;
    cout<<(m+1)*(1<<n);
    return 0;
}

	

B.华华对月月的忠诚

题解：在斐波那契数列上：

gcd(a(n),a(n−1))=gcd(a(1),a(2))，

附代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
     long  long a,b,n;
     cin>>a>>b>>n;
     cout<<__gcd(a,b)<<endl;
} 

C.Game

题解：统计n的质因子数量，判断奇偶即可（特判1），注意一点题上说是多重集合，要是集合就不好办。
附代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    if(n==1){cout<<"Johnson";return 0;}
    int ans=0;
    for(int i=2;i*i<=n;i++){
        while(n%i==0)n/=i,ans++;
    }
    if(n>1)ans++;
    if(ans&1)cout<<"Nancy";
    else cout<<"Johnson";
} 

D.挖沟

题解：最小生成树模板，没意义，kruskal（克鲁斯卡尔算法） 加边法
附模板：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int pre[100005];
struct node{int u,v,w;} edge[500005];
int cmp(node a,node b) {return a.w<b.w;}
int find(int x) {
    if(x==pre[x])return x;
    return pre[x]=(find(pre[x]));
}
int main() {
    int p,r;
    cin>>p>>r;
    for(int i=1;i<=p;i++)pre[i]=i;
    for(int i=1;i<=r;i++)scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
    sort(edge+1,edge+r+1,cmp);
    int ans=0,num=0;
    for(int i=1;i<=r;i++){
        int fx=find(edge[i].u);
        int fy=find(edge[i].v);
        if(fx!=fy){
            pre[fx]=fy;
            ans+=edge[i].w;
            num++;
        }
        if(num==p-1)
            break;
    }
    printf("%d\n",ans);
    return 0;
} 

E.签到题

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 1e7+5;
int a[N<<2],b[N<<2];
set<pii>s;
void updata(int x,int y,int z,int l,int r,int rat){
    if(x<=l&&r<=y){
        a[rat]+=z;
        if(a[rat])b[rat]=r-l+1;
        else if(l!=r)b[rat]=b[rat<<1]+b[rat<<1|1];
        else b[rat]=0;//单点情况
        return ;
    }
    int mid=(r+l)>>1;
    if(mid>=x)
        updata(x,y,z,l,mid,rat<<1);
    if(mid<y)
        updata(x,y,z,mid+1,r,rat<<1|1);
    if(a[rat])b[rat]=r-l+1;
    else if(l!=r)b[rat]=b[rat<<1]+b[rat<<1|1];
    else b[rat]=0;//单点情况
}
int main(){
    int n,m;
    cin>>n>>m;
    while(n--){
        int opt,x,y;
        cin>>opt>>x>>y;
        if(opt == 1){
            if(s.find((pii){x,y}) != s.end()) continue;
            s.insert((pii){x,y});
            updata(x,y,1,1,m,1);
        }
        if(opt == 2){
            if(s.find((pii){x,y}) == s.end()) continue;
            s.erase((pii){x,y});
            updata(x,y,-1,1,m,1);
        }
        if(opt == 3){
            cout<<b[1]<<'\n';
        }
    }
    return 0;
}