牛客周赛 Round 31

发表于 更新于 分类于 阅读次数： 本文字数： 620 阅读时长 ≈ 2 分钟
God helps those who help themselves.

A. 小红小紫替换

思路：

  • 按题意模拟即可

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string s;
    std::cin >> s;

    if (s == "kou") {
        std::cout << "yukari\n";
    } else {
        std::cout << s << "\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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    i64 n;
    std::cin >> n;

    int ans = 0;
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            ans++;
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) ans++;
    std::cout << ans << "\n";

    return 0;
}

C. 小红的字符串中值

思路：

  • 每次取最小子段即可

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    char c;
    std::cin >> n >> c;

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

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == c) {
            ans += std::min(i + 1, n - i);
        }
    }
    std::cout << ans << "\n";

    return 0;
}

D. 小红数组操作

思路：

  • 双链表板子题，其实也可以用map做

时间复杂度：

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    int idx = 0;
    std::vector<int> l(n + 1), r(n + 1), e(n + 1);
    r[0] = 1, l[1] = 0;
    idx = 2;
    std::unordered_map<int, int> h;
    for (int i = 0; i < n; i++) {
        int op;
        std::cin >> op;

        int x, y;
        if (op == 1) {
            std::cin >> x >> y;
            auto add = [&](int a, int x) {
                h[x] = idx;
                e[idx] = x;
                l[idx] = a, r[idx] = r[a];
                l[r[a]] = idx, r[a] = idx++;
            };
            if (y == 0) {
                add(0, x);
            } else {
                add(h[y], x);
            }
        } else {
            std::cin >> x;
            auto remove = [&](int x) {
                l[r[x]] = l[x];
                r[l[x]] = r[x];
            };
            remove(h[x]);
        }
    }    

    int ans = 0;
    for (int i = r[0]; i != 1; i = r[i]) {
        ans++;
    }
    std::cout << ans << "\n";
    for (int i = r[0]; i != 1; i = r[i]) {
        std::cout << e[i] << " \n"[i == 1];
    }

    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
constexpr int inf = 0x3f3f3f3f;

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

    const int m = 80010;
    std::vector dp(205, std::vector<int>(80010, inf)); // 前i个元素，使得最终值为j的最小计数
    dp[0][40000] = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        std::cin >> x;
        for (int j = 0; j < m; j++) {
            if (j - x < m && j - x >= 0) dp[i][j] = std::min(dp[i - 1][j - x] + 1, dp[i][j]);
            if (j + x <= m && j + x >= 0) dp[i][j] = std::min(dp[i - 1][j + x], dp[i][j]);
        }
    }

    if (dp[n][40000] > n) {
        std::cout << "-1\n";
    } else {
        std::cout << dp[n][40000] << "\n";
    }

    return 0;
}