感觉这场比较简单？不过自己还是挺sd的，巨慢，rk1直接16分钟就ak了，而我整了2小时活。。。

Allocation

有$N$个房子，每个房子都有自己的价格$A_i$，现在手上有$B$，问最多能买房子的数量。

只要排序后贪心从小买到大就可以了，$O(n\log n)$，C++语法题。

Allocation.cpp
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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int a[N];

int main() {
    int t;
    cin >> t;
    for (int T = 1; T <= t; ++T) {
        int n, b;
        cin >> n >> b;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        sort(a, a + n, less<>());
        int ans = 0;
        for (int i = 0; i < n && b >= a[i]; ++i) {
            ++ans;
            b -= a[i];
        }
        printf("Case #%d: %d\n", T, ans);
    }
    return 0;
}

Plates

有$N$堆盘子，每堆有&K&个，每个盘子有权值。现在需要从中选择$P$个盘子，每堆盘子都必须像栈一样从顶开始取，问取$P$个可以获得的最大权值和是多少。

我写了个暴力DP，预处理$sum[i][j]$表示第$i$堆取前$j$个盘子的前缀和。枚举每一堆中取$j$个，那么位于第$i$堆，已经拿到了$l$个盘子的最优答案：$$dp[i][l] = \max_{j=0}^{max(l,k)}(dp[i-1][l-j] + sum[i][j])$$$O(Tnkp)$

Plates.cpp
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
#include <bits/stdc++.h>
using namespace std;

int a[55][35];

int main() {
    int t;
    cin >> t;
    for (int T = 1; T <= t; ++T) {
        int n, k, p;
        cin >> n >> k >> p;

        vector<vector<int>> dp(n + 1, vector<int> (n * k + 1));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                cin >> a[i][j];
                a[i][j] += a[i][j - 1];
            }
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                for (int l = j; l <= p; ++l) {
                    dp[i][l] = max(dp[i][l], dp[i - 1][l - j] + a[i][j]);
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans = max(ans, dp[i][p]);
        }
        printf("Case #%d: %d\n", T, ans);
    }
    return 0;
}

Workout

一个$N$个数的严格递增数列，分成了$N-1$段，现在可以至多添加$K$个数，问最后形成的严格递增序列的差值中的最大值可以被最小化到多少。

正解二分，$O(Tn\log n)$。被自己一开始的假思路骗到了，罚时++。

Workout.cpp
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
#include <bits/stdc++.h>
using namespace std;

vector<int> seg;

int check(int x) {
    int ret = 0;
    for (int i = seg.size() - 1; i >= 0 && seg[i] > x; --i) {
        ret += (seg[i] - 1) / x;
    }
    return ret;
}

int main() {
    int t;
    cin >> t;
    for (int T = 1; T <= t; ++T) {
        int n, k;
        cin >> n >> k;

        seg.clear();
        int la;
        cin >> la;
        for (int i = 1, p; i < n; ++i) {
            cin >> p;
            seg.emplace_back(p - la);
            la = p;
        }
        sort(seg.begin(), seg.end(), [](int x, int y) { return x < y;});

        int l = 1, r = 1e9, ans, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (check(mid) <= k) {
                ans = mid;
                r = mid - 1;
            } else
                l = mid + 1;
        }
        printf("Case #%d: %d\n", T, ans);
    }
    return 0;
}

Bundling

有$N$个仅含大写字母的字符串，现在要分成$N/K$组，每组的权值是组内最长公共前缀$LCP$的长度，问可以达到最大的权值和是多少。

字典树，$cnt[x]$是$x$被经过的次数，也代表了从根到$x$的前缀出现的次数，每当前缀出现次数$≥k$，就可以分成$cnt[x]/k$组，那么这个前缀对答案贡献$cnt[x]/k$，$O(\sum_T \sum_i len(s_i))$。

Bundling.cpp
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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;

namespace String {
    const int csize = 26;
    int ans, k;

    class trie {
        int ch[N][csize];
        int cnt[N];
        int numv;

    public:
        void init() {
            while (numv) {
                memset(ch[numv], 0, sizeof(ch[numv]));
                cnt[numv] = 0;
                --numv;
            }
            memset(ch[numv], 0, sizeof(ch[numv]));
            cnt[numv] = 0;
        }

        void insert(string &s) {
            int u = 0;
            for (char &c : s) {
                if (!ch[u][c - 'A'])
                    ch[u][c - 'A'] = ++numv;
                u = ch[u][c - 'A'];
                ++cnt[u];
            }
        }

        int count() {
            int ret = 0;
            for (int i = 1; i <= numv; ++i) {
                ret += cnt[i] / k;
            }
            return ret;
        }
    };
}
using namespace String;

trie tree;

int main() {
    int t;
    cin >> t;
    for (int T = 1; T <= t; ++T) {
        int n;
        string s;
        cin >> n >> k;
        tree.init();
        for (int i = 0; i < n; ++i) {
            cin >> s;
            tree.insert(s);
        }

        printf("Case #%d: %d\n", T, tree.count());
    }
    return 0;
}