牛客算法周周练6

闲聊:这次的有点简单.....
A题:看了一下感觉像汉诺塔问题....
假设最开始n=0,也就是石墩数为0,此时荷叶数为m,那么可以过去 只青蛙,相信这个大家都知道
现在n=1,我们可以由前一个状态得到,可以假设1号石墩为上一个的终点的石墩,那么除了1号石墩,剩下的状态为n=0的状态,此时可以跳过来m+1个,然后现在1号石墩上还剩余m+1个,把这m+1个每个荷叶和1号石墩上各一个,然后逐步累加到终点石墩上,此时答案为
现在n=2,那么我们同理2号石墩等于n=1时终点石墩的状态,然后剩下的状态就为拿n=1时候的状态,那么为
然后多写几个发现

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

B题:蒙一发 然后过了.......
多写几组看看就行,具体解释就跳了

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

C题:咦!分解到不能分解然后算输
唯一分解定理:任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积
也就是
P为质数,a为幂次
然后就是判断幂次和的奇偶

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);
    if(n==1) printf("Nancy\n");
    else
    {
        int num=0;
        for(int i=2;i<=n;i++)
        {
            while(n%i==0)
            {
                n/=i;
                num++;
            }
        }
        printf(num&1?"Nancy\n":"Johnson\n");
    }

    return 0;
}

D题:读完感觉最小生成树的裸体,可能是错觉,咦!好像真的是裸题
keruskal直接套.....
并查集+边权贪心

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edges
{
    int s,t,w;
    bool operator<(const edges &e) const{
        return w<e.w;
    }
}edge[500005];
inline int read(void)
{
    int s=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9') {s=s*10+c-'0';c=getchar();}
    return f*s;
}
int parent[100005];
int find(int x){
    return parent[x]==x?parent[x]:parent[x]=find(parent[x]);
}
long long keruskal(void)
{
    long long sum=0,cnt=0;
    for(int i=1;i<=m;i++){
        if(cnt==n-1) break;
        int u=edge[i].s;int v=edge[i].t;
        if(find(u)!=find(v)){
            sum+=edge[i].w;
            parent[find(u)]=find(v);
            cnt++;
        }
    }
    return sum;
}
int main(void)
{
    n=read();m=read();
    for(int i=1;i<=n;i++)parent[i]=i;
    for(int i=1;i<=m;i++){
        edge[i].s=read();edge[i].t=read();edge[i].w=read();
    }
    sort(edge+1,edge+m+1);
    cout<<keruskal();
}

E题:有毒的签到题
代码补全???,反正队友写的暴力过了.........
具体看代码......

int main()
{
    scanf("%d%d", &N, &maxL);
    while (N--)
    {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 1)
        {
            if (L.find(make_pair(x, y)) != L.end())
                continue;
            L.insert(make_pair(x, y));
            for (int i = x; i <= y; ++i)
            {
                a[i]++;
                if (a[i] == 1)
                    ans++;
            }
        }
        if (opt == 2)
        {
            if (L.find(make_pair(x, y)) == L.end())
                continue;
            L.erase(make_pair(x, y));
            for (int i = x; i <= y; ++i)
            {
                a[i]--;
                if (a[i] == 0)
                    ans--;
            }
        }
        if (opt == 3)
            printf("%d\n", ans);
    }
    return 0;
}