15届省赛冲刺营结营考试

发表于 更新于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 5 分钟
A contented mind is a perpetual feast.

A. 小蓝的决议

思路：

  • 判断是否大于 \(\frac{N}{2}\) 即可

时间复杂度：\(O(1)\)

1
2
3
4
5
6
void solve() {
    int N, X;
    std::cin >> N >> X;
    
    std::cout << (X >= (N + 1) / 2 ? "YES\n" : "NO\n");
}

B. 鸡哥的奇特密码

思路：

  • 模拟即可

时间复杂度：\(O(n)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string S;
    std::cin >> S;
        
    int n = S.size();
        
    std::vector<int> vis(n);
    for (int i = 0; i < n; i++) {
        if (S[i] == 'Q') {
            vis[i] = true;
        }
    }
    
    bool f = false;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            if (!f) {
                std::cout << "L";
                f = true;
            }
        } else {
            std::cout << S[i];
            f = false;
        }
    }
    
    return 0;
}

C. 鸡哥的蛋糕大作战

思路：

  • 按照题意模拟

时间复杂度：\(O(nlen_{a_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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int A, B;
    std::cin >> A >> B;
    
    int max = 0;
    std::map<int, int> mp{{0, 1}, {6, 1}, {9, 1}, {8, 2}};
    for (int i = A; i <= B; i++) {
        int t = i, cnt = 0;
        while (t) {
            cnt += mp[t % 10];
            t /= 10;
        }
        max = std::max(max, cnt);
    }
    for (int i = A; i <= B; i++) {
        int t = i, cnt = 0;
        while (t) {
            cnt += mp[t % 10];
            t /= 10;
        }
        if (cnt == max) {
            std::cout << i << "\n";
            return 0;
        }
    }

    return 0;
}

D. 对称排序

思路：

  • 每次遇到 a[l] > a[r] 就互换位置即可

时间复杂度：\(O(N + \frac{N}{2})\)

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
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];
    }
    
    for (int i = 0, j = n - 1; i < j; i++, j--) {
        if (a[i] > a[j]) {
            std::swap(a[i], a[j]);
        }
    }
    
    if (std::is_sorted(a.begin(), a.end())) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
    
    return 0;
}

E. 最大花之能量

思路：

  • 朴素版最大上升子序列和的模板题，还有一个用二分的版本，数据范围较大

时间复杂度：\(O(n^2)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    } 
    
    int res = 0;
    std::vector<int> dp(n + 1);
    for (int i = 1; i <= n; i++) {
        dp[i] = a[i];
        for (int j = 1; j <= i; j++) {
            if (a[j] < a[i]) {
                dp[i] = std::max(dp[i], dp[j] + a[i]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        res = std::max(res, dp[i]);
    }
    std::cout << res << '\n';
    
    return 0;
}

F. 七彩之城的独特序列

题目大意：每次你可以选择一个序列，使得这个序列里的所有元素都是不同的，请你统计总共有多少种这种序列

思路：

  • 利用乘法原理，对于一个元素 a[i]，我们可以选择 cnt[a[i]] + 1 次，这包含了不选它和选它的所有次数的可能性
  • 最后，我们只需要删除空集-1即可

时间复杂度：\(O(10^6)\)

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
constexpr int P = 1E9 + 7;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::map<int, int> cnt;
    for (int i = 1; i <= n; i++) {
        int x;
        std::cin >> x;
        cnt[x]++;
    } 
    
    i64 ans = 1;
    for (int i = 1; i <= 1E6; i++) {
        if (cnt[i]) {
            ans = ans * (cnt[i] + 1) % P;
        }
    }
    std::cout << ans - 1 << "\n";
    
    return 0;
}

G. 基德的密码锁

思路：

时间复杂度：

H. 完美队列的数目

思路：

  • 首先，我们将原始序列排个序，题目要求任意选择人员组成一个集合，集合内的最大和最小元素和小于等于K，那么我们可以思考一下，对于一个区间[l, r]，有多少种选法，可以构造一个以下的区间 n = 3, k = 5, a = [1, 2, 3]:
    • 我们可以选择 [1], [2], [1, 2], [1, 2, 3], [1, 3], [2, 3]
    • 序列中的 [3]不能选，因为 3 + 3 > k
  • 对于一个给定的序列，如果让你任 \(x\) 个数，那么最多有 \(2^n\) 种选法

时间复杂度：\(O(nlogn)\)

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
constexpr int P = 1E9 + 7; 
template <typename T>
T power(T a, T b) {
    T res = 1;
    for (; b; b /= 2) {
        if (b & 1) res = res * a % P;
        a = a * a % P;
    }
    return res % P;
}

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

    int n, k;
    std::cin >> n >> k;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    std::sort(a.begin(), a.end());
    
    i64 ans = 0;
    int l = 0, r = n - 1;
    while (l < r) {
        if (a[l] + a[r] <= k) {
            ans += power(2, r - l) % P;
            ans %= P;
            l++;
        } else {
            r--;
        }
    }
    std::cout << ans << "\n";
        
    return 0;
}

