树状数组

树状数组

关注
发信
关注(28)粉丝(399)

绍兴市第十三届大学生计算机技能竞赛程序设计

A .Cake Cutting Problem

-------------------零AC，打扰了

B .Function

des：f(x) = f(x-1) + 1. f(0) = k. 给出x、k，求f(x)。

sol：签到题，好翻译好做。直接两数相加没什么好说的。

  • 数学
    #include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int main() {
    int t, a, b;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &a, &b);
        printf("%d\n", a + b);
    }
    return 0;
}
    View Code

C .Kira Yoshikage's Chessboard

des：给一个n * m的棋盘，问在至少有一个格子为free的情况下最多能放多少个马(free的意思是该格子没马且别的马无法一步到达该格子)。

sol：若棋盘小于等于3 * 3，或者min(n, m) == 1，答案为n * m - 1；否则若min(n, m) == 2，答案为n * m - 2； 否则答案为n * m - 3；

  • 贪心
    #include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int main() {
    int t, n, m;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        if (n > m) swap(n, m);
        if (n == 1) printf("%d\n", m - 1);
        else if (n == 2) {
            if (m <= 3) printf("%d\n", n * m - 1);
            else printf("%d\n", n * m - 2);
        } else {
            if (m == 3) puts("8");
            else printf("%d\n", n * m - 3);
        }
    }
    return 0;
}
    View Code

D .Special Graph Isomorphism

des：给定两个点数，边数相等的图，每个点的度数为2，且边为无权双向边。判断这两个图是否同构。

sol：看了用并查集的解法，感觉代码懂了，但是对题目的理解还不是很透彻。这两个图必由数个环构成。判断环的大小相等即可。

  • 并查集
    #include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 1e5 + 10;
int a[MAXN], b[MAXN];
int aa[MAXN], bb[MAXN];
int aaa[MAXN], bbb[MAXN];
int find(int* c, int i) {
    if (c[i] == -1) return i;
    return c[i] = find(c, c[i]);
}
int main() {
    int t, n, m;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        memset(a, -1, sizeof(int) * (n + 1));
        memset(b, -1, sizeof(int) * (n + 1));
        memset(aaa, 0, sizeof(int) * (n + 1));
        memset(bbb, 0, sizeof(int) * (n + 1));
        for (int i = 1; i <= n; i++)
            aa[i] = bb[i] = 1;
        for (int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            int fu = find(a, u);
            int fv = find(a, v);
            if (fu != fv) {
                a[fu] = fv;
                aa[fv] += aa[fu];
            }
        }
        for (int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            int fu = find(b, u);
            int fv = find(b, v);
            if (fu != fv) {
                b[fu] = fv;
                bb[fv] += bb[fu];
            }
        }
        for (int i = 1; i <= n; i++) {
            if (a[i] == -1) aaa[aa[i]] ++;
            if (b[i] == -1) bbb[bb[i]] ++;
        }
        bool ok = true;
        for (int i = 1; i <= n; i++)
            if (aaa[i] != bbb[i])
                ok = false;
        puts(ok ? "YES" : "NO");
    }
    return 0;
}
    View Code

    由于题目不是很懂，所以变量名也比较随意了。

E .Bang!

des：有n个怪物需要被消灭。第i个怪物的生命值为a_i。可以消耗3点体力造成5点伤害或者消耗1点体力造成1点伤害，求击杀n个怪物最少体力消耗。

sol：贪心：先五点五点打，最后如果血量少于3就一点一点打。

  • 贪心
    #include "bits/stdc++.h"
using namespace std;
#define debug puts("what the fuck");
typedef long long LL;
typedef pair<int, int> PII;
int main() {
    int t, n, m;
    scanf("%d", &t);
    while (t--) {
        int sum = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &m);
            sum += m / 5 * 3;
            if (m % 5 < 3) sum += m % 5;
            else sum += 3;
        }
        printf("%d\n", sum);
    }
    return 0;
}
    View Code

F .The villagers' election

des：有n个人，其中一些人相互认识，可以理解成n个点m条边。每个人可以代表自己和认识的人成为村委。问每个人都被奇数个人代表的方案数。

sol：这题的n很小，只有20，所以可以二进制枚举，另外可以再加一个二进制位运算优化。dfs应该也可以吧。

  • 二进制枚举+位运算
    #include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 30;
