2021年B组第2场真题 - Cache One

2021年B组第2场真题

试题 A: 求余

试题 A: 求余
本题总分: 5 分
【问题描述】
在 C/C++/Java/Python 等语言中,使用 % 表示求余,请问 2021%20 的
值是多少?
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一
个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
printf("%d\n", 2021 % 20); // 1

试题 B: 双阶乘

本题总分: 5 分
【问题描述】
一个正整数的双阶乘,表示不超过这个正整数且与它有相同奇偶性的所有
正整数乘积。 n 的双阶乘用 n!! 表示。
例如:
3!! = 3 × 1 = 3。
8!! = 8 × 6 × 4 × 2 = 384。
11!! = 11 × 9 × 7 × 5 × 3 × 1 = 10395。
请问, 2021!! 的最后 5 位(这里指十进制位)是多少?
注意: 2021!! = 2021 × 2019 × · · · × 5 × 3 × 1。
提示:建议使用计算机编程解决问题。
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一
个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
int ans = 1;
for (int i = 1; i <= 2021; i += 2) {
    ans = ans * i % 100000;
}
printf("%d\n", ans); // 59375

试题 C: 格点


本题总分: 10 分
【问题描述】
如果一个点 (x; y) 的两维坐标都是整数,即 x 属于 Z 且 y 属于 Z,则称这个点为
一个格点。
如果一个点 (x; y) 的两维坐标都是正数,即 x > 0 且 y > 0,则称这个点在
第一象限。
请问在第一象限的格点中,有多少个点 (x; y) 的两维坐标乘积不超过 2021,
即 x · y ≤ 2021。
提示:建议使用计算机编程解决问题。
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一
个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
for (int i = 1; i <= 3000; ++i) {
    for (int j = 1; j <= 3000; ++j) {
        if (i * j <= 2021) {
            ++res;
        }
    }
}
printf("%d\n", res); // 15698

试题 D: 整数分解

【问题描述】
将 3 分解成两个正整数的和,有两种分解方法,分别是 3 = 1 + 2 和
3 = 2 + 1。注意顺序不同算不同的方法。
将 5 分解成三个正整数的和,有 6 种分解方法,它们是 1+1+3 = 1+2+2 =
1 + 3 + 1 = 2 + 1 + 2 = 2 + 2 + 1 = 3 + 1 + 1。
请问,将 2021 分解成五个正整数的和,有多少种分解方法?
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一
个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

暴力不行的

int a[5];
int res;

for (a[0] = 1; a[0] <= 2021; ++a[0]) {
    for (a[1] = 1; a[1] <= 2021; ++a[1]) {
        for (a[2] = 1; a[2] <= 2021; ++a[2]) {
            for (a[3] = 1; a[3] <= 2021; ++a[3]) {
                for (a[4] = 1; a[4] <= 2021; ++a[4]) {
                    if (a[0] + a[1] + a[2] + a[3] + a[4] == 2021) {
                        ++res;
                    }
                }
            }
        }
    }
}
printf("%d\n", res);
typedef unsigned long long ULL;

ULL f[10][2030];

ULL dfs(int k, int s) {
    if (f[k][s] != -1) {
        return f[k][s];
    } 
    if (!k) {
        if (!s) {
            return 1;
        }
        return 0; // 不存在
    }
    f[k][s] = 0;
	for (int i = 1; i <= s; ++i) {
        f[k][s] += dfs(k - 1, s - i);
    }
    return f[k][s];
}

int main() {
	memset(f, -1, sizeof(f));
    printf("%llu\n", dfs(5, 2021));
    return 0;
}

C 2020 4 C_{2020}^{4} C20204

LL res = 1;
for (int i = 2020, j = 1; j <= 4; --i, ++j) {
    res = res * i / j;
}
printf("%lld", res);

试题 E: 城邦

