[CF1034B] Longest Palindrome

如果自己是回文串可以做中心

如果一个串和另一个串的转置相等则可以凑一对

优先配对

#include <bits/stdc++.h>

using namespace std;

int n,m,u[105];

string str[105];

vector <int> a,b;

signed main() {

    ios::sync_with_stdio(false);

    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>str[i];

    int ans=0;

    for(int i=1;i<=n;i++) {

        if(u[i]) continue;

        for(int j=i+1;j<=n;j++) {

            int flag=1;

            for(int k=0;k<m;k++) if(str[i][k]!=str[j][m-k-1]) flag=0;

            if(flag) {

                u[i]=1;

                u[j]=1;

                a.push_back(i);

                b.push_back(j);

                ans+=2;

                break;

            }

        }

    }

    int flag=0;

    for(int i=1;i<=n;i++) {

        int tmp=1;

        for(int k=0;k<m;k++) if(str[i][k]!=str[i][m-k-1]) tmp=0;

        if(tmp) flag=i;

    }

    if(flag) ++ans;

    cout<<ans*m<<endl;

    for(int i=0;i<a.size();i++) cout<<str[a[i]];

    cout<<str[flag];

    for(int i=b.size()-1;i>=0;--i) cout<<str[b[i]];

}

巴特西

[CF1034B] Longest Palindrome - 贪心

最新文章

热门文章