2019牛客暑期多校训练营（第六场）

本文最后更新于：星期四, 二月 3日 2022, 9:15 晚上

A. Garbage Classification

签到

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

#include <bits/stdc++.h>
using namespace std;

#define N 2010
char s[N], t[N], mp[N];

int main() {
    int T; scanf("%d", &T);
    for (int kase = 1; kase <= T; ++kase) {
        printf("Case #%d: ", kase);
        scanf("%s%s", s + 1, t);
        for (int i = 0; i < 26; ++i) {
            mp['a' + i] = t[i];
        }
        int d = 0, w = 0, h = 0;
        int len = strlen(s + 1);
        for (int i = 1; i <= len; ++i) {
            int c = mp[s[i]];
            if (c == 'w') ++w;
            else if (c == 'd') ++d;
            else ++h;
        }
        if (h * 4 >= len) {
            puts("Harmful");
        } else if (h * 10 <= len) {
            puts("Recyclable");
        } else if (d >= w * 2) {
            puts("Dry");
        } else {
            puts("Wet");
        }
    }
    return 0;
}

B. Shorten IPv6 Address

模拟

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

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 1010
char s[N];
int a[8];
vector <string> res;

string f(int x) {
    string res = "";
    if (!x) return "0";
    while (x) {
        int y = x % 16;
        if (y < 10) res += y + '0';
        else if (y == 10) res += 'a';
        else if (y == 11) res += 'b';
        else if (y == 12) res += 'c';
        else if (y == 13) res += 'd';
        else if (y == 14) res += 'e';
        else res += 'f';
        x /= 16;
    }  
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    for (int kase = 1; kase <= T; ++kase) {
        cout << "Case #" << kase << ": ";
        cin >> (s + 1);
        int len = 128;
        for (int i = 1; i <= len; i += 16) {
            int num = 0;
            for (int j = i; j < i + 16; ++j) {
                num = num * 2 + s[j] - '0';
            }
            a[i / 16] = num;
        }      
        res.clear();
        string str = f(a[0]);
        for (int i = 1; i < 8; ++i) {
            str += ":";
            str += f(a[i]);
        }
        res.push_back(str);
        string tmp = "";
        for (int i = 0; i < 8; ++i) {
            string now = tmp;
            now += ":";
            int j = i;
            for (; j < 8; ++j) {
                if (a[j])
                    break;
            }
            for (int k = j; k < 8; ++k) {
                now += ":";
                now += f(a[k]);
            }
            if (j >= 8) now += ":";
            if (j > i + 1) res.push_back(now);
            if (i) tmp += ":";
            tmp += f(a[i]);
        }
        sort(res.begin(), res.end(), [](string x, string y){
            if (x.length() != y.length())
                return x.length() < y.length();
            return x < y;       
        });
        cout << res[0] << "\n";
    }
    return 0;
}

C. Palindrome Mouse

题意：询问有多少对不同的(a,b)(a,b)满足a,ba,b都是回文串且aa是bb的子串

思路：回文树

1

D. Move

题意：有nn个物品，每个物品体积为ViV_i，有KK个体积相同的盒子，要求满足规则下的盒子体积最大值

  • 一个盒子装不下了才能装另一个
  • 每次选取能装进去的最大的物品，直到装不下

思路：枚举

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

#include <bits/stdc++.h>
using namespace std;

#define N 1010
#define INF 0x3f3f3f3f
int n, k, a[N];

int check(int x) {
    int sum = 0;
    int box = 0;
    multiset <int> se;
    for (int i = 1; i <= n; ++i) {
        se.insert(a[i]);
        sum += a[i];
    }
    for (int i = 1; i <= k; ++i) {
        int remind = x;
        while (!se.empty()) {
            auto pos = se.upper_bound(remind);
            if (pos != se.begin()) {
                --pos;
                remind -= (*pos);
                sum -= (*pos);
                se.erase(pos);
            } else {
                break;
            }
        }
        box += remind;
        if (se.empty()) return -INF;
    }
    return sum - box;
}

int main() {
    int T; scanf("%d", &T);
    for (int kase = 1; kase <= T; ++kase) {
        printf("Case #%d: ", kase);
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; ++i) scanf("%d", a + i);
        for (int i = 1; ; ) {
            int x = check(i);
            if (x == -INF) {
                printf("%d\n", i);
                break;
            } else {
                i += max(1, x / k + (x % k != 0));
            }
        }
    }
    return 0;
}

E. Androgynos

题意：构造nn阶自补图，如果没有则输出NONO，否则输出邻接矩阵

思路：

  • nn阶自补图存在当且仅当$n=4\cdot k 或者或者n=4\cdot k+1$
  • 对于一个长度为四的的自补图，可以通过构造一条链X−Y−Z−WX-Y-Z-W，他的补图为Y−W−X−ZY-W-X-Z
  • 考虑两个自补图合并，只需要X,WX,W与其余点相连，就可以形成新的自补图
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

#include <bits/stdc++.h>

using namespace std;

#define N 2010

int n;
int G[N][N];
int ans[N];

