模拟测验（一）双色球 做题笔记

题面

思路

50 pts

暴力。我们发现每次操作等于将前面的红的变成蓝的，将第一个蓝的变成红的。

要养成写暴力的好习惯。

#include <bits/stdc++.h>

using namespace std;
/*
*/
int n; string s;
int cnt = 0;
bool check() {
    for (int i = 0; i < s.size(); i ++) if (s[i] != 'R') return false;
    return true;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    // freopen("out.out", "r", stdin);
    cin >> n >> s;
    while (!check()) {
        int i;
        for (i = 0; i < s.size() && s[i] != 'B'; i ++) s[i] = 'B';
        s[i] = 'R';
        cnt ++;
        if (cnt <= 20) cout << s << "\n";
    }
    cout << cnt;
    return 0;
}

100 pts

我们可以通过暴力的输出推断出，设第一个蓝的前面有 $x$ 个红的，那么我们需要花费 $2 ^ x$ 次操作才能消除这个蓝的。

#include <bits/stdc++.h>

using namespace std;
/*
*/
int n; string s;
long long cnt = 0;
bool check() {
    for (int i = 0; i < s.size(); i ++) if (s[i] != 'R') return false;
    return true;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    // freopen("out.out", "r", stdin);
    cin >> n >> s;
    while (!check()) {
        int i;
        for (i = 0; i < s.size() && s[i] != 'B'; i ++) s[i] = 'R';
        s[i] = 'R';
        cnt += pow(2, i);
        // cout << s << "\n";
    }
    cout << cnt;
    return 0;
}   

总结

一道比较简单的数学题。