欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【Codeforces Round #519 by Botan Investments C】 Smallest Word

程序员文章站 2022-05-09 17:41:52
...

【链接】 我是链接,点我呀:)
【题意】

【题解】


模拟了一两下。。
然后发现。
对于每一个前缀。
组成的新的最小字典序的字符串
要么是s[i]+reverse(前i-1个字符经过操作形成的最大字典序的字符串);或者是 (前i-1个字符经过操作形成的最小字典序的字符串)+s[i]
因为最大字典序,翻转一下,然后把s[i]放前面。。显然更可能得到较小字典序的字符串。
这个最大字典序的字符串类似处理一下就Ok.

【代码】

#include <bits/stdc++.h>
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)

using namespace std;

const int N = 1000;

string s;
string tempma = "",tempmi ="";
string ma,mi;
vector<int> v1,v2,tv1,tv2;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> s;
    for (int i = 0;i < (int)s.size();i++){
        ma = tempma + s[i];mi = tempmi + s[i];
        v1.push_back(0);v2.push_back(0);
        tv1 = v1;tv2 = v2;
        //no operation

        reverse(tempmi.begin(),tempmi.end());
        if (ma<s[i]+tempmi){
            v1 = tv2;
            v1[(int)v1.size()-1] = 1;
            ma = s[i]+tempmi;
        }

        reverse(tempma.begin(),tempma.end());
        if (mi>s[i]+tempma){
            v2 = tv1;
            v2[(int)v2.size()-1] = 1;
            mi = s[i]+tempma;
        }
        tempmi = mi;tempma = ma;
    }
    for (int i = 0;i < (int)v2.size();i++){
        cout<<v2[i]<<' ';
    }
    return 0;
}