2015 ACM-ICPC Asia Amritapuri Regional Contest H - Longest Palindrome (构造最长回文)贪心

xiaoxiao2021-02-28  5

H - Longest Palindrome

  CodeChef - AMLPALIN 

Farzi Coder wants to give a nice Christmas present to his brother. For that he has brought N pairs of letters where each letter is either 'a' or 'b'. So, the possible pairs are "aa", "ab", "ba" or "bb". Now, Farzi Coder's brother loves palindromes. So, he decided to concatenate some of the pairs (possibly all or none) and form a palindrome. He wants the longest such palindrome possible. If there are multiple such longest palindromes possible, he wants to give his brother the lexicographically smallest palindrome among them as the gift. Since he is, well, Farzi Coder, you have to help him build the gift.


The first line of the input has the number T denoting the number of test cases.

The first line of each test case has the number N denoting the number of pairs in this case.

Each of the next N lines contain a pair of characters which are either aa, ab, ba or bb.


For each test case, output on a seperate line the gift that Farzi Coder has to build. Note that the empty string is a palindrome.


1 ≤ T ≤ 5001 ≤ N ≤ 2000Each pair can be either aa, ab, ba or bb



2 4 aa aa bb bb 3 ab ba ab


aabbbbaa abba


Case 1: The following palindromes are possible: "aa", "aaaa", "bb", "bbbb", "aabbaa", "bbaabb", "aabbbbaa", "bbaaaabb". Of these, "aabbbbaa" and "bbaaaabb" are of the maximum length. Among these two, "aabbbbaa" is the lexicographically smallest. Case 2: The palindromes possible here are: "baab" and "abba".

思路:贪心。先考虑 aa,把一半aa放在前边,然后是min(ab,ba)个ab,再放一半bb中间是(aa为奇数则放aa,否则bb是奇数放bb,否则不放),再放一半bb,后边是min(ab,ba)个ba,最后是一半aa。具体建代码,用了map实现,代码更简单易写。

map<string,int>mp; int n; string s; int main(int argc, const char * argv[]) { int T; cin>>T; while(T--) { mp.clear(); cin>>n; for(int i=0;i<n;i++) { cin>>s; mp[s]++; } s=""; if(mp["aa"]>1) for(int i=0;i<mp["aa"]/2;i++) s+="aa"; int ab=min(mp["ab"],mp["ba"]); for(int i=0;i<ab;i++) s+="ab"; if(mp["bb"]>1) for(int i=0;i<mp["bb"]/2;i++) s+="bb"; if(mp["aa"]%2)s+="aa"; else if(mp["bb"]%2) s+="bb"; if(mp["bb"]>1) for(int i=0;i<mp["bb"]/2;i++) s+="bb"; for(int i=0;i<ab;i++) s+="ba"; if(mp["aa"]>1) for(int i=0;i<mp["aa"]/2;i++) s+="aa"; cout<<s<<endl; } return 0; }

转载请注明原文地址: https://www.6miu.com/read-1750056.html