задачи на палиндромы

219

06 января 2018, 03:20

В первой строке входных данных содержится число N (1 <= N <= 100000). Во второй строке задается последовательность из N больших латинских букв (буквы записаны без пробелов). ребуется из данных букв по указанным правилам составить палиндром наибольшей длины, а если таких палиндромов несколько, то выбрать первый из них в алфавитном порядке.

#include <iostream> 
#include <iomanip> 
#include <string>
#include <vector> 
#include <algorithm>
using namespace std;
int i, j, oi = 0;
string a, outpit;
char z;
bool flag = true;
void work() {
  for (j = 0; j < a.size(); ++j) {
    if (i == j) j++;
    if (a[i] == a[j]) {
      cout << a << endl;
      outpit[oi] = a[i];
      oi++;
      a[i] = i;
      return;
    }
  }
  if (flag == true) {
    z = a[i];
    flag = false;
  }
  return;
}
int main() {
  int h;
  cin >> h;
  cin >> a;
  sort(a.begin(), a.end());
  for (i = 0; i < a.size(); ++i) {
    work();
  }
  for (i = 0; i < oi; i += 2)
    cout << outpit[i];
  if (flag == false)
    cout << z;
  for (i = oi - 1; i >= 0; i -= 2)
    cout << outpit[i];
  return 0;
}

Answer 1

Как вариант Заводим массив на количество символов в алфавите. Проходимся по строке и считаем каждую букву (+1 в массив для букву)

Допустим AABCCAD

Тогда в массиве будет A=3 B=1 C=2 D=1

Дальше проходим по массиву и составляем строку по правилу

While (array[A] >= 2) то добавляем букву в начало и в конец строки, делаем array[A]-2;

При этом смотрим if (array[A]%2 != 0) Если число не кратное, то запоминаем его в переменную. После прохождения всех элементов массива в середину строки записываем символ который мы запомнили.

Таким образом мы получим строку ACACA

Answer 2

Ну, если там точно (!) N символов во второй строке и без пробелов, то можно сразу читать строку символов и обрабатывать:

int main(int argc, const char * argv[])
{
    string s,p;
    cin >> s;
    cin >> s;
    sort(s.begin(),s.end());
    char center = 0;
    for(int i = 0; i < s.length(); i++)
    {
        if (s[i] == s[i+1])
        {
            p += s[i];
            i++;
        }
        else if (center == 0) center = s[i];
    }
    s = p;
    reverse(s.begin(),s.end());
    if (center) p += center;
    p += s;
    cout << p << endl;
}