牛客算法周周练6

B、华华对月月的忠诚

辗转相减法（更相减损术），gcd与斐波那契数列的关系。
先介绍下辗转相除法之外的辗转相减法。gcd(a,b)如果a>b那么会等于gcd(a-b,b)。如果b>a那么会等于gcd(a,b-a)，如果a，b相等此时就是gcd。
还有一个结论就是 gcd(2a,2b) = 2gcd(a,b)
多用于高精度，代替复杂的取模运算。
先给结论题目要求的答案 $图片说明$ 证明如下：

import math
a,b,n = map(int,input().split())
print(math.gcd(a,b))

C、Game

给定n，每次可以把n拆分成两个数相乘，第二个人对拆分出来的数操作，谁最先不能操作，也就是集合内全是素数，就输了。
那么题目意思很简单，就是问你这个数，分解成若干素数相乘的形式，无论你是这么拆分，最后分解出来一定是同一个素数积。
所以直接对素数分解即可，遇到一个素数拆分一次。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int ans[N];

bool isprime(int x) {
    if (x < 2)    return false;
    for (int i = 2; i <= sqrt(x); ++i) {
        if (x % i == 0)    return false;
    }
    return true;
}

int countprime(int x) {
    int ret = 0;
    for (int i = 2; i <= sqrt(x); ++i) {
        if (isprime(i) && x % i == 0) {
            ret = 1 + ans[x / i];
            break;
        }
    }
    return ret;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 4; i <= n; ++i) {
        ans[i] = countprime(i);
    }
    //printf("%d\n", ans[n]);
    if (ans[n] & 1)    puts("Johnson");
    else    puts("Nancy");
    return 0;
}

D、挖沟

……迪杰斯特拉模板题，真就全模板，一点都没改，如果还不会就是数据结构没认真听课或者还没学图，最小生成树还是要会滴。
具体证明网上很多，这就不展开。

//kruskal 适用于稀疏图  O(n+m*log2(m))
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e5 + 7; //节点
const int M = 5e5 + 7; //路径数
int n, m;
struct Edge {
    int u, v, w;
    bool operator <(const Edge tmp) const {
        return w < tmp.w;
    }
}edge[M];
int father[N];
ll ans = 0; //最小生成树的花费和

int find(int root) {
    int son = root;
    while (root != father[root])
        root = father[root];
    while (son != root) { //路径压缩
        int temp = father[son];
        father[son] = root;
        son = temp;
    }
    return root;
}

void kruskal() {
    for (int i = 1; i <= m; i++) {
        int u = edge[i].u, v = edge[i].v;
        int x = find(u), y = find(v);
        if (x != y) {
            father[x] = y;
            ans += edge[i].w;
        }
    }
}
int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        father[i] = i;
    for (int i = 1; i <= m; ++i)
        edge[i].u = read(), edge[i].v = read(), edge[i].w = read();
    sort(edge + 1, edge + 1 + m);
    kruskal();
    printf("%lld\n", ans);
    return 0;
}

E、签到题

和我一样一开始照着出题人描述补函数的举起爪子，我最后TLE吐了，才发现，如果按照他思路，时间爆炸了……
直接改掉函数，模拟就行了，其实也可以用线段树，当然更快，模拟更轻松一点就是了。）看来被set大常数卡的不轻，当然也感谢出题人仁慈没给极限数据……

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;
int a[maxn];
int opt, x, y;
set<pair<int, int> >P;
int main(){
    int n, L;
    cin >> n >> L;
    int ans = 0;
    while (n--){
        cin >> opt >> x >> y;
        if (opt == 1){
            if (P.find(make_pair(x, y)) != P.end()) continue;
            P.insert(make_pair(x, y));
            for (int i = x; i <= y; i++){
                a[i]++;
                if (a[i] == 1) ans++;
            }
        }
        else if (opt == 2){
            if (P.find(make_pair(x, y)) == P.end()) continue;
            P.erase(make_pair(x, y));
            for (int i = x; i <= y; i++){
                a[i]--;
                if (a[i] == 0) ans--;
            }
        }
        else{
            cout << ans << endl;
        }
    }
    return 0;
}

E正解、线段树写法

区间更新，区间查询，如果区间值大于1，正解求区间长度即可。否则就要去左右子树累加区间值大于1的区间长度，线段树操作

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }

const int MAXN = 100010;
struct Node {
    int l, r;
    //ll lazy;
    ll sum;
} segTree[MAXN << 2];
void build(int i, int l, int r) {
    segTree[i].l = l;
    segTree[i].r = r;
    if (l == r) {
        //scanf("%lld", &segTree[i].sum);
        return;
    }
    int mid = l + r >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    //segTree[i].sum = segTree[i << 1].sum + segTree[i << 1 | 1].sum;
}
void push_up(int i) {
    ll tmp = min(segTree[i << 1].sum, segTree[i << 1 | 1].sum);
    segTree[i].sum += tmp;
    segTree[i << 1].sum -= tmp;
    segTree[i << 1 | 1].sum -= tmp;
}
void push_down(int i) {
    if (segTree[i].sum) {
        segTree[i << 1].sum += segTree[i].sum;
        segTree[i << 1 | 1].sum += segTree[i].sum;
        segTree[i].sum = 0;
    }
}
void add(int i, int l, int r, ll v) {
    if (segTree[i].l >= l && segTree[i].r <= r) {
        segTree[i].sum += v;
        return;
    }
    push_down(i);
    int mid = segTree[i].l + segTree[i].r >> 1;
    if (mid >= l) add(i << 1, l, r, v);
    if (mid < r) add(i << 1 | 1, l, r, v);
    push_up(i);
}
ll query(int i, int l, int r) {
    ll res = 0;
    if (segTree[i].l >= l && segTree[i].r <= r)
        if (segTree[i].sum > 0)
            res += r - l + 1;
        else if (l != r) {
            int mid = segTree[i].l + segTree[i].r >> 1;
            push_down(i);
            res += query(i << 1, l, mid);
            res += query(i << 1 | 1, mid + 1, r);
            push_up(i);
        }
    return res;
}
int main() {
    int n, m, op;
    scanf("%d%d", &n, &m);
    build(1, 1, m);
    int l, r;
    while (n--) {
        op = read(), l = read(), r = read();
        if (op == 1)
            add(1, l, r, 1);
        else if (op == 2)
            add(1, l, r, -1);
        else
            printf("%lld\n", query(1, 1, m));
    }
    return 0;
}