CFR 613 C. Necklace ( Ad hoc, Palindrome )

Problem - C - Codeforces

題意：
給 'a' ~ 'a' + N - 1 各個字母的出現頻度。要求構造一個環狀的字串，使得最多處切下去會是迴文。

資料規模：
N ≤ 26
出現頻度總數不超過 1e5

解法：
因為至少要有一個迴文就必須有不超過一個奇數的頻度，所以接下來可以分開討論：
若洽有一個奇數頻度的字母，那麼令 g 為所有頻度的一半，以及奇數頻度的頻度的公因數。此時 g 為極值，直接構造這個迴文輸出 g 次即可。
若沒有奇數頻度的字母，那麼令 g 為所有頻度的一半的公因數。此時 2 * g 為極值，構造出這個迴文後，正逆交替輸出即可。

時間 / 空間複雜度：
O( 1e5 )

#include <bits/stdc++.h>
using namespace std;

int N;
int C[ 26 ];

signed main(){
  ios::sync_with_stdio( 0 );
  {
    cin >> N;
    for( int i = 0; i < N; ++i ){
      cin >> C[ i ];
    }
  }
  {
    int odd = -1;
    for( int i = 0; i < N; ++i ){
      if( ~ C[ i ] & 1 ) continue;
      if( odd != -1 ){
        cout << 0 << endl;
        for( int j = 0; j < N; ++j ){
          for( int k = 0; k < C[ j ]; ++k ){
            cout << ( char ) ( 'a' + j );
          }
        }
        cout << endl;
        exit( 0 );
      }
      odd = i;
    }
    if( odd == -1 ){
      int g = 0;
      for( int j = 0; j < N; ++j ){
        g = __gcd( g, C[ j ] / 2 );
      }
      cout << 2 * g << endl;
      string s;
      for( int j = 0; j < N; ++j ){
        for( int k = 0; k < C[ j ] / 2 / g; ++k ){
          s += ( char ) ( 'a' + j );
        }
      }
      for( int i = 0; i < 2 * g; ++i ){
        cout << s;
        reverse( s.begin(), s.end() );
      }
      cout << endl;
    } else{
      int g = 0;
      for( int j = 0; j < N; ++j ){
        g = __gcd( g, C[ j ] );
      }
      cout << g << endl;
      string s, t;
      for( int j = 0; j < C[ odd ] / g; ++j ){
        t += ( char ) ( 'a' + odd );
      }
      for( int j = 0; j < N; ++j ){
        if( odd == j ) continue;
        for( int k = 0; k < C[ j ] / 2 / g; ++k ){
          s += ( char ) ( 'a' + j );
        }
      }
      string ns = s + t;
      reverse( s.begin(), s.end() );
      ns += s;
      for( int i = 0; i < g; ++i ){
        cout << ns;
      }
      cout << endl;
    }
  }
  return 0;
}