752-D. Santa Claus and a Palindrome
Tags: palindrome, priority-queue
出處：https://codeforces.com/contest/752/problem/D
提交：https://codeforces.com/contest/752/submission/110458664
問題：給定 $k\in[1,100000]$ 個長度都固定為 $n\in[1,100000]$ 的字串，每個字串有一個介於 $[-10000,10000]$ 的爽度，現在我們要從中挑出一些字串，使得組合後的結果為回文而且有最大的爽度總和，請問這個總和？另外，此答案必非負，因為空字串也符合條件而且爽度總和為 0。
解法：可將候選字串們分為兩類。
如果是非回文，就必須找另外一個倒過來的字串匹配成一對，舉例來說，abc 必須和 cba 搭配，而它們可能會各自出現很多次，因此必須先把各自的多個爽度由高到低排序再依序匹配，如果 abc 出現四次的爽度分別為 5、3、1、-2，cba 出現三次的爽度分別為 4、-1、-2，那麼第一組的爽度總和為 5 + 4 = 9、第二組的爽度總和為 3 - 1 = 2，而剩下的爽度因為總和不可能為正，可以直接捨棄。
如果是回文，它可以自己跟自己配，也可以單獨一人放在正中央。所以我們一樣對自己的多個爽度由高到低排序再依序匹配，剛開始一樣是兩個兩個一組令為 (a,b)，如果是 a>=0 且 b>=0，當然直接放到兩側，而 a<=0 且 b<=0 則直接丟棄不用，那這題比較 tricky 的地方在於如果是 a>=0 且 b<=0，又可以分成 a+b<0 和 a+b>=0 兩部分，前者也很簡單，我們必定不選 b 而把 a 放進「正中央的候選名單」即可，但是後者呢？它會有兩種可能作法，一種 (*) 是把 a 和 b 放在兩側，另一種 (**) 是只把 a 放在正中央。究竟要哪一種？因為正中央只能放一個字串，於是一個技巧是我們都先當成 (*) 去處理，然後再把 -b 放進「正中央的候選名單」，如果最後這個 -b 真的是「候選名單」內的最爽字串，那麼它對應的 a 才真正擠上正中央字串的衛冕者寶座。最後對於這個特定字串而言，如果兩兩配對之後還剩下一個爽度，那它當然也是放進「正中央的候選名單」去作比較。
實作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <bits/stdc++.h>
using namespace std;
map<string, priority_queue<int>> mymap;
int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
int k, n, ans=0, single=0;
cin >> k >> n; string str;
for (int i=0; i<k; i++) {
cin >> str >> n;
mymap[str].push(n);
}
for (auto &kv: mymap) {
string rev = string(kv.first.rbegin(), kv.first.rend());
if (kv.first != rev) {
while (!kv.second.empty() && !mymap[rev].empty()
&& kv.second.top() + mymap[rev].top() > 0) {
ans += kv.second.top() + mymap[rev].top();
kv.second.pop(); mymap[rev].pop();
}
} else {
while (kv.second.size() >= 2) {
int a = kv.second.top(); kv.second.pop();
int b = kv.second.top(); kv.second.pop();
if (a + b >= 0) {
ans += a + b;
if (b < 0) single = max(single, -b); // 重要！！！
} else {
if (a > 0) single = max(single, a); // 重要！！！
break;
}
}
if (!kv.second.empty())
single = max(single, kv.second.top());
}
}
cout << ans + single;
return 0;
}
|
結果：
alan23273850 的刷題筆記