题解

NOIP半年集训day6

A.Scape

枚举起点就完了,随便做。
考场上我居然还想麻烦了,幸好没耽误太久。

代码

#include <cstdio>
#include <iostream>
#include <climits>
#include <map>
const int MAXN = 1e3 + 7;
int n, c;
int w[MAXN];
int main(int argc, char *argv[]) {
    scanf("%d %d", &n, &c);
    for (int i = 1; i <= n; i++) {
        scanf("%d", w + i);
    }
    int ans = 0;
    for (int s = 1; s <= n; s++) {
        int tmp = 0, cap = c;
        for (int j = s; j <= n && cap > 0; j++) {
            if (w[j] <= cap) {
                cap -= w[j];
                tmp++;
            }
        }
        ans = std::max(ans, tmp);
    }
    printf("%d\n", ans);
    return 0;
}

B.And

这道题应该是有好几种做法的,这里我就只给我考场上最直观的想法吧。
矩阵中的一个权值 $X_{i,\ j}$,把这个数二进制分解一下,是 $1$ 的那一位就意味着 $A_i$ 和 $A_j$ 的这个二进制位是 $1$ 。然后也保证了一定合法,剩下的都填 $0$ 就可以了。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <cmath>
#include <algorithm>
#include <iostream>
const int MAXN = 1e3 + 7;
int map[MAXN][MAXN];
int a[MAXN][32];
inline int lowbit(int x) {
    return x & (-x);
}
int main(int argc, char *argv[]) {
    int n;
    scanf("%d", &n);
    memset(a, -1, sizeof a);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &map[i][j]);
            if (i == j) continue;
            for (int k = 0; k <= 30; k++) {
                if (map[i][j] & (1 << k)) {
                    a[i][k] = 1;
                    a[j][k] = 1;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        int tmp = 0;
        for (int j = 0; j <= 30; j++) {
            if (a[i][j] == 1) tmp += (1 << j);
        }
        printf("%d ", tmp);
    }
    puts("");
    return 0;
}

C.Dist

数据范围里面保证了 $k > 1$,那么这棵树的最大深度是 $\log^2(n)$ 。每次查询暴力跳 $lca$ 就可以了。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <climits>
#include <algorithm>
#define int long long
const int MAXN = 1e6 + 7;
int k, q, n, num[MAXN];
int end;
struct Node {
    int deep, rank;
    bool operator == (const Node &other) const {
        return deep == other.deep && rank == other.rank;
    }
    bool operator != (const Node &other) const {
        return deep != other.deep || rank != other.rank;
    }
};
inline int queryDeep(int pos) {
    int l = 0, r = end;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (num[mid] <= pos) l = mid;
        else r = mid - 1;
    }
    if (pos == num[l]) return l;
    else return l + 1;
}
Node find(Node a) {
    Node ret;
    ret = (Node){a.deep - 1, (a.rank - 1) / k + 1};
    return ret;
}
int getLca(Node u, Node v) {
    if (u.deep > v.deep) std::swap(u, v);
    while (u.deep < v.deep) {
        v = find(v);
    }
    if (u == v) return u.deep;
    while (u != v) {
        u = find(u);
        v = find(v);
    }
    return u.deep;
}
signed main() {
    std::cin >> n >> k >> q;
    num[0] = 1;
    int qwq = k;
    for (int i = 1; ; qwq *= k, i++) {
        if (num[i - 1] + qwq > n) {
            end = i - 1;
            break;
        }
        num[i] = num[i - 1] + qwq;
    }
    int u, v;
    while (q--) {
        scanf("%lld %lld", &u, &v);
        int du = queryDeep(u), dv = queryDeep(v);
        int ru = u - num[du - 1], rv = v - num[dv - 1];
        Node a, b;
        a = (Node){du, ru};
        b = (Node){dv, rv};
        printf("%lld\n", du + dv - 2 * getLca(a, b));
    }
    return 0;
}

D.Path

题面花里花哨的,还扯了什么删边之类的,不强制离线就都是假的。
把删边看成倒着加边就可以了。路径 $(u,\ v)$ 的异或和为 $0$ 就是说这两个点到根节点的异或和相等,这个都是套路了。
那这样的话就倒着加边,并查集记录一个 $size$ 启发式合并每次把小的合并到大的上面,这样每个点最多被合并 $\log^2(n)$ 次。
每次合并做一遍 $dfs$ 求出到新的根节点的距离,然后开个 $map$ 当计数器用,顺带着计算答案的偏移量就可以了。
考场上写错邻接表我也是个人才。。。$\text{100pts} \to \text{0pts}$
只是准备了一周期末考试没写代码而已就生疏成这个样子,简直丢人了QAQ
浪费了一次可以 $\text{AK}$ 的机会QAQ

代码

#include <cstdio>
#include <map>
#include <algorithm>
#include <climits>
const int MAXN = 1e5 + 7;
#define int long long
int f[MAXN], dist[MAXN], h[MAXN];
std::map<int, int> num[MAXN];
long long ans = 0;
int n, from[MAXN], to[MAXN], weight[MAXN];
int p[MAXN];
long long seq[MAXN];
struct Edge {
    int t, w, next;
} edge[MAXN << 1];
int head[MAXN], cnt;
inline void add(int u, int v, int w) {
    edge[++cnt] = (Edge){v, w, head[u]}; head[u] = cnt;
}
void dfs(int root, int u, int pre) {
    f[u] = root;
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (v == pre) continue;
        dist[v] = dist[u] ^ edge[e].w;
        if (num[root].count(dist[v])) ans += 1ll * num[root][dist[v]];
        dfs(root, v, u);
    }
}
void change(int root, int u, int pre) {
    if (num[root].count(dist[u])) num[root][dist[u]]++;
    else  num[root][dist[u]] = 1;
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (v == pre) continue;
        change(root, v, u);
    }
}
void merge(int u, int v, int w) {
    if (h[f[u]] > h[f[v]]) std::swap(u, v);
    dist[u] = w ^ dist[v];
    if (num[f[v]].count(dist[u])) ans += 1ll * num[f[v]][dist[u]];
    h[f[v]] += h[f[u]];
    num[f[u]].clear();
    dfs(f[v], u, 0);
    change(f[v], u, 0);
    add(u, v, w);
    add(v, u, w);
}
signed main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) f[i] = i, h[i] = 1, num[i][0] = 1;
    for (int i = 1; i < n; i++) {
        scanf("%lld %lld %lld", from + i, to + i, weight + i);
    }
    for (int i = 1; i < n; i++) {
        scanf("%lld", p + i);
    }
    seq[n] = 0;
    for (int i = n - 1; i >= 1; i--) {
        int u = from[p[i]], v = to[p[i]], w = weight[p[i]];
        merge(u, v, w);
        seq[i] = ans;
    }
    for (int i = 1; i <= n; i++) {
        printf("%lld\n", seq[i]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注