I. GCD王国和LCM王国

思路：

  • 这题题目有问题，样例输出是2
  • 我们定义\(f(i) = gcd(lcm(a_i, a_{i + 1}), lcm(a_i, a_{i + 2}),...,lcm(a_i, a_n))\)，那么最终的答案为：\(gcd(f(1), f(2),...,f(n))\)
  • 如果我们暴力求解每一个 \(f(i)\)，则需要 \(O(nlogn)\) 的时间，总耗费 \(O(n^2logn)\)，这一定会超时，所有我们需要优化
  • 我们可以将原始式子变换为 \(lcm(gcd(a_i, a_{i + 1}), gcd(a_i, a_{i + 2}),...,gcd(a_i, a_n))\)，所以，我们可以直接预处理每一个 \(nxt_i\) 作为 \(gcd\)，最后递推求出 \(ans\)

时间复杂度：\(O(nlogn)\)

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
constexpr int P = 1E9 + 7; 

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::vector<int> a(n + 1), nxt(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    nxt[n] = a[n];
    for (int i = n - 1; i >= 1; i--) {
        nxt[i] = std::__gcd(nxt[i + 1], a[i]);
    }
    
    i64 ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = std::__gcd(ans, 1LL * a[i] * nxt[i] / std::__gcd(a[i], nxt[i]));
    }
    std::cout << ans << "\n";
    
    return 0;
}

J. 星际探险

思路：

  • 这题可以使用prim或者kruskal来求最大生成树，然后输出答案即可

时间复杂度：\(O(n^2)\)

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
constexpr int P = 1E9 + 7, inf = 0x3f3f3f3f;
template <typename T>
T power(T a, T b) {
    T res = 1;
    for (; b; b /= 2) {
        if (b & 1) {
            res = res * a % P;
        }
        a = a * a % P;
    }
    return res % P;
}

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

    int n;
    std::cin >> n;

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

    std::vector<std::vector<i64>> g(510, std::vector<i64>(510, inf));
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            g[i][j] = g[j][i] = std::max(power(a[i], a[j]) % P, power(a[j], a[i]) % P);
        }
    }
    
    std::vector<int> vis(n + 1), dist(n + 1, -inf);
    std::function<int()> prim = [&]() {
        int res = 0;
        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && (t == -1 || dist[t] < dist[j])) {
                    t = j;
                }
            }
            if (i && dist[t] == inf) return inf;

            if (i) res = (res + dist[t]) % P;
            vis[t] = true;

            for (int j = 1; j <= n; j++) dist[j] = std::max(1LL * dist[j], g[t][j]);
        }

        return res % P;
    };

    std::cout << prim() % P << "\n";

    return 0;
}