P13132 Saving The Universe Again

yongqian123 · 2025-07-09 19:43:50 · 题解

无脑打框架

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

#define int long long
#define io ios::sync_with_stdio(0), cin.tie(), cout.tie()
//
int T, D, c, s, y; //
string P;
void out(int x){
    //
    cout << "Case #" << x << ": " << y << '\n';
}
signed main(){
    io;
    cin >> T;
    for (int x = 1; x <= T; x++){
        //
        c = s = y = 0;
        cin >> D >> P;
        //
        out(x);
    }return 0;
}

分析

二进制。每个 S 前面有多少 C，damage（损害）就增加 2 的多少次方。

发现每次都将最后一个 CS 交换，这是因为贪心，想要最大程度地减少 damage，这时 damage 减少这个 S 对应的 damage 的一半。

于是开一个 p 数组存每个 S 对应的 damage。

const int _P_l = 30;
int p[_P_l];

想让 damage\le D，循环：

while (s > D){
    //
}if (s > D){cout << "Case #" << x << ": IMPOSSIBLE\n"; return;}

穿插介绍一个函数 rfind，用于找最后一个……的首字符位置。

如 P.rfind("CS") 返回最后一个 \texttt{CS} 的 \texttt{C} 的位置。

于是，out 函数就写好了：

void out(int x){
    while (s > D){
        pos = P.rfind("CS");
        if (pos == string::npos){cout << "Case #" << x << ": IMPOSSIBLE\n"; return;}
        P[pos] = 'S', P[pos + 1] = 'C', s -= 1 << (p[pos] = p[pos + 1] - 1), p[pos + 1] = 0, y++;
    }if (s > D){cout << "Case #" << x << ": IMPOSSIBLE\n"; return;}
    cout << "Case #" << x << ": " << y << '\n';
}

别忘记清空 p：

memset(p, 0, sizeof p);

完整代码

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

#define int long long
#define io ios::sync_with_stdio(0), cin.tie(), cout.tie()
const int _P_l = 30;
int T, D, c, s, y, pos, p[_P_l];
string P;
void out(int x){
    while (s > D){
        pos = P.rfind("CS");
        if (pos == string::npos){cout << "Case #" << x << ": IMPOSSIBLE\n"; return;}
        P[pos] = 'S', P[pos + 1] = 'C', s -= 1 << (p[pos] = p[pos + 1] - 1), p[pos + 1] = 0, y++;
    }if (s > D){cout << "Case #" << x << ": IMPOSSIBLE\n"; return;}
    cout << "Case #" << x << ": " << y << '\n';
}
signed main(){
    io;
    cin >> T;
    for (int x = 1; x <= T; x++){
        memset(p, 0, sizeof p);
        c = s = y = 0;
        cin >> D >> P;
        for (int i = 0; i < P.size(); i++) if (P[i] == 'C') c++; else s += 1 << c, p[i] = c;
        out(x);
    }return 0;
}