int main() {
//    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        printf("Case #%d: ", cas);
        scanf("%d", &n);
        if (n % 4 == 2 || n % 4 == 3) {
            puts("No");
            continue;
        }
        memset(G, 0, sizeof G);
        puts("Yes");
        if (n % 4 == 0) {
            for (int i = 1; i <= n; i += 4) {
                int x = i, y = i + 1, z = i + 2, w = i + 3;
                ans[x] = y;
                ans[y] = w;
                ans[z] = x;
                ans[w] = z;
                G[x][y] = G[y][x] = 1;
                G[y][z] = G[z][y] = 1;
                G[z][w] = G[w][z] = 1;
                for (int j = 1; j < i; ++j) {
                    G[x][j] = G[j][x] = 1;
                    G[w][j] = G[j][w] = 1;
                }
            }
        } else if (n % 4 == 1) {
            ans[1] = 1;
            for (int i = 2; i <= n; i += 4) {
                int x = i, y = i + 1, z = i + 2, w = i + 3;
                ans[x] = y;
                ans[y] = w;
                ans[z] = x;
                ans[w] = z;
                G[x][y] = G[y][x] = 1;
                G[y][z] = G[z][y] = 1;
                G[z][w] = G[w][z] = 1;
                for (int j = 1; j < i; ++j) {
                    G[x][j] = G[j][x] = 1;
                    G[w][j] = G[j][w] = 1;
                }
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                printf("%d", G[i][j]);
            }
            puts("");
        }
        for (int i = 1; i <= n; ++i) {
            printf("%d%c", ans[i], " \n"[i == n]);
        }
    }
    return 0;
}

G. Is Today Friday?

题意：用字母代替数字，输出最小的方案，要求每个日期都合法且每个日期都是周五

思路：暴力

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

#include <bits/stdc++.h>

#include <random>

using namespace std;

#define N 100010

int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeap(int year) {
    return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
}


int n;
string s[N];
int a[10];

int getDay(int year, int month) {
    if (month == 2) {
        return days[2] + isLeap(year);
    } else {
        return days[month];
    }
}

int week(int y, int m, int d) {
    int ans;
    if (m == 1 || m == 2) m += 12, y--;
    if ((y < 1752) || (y == 1752 && m < 9) || (y == 1752 && m == 9 && d < 3)) {
        ans = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 + 5) % 7;
    } else {
        ans = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7;
    }
    ans = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7;
    return ans + 1;
}

bool check(int idx) {
    int y = 0, m = 0, d = 0;
    for (int i = 0; i < 4; i++) y = y * 10 + a[s[idx][i] - 'A'];
    for (int i = 5; i < 7; i++) m = m * 10 + a[s[idx][i] - 'A'];
    for (int i = 8; i < 10; i++) d = d * 10 + a[s[idx][i] - 'A'];
    if (y < 1600) return false;
    if (m < 1 || m > 12) return false;
    if (d < 1 || d > getDay(y, m)) return false;
    return week(y, m, d) == 5;
}


void solve() {
    sort(s + 1, s + 1 + n);
    n = unique(s + 1, s + 1 + n) - s - 1;
    shuffle(s + 1, s + 1 + n, std::mt19937(std::random_device()()));
    for (int i = 0; i < 10; ++i) {
        a[i] = i;
    }
    do {
        bool flag = true;
        for (int i = 1; i <= n; ++i) {
            if (!check(i)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            for (int i : a) {
                cout << i;
            }
            cout << "\n";
            return;
        }
    } while (next_permutation(a, a + 10));
    cout << "Impossible\n";
}

int main() {
//    freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    for (int cas = 1; cas <= T; ++cas) {
        cout << "Case #" << cas << ": ";
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> s[i];
        }
        solve();
    }
    return 0;
}

J. Upgrading Technology

题意：有nn个技能，mm个等级，每个技能从j−1j-1升级到jj需要消耗CijC_{ij}，如果所有技能到达了jj，则可以获得djd_j，求最大收益：

思路：求前缀和的后缀最大值，枚举ii作为最低等级jj的值，取MAXMAX

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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 1010
#define INFLL 0x3f3f3f3f3f3f3f3f

int n, m;
ll a[N][N], b[N];
ll f[N][N], g[N], f2[N][N];

int main() {
//    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        printf("Case #%d: ", cas);
        scanf("%d %d", &n, &m);
        memset(f, 0, sizeof f);
        memset(f2, 0, sizeof f2);
        memset(g, 0, sizeof g);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                scanf("%lld", &a[i][j]);
            }
        }
        for (int i = 1; i <= m; ++i) {
            scanf("%lld", b + i);
            g[i] = g[i - 1] + b[i];
        }
        ll ans = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                f[i][j] = f[i][j - 1] - a[i][j];
                f2[i][j] = f2[i][j - 1] - a[i][j];
            }
            for (int j = m; j >= 0; --j) {
                if (j + 1 <= m) {
                    f[i][j] = max(f[i][j], f[i][j + 1]);
                }
            }
        }
        for (int j = m; j >= 0; --j) {
            ll tmp = 0;
            for (int i = 1; i <= n; ++i) {
                tmp += f[i][j];
            }
            for (int i = 1; i <= n; ++i) {
                ans = max(ans, tmp - f[i][j] + f2[i][j] + g[j]);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}