kickstart 2020 A Bundling

Bundling

---

题目链接

---

题目简介

有$N$个字符串，现在要把这$N$个字符串分成不同组，每组字符串个数均为$K$个，每组的得分记为$K$个字符串的最长公共前缀的字母数，现在要让得分最大化。

---

解题思路

• 容易想到用构建一个前缀树去做
• 前缀树的数据结构可以是多叉树，也可以是数组(前排大佬的做法)
• 具体解释下数组的做法
  • 为所有前缀记一个索引($m$)
  • 数组$c$第一维是前缀索引，第二维是该前缀加上一个字母形成的前缀，值代表该前缀加上一个字母形成的前缀索引(这样做的原因是为了在dfs时，可以轻松遍历到这个前缀加上任意长字母形成的前缀)
  • 数组$cnt$索引代表着前缀的索引，值代表这个前缀在所有$N$个字符串中的出现次数(这是在dfs函数运行之后，运行之前数组的值初始化为恰好为这$N$个字符串的前缀索引对应的值为1)
  • dfs中用到了回溯的思想

---

代码

• 用数组实现的大佬的做法

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

#define ll long long
#define ar array

int n, k, c[2000001][26], m, cnt[2000001];
ll ans;

void dfs(int u=0, int d=0) {
	for(int v=0; v<26; ++v)
		if(c[u][v])
			dfs(c[u][v], d+1), cnt[u]+=cnt[c[u][v]];
	while(cnt[u]>=k) {
		cnt[u]-=k;
		ans+=d;
	}
}

void solve() {
	cin >> n >> k;
	m=1;
	for(int i=0; i<n; ++i) {
		string s;
		cin >> s;
		int u=0;
		for(char d : s) {
			if(!c[u][d-'A'])
				c[u][d-'A']=m++;
			u=c[u][d-'A'];
		}
		++cnt[u];
	}
	ans=0;
	dfs();
	cout << ans << "\n";
	memset(c, 0, m*sizeof(c[0]));
	memset(cnt, 0, m*4);
}

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

	int t, i=1;
	cin >> t;
	while(t--) {
		cout << "Case #" << i << ": ";
		solve();
		++i;
	}
}

• 用多叉树实现的做法

#include<bits/stdc++.h>
using namespace std;
struct Node{
	char val;
	long long num=0;
	int score=0;
	bool flag=0;
	Node* last=NULL;
	Node* nxt[26];
};
int T,N,K,rest_num;
long long ret;
vector<Node*>rep;
bool cmp(const Node* n1,const Node* n2){
		return n1->score > n2->score;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> T;
	for(int g=1;g<=T;g++){
		rep.clear();ret = 0;
		Node* front = new Node();
		front->score = 0;
		cin >> N >> K;
		cin.get();
		for(int i=0;i<N;i++){
			char ch;
			Node* cur = front;
			ch = cin.get();
			while(ch!='\n'){
				if(cur->nxt[ch-'A']){
					cur = cur->nxt[ch-'A'];
					cur->num ++;
					if(cur->num>=K&&!cur->flag){
						rep.push_back(cur);
						cur->flag = 1;
					}
				}else{
					Node* tmp = new Node();
					tmp->num = 1;
					tmp->val = ch;
					cur->nxt[ch-'A'] = tmp;
					tmp->last = cur;
					tmp->score = cur->score + 1;
					cur = tmp;
				}
				ch = cin.get();
			}
		}
		sort(rep.begin(),rep.end(),cmp);
		for(Node* e:rep){
			if(e->num>=K){
				long long number = e->num/K;
				ret += number*e->score;
				while(e->last){
					e->num -= number*K;
					e = e->last;	
				}
			}
		}
		cout << "Case #" << g << ": " << ret << "\n";
	}
}