int edge[MAXN];
int lowbit(int i) {return i & -i;}
int count(int k) {
    int cnt = 0;
    while (k) {
        cnt ++;
        k -= lowbit(k);
    }
    return cnt;
}
int main() {
    int t, n, m;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) edge[i] = 1 << i - 1;
        for (int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            edge[u] |= 1 << v - 1;
            edge[v] |= 1 << u - 1;
        }
        int sum = 0;
        for (int i = 1; i < (1 << n); i++) {
            bool ok = true;
            for (int j = 1; j <= n; j++) {
                if (count(i & edge[j]) % 2 == 0) {
                    ok = false;
                    break;
                }
            }
            if (ok) sum++;
        }
        printf("%d\n", sum);
    }
    return 0;
}
    View Code

G .Big Bridge

-------------------抱歉，打扰了

H .Don's candy

des：

需要写一种数据结构来维护三种操作。

1　　x ：插入一个x

2　　x ：删除一个x

3　　x ：查询第x小的数

sol：官方题解中提到了几种解法：树状数组、线段树、平衡树、红黑树。。。比赛的时候我用的是fhq-treap后来又想到了线段树解法和树状数组解法。红黑树，这辈子都不可能手写红黑树的

  • fhq-treap
    #include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 1e5 + 10;
struct Treap {
    int val, rand;
    int size;
    int lson, rson;
} node[MAXN];
int root, tot;
int add_node(int v) {
    int i = ++tot;
    node[i].val = v;
    node[i].rand = rand();
    node[i].lson = node[i].rson = 0;
    node[i].size = 1;
    return i;
}
void split(int rt, int& a, int& b, int v) {
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (node[rt].val <= v) {
        a = rt;
        split(node[rt].rson, node[a].rson, b, v);
        node[a].size = node[node[a].lson].size + node[node[a].rson].size + 1;
    } else {
        b = rt;
        split(node[rt].lson, a, node[b].lson, v);
        node[b].size = node[node[b].lson].size + node[node[b].rson].size + 1;
    }
}
void merge(int& rt, int a, int b) {
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    if (node[a].rand < node[b].rand) {
        rt = a;
        merge(node[rt].rson, node[a].rson, b);
        node[rt].size = node[node[rt].lson].size + node[node[rt].rson].size + 1;
    } else {
        rt = b;
        merge(node[rt].lson, a, node[b].lson);
        node[rt].size = node[node[rt].lson].size + node[node[rt].rson].size + 1;
    }
}
void insert(int v) {
    int x, y;
    split(root, x, y, v);
    merge(x, x, add_node(v));
    merge(root, x, y);
}
void erase(int v) {
    int x, y, z;
    split(root, root, z, v);
    split(root, x, y, v - 1);
    merge(y, node[y].lson, node[y].rson);
    merge(root, x, y);
    merge(root, root, z);
}
int get_rank(int i, int k) {
    int sz = node[node[i].lson].size;
    if (k <= sz) return get_rank(node[i].lson, k);
    if (k == sz + 1) return node[i].val;
    if (k > sz + 1) return get_rank(node[i].rson, k - sz - 1);
}
int main() {
    int t, n;
    srand(time(NULL));
    scanf("%d", &t);
    while (t--) {
        root = 0, tot = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            int opt, x;
            scanf("%d%d", &opt, &x);
            if (opt == 1) insert(x);
            if (opt == 2) erase(x);
            if (opt == 3) printf("%d\n", get_rank(root, x));
        }
    }
    return 0;
}
    View Code

    优点：因为引入了随机数，所以不可能构造出卡掉treap的数据，如果有，就再交一次。

  • 线段树
    #include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 1e5 + 10;
