@Dmaxiya 2018-08-17T10:25:11.000000Z 字数 6611 阅读 1167

Codeforces Round #491 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #491 (Div. 2)
过题数：5
排名：384/7193

A. If at first you don't succeed...

题意

有 $A$ 个人去第一家餐厅， $B$ 个人去第二家餐厅， $C$ 个人两家餐厅都去，总共有 $N$ 个人，已经知道至少有一个人两家餐厅都不去，问 $A~B~C~N$ 是否是合法的，如果不合法，输出 $-1$ ，否则输出有多少个人两家餐厅都不去。

输入

输入为四个整数 $A,B,C,N~(0\leq A,B,C,N\leq100)$ 。

输出

输出有多少个人两家餐厅都没去，如果输入的数字是不合法的，就输出 $-1$ /。

样例

输入	输出	提示
10 10 5 20	5	符合这组数据的情况是： $5$ 个人只去第一家餐厅， $5$ 个人只去第二家餐厅， $5$ 个人两家餐厅都去了， $5$ 个人两家餐厅都没去。
2 2 0 4	-1	假设有 $2$ 个人只去第一家餐厅， $2$ 个人只去第二家餐厅，没有人两家餐厅都去，总共只有 $4$ 个人，说明没有人两家餐厅都不去，与题意不符。
2 2 2 1	-1	去餐厅的人数比总人数多，这是不可能出现的情况。

题解

首先应该满足 $c\leq\min(A,B)$ ，在满足该条件的情况下，可以由 $N-(A+B-C)$ 计算出两家餐厅都不去的人数，这个人数应该不小于 $1$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
typedef long long LL;
int A, B, C, N;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d%d", &A, &B, &C, &N) != EOF) {
        if(C > min(A, B)) {
            printf("-1\n");
            continue;
        }
        int tmp = (A + B) - C;
        tmp = N - tmp;
        if(tmp < 1) {
            printf("-1\n");
        } else {
            printf("%d\n", tmp);
        }
    }
    return 0;
}

B. Getting an A

题意

给定 $n$ 个分数，分数只有 $5~4~3~2$ 四种， $Vasya$ 可以修改其中的一些分数，问他最少修改多少个分数，可以使得这些分数的平均分等于 $5$ ，平均分的计算方式为所有分数的和除以 $n$ 之后四舍五入到整数位。

输入

第一行为一个整数 $n~(1\leq n\leq100)$ ，第二行包含 $n$ 个整数，每个整数都在区间 $[2,5]$ 内。

输出

输出应该修改的最少的分数个数。

样例

输入	输出	提示
3 4 4 4	2	只要修改其中的两个 $4$ 为 $5$ ，就可以使平均分为 $5$ 。
4 5 4 5 5	0	$Vasya$ 的平均分已经达到了 $4.75\approx5$ ，所以不用修改任何分数。
4 5 3 3 5	1	$Vasya$ 可以将其中一个 $3$ 修改为 $5$ ，这样他的平均分就可以达到 $4.5\approx5$ 。

题解

