首页 > 其他 > 详细

Codeforces 1304B. Longest Palindrome

时间:2020-02-16 14:59:30      阅读:65      评论:0      收藏:0      [点我收藏+]

根据数据范围,暴力可以解决,对每一个串,找与其互为回文的串,或者判断自身是否为回文串,然后两两将互为回文的串排列在头尾,中间放且只能最多放一个自身为回文串的串,因为题目说每个串都是不同的

技术分享图片
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long LL;

string str[105];
int cache[105], self[105], s[105], chosen[105];

void run_case() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) 
        cin >> str[i];
    for(int i = 1; i <= n; ++i) {
        bool flag = true;
        for(int j = 0; j < m/2 && flag; ++j) {
            if(str[i][j] != str[i][m-j-1]) flag = false;
        }
        if(flag) {
            self[i] = 1;
            continue;
        }
        if(cache[i]) continue;
        string now = str[i];
        reverse(now.begin(), now.end());
        for(int j = 1; j <= n; ++j) {
            if(j != i && now == str[j]) {
                cache[i] = j; break;
            }
        }
    }
    vector<int> ans, selfs;
    int top = 0;
    for(int i = 1; i <= n; ++i)
        if(cache[i] && !chosen[i]) {
            ans.push_back(i);
            s[++top] = cache[i];
            chosen[cache[i]] = i;
        } else if(self[i]) selfs.push_back(i);
    if(selfs.size()) ans.push_back(selfs[0]);
    while(top) {
        ans.push_back(s[top--]);
    }
    cout << ans.size() * m << "\n";
    for(auto i : ans) 
        cout << str[i];
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    //cout.setf(ios_base::showpoint);cout.precision(10);
    //int t; cin >> t;
    //while(t--)
    run_case();
    cout.flush();
    return 0;
}
View Code

 

Codeforces 1304B. Longest Palindrome

原文:https://www.cnblogs.com/GRedComeT/p/12316571.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!