struct Node {
    int l, r;
    int sum;
} segTree[MAXN * 4];
void build(int i, int l, int r) {
    segTree[i].l = l;
    segTree[i].r = r;
    segTree[i].sum = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
}
void add(int i, int ind, int val) {
    if (segTree[i].l == segTree[i].r) {
        segTree[i].sum = max(segTree[i].sum + val, 0); // 防止取走魔法口袋中不存在的糖果，然后发现没有这样的数据
        return;
    }
    int mid = segTree[i].l + segTree[i].r >> 1;
    if (ind <= mid) add(i << 1, ind, val);
    else add(i << 1 | 1, ind, val);
    segTree[i].sum = segTree[i << 1].sum + segTree[i << 1 | 1].sum;
}
int get_rank(int i, int k) {
    if (segTree[i].l == segTree[i].r)
        return segTree[i].l;
    if (k <= segTree[i << 1].sum) return get_rank(i << 1, k);
    else return get_rank(i << 1 | 1, k - segTree[i << 1].sum);
}
int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        build(1, 1, 100000);
        for (int i = 1; i <= n; i++) {
            int opt, x;
            scanf("%d%d", &opt, &x);
            if (opt == 1) add(1, x, 1);
            if (opt == 2) add(1, x, -1);
            if (opt == 3) printf("%d\n", get_rank(1, x));
        }
    }
    return 0;
}
    View Code
  • 树状数组+二分
    #include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 1e5 + 10;
int c[MAXN];
int lowbit(int i) {return i & -i;}
void add(int i, int v) {
    while (i < MAXN) {
        c[i] += v;
        i += lowbit(i);
    }
}
int sum(int i) {
    int res = 0;
    while (i > 0) {
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}
int get_rank(int k) {
    int l = 0, r = MAXN;
    while (l < r - 1) {
        int mid = l + r >> 1;
        if (sum(mid) < k) l = mid;
        else r = mid;
    }
    return r;
}
int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        memset(c, 0, sizeof(c));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            int opt, x;
            scanf("%d%d", &opt, &x);
            if (opt == 1) add(x, 1);
            if (opt == 2) add(x, -1);
            if (opt == 3) printf("%d\n", get_rank(x));
        }
    }
    return 0;
}
    View Code

    这是我看标程之前自己写的树状数组，后来想想这样复杂度不是成了O(n*logn*logn)，但是树状数组的常数是真优秀，比上面两份O(n * logn)的还快

  • 树状数组内二分
    #include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 1e5 + 10;
int c[MAXN];
int lowbit(int i) {return i & -i;}
void add(int i, int v) {
    while (i < MAXN) {
        c[i] += v;
        i += lowbit(i);
    }
}
int get_rank(int k) {
    int cnt = 0, number = 0;
    for (int i = 16; i >= 0; i--) {
        if (cnt + c[1 << i | number] < k) {
            cnt += c[1 << i | number];
            number += 1 << i;
        }
    }
    return number + 1;
}
int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        memset(c, 0, sizeof(c));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            int opt, x;
            scanf("%d%d", &opt, &x);
            if (opt == 1) add(x, 1);
            if (opt == 2) add(x, -1);
            if (opt == 3) printf("%d\n", get_rank(x));
        }
    }
    return 0;
}
    View Code

    标程还是标程，最高效的解法。

I .extract

des：一个带数字的字符串，先输出里面数的个数，再按顺序输出所以数，给出每个字符串的长度

sol：有种东西叫快读，就是在字符串里提取数，稍微改改拿来做这题就正好了，字符串都不用存。

  • 快读
    #include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 100010;
int a[MAXN], tot;
inline bool read(int& n) {
    char c = getchar();
    n = 0;
    while (c < '0' || c > '9') {
        if (c == '\n') {
            n = -1;
            return false;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        n = n * 10 + c - '0';
        c = getchar();
    }
    return c != '\n';
}
int main() {
    int t, n, m;
    bool has_next;
    read(t);
    while (t--) {
        tot = 0;
        read(n);
        do {
            has_next = read(m);
            if (m != -1) a[++tot] = m;
        } while (has_next);
        printf("%d\n", tot);
        for (int i = 1; i < tot; i++)
            printf("%d ", a[i]);
        printf("%d\n", a[tot]);
    }
    return 0;
}
    View Code

    写好快读再写主函数就很快乐了。

J .The long journey

des：求0到n - 2的全排列个数，t组测试数据

sol：a[i] = a[i - 1] * (i - 2) + 1

  • 打表+排列组合
    #include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 1e7 + 10;
const int MOD = 1e9 + 7;
int a[MAXN];
void init() {
    a[2] = 1;
    for (int i = 3; i <= 1e7; i++)
        a[i] = (1LL * a[i - 1] * (i - 2) + 1) % MOD;
}
int main() {
    int t, n; init();
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        printf("%d\n", a[n]);
    }
    return 0;
}
    View Code
01-05 15:03
Powered by LMLPHP ©2024 树状数组 0.081583