Codeforces题解｜1369B - AccurateLee

题目信息 📚

【题目描述】

Lee was cleaning his house for the party when he found a messy string under the carpets. Now he’d like to make it clean accurately and in a stylish way…

The string $s$ he found is a binary string of length $n$ (i.e., the string consists only of 0s and 1s).

In one move, he can choose two consecutive characters $s_i$ and $s_{i+1}$, and if $s_i$ is 1 and $s_{i+1}$ is 0, he can erase exactly one of them (he can choose which one to erase but can’t erase both characters simultaneously). The string shrinks after erasing.

Lee can make an arbitrary number of moves (possibly zero) and he’d like to make the string $s$ as clean as possible. He thinks for two different strings $x$ and $y$, the shorter string is cleaner, and if they are the same length, then the lexicographically smaller string is cleaner.

Now you should answer $t$ test cases: for the $i$-th test case, print the cleanest possible string that Lee can get by doing some number of moves.

Small reminder: if we have two strings $x$ and $y$ of the same length then $x$ is lexicographically smaller than $y$ if there is a position $i$ such that $x_1=y_1, x_2=y_2,\ldots, x_{i-1}=y_{i-1}$ and $x_i < y_i$.

【输入】

The first line contains the integer $t$ $(1 \leq t \leq 10^4)$ — the number of test cases.

Next $2t$ lines contain test cases — one per two lines.

The first line of each test case contains the integer $n$ $(1 \leq n \leq 10^5)$ — the length of the string $s$.

The second line contains the binary string $s$. The string $s$ is a string of length $n$ which consists only of zeroes and ones.

It’s guaranteed that the sum of $n$ over test cases doesn’t exceed $10^5$.

【输出】

Print $t$ answers — one per test case.

The answer to the $i$-th test case is the cleanest string Lee can get after doing some number of moves (possibly zero).

【输入样例1】

【输出样例1】

3
2

【提示】

In the first test case, Lee can’t perform any moves.

In the second test case, Lee should erase $s_2$.

In the third test case, Lee can make moves, for example, in the following order: $11001101 \rightarrow 1100101 \rightarrow 110101 \rightarrow 10101 \rightarrow 1101 \rightarrow 101 \rightarrow 01$.

【题目来源】

https://codeforces.com/problemset/problem/1369/B#

题目解析 🍉

【题目分析】

思维题。

找到 s 中最左边的 1，与最右边的 0，这个区间可以消去为 0。

【C++代码】✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;

void solve() {
    string s;
    cin >> n >> s;

    // 寻找s最右边的0
    int right_zero = -1;
    for (int i = s.size() - 1; i >= 0; i--) {
        if (s[i] == '0') {
            right_zero = i;
            break;
        }
    }

    // 寻找s最左边的1
    int left_one = -1;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '1') {
            left_one = i;
            break;
        }
    }

    // 输出结果
    if (left_one == -1 || right_zero == -1 || (left_one > right_zero)) {
        // 不存在消去区间，直接原样输出s
        cout << s << endl;
    } else if (left_one < right_zero) {  // 存在消去区间
        // [0, left_one) 原样输出
        for (int i = 0; i < left_one; i++) cout << s[i];
        // 在[left_one, right_zero]区间内的字符，均可以被消去，最后为0
        cout << '0';
        // (right_zero, s.size()-1]原样输出
        for (int i = right_zero + 1; i < s.size(); i++) cout << s[i];
        cout << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }

    return 0;
}

【C++代码】jangly大神の优雅代码

 #include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--) {
        int n;
        std::cin >> n;
        std::string s;
        std::cin >> s;
        int i = 0, j = n;
        while (i < n && s[i] == '0')
            ++i;
        while (j > 0 && s[j - 1] == '1')
            --j;
        if (i == j) {
            std::cout << s << "\n";
        } else {
            std::cout << s.substr(0, i) + '0' + s.substr(j) << "\n";
        }
    }
    return 0;
}