CF1304B Longest Palindrome（可逆转符号，数学分析，回文串）

题目描述

Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse. For example, strings "pop", "noon", "x", and "kkkkkk" are palindromes, while strings "moon", "tv", and "abab" are not. An empty string is also a palindrome.

Gildong loves this concept so much, so he wants to play with it. He has nn distinct strings of equal length mm . He wants to discard some of the strings (possibly none or all) and reorder the remaining strings so that the concatenation becomes a palindrome. He also wants the palindrome to be as long as possible. Please help him find one.

输入格式

The first line contains two integers nn and mm ( 1 \le n \le 1001≤n≤100 , 1 \le m \le 501≤m≤50 ) — the number of strings and the length of each string.

Next nn lines contain a string of length mm each, consisting of lowercase Latin letters only. All strings are distinct.

输出格式

In the first line, print the length of the longest palindrome string you made.

In the second line, print that palindrome. If there are multiple answers, print any one of them. If the palindrome is empty, print an empty line or don't print this line at all.

题意翻译

• 给你  n 个长度为  m 的字符串。
• 请你判断删去其中的几个（或者不删去），能使得将剩下字符串随意排列所形成的回文串长度最大。
• 请你输出最大的长度和那个回文串。
• 1≤n≤100， 1≤m≤50。

输入输出样例

输入  

3 3

tab

one

bat

输出  

6

tabbat

输入

4 2

oo

ox

xo

xx

输出  

6

oxxxxo

输入

3 5

hello

codef

orces

输出  

0

输入

9 4

abab

baba

abcd

bcde

cdef

defg

wxyz

zyxw

ijji

输出  

20

ababwxyzijjizyxwbaba

题目刨析，首先我们观察答案发现是由2*n个互相可以颠倒相同的字符串组成，或者由2*n个互相颠倒的字符串组成然后再字符串中间加上一个本身可以颠倒的字符串组成答案，所以我们思路是定一个字符串然后遍历后面的字符串，如果相同用一个string来存字符串，最后找一个自身颠倒自己的字符串加在中间，退出循环。就是答案。思路就是这样，具体操作看代码。

#include<bits/stdc++.h>
using namespace std;
struct node{
  string word;//字符串
  int flag;//标记是否已经用过、、先默认为·0 
}a[105];
string ans;//用来输出
int main()
{
  int n,m;
  cin>>n>>m;
  getchar();
  for(int i=0;i<n;i++)
      cin>>a[i].word;
   for(int i=0;i<n;i++)
        {
      if(!a[i].flag)//=0
      { 
         for(int j=i+1;j<n;j++)//枚举i后面字符串是否对称
        {
          string temp=a[j].word;
          reverse(temp.begin(),temp.end());//反转字符串 
            if(strcmp(a[i].word.c_str(),temp.c_str())==0)//第一个是前面的反转后的字符，第二个是后面的字符看是不是相等 
            {
              ans=a[i].word+ans+a[j].word;//string 可以直接连在一起 
              a[i].flag=a[j].flag=1;//标记 
            }
        }
          } 
      }
    for(int i=0;i<n;i++)
    {
        if(!a[i].flag)//=0
        {
          string temp=a[i].word;
          reverse(temp.begin(),temp.end());
          if(strcmp(temp.c_str(),a[i].word.c_str())==0)//看自己是不是回文串 
          {
             ans.insert(ans.size()/2,a[i].word);//插入自身对称的字符串（回文串）
                break;
          }
            }
    }
    cout<<ans.size()<<"\n";
    cout<<ans<<endl;
 }