Codeforces Round 640 (Div. 4)

发表于 分类于 阅读次数： 本文字数： 1k 阅读时长 ≈ 4 分钟
If you can dream it, you can do it.

A. Sum of Round Numbers

思路：

  • 把输入的数拆分为单个整体，例如，5031 => 5000 30 1，就按照这个思路拆分数位即可

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
    int n;
    std::cin >> n;

    int base = 1;
    std::vector<int> ans;
    while (n) {
        if (n % 10 != 0) {
        	ans.push_back(n % 10 * base);
        }
        base *= 10;
        n /= 10;
    }
    
    std::cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++) {
        std::cout << ans[i] << " \n"[i == ans.size() - 1];
    }
}

B. Same Parity Summands

思路：

  • 所有数要求是正整数，直接用最小的奇数1和最小的偶数2，然后判断这两种情况中的任意一种是否存在即可

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve() {
    int n, k;
    std::cin >> n >> k;

    int a = k - 1;
    int b = (k - 1) * 2;
    if ((n - a) % 2 == 1 && n - a > 0) {
        std::cout << "YES\n";
        for (int i = 0; i + 1 < k; i++) {
            std::cout << "1 ";
        }
        std::cout << n - a << "\n";
    } else if ((n - b) % 2 == 0 && n - b > 0) {
        std::cout << "YES\n";
        for (int i = 0; i + 1 < k; i++) {
            std::cout << "2 ";
        }
        std::cout << n - b << "\n";
    } else {
        std::cout << "NO\n";
    }
}

C. K-th Not Divisible by n

思路：

  • 对于一个数x，小于等于x的正整数，且不能被x整除的数，有x - 1个，那么第k个不能被x整除的数的位置即为k / (n - 1) * n + (k == 0 ? -1 : k)

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

1
2
3
4
5
6
7
8
9
void solve() {
    int n, k;
    std::cin >> n >> k;

    int t = k / (n - 1);
    k -= (t * (n - 1));

    std::cout << 1LL * t * n + (k == 0 ? -1 : k) << "\n";
}

D. Alice, Bob and Candies

思路：

  • 按照题目意思模拟即可，双向开始互相吃糖果

时间复杂度：\(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
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
void solve() {
    int n;
    std::cin >> n;

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

    int l = 0, r = n - 1;
    int a = 0, b = 0, step = 0;
    std::vector<int> vis(n);
    int nowa = 0, nowb = 0;
    int lsta = 0, lstb = 0;
    while (l <= r) {
        while (l <= r) {
            if (!vis[l]) {
                nowa += caddy[l];
                a += caddy[l];
                vis[l] = true;
                l++;
                if (l > r) {
                    step++;
                    break;
                }
                if (nowa > lstb) {
                    lsta = nowa;
                    nowa = 0;
                    step++;
                    break;
                }
            } else {
                break;
            }
        }
        while (l <= r) {
            if (!vis[r]) {
                nowb += caddy[r];
                b += caddy[r];
                vis[r] = true;
                r--;
                if (l > r) {
                    step++;
                    break;
                }
                if (nowb > lsta) {
                    lstb = nowb;
                    nowb = 0;
                    step++;
                    break;
                }
            } else {
                break;
            }
        }
    }
    std::cout << step << " " << a << " " << b << "\n";
}

E. Special Elements

思路：

  • n为8000，可以暴力求解，我们只需要枚举左右端点，然后用hash表来 \(O(1)\) 的查询这个区间和是否等于数组中的任意一个数即可

时间复杂度：\(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
void solve() {
    int n;
    std::cin >> n;

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

    std::vector<int> s(n + 1);
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }
    
    int res = 0;
    std::unordered_set<int> ans;
    for (int l = 1; l <= n; l++) {
        for (int r = l + 1; r <= n; r++) {
            int sum = s[r] - s[l - 1];
            if (mp.count(sum) && r - l >= 1) {
                if (!ans.count(sum)) {
                    res += mp[sum];
                    ans.insert(sum);
                }
            }
        }
    }
    std::cout << res << "\n";
}

F. Binary String Reconstruction

思路：

  • 首先，我们观察n1的值，如果n1为0，那么n0和n2一定有一个也是0，这种情况直接特判即可
  • 然后我们根据n1的值，来创建一个满足条件的01序列，然后我们在把n0和n2的全0或全1的序列加在任意一个0或1的旁边，这样不会改变n1和n0以及n2的数量

时间复杂度：\(O(max(n_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
42
43
44
45
46
void solve() {
    int n0, n1, n2;
    std::cin >> n0 >> n1 >> n2;

    if (n1 == 0) {
        if (n0 == 0) {
            n2++;
            for (int i = 0; i < n2; i++) {
                std::cout << 1;
            }
        } else if (n2 == 0) {
            n0++;
            for (int i = 0; i < n0; i++) {
                std::cout << 0;
            }
        }
        std::cout << "\n";
        return ;
    }

    int cnt = 0;
    std::string ans = "";
    for (int i = 0; cnt < n1; i++) {
        if (i % 2 == 0) {
            ans += '0';
        } else {
            ans += '1';
        }
        if (i >= 1) {
            cnt++;
        }
    }
    std::string a = "", b = a;
    while (n0) {
        a += '0';
        n0--;
    }
    while (n2) {
        b += '1';
        n2--;
    }

    ans.insert(1, b);
    ans = a + ans;
    std::cout << ans << "\n";
}

G. Special Permutation

思路：

  • 按照题目意思，找到一个序列满足 \(2 \le |a_i - a_{i - 1}| \le 4\) ，我们推一下满足条件的序列，可以猜到从大到小一半，然后从小到大再回去，按照奇偶性的不同

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
    int n;
    std::cin >> n;

    if (n < 4) {
        std::cout << "-1\n";
    } else {
        int t = n;
        if (n % 2 == 0) t = n - 1;
        for (int i = t; i >= 1; i -= 2) {
            std::cout << i << " ";
        }
        std::cout << 4 << " " << 2 << " ";
        for (int i = 6; i <= n; i += 2) {
            std::cout << i << " ";
        }
        std::cout << "\n";
    }
}