998——Codeforces Round #493 (Div. 2)

http://codeforces.com/contest/998

codeforces

2018.7.1参加（A,B,C）
2018.7.2整理

A：模拟
B：找到所有可以分割的点，从小的取。
C：两种情况讨论。

A

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int a[1000];
int main () {
    int n = read(),sum = 0;
    for (int i=1; i<=n; ++i) {
        a[i] = read();sum += a[i];
    }
    if (n == 1) {
        return !printf("-1");
    }
    if (n==2) {
        if (a[1] == a[2]) printf("-1");
        else printf("1\n1");
        return 0;
    }
    for (int i=1; i<=n; ++i) {
        if (a[i] != sum-a[i]) {
            printf("1\n%d",i);return 0;
        }
    }
    return 0;
}

B

/*
10 3
4 1 2 3 4 5 4 4 5 5
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int a[1010],f[1010];
int main () {
    int n = read(),B = read();
    for (int i=1; i<=n; ++i) a[i] = read();
    int c1 = 0,c2 = 0;
    if (a[1] & 1) c1++;
    else c2++;
    int tot = 0;
    for (int i=2; i<n; ++i) {
        if (a[i] & 1) c1++;
        else c2++;
        if (c1 == c2) {
            f[++tot] = abs(a[i+1] - a[i]); // a[i+1]-a[i] 不是 a[i]-a[i-1]
            c1 = 0,c2 = 0;
        }
    }
    sort(f+1,f+tot+1);
    int cnt = 0,ans = 0;
    for (int i=1; i<=tot; ++i) {
        if (ans + f[i] <= B) ans += f[i],cnt ++;
    }
    cout << cnt;
    return 0;
}

C

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
char s[500000];
int main () {
    int n = read(),x = read(),y = read();
    scanf("%s",s+1);
    int cnt = 0;
    LL ans1 = 0,ans2 = 0;
        cnt = 0;
        s[0] = '#';
        for (int i=1; i<=n; ++i) {
            if (s[i] == '0') {
                cnt ++;
                if (s[i] == s[i-1]) cnt--;
            }
        }
    if (cnt == 0) {cout << 0; return 0;}
    if (cnt == 1) {cout << y;return 0;}
    if (x < y) ans1 = 1ll * (cnt - 1) * x + y;
    else ans1 = 1ll * cnt * y;
    cout << ans1;
    return 0;   
    /*if (x >= y) {
        cnt = 0;
        s[0] = '#';
        for (int i=1; i<=n; ++i) {
            if (s[i] == '0') {
                cnt ++;
                if (s[i] == s[i-1]) cnt--;
            }
        }
        ans1 = 1ll * cnt * y;
        cout << ans1;
        //return 0;
    }
    else {
        cnt = 0;
        s[0] = '#';
        for (int i=1; i<=n; ++i) {
            if (s[i] == '1') {
                cnt ++;
                if (s[i] == s[i-1]) cnt--;
            }
        }
        if (s[1] == '1') cnt--;
        if (s[n] == '1') cnt--;
        if (cnt < 0) {cout << 0;return 0;}
        ans2 = cnt * x + y;
        cout << ans2;
    }*/
    return 0;
}
/*
9 3 2
101010101
*/