Summary

今年KS的改革包括题目数量从三题变成四题，大数据集的结果可以直接即时返回。由于题目数量的增加，第一二题的难度有所降低，第三第四题还是具有一定难度的。不过也有可能由于是A轮，题目会出的简单一些，也是我第七次参加KS中唯一一次AC，不过排名也是七次中最低的一次。

Allocation

Problem

There are N houses for sale. The i-th house costs Ai dollars to buy. You have a budget of B dollars to spend.

What is the maximum number of houses you can buy?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a single line containing the two integers N and B. The second line contains N integers. The i-th integer is Ai, the cost of the i-th house.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of houses you can buy.

Limits

Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ B ≤ 105.
1 ≤ Ai ≤ 1000, for all i.

Test set 1

1 ≤ N ≤ 100.

Test set 2

1 ≤ N ≤ 105.

Sample

Input
3
4 100
20 90 40 90
4 50
30 30 10 10
3 300
999 999 999
Output
Case #1: 2
Case #2: 3
Case #3: 0

In Sample Case #1, you have a budget of 100 dollars. You can buy the 1st and 3rd houses for 20 + 40 = 60 dollars.
In Sample Case #2, you have a budget of 50 dollars. You can buy the 1st, 3rd and 4th houses for 30 + 10 + 10 = 50 dollars.
In Sample Case #3, you have a budget of 300 dollars. You cannot buy any houses (so the answer is 0).

Note: Unlike previous editions, in Kick Start 2020, all test sets are visible verdict test sets, meaning you receive instant feedback upon submission.

题意：一共有N套房子正在出售，第i个房子的售价是A_i，我们的总预算是B，请问我们最多能买多少个房子。

题解：这题按照以往的难度思维惯性，我一度以为是个背包问题，但是计算了时间复杂度后发现不可行。仔细一看其实就是一个简单的贪心问题，每次尽可能的选取售价最低的房子即可。时间复杂度$O(NlogN)$

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;

int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        int A[N],n,m;
        scanf("%d %d",&n,&m);
        for(int i = 0 ; i < n ; i ++)
            scanf("%d",&A[i]);
        sort(A,A + n);
        int i = 0,cur = 0;
        for(i = 0 ; i < n ; i ++){
            cur += A[i];
            if(cur > m)
                break;
        }

        printf("Case #%d: %d\n",t,i);
    }
    return 0;
}

如果我们可以观察到房屋的售价不超过1000，那么计数排序可以略微加快运行速度。时间复杂度$O(N) $

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;
int A[N];
int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        int n,m,x;
        memset(A,0,sizeof(A));
        scanf("%d %d",&n,&m);
        for(int i = 0 ; i < n ; i ++){
            scanf("%d",&x);
            A[x] ++;
        }
        int res = 0;
        for(int i = 1 ; m > 0 && i <= 1000 ; i ++){
            int cur = min(m / i, A[i]);
            res += cur;
            m -= cur * i;
        }

        printf("Case #%d: %d\n",t,res);
    }
    return 0;
}

Plates

Dr. Patel has N stacks of plates. Each stack contains K plates. Each plate has a positive beauty value, describing how beautiful it looks.

Dr. Patel would like to take exactly P plates to use for dinner tonight. If he would like to take a plate in a stack, he must also take all of the plates above it in that stack as well.

Help Dr. Patel pick the P plates that would maximize the total sum of beauty values.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the three integers N, K and P. Then, N lines follow. The i-th line contains K integers, describing the beauty values of each stack of plates from top to bottom.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum total sum of beauty values that Dr. Patel could pick.

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ K ≤ 30.
1 ≤ P ≤ N * K.
The beauty values are between 1 and 100, inclusive.

Test set 1

1 ≤ N ≤ 3.

Test set 2

1 ≤ N ≤ 50.

Sample

Input
2
2 4 5
10 10 100 30
80 50 10 50
3 2 3
80 80
15 50
20 10

Output
Case #1: 250
Case #2: 180

In Sample Case #1, Dr. Patel needs to pick P = 5 plates:

