Fork me on GitHub

Codeforces Round #734 (Div. 3)

字数统计: 1.7k字   |   阅读时长≈ 9分

比赛链接

https://codeforces.com/contest/1551

1. A. Polycarp and Coins

1.1. 题意

给你一个数n，你要把他拆为$c_1+2c_2$的形式，你需要最小化$c_1$和$c_2$的差

1.2. 做法

对模3的余数进行分类讨论

1.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
#include <bits/stdc++.h>

using namespace std;


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

    int step;
    cin >> step;
    while (step--) {
        int n;
        cin >> n;
        if (n % 3 == 0) {
            cout << n / 3 << " " << n / 3 << endl;
        } else if (n % 3 == 1) {
            cout << n / 3 + 1 << " " << n / 3 << endl;
        } else {
            cout << n / 3 << " " << n / 3 + 1 << endl;
        }
    }
}
 

2. B2. Wonderful Coloring - 2

2.1. 题意

给你一个长度为n的序列，你要用k种颜色给序列的每个元素染色，

  1. each element of the sequence is either painted in one of k colors or isn’t painted;
  2. each two elements which are painted in the same color are different (i. e. there’s no two equal values painted in the same color);
  3. let’s calculate for each of k colors the number of elements painted in the color — all calculated numbers must be equal;
  4. the total number of painted elements of the sequence is the maximum among all colorings of the sequence which meet the first three conditions.

你要最大化被染色的元素的个数

2.2. 做法

贪心染色，先把元素按照值分类，每个类中如果有超过k个颜色，则直接丢弃，最后把这些元素放到一起构成集合$S$，继续丢弃一些元素,直到$|s|$是k的倍数

2.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
41
#include <bits/stdc++.h>

using namespace std;

inline int read() {
    int x;
    cin >> x;
    return x;
}


int main() {

    int step = read();
    while (step--) {
        int n = read();
        int k = read();
        vector<int> a(n);
        vector<int> pos;
        vector<int> vis(n + 1);
        for (int i = 0; i < n; i++) {
            a[i] = read();
            if (vis[a[i]] < k) {
                pos.push_back(i);
            }
            vis[a[i]]++;
        }
        sort(pos.begin(), pos.end(), [&a](int x, int y) { return a[x] < a[y]; });
        vector<int> ans(n, 0);
        while (pos.size() % k != 0) pos.pop_back();
        for (int i = 0; i < pos.size(); i++) {
            ans[pos[i]] = i % k + 1;
        }
        for (int i = 0; i < n; i++) {
            printf("%d ", ans[i]);
        }
        printf("\n");
    }
}


3. C. Interesting Story

3.1. 题意

A story is called interesting if there exists a letter which occurs among all words of the story more times than all other letters together.

如果一个字符串中，有一个字符出现的次数，币其他字符出现的次数之和还要大，则这个字符串为有趣。

You are given a sequence of n words consisting of letters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’. Your task is to choose the maximum number of them to make an interesting story. If there’s no way to make a non-empty story, output 0.

给你一些字符串，你要从中选择最多的字符串，这些字符串拼在一起之后是一个有趣的字符串、

字符串只由abcde五种字符构成

3.2. 做法

对每种字符分别判断，假设现在在处理a，每个字符串中a出现的次数为$a_i$其他字符出现的次数为$x_i$,然后对字符串按照$a_i-x_i$排序，贪心选择前几项即可

3.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
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>

using namespace std;

int solve(const vector<vector<int>> &a, int pos) {
    vector<int> t(a.size());
    for (int i = 0; i < a.size(); i++) {
        t[i] = i;
    }
    sort(t.begin(), t.end(), [&a, pos](int x, int y) {
        return 2 * a[x][pos] - a[x][5] > 2 * a[y][pos] - a[y][5];
    });

    int ans = 0;
    int cnt = 0;
    int all = 0;
    for (int i = 0; i < a.size(); i++) {
        cnt += a[t[i]][pos];
        all += a[t[i]][5];
        //cout << "i " << i << " cnt " << cnt << " all " << all << endl;
        if (cnt > all - cnt) {
            ans = i + 1;
        }
    }
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    int step;
    cin >> step;
    while (step--) {
        int n;
        cin >> n;
        vector<vector<int>> a(n, vector<int>(6));
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            for (char ch:s) {
                a[i][ch - 'a']++;
                a[i][5]++;
            }
        }
        cout << max({solve(a, 0), solve(a, 1), solve(a, 2), solve(a, 3), solve(a, 4)}) << endl;
    }
}



