题解：CF2092D Mishkin Energizer

Suin_tryin · 2026-03-05 20:00:24 · 题解

感觉做法比较复杂，也有可能是我写太复杂了。

想法是在两个字符之间操作两次可以让其中一个字符个数加 1，缺的那个字符个数加 1。所以每次找一组相邻字符，包含出现最多的字符和出现不是最多的字符，然后操作两次使得出现最多的字符不增加即可。

如果说三种字符两种字符个数相同且第三种没有出现，那只能退一步先随便找一个可以插入的位置插一下。

submission

::::success[代码如下]

#include<iostream>
using namespace std;
int t, n;
char s[310];
int ans[310];
void solve() {
    cin >> n;
    int cntl = 0, cnti = 0, cntt = 0;
    for(int i = 1; i <= n; i ++) {
        cin >> s[i];
        if(s[i] == 'L') cntl ++;
        if(s[i] == 'I') cnti ++;
        if(s[i] == 'T') cntt ++;
    }
    if(cntl == cnti && cntl == cntt) {
        cout << 0 << '\n';
        return;
    }
    int c = (cntl == 0) + (cnti == 0) + (cntt == 0);
    if(c == 2) {
        cout << -1 << '\n';
        return;
    }
    int cnt = 0;
    //cout << cntl << " " << cnti << " " << cntt << '\n';
    while(!(cntl == cnti && cntl == cntt)) {
        int mx = max(cntl, max(cnti, cntt));
        int mn = min(cntl, min(cntl, cntt));
        char c1 = '0', c2 = '0';
        if(mx == cntl) c1 = 'L';
        if(mx == cnti) {if(c1 == '0') c1 = 'I'; else c2 = 'I';}
        if(mx == cntt) {if(c1 == '0') c1 = 'T'; else c2 = 'T';}
        bool flag = 0;
        for(int i = 1; i < n; i ++) {
            if((s[i] == c1 || s[i] == c2) && s[i + 1] != c1 && s[i + 1] != c2) {
                ans[++cnt] = i;
                ans[++cnt] = i;
                for(int j = i + 1; j <= n; j ++)
                    s[j + 2] = s[j];
                n += 2;
                s[i + 1] = s[i + 3];
                s[i + 2] = 'L' + 'I' + 'T' - s[i] - s[i + 1];
                if(s[i + 1] == 'L') cntl ++; if(s[i + 1] == 'I') cnti ++; if(s[i + 1] == 'T') cntt ++;
                if(s[i + 2] == 'L') cntl ++; if(s[i + 2] == 'I') cnti ++; if(s[i + 2] == 'T') cntt ++;
                flag = 1;
                break;
            }
            if((s[i + 1] == c1 || s[i + 1] == c2) && s[i] != c1 && s[i] != c2) {
                ans[++cnt] = i;
                ans[++cnt] = i + 1;
                for(int j = i + 1; j <= n; j ++)
                    s[j + 2] = s[j];
                n += 2;
                s[i + 2] = s[i];
                s[i + 1] = 'L' + 'I' + 'T' - s[i] - s[i + 1];
                if(s[i + 1] == 'L') cntl ++; if(s[i + 1] == 'I') cnti ++; if(s[i + 1] == 'T') cntt ++;
                if(s[i + 2] == 'L') cntl ++; if(s[i + 2] == 'I') cnti ++; if(s[i + 2] == 'T') cntt ++;
                flag = 1;
                break;
            }
        }
        if(!flag) {
            for(int i = 1; i < n; i ++) {
            if(s[i] == c1 && s[i + 1] != s[i]) {
                ans[++cnt] = i;
                ans[++cnt] = i;
                for(int j = i + 1; j <= n; j ++)
                    s[j + 2] = s[j];
                n += 2;
                s[i + 1] = s[i + 3];
                s[i + 2] = 'L' + 'I' + 'T' - s[i] - s[i + 1];
                if(s[i + 1] == 'L') cntl ++; if(s[i + 1] == 'I') cnti ++; if(s[i + 1] == 'T') cntt ++;
                if(s[i + 2] == 'L') cntl ++; if(s[i + 2] == 'I') cnti ++; if(s[i + 2] == 'T') cntt ++;
                flag = 1;
                break;
            }
            if(s[i + 1] == c1 && s[i] != s[i + 1]) {
                ans[++cnt] = i;
                ans[++cnt] = i + 1;
                for(int j = i + 1; j <= n; j ++)
                    s[j + 2] = s[j];
                n += 2;
                s[i + 2] = s[i];
                s[i + 1] = 'L' + 'I' + 'T' - s[i] - s[i + 1];
                if(s[i + 1] == 'L') cntl ++; if(s[i + 1] == 'I') cnti ++; if(s[i + 1] == 'T') cntt ++;
                if(s[i + 2] == 'L') cntl ++; if(s[i + 2] == 'I') cnti ++; if(s[i + 2] == 'T') cntt ++;
                flag = 1;
                break;
            }
        }
        }
    }
    cout << cnt << '\n';
    for(int i = 1; i <= cnt; i ++) cout << ans[i] << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t --) solve();
    return 0;
}

::::