• He can pick the top 3 plates from the first stack (10 + 10 + 100 = 120).
• He can pick the top 2 plates from the second stack (80 + 50 = 130) .

In total, the sum of beauty values is 250.

In Sample Case #2, Dr. Patel needs to pick P = 3 plates:

• He can pick the top 2 plates from the first stack (80 + 80 = 160).
• He can pick no plates from the second stack.
• He can pick the top plate from the third stack (20).

In total, the sum of beauty values is 180.

题意：帕特尔有N堆盘子，每一堆盘子包括K个盘子，每个盘子有一个正的美丽值来形容这个杯子有多么的好看。现在帕特尔想取出其中恰好P个盘子在今天的晚餐中使用。如果他决定拿出堆中某一个盘子，他必须同时把在这一堆中在该盘子上面的所有盘子也取走。请帮助帕特尔先生求出P个盘子的美丽值的最大和。

题解：这一题看起来就是一个比较经典的背包问题了。

状态表示：dp[i][j]代表从前i堆盘子中总共取出j个盘子能够获得的最大美丽值。

状态初始化：全部初始化为0即可。

状态转移：dp[i][j] = max(temp[k] + dp[i - 1][j - k])。其中k代表第i堆盘子取出k个盘子，那么前i - 1堆只需要取出j - k个盘子即可。注意到这里k的取值范围是[0,min(j,K)],因为每一堆最多只有K个盘子，前面堆至少需要0个盘子，遍历所有可能的k，求最大值即可。

答案表示：dp[N][P]。

时间复杂度:$O(NPK)$。

#include<stdio.h>
#include<cstring>
#include<iostream>

using namespace std;

int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        int N,K,P;
        scanf("%d %d %d",&N,&K,&P);
        int dp[N + 1][P + 1];
        memset(dp,0,sizeof(dp));
        for(int i = 1 ; i <= N ; i ++){
            int temp[K + 1];
            memset(temp,0,sizeof(temp));
            for(int j = 1 ; j <= K ; j ++)
                scanf("%d ",&temp[j]);
            for(int j = 1 ; j <= K ; j ++)
                temp[j] = temp[j] + temp[j - 1];
            for(int j = 1 ; j <= P ; j ++){
                for(int k = 0 ; k <= min(j,K) ; k ++){
                    dp[i][j] = max(dp[i][j],temp[k] + dp[i - 1][j - k]);
                }
            }
        }
        printf("Case #%d: %d\n",t,dp[N][P]);
    }
    return 0;
}

Workout

Tambourine has prepared a fitness program so that she can become more fit! The program is made of N sessions. During the i-th session, Tambourine will exercise for Mi minutes. The number of minutes she exercises in each session are strictly increasing.

The difficulty of her fitness program is equal to the maximum difference in the number of minutes between any two consecutive training sessions.

To make her program less difficult, Tambourine has decided to add up to K additional training sessions to her fitness program. She can add these sessions anywhere in her fitness program, and exercise any positive integer number of minutes in each of them. After the additional training session are added, the number of minutes she exercises in each session must still be strictly increasing. What is the minimum difficulty possible?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and K. The second line contains N integers, the i-th of these is Mi, the number of minutes she will exercise in the i-th session.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum difficulty possible after up to K additional training sessions are added.

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
For at most 10 test cases, 2 ≤ N ≤ 105.
For all other test cases, 2 ≤ N ≤ 300.
1 ≤ Mi ≤ 109.
Mi < Mi+1 for all i.

Test set 1

K = 1.

Test set 2

1 ≤ K ≤ 105.

Samples

Input 1
1
3 1
100 200 230

Output 1
Case #1: 50

Input2
3
5 2
10 13 15 16 17
5 6
9 10 20 26 30
8 3
1 2 3 4 5 6 7 10

Output2
Case #1: 2
Case #2: 3
Case #3: 1

Sample #1

In Case #1: Tambourine can add up to one session. The added sessions are marked in bold: 100 150 200 230. The difficulty is now 50.

Sample #2

In Case #1: Tambourine can add up to six sessions. The added sessions are marked in bold: 9 10 12 14 16 18 20 23 26 29 30. The difficulty is now 3.

