AtCoder Beginner Contest 124

目录

• A - Buttons
• B - Great Ocean View
• C - Coloring Colorfully
• D - Handstand

A - Buttons

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
typedef long long LL;
int a, b;
int main(){
    cin>>a>>b;
    cout << max({a + a - 1, b + b - 1, a + b}) << endl;
    return 0;
} 

B - Great Ocean View

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
typedef long long LL;

int main() {
    int n;
    cin >> n;
    int maxn = 0;
    int res = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin>>x;
        if (x >= maxn) maxn=x, res++;
    }
    cout << res << endl;
    return 0;
}

C - Coloring Colorfully

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
typedef long long LL;
int n;
string s;
int main() {
    cin >> s;
    int res1 = 0, res2 = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '0' && (i % 2 == 0)) res1++;
        if (s[i] == '1' && (i % 2 == 1)) res1++;
    }
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '0' && (i % 2 == 1)) res2++;
        if (s[i] == '1' && (i % 2 == 0)) res2++;
    }
    cout << min(res1, res2) << endl;
    return 0;
}

D - Handstand

给出n个数的01串，每次可以选择一个区间，使得区间内的所有值从0变1，从1变0，问最多进行k次操作，可以获得的最长的连续1区间是多长

本题可以转化为k+1个连续1区间加起来有多长（包括各个区间之间的0区间）

所以只需要分割出每个1区间，然后算每个区间与前k个区间的长度即可，注意前导0和后缀0的边界条件即可

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
typedef long long LL;
int n, k;
char a[N];
struct node {
    int l, r;
} q[N];
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int cnt = 1;
    if (a[0] == '1') q[1].l = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] != a[i - 1] && a[i] == '0') {
            q[cnt++].r = i-1;
        } else if (a[i] != a[i - 1] && a[i] == '1') {
            q[cnt].l = i;
        }
    }
    if (a[n - 1] == '1') q[cnt++].r = n - 1;
    q[0].l = 0, q[0].r = q[1].l - 1;
    q[cnt].l = q[cnt - 1].r + 1, q[cnt].r = n - 1;
    int res = 0;
    for (int i = 1; i < cnt; i++) {
        int pre = max(1, i - k);
        res = max(res, q[i].r - q[pre].l + 1);
    }
    res = max(res, q[min(k, cnt)].r + 1);
    res = max(res, n - 1 - q[max(0, cnt - k)].l + 1);
    cout << res << endl;
    return 0;
}