贪心地从最低的分数开始修改，因为修改最低分才能使总分提高得最多，只要使总分达到 $4.5\times n$ ，就能使平均分达到 $4.5\approx5$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
typedef long long LL;
const int maxn = 100 + 100;
int n;
int num[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        int ans = 0;
        double sum = 0;
        double tot = n * 4.5;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
            sum += num[i];
        }
        sort(num, num + n);
        for(int i = 0; i < n; ++i) {
            if(sum >= tot) {
                break;
            }
            sum += 5 - num[i];
            ++ans;
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Candies

题意

最初有 $n$ 个糖果， $Vasya$ 和 $Petya$ 分这些糖果， $Vasya$ 每个白天吃 $k$ 个糖果， $Petya$ 晚上吃剩下的糖果中的 $\frac{1}{10}$ （向下取整，比如 $97$ 的 $\frac{1}{10}$ 等于 $9$ ， $9$ 的 $\frac{1}{10}$ 等于 $0$ ）个糖果，如果糖果没有吃完，第二天、第三天继续……直到吃完糖果，如果剩下的糖果数量少于 $k$ 个，那么 $Vasya$ 就会把剩下的糖果全部吃完，问 $Vasya$ 每天最少要吃多少个，才能使他吃的糖果数量至少为 $n$ 的 $\frac{1}{2}$ 。

输入

输入只有一个整数 $n~(1\leq n\leq10^{18})$ 。

输出

输出 $Vasya$ 每天至少要吃的糖果数 $k$ 。

样例

输入	输出	提示
68	3	当 $k=3$ 时，糖果数量的变化为： $68\rightarrow65\rightarrow59\rightarrow56\rightarrow51\rightarrow48\rightarrow44\rightarrow41\rightarrow37\rightarrow34$ $\rightarrow31\rightarrow28\rightarrow26\rightarrow23\rightarrow21\rightarrow18\rightarrow17\rightarrow14\rightarrow13$ $\rightarrow10\rightarrow9\rightarrow6\rightarrow6\rightarrow3\rightarrow3\rightarrow0$ 此时 $Vasya$ 可以吃到 $39$ 个糖果而 $Petya$ 只能吃到 $29$ 个。

题解

由于答案 $k$ 满足二分性质（ $k$ 越大 $Vasya$ 可以吃到的糖果数量越多），所以可以通过二分 $k$ 来得到答案。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
typedef long long LL;
LL n;
bool judge(LL k, LL nn) {
    LL a, b;
    a = b = 0;
    while(nn != 0) {
        if(nn >= k) {
            a += k;
            nn -= k;
        } else {
            a += nn;
            nn = 0;
        }
        LL tmp = nn / 10;
        b += tmp;
        nn -= tmp;
    }
    return a >= b;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%I64d", &n) != EOF) {
        LL high = n;
        LL low = 0;
        LL mid;
        while(high - low > 1) {
            mid = (high + low) >> 1;
            if(judge(mid, n)) {
                high = mid;
            } else {
                low = mid;
            }
        }
        printf("%I64d\n", high);
    }
    return 0;
}

D. Bishwock

题意

有以下四种方块：
XX $\quad$ $\quad$ XX $\quad$ $\quad$ .X $\quad$ $\quad$ X.
X. $\quad$ $\quad$ .X $\quad$ $\quad$ XX $\quad$ $\quad$ XX
'X' 表示方块中有砖块，'.' 表示方块中没有东西填充，现在给出两行方块，'0'（零）表示空 'X' 表示有砖块填充，问在不破坏这两行方块中有砖块的地方的情况下，最多能放下这种方块多少块。

输入

输入为两行长度相同的字符串，字符串内只包含字符 '0' 和 'X'，字符串长度最大为 $100$ 。

输出

输出能放下的数量最多的方块。

样例

输入	输出
`00` `00`	1
`00X00X0XXX0` `0XXX0X00X00`	4
`0X0X0` `0X0X0`	0
`0XXX0` `00000`	2

题解

