Written by @Yue_chen

题意：

给定一个长度为 n 的仅包含 'd' 和 'p' 字符串 s。

对于这个字符串的任意子串s[l, r]，你可以180°翻转它（相当于先reverse 然后 'p'会变成‘d’, 'd'会变成'p')，得到F(s[l, r])

然后你可以选择任意一个子串，用他的F(s[l, r]) 替换 s[l, r]，求最小字典序的串。

当然也可以不操作。

思路：

看见最小字典序直接贪心。

从前到后找第一个不是 d 的位置，然后将该位置固定为左端点 l ，枚举右端点 r ，

依次尝试把F(s[l,r])替换进来，对答案取min。

时间复杂度O(n2)

AC代码：

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
    int n; cin>>n;
    string s; cin>>s;
    
    string ans = s;
    string a1 = s;
    for(int i=0; i<n; ++i) {
        if(a1[i] == 'p') {
            for(int j=i; j<n; ++j) {
                for(int k=i; k<=j; ++k) {
                    a1[k] = (s[j+i-k]=='p'?'d':'p');
                }
                ans = min(ans, a1);
            }
            break;
        }
    }
   
    cout<<ans<<"\n";
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1; //cin>>t;
    while (t--) solve();
    return 0;
}