In Case #2: Tambourine can add up to three sessions. The added sessions are marked in bold: 1 2 3 4 5 6 7 8 9 10. The difficulty is now 1. Note that Tambourine only added two sessions.

Note #1: Only Sample #1 is a valid input for Test set 1. Consequently, Sample #1 will be used as a sample test set for your submissions.

Note #2: Unlike previous editions, in Kick Start 2020, all test sets are visible verdict test sets, meaning you receive instant feedback upon submission.

题意：我们准备了一个健身计划来让自己变得更加健康，这个计划由N个课程组成，在第i个课程当中，我们将会锻炼M_i分钟，在这个健身计划中，每个课程的持续时长是严格递增的。我们健身计划的难度等于任意相邻两个训练课程时间长度的最大差值。为了让我们的计划变得容易一些，我们决定额外增加K个课程。我们可以在任意两个课程之间加入一个或者多个任意时间长度的课程。唯一的要求是，增加完之后，我们每个课程的持续时长仍然是严格递增的。那么在添加了K个课程之后，最小难度是多少呢。

题解1(优先队列，堆，贪心)：其实我们并不关心每一个课程的持续长度是多少，我们关心的是连续两个课程时间的差值。假设我们由M时长数组计算出差值数组gap。

我们考虑K = 1的情况（小数据集），我们如何使得难度最小呢？我们贪心的选择差值最大的两个相邻课程之间插入一个新的课程，可以使得我们的答案最小。

假设差值是x，那么在中间插入一个课程后，该部分的最大差值就变成了x / 2 + (x % 2 != 0)。我们只需要将该值和次大的差值取一个最大值即可。更一般的，对于差值是x的两个相邻课程，其中插入了k个新的课程之后，该部分的最大差值就是x / k + (x % k != 0)。

那么K > 1的情况呢？我们只需要将上述思路重复K次即可。我们使用一个结构体记录（用pair数据结构也可以，重写比较函数即可）每一个区间长度sum和该区间已经插入了cnt个新课程。我们按照该区间插入cnt个课程后的该区间的最大差值从大到小排序即可。每次取出堆顶元素，将其cnt加上1之后重新插入优先队列。重复K次后，堆顶元素对应的区间最大值就是答案。

时间复杂度:$O(KlogN)$

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 100010;
int A[N],gap[N];
struct node{
    int sum,cnt;
    node(){}
    node(int sum,int cnt):sum(sum),cnt(cnt){}
    bool operator< (const node& b) const{
        int x = (sum / cnt) + (sum % cnt > 0);
        int y = (b.sum / b.cnt) + (b.sum % b.cnt > 0);
        return x < y;
    }
};
int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        memset(A,0,sizeof(A));
        memset(gap,0,sizeof(gap));
        int n,K;
        scanf("%d %d",&n,&K);
        for(int i = 0 ; i < n ; i ++)
            scanf("%d",&A[i]);
        for(int i = 0 ; i < n - 1 ; i ++)
            gap[i] = A[i + 1] - A[i];
        if(K == 1){
            sort(gap,gap + n - 1);
            if(n == 2) 
                printf("Case #%d: %d\n",t,(gap[0] + 1) / 2);
            else
                printf("Case #%d: %d\n",t,max((gap[n - 2] + 1) / 2,gap[n - 3]));
        }else{
            priority_queue<node> q;
            for(int i = 0 ; i < n - 1 ; i ++){
                q.push(node(gap[i],1));
            }
            for(int i = 0 ; i < K ; i ++){
                auto p = q.top();
                q.pop();
                q.push(node(p.sum,p.cnt + 1));
            }
            auto p = q.top();
            int res = (p.sum / p.cnt) + (p.sum % p.cnt > 0);
            printf("Case #%d: %d\n",t,res);
        }
    }
    return 0;
}

题解2（二分）：假设我们的最优答案是res，那么每一个区间x最少需要插入多少个新课程才能满足上述要求呢？我们最少需要插入(x - 1)/ res个新的课程。我们发现随着res的增加，所需要的新课程总量是减少的，随着res的减少，所需要的新课程总量是增加的。所以我们需要找到一个最小的res，使的所需要的课程总量个数小于等于K。那么我们可以使用二分查找解决这一题。

