Codeforces Round #608 (Div. 2) 题解

作者: xht37 分类: 题解 发布时间: 2019-12-15 19:58

点击数:128

Codeforces Round #608 (Div. 2)

Suits

枚举。

int main() {
    ll a, b, c, d, e, f, ans = 0;
    cin >> a >> b >> c >> d >> e >> f;
    for (ll i = 0; i <= d; i++) {
        ans = max(ans, min(a, i) * e + min(min(b, c), d - i) * f);
    }
    cout << ans << endl;
    return 0;
}

Blocks

贪心。

const int N = 207;
int n;
char s[N];

int main() {
    rd(n), rds(s, n);
    vi p;
    for (int i = 2; i < n; i++)
        if (s[i] != s[1]) p.pb(i), s[i] = s[i] == 'B' ? 'W' : 'B', s[i+1] = s[i+1] == 'B' ? 'W' : 'B';
    if (s[1] != s[n]) {
        if (n & 1) {
            for (int i = 1; i < n; i += 2) p.pb(i);
        } else return print(-1), 0;
    }
    print(p.size());
    for (ui i = 0; i < p.size(); i++)
        print(p[i], ' ');
    return 0;
}

Shawarma Tent

贪心。

const int N = 2e5 + 7;
int n, a, b, c[4];

int main() {
    rd(n), rd(a), rd(b);
    for (int i = 1, x, y; i <= n; i++) {
        rd(x), rd(y);
        if (x < a) c[2]++;
        if (x > a) c[3]++;
        if (y < b) c[1]++;
        if (y > b) c[0]++; 
    }
    int o = 0;
    for (int i = 1; i <= 3; i++)
        if (c[i] > c[o]) o = i;
    print(c[o]);
    if (o == 0) print(a, ' '), print(b + 1);
    if (o == 1) print(a, ' '), print(b - 1);
    if (o == 2) print(a - 1, ' '), print(b);
    if (o == 3) print(a + 1, ' '), print(b);
    return 0;
}

Portals

按贡献从大到小贪心,能选就选,用堆维护,判断是否能选时前缀和即可。

const int N = 5e3 + 7;
int n, m, a[N], b[N], p[N], ans;
pq< pi > q;

int main() {
    rd(n), rd(m), rd(b[0]);
    for (int i = 1, x; i <= n; i++)
        rd(a[i-1]), rd(b[i]), b[i] += b[i-1], rd(x), q.push(mp(x, i)), p[i] = i;
    for (int i = n - 1; ~i; i--) b[i] = min(b[i+1], b[i] - a[i]);
    if (b[0] < 0) return print(-1), 0;
    for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), p[y] = max(p[y], x);
    while (q.size()) {
        int x = p[q.top().se], o = q.top().fi;
        q.pop();
        if (b[x]) {
            ans += o;
            for (int i = x; i <= n; i++) --b[i];
            for (int i = x - 1; ~i; i--) b[i] = min(b[i], b[i+1]);
        }
    }
    print(ans);
    return 0;
}

Common Number

把所有有可能的值都算一遍就好了,代码太丑了不贴了。

Divide The Students

题目太长了,不想读。

发表评论

电子邮件地址不会被公开。 必填项已用*标注