KickStart 2020 Round A-D Bundling
Problem
将$N$个字符串分为$K$个一组,使得每组的最长公共前缀长度之和最大。
官方参考解法是用字典树存放字符串(很直观),然而我忘了有这个数据结构,用优先队列+滚动哈希xjb过了。
Solution
#include <iostream>
#include <map>
#include <string>
#include <queue>
using namespace std;
const long long base = 31LL;
const long long mod = 1000000007LL;
const long long rev = 129032259LL;
int n = 0, k = 0;
string s[100005];
class Node {
public:
int len, cnt, str;
long long hash;
explicit Node(int str) : str(str) {
len = s[str].size(), cnt = 1;
hash = 0LL;
for (int i = 0; i < len; ++i) {
hash = (hash * base + (s[str][i] - 'A')) % mod;
}
}
Node(int len, int cnt, int str, long long hash)
: len(len), cnt(cnt), str(str), hash(hash) {}
bool operator<(const Node &rhs) const {
return len < rhs.len or (len == rhs.len and hash < rhs.hash);
}
};
priority_queue<Node> pq;
long long findAns() {
long long ans = 0;
while (!pq.empty()) {
auto t = pq.top();
pq.pop();
int cnt = t.cnt;
while (!pq.empty() and t.len == pq.top().len and t.hash == pq.top().hash) {
cnt += pq.top().cnt;
pq.pop();
}
if (cnt >= k) {
ans += (long long)t.len * (cnt / k);
cnt %= k;
}
if (cnt > 0 and t.len > 1) {
long long hash = ((t.hash - (s[t.str][t.len-1] - 'A') + mod) % mod) * rev % mod;
pq.emplace(Node(t.len-1, cnt, t.str, hash));
}
}
return ans;
}
int main() {
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T = 0;
cin >> T;
for (int t = 1; t <= T; ++t) {
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
pq.emplace(Node(i));
}
cout << "Case #" << t << ": " << findAns() << endl;
}
}
<EOF>