该题目属于二分查找满足某条件的最小值

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 100010;
int A[N],gap[N];
bool check(int op,int n,int K){
    int cnt = 0;
    for(int i = 0 ; i < n - 1 ; i ++)
        cnt += (gap[i] - 1) / op;
    return cnt <= K;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        memset(A,0,sizeof(A));
        memset(gap,0,sizeof(gap));
        int n,K;
        scanf("%d %d",&n,&K);
        for(int i = 0 ; i < n ; i ++)
            scanf("%d",&A[i]);
        for(int i = 0 ; i < n - 1 ; i ++)
            gap[i] = A[i + 1] - A[i];
        int l = 1,r = 1e9;
        while(l < r){
            int mid = (l + r) >> 1;
            if(check(mid,n,K)) r = mid;
            else l = mid + 1;
        }
        printf("Case #%d: %d\n",t,l);
    }
    return 0;
}

Bunding

Problem

Pip has N strings. Each string consists only of letters from A to Z. Pip would like to bundle their strings into groups of size K. Each string must belong to exactly one group.

The score of a group is equal to the length of the longest prefix shared by all the strings in that group. For example:

• The group {RAINBOW, RANK, RANDOM, RANK} has a score of 2 (the longest prefix is 'RA').
• The group {FIRE, FIREBALL, FIREFIGHTER} has a score of 4 (the longest prefix is 'FIRE').
• The group {ALLOCATION, PLATE, WORKOUT, BUNDLING} has a score of 0 (the longest prefix is '').

Please help Pip bundle their strings into groups of size K, such that the sum of scores of the groups is maximized.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and K. Then, N lines follow, each containing one of Pip’s strings.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum sum of scores possible.

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ N ≤ 105.
2 ≤ K ≤ N.
K divides N.
Each of Pip’s strings contain at least one character.
Each string consists only of letters from A to Z.

Test set 1

Each of Pip’s strings contain at most 5 characters.

Test set 2

The total number of characters in Pip’s strings across all test cases is at most 2 × 106.

Samples

Input1
2
2 2
KICK
START
8 2
G
G
GO
GO
GOO
GOO
GOOO
GOOO

Output1
Case #1: 0
Case #2: 10

Input2
1
6 3
RAINBOW
FIREBALL
RANK
RANDOM
FIREWALL
FIREFIGHTER

Output2
Case #1: 6

Sample #1

In Case #1, Pip can achieve a total score of 0 by make the groups:

• {KICK, START}, with a score of 0.

In Case #2, Pip can achieve a total score of 10 by make the groups:

• {G, G}, with a score of 1.
• {GO, GO}, with a score of 2.
• {GOO, GOO}, with a score of 3.
• {GOOO, GOOO}, with a score of 4.

Sample #2

In Case #1, Pip can achieve a total score of 6 by make the groups:

• {RAINBOW, RANK, RANDOM}, with a score of 2.
• {FIREBALL, FIREWALL, FIREFIGHTER}, with a score of 4.

Note #1: Only Sample #1 is a valid input for Test set 1. Consequently, Sample #1 will be used as a sample test set for your submissions.

Note #2: Unlike previous editions, in Kick Start 2020, all test sets are visible verdict test sets, meaning you receive instant feedback upon submission.

题意：我们现在有N个字符串，每个字符串只包括字符A-Z，我们现在将这N个字符串划分为K个字符串一组，每个字符串只能属于一组，我们保证N % K = 0。每一组字符串的得分等于该组所有字符串的最长公共前缀长度。请帮助我进行划分，使得划分后所有组的得分总和最大。

题解：因为是公共前缀的题目，而且大数据特意强调了总字符个数不超过$2 \times 10^6$，大概率这一题是Trie树数据结构的做法。

我们考虑被划分为同一个组的字符串，假设其最长公共前缀为ABCD，长度为4，得分也为4，我们也可以看作是前缀A,AB,ABC,ABCD分别贡献了一分。如果某个前缀在x个组中都是公共前缀（不一定是最长的），那么这个前缀贡献的分数就是x。

