3451. 易位构词

LzQuarter
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
int cnt[26] ={0};
stack<char> sta[26];
int fun(char a, char b){
    return a < b;
}
int main(){
    string str;
    cin >> str;
    int i;
    int possible = 1;
    for(i = 0; i < str.length(); i++){
        char temp = str[i];
        cnt[(int)temp-(int)'a']++;
    }
    int maxd = 0;
    char strarr[100001];
    for(i = 0; i < 26; i++){
        maxd = cnt[i] > maxd ? cnt[i] : maxd;
        if(cnt[i] > str.length() / 2){
            possible = 0;
        }
    }
    if(!possible){
        cout << "impossible" << endl;
    }
    else{
        for(i = 0; i < str.length(); i++){
            strarr[i] = str[i];
        }
        sort(strarr, strarr + str.length(), fun);
        for(i = 0; i < str.length(); i++){
            sta[(int)strarr[i] - (int)'a'].push(strarr[(i+maxd)%str.length()]);
        }
        for(i = 0; i < str.length(); i++){
            char temp = str[i];
            cout << sta[(int)temp-(int)'a'].top();
            sta[(int)temp-(int)'a'].pop();
        }
        cout << endl;
    }
    return 0;
}

代码仅供A题
一种可行的替换方案是将所有字符排序,每个字符都用其后的第x个字符代换,x为最多的那个字符的数量。再将这种替换关系代回原串中。

改个名字吧

该替换方案的代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct C{
    char c;
    int num;
};
int cmp(const C&a,const C&b){return a.c<b.c;}
int main()
{
    int n[26]={0};
    char s[100005];
    cin>>s;
    int len=strlen(s);
    C c[len];
    for(int i=0;i<len;i++)
    {
        n[s[i]-'a']++;
        c[i].c=s[i];
        c[i].num=i;
    }

    int x=0;
    for(int i=0;i<26;i++)
    {
        if(n[i]>len/2){printf("impossible");return 0;}//特判不可能的情况 
        if(n[i]>x) x=n[i];  
    }

    sort(c,c+len,cmp);
    for(int i=0;i<len;i++)
        s[c[i].num]=c[(i+x)%len].c;
    cout<<s;
}
LzQuarter

补充说明一下,这个构造法是基于这样一个显而易见的事实的:原串可以易位构词 <=> 按照字符数目从大到小进行重排的串可以易位构词
重排演示:ababa => aaabb

你当前正在回复 博客/题目
存在问题!