# 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.

## Input

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.

## Output

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.

## Constraints

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

## Sample

### Input

2 4 aa aa bb bb 3 ab ba ab

aabbbbaa abba

### Explanation

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".

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; }