AtCoder Beginner Contest 124 解题报告

佚名 5年前 (2019-04-13) 随笔 1540人围观抢沙发百度已收录

去打cometoj的比赛去了qwq然后这场开局就有点晚...
估计小号涨不了啥分。
atc啥时候才有arc啊....

A

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int ans = max(a * 2 - 1, max(b * 2 - 1, a + b));
    cout << ans;
}

B

#include <bits/stdc++.h>
using namespace std;

int f[110], a[110], ans = 0;

int main() {
    int n; cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    int now = 0;
    for(int i = 1; i <= n; ++i) {
        if(now <= a[i]) ++ans;
        now = max(now, a[i]);
    }
    cout << ans;
}

C

合法排列情况就两种...分别模拟取min即可。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 1000100;
char s[N];

int main() {
     scanf("%s", s+1);
     int now = 0, n = strlen(s+1), sum = 0, ans = 0;
     for(int i = 1; i <= n; ++i) {
        now ^= 1;
        if(s[i] - '0' != now) ++ans;
     }
     now = 1;
     for(int i = 1; i <= n; ++i) {
        now ^= 1;
        if(s[i] - '0' != now) ++sum;
     }
     printf("%d\n", min(ans, sum));
}

D

一开始看错题意写了个堆求1的最多次数的。然后发现是连续的，这个玩意是有单调性的所以直接双指针/二分即可。注意要先缩点，把相同的缩成一块不然不好算。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
char s[N];
int a[N], op[N], tot[N];

int main() {
    int n, k, cnt = 0, sum = 0; cin >> n >> k;
    scanf("%s", s+1);
    for(int i = 1; i <= n + 1; ++i) {
        if(s[i] != s[i - 1] && i - 1) {
            a[++cnt] = sum;
            op[cnt] = s[i - 1] - '0';
            sum = 0;
        }
        ++sum;
    }
    memset(tot, 0, sizeof(tot));
    for(int i = 1; i <= cnt; ++i) {
        if(!op[i]) tot[i] = tot[i - 1] + 1; else tot[i] = tot[i - 1];
        a[i] += a[i - 1];
    }
    int ans = 0;
    for(int l = 0, r = 1; r <= cnt; ++r) {
        while(l < r && tot[r] - tot[l - 1] > k) ++l;
        ans = max(ans, a[r] - a[l - 1]);
    }
    printf("%d\n", ans);
}