2024牛客寒假算法基础集训营6

发表于 更新于 分类于 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 7 分钟
We're all traveling through time together, every day of our lives. All we can do is do our best to relish this remarkable ride. — About Time

A. 宇宙的终结

思路：

  • 根据题目意思，我们需要将一个数质因数分解，然后求一下质因子是否只有3个数

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int l, r;
    std::cin >> l >> r;

    std::vector<int> a;
    for (int i = l; i <= r; i++) {
        auto check = [&](int x) {
            std::map<int, int> mp;
            for (int i = 2; i <= x / i; i++) {
                if (x % i == 0) {
                    while (x % i == 0) {
                        x /= i;
                        mp[i]++;
                    }
                }
            }
            if (x > 1) mp[x]++;

            int cnt = 0;
            for (auto [x, y] : mp) {
                if (y == 1) cnt++;
            }
            bool f = false;
            cnt == 3 ? f = 1 : f = 0;

            return (mp.size() == 3 && f);
        };	
        if (check(i)) {
            std::cout << i << "\n";
            return 0;
        }
    }

    std::cout << "-1\n";
    
    return 0;
}

B. 爱恨的纠葛

思路：

  • 只需要维护一个最小值即可，其他的位置可以随便放数，只需保证一个位置的差值最小即可
  • 可以用二分查找来求最小差值，然后将其填入相应位置即可

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
constexpr i64 inf = 1LL << 60;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
        
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    std::vector<int> b(n);
    for (int j = 0; j < n; j++) {
        std::cin >> b[j];
    }

    std::sort(a.begin(), a.end());

    i64 mn = inf, p = -1, val = 0, pl = -1;
    for (int i = 0; i < n; i++) {
        auto it = std::lower_bound(a.begin(), a.end(), b[i]) - a.begin();
        if (it == n) {
            int dif = abs(a[it - 1] - b[i]);
            if (dif < mn) {
                mn = dif;
                p = i;
                val = a[it - 1];
                pl = it - 1;
            }
        } else if (it == 0) {
            int dif = abs(a[it] - b[i]);
            if (dif < mn) {
                mn = dif;
                p = i;
                val = a[it];
                pl = it;
            }
        } else {
            int pre = abs(a[it - 1] - b[i]);
            int suf = abs(a[it] - b[i]);
            if (pre < suf) {
                if (pre < mn) {
                    mn = pre;
                    p = i;
                    val = a[it - 1];
                    pl = it - 1;
                }
            } else {
                if (suf < mn) {
                    mn = suf;
                    p = i;
                    val = a[it];
                    pl = it;
                }
            }
        }
    }

    std::vector<int> ans(n);
    ans[p] = val;
    a.erase(a.begin() + pl);

    int tot = 0;
    for (int i = 0; i < n; i++) {
        if (i == p) continue ;
        ans[i] = a[tot++];
    }
    for (int j = 0; j < n; j++) {
        std::cout << ans[j] << " \n"[j == n - 1];
    }

    return 0;
}

C. 心绪的解剖

思路：

  • 个人感觉这题主要考察时间复杂度的计算，因为斐波那契数列的第45项就已经比1e9大了，所以我们只需在询问外进行初始化即可
  • 然后询问的时候查表

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::map<i64, std::array<int, 3>> mp;
    std::vector<i64> f(50);

    f[0] = 0, f[1] = 1;
    for (int i = 2; ; i++) {
        f[i] = f[i - 2] + f[i - 1];
        if (f[i] > 1E9) {
            break;
        }
    }
    
    for (int i = 0; i < 45; i++) {
        for (int j = 0; j < 45; j++) {
            for (int k = 0; k < 45; k++) {
                mp[f[i] + f[j] + f[k]] = {f[i], f[j], f[k]};
            }
        }
    }

    int q;
    std::cin >> q;

    while (q--) {
        i64 n;
        std::cin >> n;

        if (mp.count(n)) {
            auto [x, y, z] = mp[n];
            std::cout << x << " " << y << " " << z << "\n";
        } else {
            std::cout << "-1\n";
        }
    }

    return 0;
}

D. 友谊的套路

思路：

  • 五局三胜，那么

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(10);

    double p;
    std::cin >> p;

    std::cout << pow(p, 2) * pow(1 - p, 2) << "\n";

    return 0;
}

E. 未来的预言

思路：

  • 模拟即可

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string m;
    std::cin >> m;
    m = m.substr(2);

    int n = std::stoi(m);

    std::string s;
    std::cin >> s;

    int len = s.size();
    int R = 0, P = R;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'R') R++;
        else if (s[i] == 'P') P++;

        if (R > n / 2) {
            std::cout << "kou!\n"; 
            std::cout << i + 1 << "\n";
            return 0;
        }
        if (P > n / 2) {
            std::cout << "yukai!\n";
            std::cout << i + 1 << "\n";
            return 0;
        }
    }

    std::cout << "to be continued.\n";
    std::cout << len << "\n";

    return 0;
}