本题总分: 15 分
【问题描述】
小蓝国是一个水上王国,有 2021 个城邦,依次编号 1 到 2021。在任意两
个城邦之间,都有一座桥直接连接。
为了庆祝小蓝国的传统节日,小蓝国政府准备将一部分桥装饰起来。
对于编号为 a 和 b 的两个城邦,它们之间的桥如果要装饰起来,需要的费
用如下计算:找到 a 和 b 在十进制下所有不同的数位,将数位上的数字求和。
例如,编号为 2021 和 922 两个城邦之间,千位、百位和个位都不同,将这
些数位上的数字加起来是 (2 + 0 + 1) + (0 + 9 + 2) = 14。注意 922 没有千位,千
位看成 0。
为了节约开支,小蓝国政府准备只装饰 2020 座桥,并且要保证从任意一个
城邦到任意另一个城邦之间可以完全只通过装饰的桥到达。
请问,小蓝国政府至少要花多少费用才能完成装饰。
提示:建议使用计算机编程解决问题。
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一
个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 2030;
const int M = N * N;
int n = 2021, m;
int p[N];
struct Edge {
    int a, b, c;
    bool operator < (const Edge &t) const {
        return c < t.c;
    }
} e[M];

int find(int x) {
    if (x != p[x]) {
        p[x] = find(p[x]);
    }
    return p[x];
}

int get(int x, int y) {
    int res = 0;
    while (x || y) { // 有一个不是0就行了
        int a = x % 10;
        int b = y % 10;
        if (a != b) {
            res += a + b;
        }
        x /= 10;
        y /= 10;
    }
    return res;
}

int main() {
    for (int i = 1; i <= n; ++i) {
        p[i] = i;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            e[m++] = {i, j, get(i, j)}; // get(i, j) 是获取权值
        }
    }
    
    // 算边权和
    sort(e, e + m);
    int res = 0;
    for (int i = 0; i < m; ++i) {
        int a = e[i].a;
        int b = e[i].b;
        int c = e[i].c;
        if (find(a) != find(b)) { // 不在一个集合里面
            res += c; // 加到集合里
            p[find(a)] = find(b); // 合并
        }
    }
    printf("%d\n", res);
    return 0;
}

F_特殊年份

【问题描述】
今年是 2021 年, 2021 这个数字非常特殊,它的千位和十位相等,个位比
百位大 1,我们称满足这样条件的年份为特殊年份。
输入 5 个年份,请计算这里面有多少个特殊年份。
【输入格式】
输入 5 行,每行一个 4 位十进制数(数值范围为 1000 至 9999),表示一个
年份。
【输出格式】
输出一个整数,表示输入的 5 个年份中有多少个特殊年份。
【样例输入】
2019
2021
1920
2120
9899
【样例输出】
2
【样例说明】
2021 和 9899 是特殊年份,其它不是特殊年份
#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

int main() {
    int res = 0;
    string s;
    for (int i = 0; i < 5; ++i) {
        cin >> s;
        if (s[0] == s[2] && s[1] == s[3] - 1) {
            res++;
        }
    }
    printf("%d\n", res);
    return 0;
}

G_小平方

试题 G: 小平方
时间限制: 1.0s 内存限制: 256.0MB 本题总分: 20 分
【问题描述】
小蓝发现,对于一个正整数 n 和一个小于 n 的正整数 v,将 v 平方后对 n
取余可能小于 n 的一半,也可能大于等于 n 的一半。
请问,在 1 到 n − 1 中,有多少个数平方后除以 n 的余数小于 n 的一半。
例如,当 n = 4 时, 1; 2; 3 的平方除以 4 的余数都小于 4 的一半。
又如,当 n = 5 时, 1; 4 的平方除以 5 的余数都是 1,小于 5 的一半。而
2; 3 的平方除以 5 的余数都是 4,大于等于 5 的一半。
【输入格式】
输入一行包含一个整数 n。
【输出格式】
输出一个整数,表示满足条件的数的数量。
【样例输入】
5
【样例输出】
2
【评测用例规模与约定】
对于所有评测用例, 1 ≤ n ≤ 10000。
#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

