2020 Round A – Bundling

呜呜呜,我还是好菜呀。一开始上来第一题就脑子抽风TLE了,然后做出了第二题的DP很高兴,因为我基本上无法独立完成DP,然后第三题WA了在zz的提示下过了,然后开始挂机最后发现有1000个人AK了……而我排1500+。

不过我死而无憾,因为我从来没见过字典树,不过学了一下觉得好简单噢,感觉这是后三题里最简单的一题了。

4. Bundling

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 ≤ 10^5.
2 ≤ KN.
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 × 10^6.

Samples

Input 1

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

Output 1

Case #1: 0
Case #2: 10

Input 2

1
6 3
RAINBOW
FIREBALL
RANK
RANDOM
FIREWALL
FIREFIGHTER

Output 2

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 个字符串,需要将其分为容量为 K 的组,每个组统计其最长公共前缀的长度。
求一种分组方法,使得各组的最长公共前缀长度之和最大。

思路

【字典树科普】

字典树由一个根节点和许多其他节点组成,每一个节点有两个元素:被访问次数 val 与 指向下一个节点的边 nxt[i] 。树中的每一条边上都标识有一个字符,从根节点到任意一个节点的路径组成一个字符串。

【贪心】

可以将问题转化一下,求许多字符串的最长公共前缀长度,其实就是在求这些字符串的所有公共前缀的数量。

例如三个字符串 aaabbbaaabbcaaabcc ,横向来看最长公共前缀是 aaab ,长度为 4 ;纵向来看,其实有 aaaaaaaaab 四个公共前缀。

我们又知道 n 个字符串的所谓公共前缀,就是在字典树上这一段路径被访问了 n 次,也就是指定结点的 val 值为 n 。所以,对于每一个字符串,读入之后将其加入字典树,并不断更新 TreeNodeval 值。一旦 val 值达到 k ,就意味着已经有 k 个字符串达到了这个节点,答案加一。

代码

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

const int MAXN = 1e5 + 5;

int n, k, ans; 
string s[MAXN];

struct TreeNode {
    int val;
    TreeNode* nxt[26];
    TreeNode() {
        val = 0;
        for(int i=0; i<26; i++) nxt[i] = NULL;
    }
};

void build(TreeNode* root, string& now) {
    int len = now.size();
    for(int i=0; i<len; i++) {
        int ch = now[i] - 'A';
        if(root->nxt[ch] == NULL) root->nxt[ch] = new TreeNode();
        
        root = root->nxt[ch];
        root->val++;
        if(root->val == k) {
            ans++;
            root->val = 0;
        }
    } 
}

int main() {
    int T; cin>>T;
    for(int t=1; t<=T; t++) {
        cin>>n>>k; ans = 0;
        TreeNode* root = new TreeNode();
        for(int i=0; i<n; i++) {
            cin>>s[i];
            build(root, s[i]);
        }
        cout<<"Case #"<<t<<": "<<ans<<endl;
        
    }
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