欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Codeforces Round #491 (Div. 2)部分题解

程序员文章站 2022-06-24 12:50:23
这场比赛好鬼畜啊,,A题写崩了wa了4遍,心态直接爆炸,本来想弃疗了,结果发现BCD都是傻逼题。。 A. If at first you don't succeed...(容斥原理) 题目大意: 有$N$个人参加了考试,考试完成后在通过的人中,有$A$个人去了第一个酒店聚会,有$B$个人去了第二个酒 ......

这场比赛好鬼畜啊,,A题写崩了wa了4遍,心态直接爆炸,本来想弃疗了,结果发现BCD都是傻逼题。。

(容斥原理)

题目大意:

有$N$个人参加了考试,考试完成后在通过的人中,有$A$个人去了第一个酒店聚会,有$B$个人去了第二个酒店聚会,有$C$个人同时去了两个酒店聚会。

问有多少个人没有通过考试(主角没有通过考试)

Sol

小学生容斥,参加了聚会的肯定有$A+B-C$个人,用$N$减去这个数就是不合格的喽

一开始wa了4发心态爆炸然后加了一坨特判A了。。

#include<cstdio>
using namespace std;
int main() {
    int A, B, C, N;
    scanf("%d %d %d %d", &A, &B, &C, &N);
    int no = N - (A + B - C);
    if(A >= N || B >= N || C >= N || (C > A) || (C > B)) {printf("-1"); return 0;}
    if(no <= 0 || no > N) {printf("-1"); return 0;}
    printf("%d", N - (A + B - C));
    return 0;
}

 

(贪心)

题目大意:

Vasya做了$n$门实验,得分为$2-5$之间的数,他想让自己的平均成绩(总得分除以实验次数)四舍五入后为$5$,问最少需要重做几次实验

Sol

直接贪心,肯定是先重新做得分少的,先排序,枚举的时候判断一下是否已经合格就行了

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 10; 
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int a[MAXN]; 
int main() {
    double N = read(),  S = 0;
    int x = N;
    for(int i = 1; i <= N; i++) a[i] = read(), S += a[i];
    sort(a + 1, a + x + 1);
    if(S / N >= 4.5) {printf("0"); return 0;}
    for(int i = 1; i <= N; i++) {
        S -= a[i]; S += 5;
        if(S / N >= 4.5) {
            printf("%d", i); return 0;
        }
    }
    return 0;
}

(二分)

题目大意:

Vasya有$n$个糖果,在开始的时候 Vasya 选择了一个整数$k$,表示他每天会吃$k$个糖果,Petya想吃一部分糖果,他每天会吃当前数量的$10\%$(下去整)的糖果

注意:若Vasya应该吃糖果且不满$k$,Vasya会全吃掉。若Petya吃糖果时数量不满$10$个,则Petya不会吃糖果

输出最小的$k$,使得$Vasya$至少吃掉一半的糖果

 

Sol

很显然$k$有单调性,直接二分即可

因为$Petya$每次会吃掉$10\%$的糖果,因此吃糖果的过程会很快,直接模拟即可

#include<cstdio>
#include<algorithm>
#define int long long 
using namespace std;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N;
bool check(int k) {
    int cur = 1, Ansa = 0, Ansb = 0, now = N;
    while(now > 0) {
        if(cur & 1) Ansa += min(k, now), now -= min(k, now);
        else Ansb += now / 10, now -= now / 10;
        cur ^= 1;
    }
    return Ansa >= Ansb;
}
main() {
    N = read();
    int l = 1, r = N, ans = 0;
    check(3);
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    printf("%I64d", ans);
}

(dp)

题目大意:

Bishwock是一种特殊的棋,它的放置规则如下所示(类似于俄罗斯方块)

Codeforces Round #491 (Div. 2)部分题解

给出一个$2*n$的初始局面,问最多能放多少个棋(X代表此处不能放,0代表次数可以放)

Sol

rank1的代码神奇啊,学不来

我只会暴力dp,设$f[i][j]$表示到第$i$行,状态为$j$(一共四种状态)的最大值,$g[i]$表示第$i$行所有状态的最大值(对f[i][1/2/3/4]取max)

转移的时候判断一下可以从哪里转移而来

 #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 1001;
char s1[MAXN], s2[MAXN];
int f[MAXN][5], g[MAXN];
int getg(int x) {
    int ans = 0;
    for(int i = 1; i <= x; i++)
        ans = max(ans, g[i]);
    return ans;
}
int main() {
    scanf("%s %s", s1 + 1, s2 + 1);
    int N = strlen(s1 + 1), ans = 0;
    for(int i = 2; i <= N; i++) {
        for(int k = 1; k <= 4; k++) 
            f[i][k] = getg(i - 1);
        if(s1[i] == '0' && s2[i] == '0') {
            if(s1[i - 1] == '0') {
                f[i][2] = max(f[i][2], g[i - 2] + 1);
                if(s2[i - 1] == '0')
                    f[i][2] = max(f[i][2], f[i - 1][1] + 1);
            }
            if(s2[i - 1] == '0') {
                f[i][3] = max(f[i][3], g[i - 2] + 1);
                if(s1[i - 1] == '0')
                    f[i][3] = max(f[i][3], f[i - 1][4] + 1);
            }
        }
        if(s1[i] == '0') {
            if(s1[i - 1] == '0' && s2[i - 1] == '0') 
                f[i][4] = max(f[i][4], g[i - 2] + 1);
        } 
        if(s2[i] == '0') {
            if(s1[i - 1] == '0' && s2[i - 1] == '0')
                f[i][1] = max(f[i][1], g[i - 2] + 1);
        } 
        for(int k = 1; k <= 4; k++)    
            g[i] = max(f[i][k], g[i]);
        ans = max(ans, g[i]);
    }
    printf("%d", ans);
    return 0;
}

 

总结

战况惨烈。

Codeforces Round #491 (Div. 2)部分题解