贪心填充方块，能填则填，统计每一列有多少个 '0'，如果这一列有 $1$ 个 '0'，就看下一列是否有 $2$ 个 '0'，如果有，就把这一列的 '0' 的个数 $-1$ ，将下一列的 '0' 的个数 $-2$ ，如果这一列有 $2$ 个 '0'，就看下一列的 '0' 的个数是否不少于 $1$ 个，如果是，就把这一列的 '0' 的个数 $-2$ ，下一列的 '0' 的个数 $-1$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
typedef long long LL;
const int maxn = 200;
char str[2][maxn];
int cnt[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%s%s", str[0], str[1]) != EOF) {
        memset(cnt, 0, sizeof(cnt));
        int len = strlen(str[0]);
        for(int i = 0; i < len; ++i) {
            if(str[0][i] == '0') {
                ++cnt[i];
            }
            if(str[1][i] == '0') {
                ++cnt[i];
            }
        }
        int ans = 0;
        for(int i = 0; i < len - 1; ++i) {
            if(cnt[i] == 1) {
                if(cnt[i + 1] == 2) {
                    cnt[i] -= 1;
                    cnt[i + 1] -= 2;
                    ++ans;
                }
            } else if(cnt[i] == 2) {
                if(cnt[i + 1] >= 1) {
                    cnt[i] -= 2;
                    cnt[i + 1] -= 1;
                    ++ans;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

E. Bus Number

题意

给定一个数字 $n$ ，将 $n$ 的每一位数字打散后重组，问有多少种合法的方式。合法的重组方式为：如果数字 $n$ 中出现了某个数位 $x(0\leq x\leq9)$ ，那么重组后的数字中必须至少出现一次 $x$ ，且重组后的数字不应该有前导零。

输入

输入只有一个整数 $n~(1\leq n\leq10^{18})$ 。

输出

输出所有合法的重组方案数。

样例

输入	输出	提示
97	2	合法的重组方式只有： $97$ 、 $79$ 。
2028	13	以下数字都是合法的重组方式： $208,280,802,820,2028,2082,2208,2280,2802,2820,8022,8202,8220$ 。

题解

先统计 $n$ 的每个数位上数字 $x_i$ 出现的次数 $cnt_{x_i}$ ，然后 $dfs$ 枚举每个数字出现的次数，如果 $cnt_{x_i}$ 为 $0$ ，则直接跳过，否则从 $1$ 开始枚举 $x$ 出现的次数，对于每种数字出现的分配方式，设 $sum_x=\sum_{i=1}^xcnt_i$ ，先计算所有非 $0$ 数字的组合方案数，为 $\prod_{i=1}^9C_{sum_i}^{cnt_i}$ ，最后乘上 $0$ 在其中合法的重组方案数： $\prod_{i=1}^9C_{sum_i}^{cnt_i}\times C_{sum_9+cnt_0-1}^{cnt_0}$ ，把所有数字出现的分配方案数加到答案里，就是最终答案。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
typedef long long LL;
const int maxn = 19;
LL ans, n;
int cnt[maxn], ccnt[maxn];
LL C[maxn][maxn];
void dfs(int depth) {
    if(depth == 10) {
        LL tmp = 1;
        int dig = 0;
        for(int i = 1; i <= 9; ++i) {
            if(ccnt[i] == 0) {
                continue;
            }
            tmp *= C[dig + ccnt[i]][ccnt[i]];
            dig += ccnt[i];
        }
        if(ccnt[0] != 0) {
            tmp *= C[dig + ccnt[0] - 1][ccnt[0]];
        }
        ans += tmp;
        return ;
    }
    if(cnt[depth] != 0) {
        for(int i = 1; i <= cnt[depth]; ++i) {
            ccnt[depth] = i;
            dfs(depth + 1);
        }
    } else {
        ccnt[depth] = 0;
        dfs(depth + 1);
    }
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    for(int i = 0; i < maxn; ++i) {
        for(int j = 0; j < maxn; ++j) {
            if(j == 0 || j == i) {
                C[i][j] = 1;
            } else {
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            }
        }
    }
    while(scanf("%I64d", &n) != EOF) {
        ans = 0;
        memset(cnt, 0, sizeof(cnt));
        LL nn = n;
        while(nn != 0) {
            ++cnt[nn % 10];
            nn /= 10;
        }
        dfs(0);
        printf("%I64d\n", ans);
    }
    return 0;
}

Codeforces Round #491 (Div. 2)

A. If at first you don't succeed...

题意

输入

输出

样例

题解

过题代码

B. Getting an A

题意

输入

输出

样例

题解

过题代码

C. Candies

题意

输入

输出

样例

题解

过题代码

D. Bishwock

题意

输入

输出

样例

题解

过题代码

E. Bus Number

题意

输入

输出

样例

题解

过题代码

内容目录