Educational Codeforces Round 64 (Rated for Div. 2) B Ugly pairs

제목

You are given a string, consisting of lowercase Latin letters.
A pair of neighbouring letters in a string is considered ugly if these letters are also neighbouring in a alphabet. For example, string "abaca"contains ugly pairs at positions (1,2)(1,2) — "ab"and (2,3)(2,3) — "ba". Letters 'a' and 'z' aren't considered neighbouring in a alphabet.
Can you rearrange the letters of a given string so that there are no ugly pairs? You can choose any order of the letters of the given string but you can't add any new letters or remove the existing ones. You can also leave the order the same.
If there are multiple answers, print any of them.
You also have to answer TT separate queries.
Input
The first line contains a single integer TT (1≤T≤1001≤T≤100) — the number of queries.
Each of the next TT lines contains string ss (1≤|s|≤100)(1≤|s|≤100) — the string for the next query. It is guaranteed that it contains only lowercase Latin letters.
Note that in hacks you have to set T=1T=1.
Output
Print TT lines. The ii-th line should contain the answer to the ii-th query.
If the answer for the ii-th query exists, then print such a rearrangment of letters of the given string that it contains no ugly pairs. You can choose any order of the letters of the given string but you can't add any new letters or remove the existing ones. You can also leave the order the same.
If there are multiple answers, print any of them.
Otherwise print "No answer"for that query.

제의

N개의 소문자를 주고 서로 인접한 1의 문자가 존재하지 않고 출력 No answer가 존재하지 않도록 다시 배열합니다

분석

처음에는 이 문제가 dfs라고 고집스럽게 생각했다.왜냐하면 이 Zipper가 검색이나 DP를 기억하거든요.
그리고 DFS는 어디서부터 시작할 것 같습니까?그리고 나서 문제를 뒤집었다.홀수와 짝수가 있는 토론을 발견하다.금방 알게 될 거야.
욕심 많은 생각: 26개의 자모, 자모표의 순서에 따라 기수, 짝수로 나뉜다.기수를 함께 놓으면 반드시 추악한 짝이 나타나지 않을 것이다.짝수를 함께 놓아도 반드시 추악한 짝이 나타나지 않을 것이다.홀수 + 짝수 or 짝수 + 홀수만 봐도
또 다른 사람의 코드를 보러 갔는데, 자신의 코드는 정말 구리고 길다.orz
그렇게 판단할 필요 없잖아.

구리고 긴 코드

심지어 멀티set 때문에.end () 가 위치를 가리키고 WA가 한 번 발생했습니다.

//AC
#include
#include
#include
#include
#include
#include
#include
#include

맏형의 코드 감상

https://blog.csdn.net/a1097304791/article/details/89785158
문자열을 사용하여 판단할 때 두 문자의 차이의 절대값이 1과 같지 않은지 판단하기만 하면 된다.
알파벳이 몇 번이나 나타났는지 기록하기 위해num[]수 그룹을 엽니다.내 멀티셋과 같은 역할을 합니다.

#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1<<30;
const LL maxn = 1e5+10;

int main()
{
    int T, num[30];
    string s, s1, s2;
    cin >> T;
    while(T--){
        ms(num, 0); s1 = s2 = "";
        cin >> s;
        for(int i = 0; i < s.length(); i++)
            ++num[s[i]-'a'];
        for(int i = 0; i < 26; i+=2)
            while(num[i]--) s1 += ('a'+i);
        for(int i = 1; i < 26; i+=2)
            while(num[i]--) s2 += ('a'+i);

        if(abs(s1.back()-s2.front())!=1) cout << s1 << s2 << endl;
        else if(abs(s2.back()-s1.front())!=1) cout << s2 << s1 << endl;
        else cout << "No answer" << endl;
    }

	return 0;
}