4. D2. Domino (hard version)

4.1. 题意

sb题目没营养，不展开了

4.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
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
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>

using namespace std;


int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    int step;
    cin >> step;
    while (step--) {
        int n, m, k;
        cin >> n >> m >> k;

        vector<string> ans(n, string(m, ' '));
        if (n % 2 == 0 && m % 2 == 0) {
            if (k % 2 == 0) {
                puts("YES");
                for (int i = 0; i < n; i += 2) {
                    for (int j = 0; j < m; j += 2) {
                        if (k) {
                            k -= 2;
                            ans[i][j] = (j & 2) ? 'a' : 'c';
                            ans[i][j + 1] = (j & 2) ? 'a' : 'c';
                            ans[i + 1][j] = (j & 2) ? 'b' : 'd';
                            ans[i + 1][j + 1] = (j & 2) ? 'b' : 'd';
                        } else {
                            ans[i][j] = (i & 2) ? 'e' : 'g';
                            ans[i + 1][j] = (i & 2) ? 'e' : 'g';
                            ans[i][j + 1] = (i & 2) ? 'f' : 'h';
                            ans[i + 1][j + 1] = (i & 2) ? 'f' : 'h';
                        }
                    }
                }
                for (int i = 0; i < n; i++) {
                    cout << ans[i] << endl;
                }
            } else {
                puts("NO");
            }
        } else if (n % 2 == 0 && m % 2 == 1) {
            if (k * 2 <= n * (m - 1) && k % 2 == 0) {
                puts("YES");
                for (int i = 0; i < n; i += 2) {
                    for (int j = 0; j < m - 1; j += 2) {
                        if (k) {
                            k -= 2;
                            ans[i][j] = (j & 2) ? 'a' : 'c';
                            ans[i][j + 1] = (j & 2) ? 'a' : 'c';
                            ans[i + 1][j] = (j & 2) ? 'b' : 'd';
                            ans[i + 1][j + 1] = (j & 2) ? 'b' : 'd';
                        } else {
                            ans[i][j] = (i & 2) ? 'e' : 'g';
                            ans[i + 1][j] = (i & 2) ? 'e' : 'g';
                            ans[i][j + 1] = (i & 2) ? 'f' : 'h';
                            ans[i + 1][j + 1] = (i & 2) ? 'f' : 'h';
                        }
                    }
                }
                for (int i = 0; i < n; i += 2) {
                    ans[i][m - 1] = (i & 2) ? 'z' : 'x';
                    ans[i + 1][m - 1] = (i & 2) ? 'z' : 'x';
                }
                for (int i = 0; i < n; i++) {
                    cout << ans[i] << endl;
                }
            } else {
                puts("NO");
            }
        } else { // n%2==1 && m%2==0
            k -= m / 2;
            if (k >= 0 && k % 2 == 0) {
                puts("YES");
                for (int i = 0; i < n - 1; i += 2) {
                    for (int j = 0; j < m; j += 2) {
                        if (k) {
                            k -= 2;
                            ans[i][j] = (j & 2) ? 'a' : 'c';
                            ans[i][j + 1] = (j & 2) ? 'a' : 'c';
                            ans[i + 1][j] = (j & 2) ? 'b' : 'd';
                            ans[i + 1][j + 1] = (j & 2) ? 'b' : 'd';
                        } else {
                            ans[i][j] = (i & 2) ? 'e' : 'g';
                            ans[i + 1][j] = (i & 2) ? 'e' : 'g';
                            ans[i][j + 1] = (i & 2) ? 'f' : 'h';
                            ans[i + 1][j + 1] = (i & 2) ? 'f' : 'h';
                        }
                    }
                }
                for (int j = 0; j < m; j += 2) {
                    ans[n - 1][j] = (j & 2) ? 'z' : 'x';
                    ans[n - 1][j + 1] = (j & 2) ? 'z' : 'x';
                }
                for (int i = 0; i < n; i++) {
                    cout << ans[i] << endl;
                }
            } else {
                puts("NO");
            }
        }
    }
}



赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
Java后端开发、聚合支付、
公众号开发、开源爱好者、Linux

联系QQ:2434387555

很惭愧

只做了一点微小的工作
谢谢大家