CSES - Palindrome Reorder | Sắp xếp lại xâu đối xứng

Xem PDF

Điểm: 1100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một xâu, nhiệm vụ của bạn là sắp xếp lại các kí tự của nó sao cho xâu đó trở thành một xâu đối xứng. Xâu đối xứng là xâu khi đọc xuôi hoặc ngược đều như nhau.

Input

  • Một dòng duy nhất gồm một xâu độ dài \(n\) chỉ chứa các kí tự A-Z.

Output

  • In ra một xâu đối xứng chứa các kí tự của xâu ban đầu. Bạn có thể in ra bất kỳ đáp án thỏa mãn nào. Nếu không có đáp án, in NO SOLUTION.

Constraints

  • \(1 \le n \le 10^6\)

Example

Sample input

AAAACACBA

Sample output

AACABACAA


Bình luận


  • 0
    penistone 2:53 p.m. 25 Tháng 12, 2023

    Code C++

    #include<bits/stdc++.h>
    #define int long long
    #define endl "\n"
    using namespace std;
    
    signed main()
    {
        string s,s1=""; char c,b; int i,a[130]={},d=0,j,x;
        cin>>s;
        for(i=0;i<s.size();i++) a[s[i]]++;
        for(i=60;i<=125;i++) { if (a[i]%2!=0) d++; }
        if (d>1) { cout<<"NO SOLUTION"; return 0; }
        for(i=60;i<=125;i++)
        {
            if (a[i]%2!=0)  {b=char(i); x=i;}
            else if (a[i]%2==0&&a[i]>0) 
            {
                c=char(i); for(j=1;j<=a[i]/2;j++) s1+=c;
            }
        }
        if (d==0) 
        {
            cout<<s1; reverse(s1.begin(),s1.end()); cout<<s1; return 0;
        }
        cout<<s1; for(i=1;i<=a[x];i++) cout<<b; 
        reverse(s1.begin(),s1.end()); cout<<s1;
    }
    


    • -1
      clminhquan 3:56 p.m. 4 Tháng 8, 2023

      đây là code c++ cho ae theo lời hứa đây nè

      include <bits/stdc++.h>

      using namespace std;
      void printqueue(queue<char> q)
      {
      while (!q.empty())
      {
      cout << q.front();
      q.pop();
      }
      }
      void printstack(stack<char> s)
      {
      while (!s.empty())
      {
      cout << s.top();
      s.pop();
      }
      }
      int main()
      {
      string str;
      cin >> str;
      map<char, int> c;
      stack<char> s;
      queue<char> q;
      sort(str.begin(), str.end());
      for (char i:str) c[i]++;
      int odd = 0;
      char middle = '';
      for (pair<char,int> i:c)
      {
      if (i.second %2 !=0)
      {
      if (odd)
      {
      cout << "NO SOLUTION";
      return 0;
      }
      odd ++;
      middle = i.first;
      }
      for (int j = 0; j<i.second/2; j++)
      {
      q.push(i.first);
      s.push(i.first);
      }
      }
      printqueue(q);
      if (middle!='
      ') cout << middle;
      printstack(s);
      }

      2 phản hồi

      • 0
        clminhquan 3:43 p.m. 4 Tháng 8, 2023

        ai cần code c++ tui cho

        1 phản hồi

        • 0
          PhamtUan123 1:11 p.m. 12 Tháng 9, 2022 đã chỉnh sửa

          tại sao ở test 1 em in ra AAAAAAAAAA lại wa vậy ạ?(đã biết lỗi sai:>)