牛客NOIP暑期七天营-提高组1 Solution

T1 最短路

这题挺水的
80分应该是没有特判i != 1w[i] == 0的无解情况

#include <bits/stdc++.h>
#define N 50000
#define FOR(I, L, R) for(I = L; I <= R; ++I)
using namespace std;

int i, j, n, s, ans[N + 30][3];
struct dot {
    int id, s;
}a[N + 30];

int cmp(dot x, dot y);

int main() {
    scanf ("%d%d", &n, &s);
    FOR(i, 1, n) {scanf ("%d", &a[i].s); a[i].id = i;}
    sort(a + 1, a + n + 1, cmp);
    FOR(i, 2, n) {
        if (a[i].s == a[i - 1].s) {
            if (a[i].s < 1) {printf ("-1\n"); return 0;}
            if (j == 0) j = i - 2;
            ans[i][0] = a[j].id; ans[i][1] = a[i].id; ans[i][2] = a[i].s - a[j].s;
            continue;
        }else j = 0;
        if (a[i].s - a[i - 1].s > s) {printf ("-1\n"); return 0;}
        ans[i][0] = a[i - 1].id; ans[i][1] = a[i].id; ans[i][2] = a[i].s - a[i - 1].s;
    }printf ("%d\n", n - 1);
    FOR(i, 2, n) printf ("%d %d %d\n", ans[i][0], ans[i][1], ans[i][2]);
    return 0;
}

int cmp(dot x, dot y) {
    if (x.s == y.s) return x.id < y.id;
    return x.s < y.s;
}

T2

其实是个相当套路的题。

题面翻译:
给出序列a,求出a的一种排列,使得两两异或后求和的值最小。

解法1:

求一遍kruskal,稍微判断一下。

复杂度 O(n^2) 得分:60

解法2:

将a中的每个数转换为二进制序列,构建一棵01trie树,然后trie树从左至右分枝的排列即是最佳排列。

复杂度 O(nlogn) 得分:100

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define N 1000000
int i, j, n, high;
long long ans = 0X7F7F7F7F7F7F7F7F, a[N + 30];
struct Tire {
    int tot;
    std::vector < int > ch[2];
    Tire() {tot = 0; }
    inline void insert(long long x) {
        int Now, u = 0;
        for (j = 59; j >= 0; --j) {
            Now = (x & (1LL << j)) ? 1 : 0;
            if (!ch[Now][u]) ch[Now][u] = ++tot;
            u = ch[Now][u];
        }
    }inline long long _min(long long x) {
        int Now, u = 0;
        long long Ans = 0;
        for (j = 59; j >= 0; --j) {
            Now = (x & (1LL << j)) ? 1 : 0;
            if (!ch[Now][u]) {
                Ans |= (1LL << j);
                u = ch[Now ^ 1][u];
            }else u = ch[Now][u];
        } return Ans;
    }
}T;
int main() {
    scanf ("%d", &n);
    for (i = 1; i <= n; ++i) scanf ("%lld", &a[i]);
    T.ch[0].resize(n * 60 + 5);
    T.ch[1].resize(n * 60 + 5);
    std::sort(a + 1, a + n + 1);
    high = -1;
    for (i = 59; i >= 0; --i)
        if ((a[1] ^ a[n]) & (1LL << i)) {high = i;break;}
    if (high == -1) {
        printf ("0\n");
        return 0;
    }for (i = 1; i <= n; ++i)
        if (a[i] & (1LL << high)) ans = std::min(ans, T._min(a[i]));
        else T.insert(a[i]);
    printf ("%lld\n", ans);
    return 0;
}

T3

挖个坑
不会 Johnson 和 tarjan LCA
正在努力学习

Last modification:August 20th, 2019 at 01:49 pm

Leave a Comment