Nowcoder9983H.数字串(构造)

链接:https://ac.nowcoder.com/acm/contest/9983/H
来源:牛客网

牛牛发现了一种方法可以将只包含小写字母的字符串按照以下方式使其转换成一个数字串:
取其中的每个字母,a\mathit aa转换为1\text 11,b\mathit bb转换为2\text 22......z\mathit zz转换为26\text 2626,然后将这些数字拼接起来。
例如,abcz\mathit abczabcz可以转换为12326\text 1232612326。
现在给出一个只包含小写字母的字符串S\mathit SS,你需要找到一个只包含小写字母的字符串T\mathit TT,使得两个串不相同但是能转换成相同的数字串。

一道基础的构造,一开始因为一些细节没写好wa了很多发,智商掉线了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+100;
string s;
string ans1,ans2;
int main () {
    cin>>s;
    string t="";
    int f=0;
    for (int i=0;i<s.size();i++) {
        //printf("%d %c %d\n",i,s[i],s[i]-'a'+1);
        if (f) {
            t.push_back(s[i]);
            continue;
        }
        if (s[i]-'a'+1>10&&(s[i]-'a'+1)%10!=0) {
            f=1;
            int tt=s[i]-'a'+1;
            t.push_back(tt/10+'a'-1);
            t.push_back(tt%10+'a'-1);
        }
        else if (i+1<s.size()&&s[i]-'a'+1<=2&&(s[i+1]-'a'+1)%10!=0) {
            int tt=(s[i]-'a'+1)*10;
            if (s[i+1]-'a'+1<10) tt+=s[i+1]-'a'+1;
            else tt+=(s[i+1]-'a'+1)/10;
            if (tt<=26) {
                f=1;
                t.push_back(tt+'a'-1);
                if (s[i+1]-'a'+1>10)
                    s[i+1]=(s[i+1]-'a'+1)%10-1+'a';
                else
                    i++;
            }
            else {
                t.push_back(s[i]);
            }
        }
        else {
            t.push_back(s[i]);
        }
    }
    if (!f) return printf("-1\n"),0;
//    for (int i=0;i<s.size();i++) {
//        string tt=to_string(s[i]-'a'+1);
//        ans1+=tt;
//    }
//    for (int i=0;i<t.size();i++) {
//        string tt=to_string(t[i]-'a'+1);
//        ans2+=tt;
//    }
//    if (ans1!=ans2) while(1);
    cout<<t<<'\n';
}

 

上一篇:Nowcoder9983I.序列的美观度(线段树+DP)


下一篇:【题解】[Codeforces 914H] Ember and Storm's Tree Game | 20210930 模拟赛 游戏(game)【计数DP】