牛客算法周周练6(BCDE)

B：华华对月月的忠诚
思路：因为最后要求的是gcd(a,b)，所以我一开始是分类讨论的。
如果a和b都是偶数，那么他们的斐波拉契项都是偶数，对于任意位置的n和n+1,偶数的gcd都是2.
如果a和b都是奇数，或者是奇数与偶数，他们的斐波拉契项有可能有奇数或者偶数，一开始我猜想都是1，事实上大部分都是1，但是随手打了个表就找到了反例，a=3,b=9，然后我就发现事实上这个答案就是gcd(a,b)。
代码：

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

typedef long long int ll;
void solved(){
    ll a,b,n;cin>>a>>b>>n;
    cout<<__gcd(a,b)<<endl;

}
int main(){
    solved();
    return 0;
} 

D：挖沟
这个题。。。。。裸的最小生成树。。直接上板子就行。
克鲁斯卡尔算法：存边，对边权排序，选择n-1条最小边，并且不构成回路(并查集维护).
好久没写最小生成树了，现场花了几分钟手搓了一下
代码：

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

typedef long long int ll;
const int maxn = 5e5 + 10;
struct edge{
    int u,v,w;
    edge(){}
    edge(int a,int b,int c):u(a),v(b),w(c){}
}a[maxn];
int f[maxn];
bool cmp(edge a,edge b){
    return a.w < b.w;
}
int find(int x){
    if(f[x] != x){
        return f[x] = find(f[x]);
    }
    return x;
}
void solved(){
    int n,m;cin>>n>>m;
    for(int i = 1; i <= n; i++)f[i] = i;
    for(int i = 1; i <= m; i++){
        int u,v,w;cin>>u>>v>>w;
        a[i] = {u,v,w};
    }
    sort(a + 1 ,a + 1 + m,cmp);
    int tot = 0;
    ll ans = 0;
    for(int i = 1; i <= m; i++){
        int u = a[i].u,v = a[i].v;
        int fa = find(u);
        int fb = find(v);
        if(fa != fb){
            f[fa] = fb;
            tot++;
            ans += a[i].w;
        }
        if(tot == n - 1)break;
    }
    cout<<ans<<endl;
}
int main(){
    solved();
    return 0;
}

C：Game
思路：这题从一次操作可以将集合中一个数字分解为它的任意两个非1的因数入手，首先我们可以考虑特殊的数-素数，只能分解为1*n，所以先手必败，然后再思考普遍的情况。对于一个数，我们可以一直把他拆开，直到不能再拆为止，记录我们拆的次数，如果是奇数说明后手无法继续拆，偶数先手无法拆，输出对应答案即可。
代码：

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

bool is_prime(int n){
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0)return false;
    }return true;
} 
void solved(){
    int n;cin>>n;
    if(is_prime(n)){cout<<"Nancy"<<endl;return;} 
    queue<int>st;st.push(n);
    int cnt = 0;
    while(!st.empty()){
        int cur = st.front();st.pop();
        for(int i = 2; i * i  <= cur; i++){
            if(cur % i == 0){
                cnt++;
                st.push(i);st.push(cur / i);break;
            }
        }
    }
    if(cnt & 1)cout<<"Johnson"<<endl;
    else cout<<"Nancy"<<endl;
}
int main(){
    solved();
    return 0;
} 

E：签到题
思路：看到题直接就认为是记录每个数出现的次数，然后上线段树。。。。导致浪费好多时间。。还是先应该认真看题啊。。。题目意思是插入n段区间要我们就所有区间的并的个数，删除的区间必须是先前插入过的才行。
区间修改，区间求和，所以我们可以用线段树来维护，线段树维护cnt表示插入删除的次数，len表示当前区间长度。如果cnt为真说明这段区间已经插入过了，它的区间长度就是本身，否则，它的区间长度等于左右儿子的长度之和。如果插入的区间与已有的区间重合怎么处理？对于重合的区间说明之前已经插入过，它的cnt为真所以不用处理，就变成了只对没重合的处理。
代码：

#include <algorithm>
 #include <iostream>
 #include <cstring>
 #include <climits>
 #include <cstdio>
 #include <vector>
 #include <cstdlib>
 #include <ctime>
 #include <cmath>
 #include <queue>
 #include <stack>
 #include <map>
 #include <set>
 #define fi first
 #define lc (x<<1)
 #define se second
 #define U unsigned
 #define rc (x<<1|1)
 #define Re register
 #define LL long long
 #define MP std::make_pair
 #define CLR(i,a) memset(i,a,sizeof(i))
 #define FOR(i,a,b) for(Re int i = a;i <= b;++i)
 #define ROF(i,a,b) for(Re int i = a;i >= b;--i)
 #define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
 #define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
 #define DEBUG(x) std::cerr << #x << '=' << x << std::endl
 using namespace std;
 const int MAXN = 1000000+5;
 int N,maxL;
 std::set<std::pair<int,int> > L;

const int maxn = 1e6 + 10;
struct seg{
    int l,r,cnt;
    int len;
    seg(){}
    seg(int a,int b):l(a),r(b){}
}tree[maxn << 2];
void build(int rt,int l,int r){
    tree[rt] = {l,r};
    if(l == r){
        tree[rt].len = 0;
        tree[rt].cnt = 0;
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1,l, mid);
    build((rt << 1) + 1,mid + 1,r);
    tree[rt].cnt = 0;
    tree[rt].len = 0;
}

void update(int rt ,int l,int r,int v){
    if(tree[rt].l >= l && tree[rt].r <= r){
        tree[rt].cnt += v;
        if(tree[rt].cnt)tree[rt].len = (tree[rt].r - tree[rt].l + 1);
        else {tree[rt].len = tree[rt << 1].len + tree[rt << 1 | 1].len;}
        return ;
    }
    int mid = tree[rt].l + tree[rt].r >> 1;
    if(r <= mid) update(rt << 1,l,r,v);
    else if(l > mid) update((rt << 1) + 1,l,r,v); 
    else update(rt << 1,l,r,v),update((rt << 1) + 1,l,r,v);
    if(tree[rt].cnt)tree[rt].len = (tree[rt].r - tree[rt].l + 1);
    else {tree[rt].len = tree[rt << 1].len + tree[rt << 1 | 1].len;}
} 
int main(){
     scanf("%d%d",&N,&maxL);
     build(1,1,maxL);
     while(N--){
         int opt,x,y;
         scanf("%d%d%d",&opt,&x,&y);
         if(opt == 1){
             if(L.find(MP(x,y)) != L.end()) continue;
             L.insert(MP(x,y));
             update(1,x,y,1);
         }
         if(opt == 2){
             if(L.find(MP(x,y)) == L.end()) continue;
             L.erase(MP(x,y));
             update(1,x,y,-1);
         }
         if(opt == 3){
             printf("%d\n",tree[1].len);
         }
     }
     return 0;
 }