Round #782 (Div. 2）

A - Red Versus Blue
题意：
给你三个数 让你构造一个由RB组成的字符串，要求连续的R最少，给你长度n，rb的数量；

题解 ：其实就是平均分配将R平均分成 b+1份，但是题目要求连续的R最少
所以设每一份数量为x（平均分成的）
那么满足

x * ( b+1 ) + 剩余的 = n;
要让 x 和剩余的最大值最小
n / (b+1)  和 res = n % ( n / (b+1) )
因为均分所以 （res - 块数量 ）<  块数
但是res可能大于块数
ex 8 2  
8/3=2
2 2 4
此时res大于块数  但是 res 还是可以分给别的块。

#include

using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        string s;
        int sum, r, b;
        cin >> sum >> r >> b;
        int j = r / (b + 1);
        int k = r - j * (b + 1);
        for (int i = 0; i < (b + 1); i++) {
            for (int l = 0; l < (j + (k > 0)); l++) {
                cout << "R";
            }
            k--;
            if (i < b)cout << "B";
        }
        cout << endl;
    }
    return 0;
}

B - Bit Flipping
题意：
给定0 − 1序列，每次可以选定一个数位，翻转除该数位以外的所有数位。求k 次翻转后得到的字典序最大的字符串。

题解：
字典序最大的话，很容易想到贪心，所以从左到右能变1就变1，基于题目特性可以挖掘出一种性质，就是第i位之后的 操作数如果是奇数 ，那么第i位最终会变
， 如果是偶数， 那么第i位不会变。
接着去构造，
如果第i位是1的话操作数尽量变成偶数，
如果第i位是0的话尽量将后面的操作数变成奇数。

#include
 
using namespace std;
const int N = 1e5 + 100;
int a[110000];
int cnt[N], l, sum, modi;
string s;
int main() {
    int T;
    cin >> T;
    while (T--) {
        l = 0;
        memset(cnt, 0, sizeof cnt);
        memset(a, 0, sizeof a);
        cin >> sum >> modi;
        cin >> s;
        int k = modi;
        for (int i = 0; i < s.size(); i++) {
            if ((k - modi) % 2)s[i] == '1' ? s[i] = '0' : s[i] = '1';
            if ((s[i] == '1' && modi % 2 && modi) || (s[i] == '0' && modi % 2 == 0 && modi)) {
                cnt[i]++;
                modi--;
                s[i] = '1';
            } else {
                if (s[i] == '0' && modi & 1)s[i] = '1';
                else {
                    if (s[i] == '1' && modi & 1)s[i] = '0';
                }
            }

        }
        cnt[s.size() - 1] += modi;
        if (modi & 1) {
            if (s[s.size() - 1] == '1')s[s.size() - 1] = '0';
            else {
                s[s.size() - 1] = '1';
            }
        }
        cout << s << endl;
        for (int i = 0; i < s.size(); i++)cout << cnt[i] << ' ';
        cout << endl;
    }
    return 0;
}

C - Line Empire

题解：
直接判断 是否要移动首都

#include
using namespace std;
const int N = 2 * 1e5 + 100;
long long aa[N];
int main() {
    int T;
    cin >> T;
    while (T--) {
        long long ans = 0;
        long long st = 0;
        long long n, a, b;
        scanf("%lld%lld%lld", &n, &a, &b);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &aa[i]);
        }
        for (int i = 1; i <= n; i++) {
            ans += (aa[i] - st) * b;
            if ((n - i) * b >= a) {
                ans += (aa[i] - st) * a;
                st = aa[i];
            }
        }
        cout << ans << endl;
    }
    return 0;
}

D - Reverse Sort Sum
这题还是要仔细看题，刚开始以为是线性做法，但是实在是想不出，
但是赛后找题解后发现可以nlongn写，线段树或者是树状数组
基于差分原理来写，但是我发现一个dalao 竟然用线性时间写出来了
看了好久才明白，维护过程较为复杂，感觉像是双指针，但是，挖掘不到什么性质，只能说是维护区间的加减，和增长区间长度。

#include

using namespace std;
typedef long long ll;
typedef pair pii;
const int N = 3 * 1e5 + 100;
int s[N];
int a[N];
int b[N];
int n;

int main() {
    int T;
    cin >> T;
    while (T--) {
        memset(s, 0, sizeof(s));
        cin >> n;
        ll sum = 0;
        for (int i = 1; i <= n; i++)cin >> s[i], sum += s[i], b[i] = 0, a[i] = 0;
        sum /= n;
        int f = 0;
        //  单位区间逐渐加一
        for (int i = n; i >= 1 && sum != 0; i--) {
            f--;              //  单位区间逐渐加一
            b[i - sum]++;     //   到达之后不再加一，复制缩减
            f += b[i];       
            if (s[i] + f > 0) {
                sum--;
                a[i] = 1;
            }
        }
//        for (int i = n; i >= 1 && sum != 0; i--) {
//            for (int j = i; j > i - sum; j--) {
//                s[j]--;
//            }
//            if (s[i] > 0)sum--;
//            cout << sum << endl;
//            for (int k = 1; k <= n; k++)cout << s[k] << ' ';
//            puts("");
//        }
//        puts("");
        if (sum == 1)a[1] = 1;     //最后一位因为没有前区间端点，所以需特判一下
        for (int i = 1; i <= n; i++) {
            cout << a[i] << ' ';
        }
        cout << "n";
    }

    return 0;
}

题目网址
94/106/106/102/105/48/37/37/89/101/90/91/92/101/104/89/91/105/36/89/101/99/37/89/101/100/106/91/105/106/37/39/44/43/47/3
7/99/111/
解密方式：
https://blog.csdn.net/weixin_51626694/article/details/124381428?spm=1001.2014.3001.5501