那么现在我们不再去求每一个组的分数（我比赛时的思路，罚时爆炸），而是去考虑每一个前缀为最终答案贡献了多少分。

如果某一个前缀出现了S次，那么他的最多贡献的分就是S / K。那么是否存在一种划分能让每一个前缀都实现其最大分数呢？假设存在一个长度为L的最长前缀$P_L$，其出现次数为cnt，我们先贪心的将其尽可能的划分为同一组，那么这个前缀P的贡献分数恰好是cnt / K，那么还剩下cnt % K个字符串，我们再考虑长度为L - 1的次最长前缀$P_{L-1}$，每次都处理一个最长前缀即可，可以使得所有前缀都满足最大值。

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
using namespace std;
const int N = 2000010;
int son[N][26],cnt[N * 26],idx = 0,res;
void insert(string &s,int k){
    int p = 0;
    for(auto ch : s){
        cnt[p] ++;
        int j = ch - 'A';
        if(son[p][j] == 0) son[p][j] = ++idx;
        p = son[p][j];
    }
    cnt[p] ++;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        idx = 0,res = 0;
        memset(son,0,sizeof(son));
        memset(cnt,0,sizeof(cnt));
        int n,k;
        scanf("%d %d",&n,&k);
        string s;
        for(int i = 0 ; i < n ; i ++){
            cin >> s;
            insert(s,k);
        }
        for(int i = 1 ; i <= idx ; i ++)
            res += cnt[i] / k ;
        printf("Case #%d: %d\n",t,res);
    }
    return 0;
}

我当时比赛虽然AC了，但是思路略微麻烦，代码也不够整洁，我将我的AC代码贴在最后。我当时的思路是：使用Trie树记录所有字符串，同时记录每一个节点的出现次数及其深度。每次找到一个最深的出现次数大于K的节点，答案累计上这个深度，同时将从根节点到该节点路径上所有节点出现次数都减去K，代表这个字符串已经被使用过了，其子节点我们可以不用管，因为其子节点出现次数小于K，我们永远不会使用。

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
using namespace std;
const int N = 2000010;
int son[N][26],cnt[N * 26],pa[N * 26],dep[N * 26],idx = 0,max_depth = 0;
vector<set<int>> ha;
void insert(string &s,int k){
    int p = 0,depth = 0;
    for(auto ch : s){
        cnt[p] ++;
        if(cnt[p] >= k) {
            ha[depth].insert(p);
            max_depth = max(max_depth,depth);
        }

        int j = ch - 'A';
        if(son[p][j] == 0) son[p][j] = ++idx;
        pa[son[p][j]] = p;
        dep[son[p][j]] = ++ depth;
        p = son[p][j];
    }
    cnt[p] ++;
    if(cnt[p] >= k) {
        ha[depth].insert(p);
        max_depth = max(max_depth,depth);
    }
}
int dfs(int K){
    while(max_depth >= 0 && ha[max_depth].size() == 0)
        max_depth --;
    int i = *ha[max_depth].begin();
    while(i != 0){
        cnt[i] -= K;
        if(cnt[i] < K)
            ha[dep[i]].erase(i);
        i = pa[i];
    }
    cnt[0] -= K;
    if(cnt[0] < K)
        ha[dep[i]].erase(i);
    return max_depth;
}

int main(){
    int T;
    scanf("%d",&T);
    for(int t = 1 ; t <= T ; t ++){
        idx = 0;
        max_depth = 0;
        ha.clear();
        ha.resize(N);
        memset(son,0,sizeof(son));
        memset(cnt,0,sizeof(cnt));
        memset(dep,0,sizeof(dep));
        memset(pa,0,sizeof(pa));
        int n,k;
        scanf("%d %d",&n,&k);
        string s;
        for(int i = 0 ; i < n ; i ++){
            cin >> s;
            insert(s,k);
        }
        int res = 0;
        while(cnt[0] > 0){
            res += dfs(k);
        }
        printf("Case #%d: %d\n",t,res);
    }
    return 0;
}