牛客周赛 Round 33

A 小红的单词整理

拿到用空格隔开的两个单词。先输出第二个单词，再输出第一个单词。

void solve() {
    string s, ss;cin >> s >> ss;
    cout << ss << "\n" << s << '\n';
}

B 小红煮汤圆

小红前往超市买了 $n$ 袋汤圆，每袋汤圆有 $x$ 颗。小红每次煮 $k$ 颗汤圆，请你计算小红一共可以煮多少次，以及每次会打开几袋？（每次用完了一袋汤圆才会开新的一袋。）

(写的比较痛苦，后面希望再看看)

void solve() {
    int n, x, k;cin >> n >> x >> k;
    vector<int> a;
    int remain = 0;

    while (n > 0) {
        int cost = ceil((k - remain) * 1.0 / x);
        remain = cost * x + remain - k;
        n -= cost;
        if (n >= 0)
            a.push_back(cost);
        while (remain >= k) {
            remain -= k;
            a.push_back(0);
        }
    }
    cout << a.size() << "\n";
    for (auto i : a)cout << i << ' ';cout << '\n';
}

C 小红的 01 串

小红得到了一个 01 串，她可以进行以下两种操作：

• 删除第一个字符。
• 删除第二个字符。

经过一系列操作（可以不操作），就会获得一个最终字符串。字符串中每个 1 会得到 1 分，每个 0 会失去 1 分。小红希望获得最高分，你能帮她算一下吗？

首先将前缀 0 去掉，这样后面就只需要考虑第二个操作(删除第二个字符)即可。

这样就可以先不看第一个 1 字符，将后面的字符看成一个整体，即求一个 01 字符串每次删除第一个字符能获得的最高分

void solve() {
    string s;cin >> s;
    while (s[0] == '0')s.erase(s.begin());
    if (s == "") {
        cout << 0 << '\n';return;
    }
    int cnt = 0;
    vector<int> a(s.size());
    a[s.size() - 1] = (s[s.size() - 1] == '1' ? 1 : -1);
    for (int i = s.size() - 2;i >= 1;i--) {
        a[i] = a[i + 1] + (s[i] == '1' ? 1 : -1);
    }
    int add = 0;
    for (int i = 1;i < s.size();i++) {
        while (s[i] == '0')i++, add++;
        cnt = max(cnt, a[1] + add);
        if (s[i] == '1')add--;
    }
    cout << cnt + 1 << '\n';
}

D 小红的数组清空

小红得到一个数组，她打算用最少的代价清空整个数组。

小红有两种操作：

1. 直接删除一个元素 $x$，代价为 $1$。
2. 如果之前删除的元素是 $x$，那么删除一个元素 $x+1$ 的代价为 $0$。这个操作只能在数组中存在 $x+1$的情况下进行。

请你计算小红清空整个数组的最小代价。

(待更 $\dots$)