Bundling

題目鏈接

題目簡介

有 N N N個字串，現在要把這 N N N個字串分成不同組，每組字串個數均為 K K K個，每組的得分記為 K K K個字串的最長公共前綴的字母數，現在要讓得分最大化，

解題思路

• 容易想到用構建一個前綴樹去做
• 前綴樹的資料結構可以是多叉樹，也可以是陣列(前排大佬的做法)
• 具體解釋下陣列的做法
  • 為所有前綴記一個索引( m m m)
  • 陣列 c c c第一維是前綴索引，第二維是該前綴加上一個字母形成的前綴，值代表該前綴加上一個字母形成的前綴索引(這樣做的原因是為了在dfs時，可以輕松遍歷到這個前綴加上任意長字母形成的前綴)
  • 陣列 c n t cnt cnt索引代表著前綴的索引，值代表這個前綴在所有 N N N個字串中的出現次數(這是在dfs函式運行之后，運行之前陣列的值初始化為恰好為這 N N 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";
	}
}