【每日一题】Necklace 题解

Description

给一堆字母的使用次数，判断能否构成一个环，使得断环成链后能够成为回文串的节点尽可能多。

Solution

首先思考回文串的定义，显然如果有两个以上奇数存在是不可能构成回文串的。
接着画个图，给出几组数据

3
2 4 2

2
2 2

2
2 3

不难看出，按照我们的构造方法，答案最多只能是
如果有一个奇数，就把这个奇数放到中间处
构造方法是每次放 个字母构成一个回文串，拼接到一起

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
typedef long long ll;
int a[N];
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
  int n; cin >> n;
  int odd = 0;
  for(int i = 1; i <= n; i++) cin >> a[i], odd += (a[i] & 1);
  if(odd >= 2) { // 两个奇数
    cout << 0 << '\n';
    for(int i = 1; i <= n; i++) {
      while(a[i]--) {
        cout << char('a' + i - 1);
      }
    }
    return 0;
  } 
  ll gcd = a[1];
  for(int i = 2; i <= n; i++) {
    gcd = __gcd(1LL * a[i], gcd);
  }
  cout << gcd << '\n';
  if(odd == 1) { // 一个奇数
    int pos = -1;
    for(int i = 1; i <= n; i++) {
      if(a[i] & 1) pos = i;
    }
    for(int i = 1; i <= gcd; i++) {
      for(int j = 1; j <= n; j++) {
        if(j == pos) continue;
        for(int k = 1; k <= a[j] / gcd / 2; k++) {
          cout << char('a' + j - 1);
        }
      }
      for(int k = 1; k <= a[pos] / gcd; k++) {
        cout << char('a' + pos - 1);
      }
      for(int j = n; j >= 1; j--) {
        if(j == pos) continue;
        for(int k = 1; k <= a[j] / gcd / 2; k++) {
          cout << char('a' + j - 1);
        }
      }
    }
  } else { // 没有奇数
    for(int i = 1; i <= gcd / 2; i++) {
      for(int j = 1; j <= n; j++) {
        for(int k = 1; k <= a[j] / gcd; k++) {
          cout << char('a' + j - 1);
        }
      }
      for(int j = n; j >= 1; j--) {
        for(int k = 1; k <= a[j] / gcd; k++) {
          cout << char('a' + j - 1);
        }
      }
    }
  }
  return 0;
}