I. 时空的交织

思路：

  • 这是个结论题，只需要维护最大子段和乘最大子段和，以及最小子段和乘最小子段和

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
constexpr i64 inf = 1LL << 60;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    std::vector<i64> a(n), b(m);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        std::cin >> b[i];
    }

    i64 A1 = inf, B1 = -inf;
    i64 A2 = inf, B2 = -inf;

    i64 A = inf, B = -inf;
    for (int i = 0; i < n; i++) {
        A = std::min(a[i], A + a[i]);
        B = std::max(a[i], B + a[i]);

        A1 = std::min(A1, A);
        B1 = std::max(B1, B);
    }
    A = inf, B = -inf;
    for (int i = 0; i < m; i++) {
        A = std::min(b[i], A + b[i]);
        B = std::max(b[i], B + b[i]);

        A2 = std::min(A2, A);
        B2 = std::max(B2, B);
    }

    std::cout << std::max({A1 * A2, A1 * B2, B1 * A2, B1 * B2}) << "\n";

    return 0;
}

J. 绝妙的平衡

思路：

  • 首先，我们将所有的节点都置为1，然后选取节点置为2，当出现一个子树的权值和为1，那么一定无解，我们无法在他的下面进行修改
  • 如果出现某个红色节点的子树的权值和mod 3 == 1，那么我们可以修改他的某一个未修该的节点和当前这个节点，将其修改为2，其子树权值增量为2，这样这个子树的权值mod 3就为0，然后修改完就把这个子树的权值和给删除
  • 如果出现某个红色节点的子树权值和mod 3 == 2，那么我们直接把这个点赋值为2，其子树权值增量为1，然后删除这个子树

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<char> s(n + 1), ans(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> s[i];
        ans[i] = '1';
    }

    std::vector<std::vector<int>> adj(n + 1);
    for (int i = 2; i <= n; i++) {
        int x;
        std::cin >> x;
        adj[x].push_back(i);
    }

    bool ok = true;
    std::vector<int> f(n + 1);
    auto dfs = [&](auto self, int u) -> void {
        f[u] = 1;
        int son = -1;
        for (auto x : adj[u]) {
            self(self, x);
            f[u] += f[x];
            if (s[x] == 'W') {
                son = x;
            }
        }
        if (s[u] == 'R') {
            if (f[u] == 1) ok = false;
            else if (f[u] % 3 == 1) {
                ans[u] = ans[son] = '2';
            } else if (f[u] % 3 == 2) {
                ans[u] = '2';
            }
            f[u] = 0;
        }
    };

    dfs(dfs, 1);

    if (!ok) {
        std::cout << "-1\n";
    } else {
        for (int i = 1; i <= n; i++) {
            std::cout << ans[i];
        }
        std::cout << "\n";
    }

    return 0;
}

F. 命运的抉择

思路：

  • 数组a中的任何一个元素和数组b中的任何一个元素的gcd(x, y) = 1，说明数组a里的每一个数和数组b里的每一个数都互质
  • 首先我们将每一个数分解质因数，然后将每一个拥有相同质因子的数列入同一个集合，只要最后出现两个或两个以上的集合，那么就是可行的，如果最后只有一个集合，就一定是不行的

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
struct DSU {
    std::vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int q;
    std::cin >> q;

    while (q--) {
        int n;
        std::cin >> n;

        std::vector<int> c(n);
        std::map<int, std::vector<int>> mp;
        for (int i = 0; i < n; i++) {
            std::cin >> c[i];
            int x = c[i];
            for (int j = 2; j <= x / j; j++) {
                if (x % j == 0) {
                    while (x % j == 0) {
                        x /= j;
                    }
                    mp[j].push_back(i + 1);
                }
            }
            if (x > 1) mp[x].push_back(i + 1);
        }

        DSU f(n + 1);

        for (auto [x, y] : mp) {
            for (int i = 1; i < y.size(); i++) {
                f.merge(y[i - 1], y[i]);
            }
        }
        auto p = f.find(1);
        std::vector<int> a, b;
        for (int i = 0; i < n; i++) {
            if (f.find(i + 1) == p) a.push_back(c[i]);
            else b.push_back(c[i]);
        }

        if (b.empty()) {
            std::cout << "-1 -1\n";
        } else {
            std::cout << a.size() << " " << b.size() << "\n";
            for (int i = 0; i < a.size(); i++) {
                std::cout << a[i] << " \n"[i == a.size() - 1];
            }
            for (int i = 0; i < b.size(); i++) {
                std::cout << b[i] << " \n"[i == b.size() - 1];
            }
        }
    }

    return 0;
}