int n;
int res = 0;
int main() {
    cin >> n;
    for (int i = 1; i < n; ++i) {
        if (i * i % n * 2 < n) {
            res++;
        }
    }
    printf("%d\n", res);
    return 0;
}

H_完全平方数

题 H: 完全平方数
时间限制: 1.0s 内存限制: 256.0MB 本题总分: 20 分
【问题描述】
一个整数 a 是一个完全平方数,是指它是某一个整数的平方,即存在一个
整数 b,使得 a = b^2。
给定一个正整数 n,请找到最小的正整数 x,使得它们的乘积是一个完全平
方数。
【输入格式】
输入一行包含一个正整数 n。
【输出格式】
输出找到的最小的正整数 x。
【样例输入 1】
12
【样例输出 1】
3
【样例输入 2】
15
【样例输出 2】
15
【评测用例规模与约定】
对于 30% 的评测用例, 1 ≤ n ≤ 1000,答案不超过 1000。
对于 60% 的评测用例, 1 ≤ n ≤ 108,答案不超过 108。
对于所有评测用例, 1 ≤ n ≤ 1012,答案不超过 1012。

把n分解质因数,如果质因数的幂是奇数,就要乘一个这个质因数,让对应的幂变成偶数,就可以变成完全平方数了

#include <iostream>
#include <cstdio>
typedef long long LL;

using namespace std;

int main() {
    LL n;
    cin >> n;
    LL res = 1;
    for (LL i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
            if (cnt % 2 == 1) {
                res *= i; // 乘一个数
            }
        }
    }
    if (n > 1) {
        res *= n;
    }
    printf("%lld\n", res);
    return 0;
}

试题 I: 负载均衡


时间限制: 1.0s 内存限制: 256.0MB 本题总分: 25 分
【问题描述】
有 n 台计算机,第 i 台计算机的运算能力为 vi。
有一系列的任务被指派到各个计算机上,第 i 个任务在 ai 时刻分配,指定
计算机编号为 bi ,耗时为 ci 且算力消耗为 di 。如果此任务成功分配,将立刻
开始运行,期间持续占用 bi 号计算机 di 的算力,持续 ci 秒。
对于每次任务分配,如果计算机剩余的运算能力不足则输出 −1,并取消这
次分配,否则输出分配完这个任务后这台计算机的剩余运算能力。
【输入格式】
输入的第一行包含两个整数 n; m,分别表示计算机数目和要分配的任务数。
第二行包含 n 个整数 v1; v2; · · · vn,分别表示每个计算机的运算能力。
接下来 m 行每行 4 个整数 ai; bi; ci; di,意义如上所述。数据保证 ai 严格递
增,即 ai < ai+1。
【输出格式】
输出 m 行,每行包含一个数,对应每次任务分配的结果。
【样例输入】
2 6
5 5
1 1 5 3
2 2 2 6
3 1 2 3
4 1 6 1
5 1 3 3
6 1 3 4
【样例输出】
2
-1
-1
1
-1
0
【样例说明】
时刻 1,第 1 个任务被分配到第 1 台计算机,耗时为 5 ,这个任务时刻 6
会结束,占用计算机 1 的算力 3。
时刻 2,第 2 个任务需要的算力不足,所以分配失败了。
时刻 3,第 1 个计算机仍然正在计算第 1 个任务,剩余算力不足 3,所以
失败。
时刻 4,第 1 个计算机仍然正在计算第 1 个任务,但剩余算力足够,分配
后剩余算力 1。
时刻 5,第 1 个计算机仍然正在计算第 1; 4 个任务,剩余算力不足 4,失
败。
时刻 6,第 1 个计算机仍然正在计算第 4 个任务,剩余算力足够,且恰好
用完。
【评测用例规模与约定】
对于 20% 的评测用例, n; m ≤ 200。
对于 40% 的评测用例, n; m ≤ 2000。
对于所有评测用例, 1 ≤ n; m ≤ 200000, 1 ≤ ai; ci; di; vi ≤ 109, 1 ≤ bi ≤ n。

为您推荐