2025寒假算法练习——Week 3
文章目录
习题均来自 NEFU OJ
Problem 8 | 二倍的问题
- Description
给定2到15个不同的正整数，你的任务是计算这些数里面有多少个数对满足：数对中一个数是另一个数的两倍。比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2个两倍，18是9的两倍。
- Input
输入包括n组测试数据。每组数据包括一行，给出2到15个两两不同且小于100的正整数。每一行最后一个数是0，表示这一行的结束后，这个数不属于那2到15个给定的正整数。
- Output
对每组输入数据，输出一行，给出有多少个数对满足其中一个数是另一个数的两倍。
- Sample Input
13
21 4 3 2 9 7 18 22 0
32 4 8 10 0
47 5 11 13 1 3 0
- Sample Output
13
22
30
简单题。唯一奇怪的是使用 bitset 比直接用 int* 的内存开销大。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <cstring>
5
6using namespace std;
7
8int max_value, i, value, n, cnt;
9int values[100];
10
11int main() {
12 scanf("%d", &n);
13 while (n--) {
14 memset(values, 0, sizeof(values));
15 max_value = -1;
16 cnt = 0;
17
18 while (scanf("%d", &value) && value != 0) {
19 values[value] = 1;
20 if (value > max_value) {
21 max_value = value;
22 }
23 }
24
25 for (i = 1; i <= max_value / 2; i++) {
26 if (values[i] && values[i * 2]) {
27 cnt++;
28 }
29 }
30
31 printf("%d\n", cnt);
32 }
33 return 0;
34}
Problem 573 | 大乐透
- Description
在小明曾经玩过的一种对号码的纸牌游戏(乐透)里,玩家必须从{1,2,……，49}中选择6个数。玩Lotto的一个流行策略是（虽然它并不增加你赢的机会）：就是从这49个数中，选出k（k>6）个数组成一个子集S，然后只从S里拿出牌来玩几局游戏。例如，k=8，s={1,2,3,5,8,13,21,34}，那么有28场可能的游戏：[1,2,3,5,8,13],[1,2,3,5,8,21],[1,2,3,5,8,34],[1,2,3,5,13,21],……,[3,5,8,13,21,24]。 读取数字k和一组数S，输出由S中的数组成的所有可能的游戏。
- Input
输入数据有多组，每组一行，每行有多个整数，其中第一个整数为数字k，接下来有k个整数，即子集S。当k为0，输入结束。
- Output
输出由S中的数组成的所有可能的游戏。每种游戏一行。
- Sample Input
17 1 2 3 4 5 6 7
20
- Sample Output
11 2 3 4 5 6
21 2 3 4 5 7
31 2 3 4 6 7
41 2 3 5 6 7
51 2 4 5 6 7
61 3 4 5 6 7
72 3 4 5 6 7
用递归（深搜）解决：
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <cstring>
5#include <algorithm>
6
7using namespace std;
8
9int nums[50], k;
10
11void solve(int* nums, int start, int depth, int* combination) {
12 if (depth == 6) {
13 printf("%d %d %d %d %d %d\n", combination[0], combination[1], combination[2], combination[3], combination[4], combination[5]);
14 return;
15 }
16
17 for (int i = start; i < k; i++) {
18 combination[depth] = nums[i];
19 solve(nums, i + 1, depth + 1, combination);
20 }
21}
22
23int main() {
24 while (scanf("%d", &k) != -1) {
25 if (k == 0) {
26 break;
27 }
28
29 memset(nums, 0, sizeof(nums));
30 for (int i = 0; i < k; i++) {
31 scanf("%d", &nums[i]);
32 }
33
34 sort(nums, nums + k);
35
36 int combination[6];
37 solve(nums, 0, 0, combination);
38 }
39
40 return 0;
41}
或者暴力循环嵌套：
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <cstring>
5#include <algorithm>
6
7using namespace std;
8
9int i, nums[50], k;
10int a, b, c, d, e, f;
11
12int main() {
13 while (scanf("%d", &k) != -1 && k != 0)
14 {
15 memset(nums, 0, sizeof(nums));
16 for (i = 0; i < k; i++) {
17 scanf("%d", &nums[i]);
18 }
19
20 sort(nums, nums + k);
21 for (a = 0; a < k - 5; a++) {
22 for (b = a + 1; b < k - 4; b++) {
23 for (c = b + 1; c < k - 3; c++) {
24 for (d = c + 1; d < k - 2; d++) {
25 for (e = d + 1; e < k - 1; e++) {
26 for (f = e + 1; f < k; f++) {
27 printf("%d %d %d %d %d %d\n", nums[a], nums[b], nums[c], nums[d], nums[e], nums[f]);
28 }
29 }
30 }
31 }
32 }
33 }
34 }
35
36 return 0;
37}
使用 Python 做起来会比较简单，直接调用 itertools 模块中的 combinations 函数：
1
2from itertools import combinations
3
4
5def main():
6 while (nums := tuple(map(int, input().split(" "))))[0] != 0:
7 for c in combinations(nums[1:], 6):
8 print(*c)
9
10
11if __name__ == "__main__":
12 main()
Problem 572 | 密码箱
- Description
小明的密码箱打不开了，小明的密码箱是传统的3位滚轮密码。小明完全不记得他的密码了，所以他从 000开始以升序开始尝试，他已经试到第abc位密码了，可是箱子还是没有打开，他希望你将之后所有可能尝试的密码输出，这样他就可以完全不去思考，让他波动密码盘更有效率
- Input
每行输入一个整数n(0 < n < 1000);n没有前缀0。
- Output
n之后所有可能尝试的密码;输出有前缀0的。
- Sample Input
1989
- Sample Output
1990
2991
3992
4993
5994
6995
7996
8997
9998
10999
好睿智的问题
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4
5int n;
6
7int main() {
8 while (scanf("%d", &n) != EOF) {
9 while (n < 999) {
10 printf("%03d\n", ++n);
11 }
12 }
13 return 0;
14}
Problem 621 | 字符串统计
- Description
对于给定的一个字符串，统计其中数字字符出现的次数。
- Input
输入数据有多组，第一行是一个整数n，表示测试实例的个数，后面跟着n行，每行包括一个由字母和数字组成的字符串。
- Output
对于每个测试实例，输出该串中数值的个数，每个输出占一行。
- Sample Input
12
2asdfasdf123123asdfasdf
3asdf111111111asdfasdfasdf
- Sample Output
16
29
1#include <iostream>
2
3using namespace std;
4
5int n, cnt;
6string s;
7
8int main() {
9 cin >> n;
10 while (n--) {
11 cnt = 0;
12 cin >> s;
13 for (const auto& c : s) {
14 if (c >= '0' && c <= '9') {
15 cnt++;
16 }
17 }
18 cout << cnt << endl;
19 }
20 return 0;
21}
Problem 574 | 丑数
- Description
只有质数2,3,5,7这几个作为因子的数叫做,丑数,比如前20个丑数是(从小到大来说) 1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24和25.
- Input
我们给你个n（1<= n<=5842）当输入n为0结束。
- Output
输出第n个丑数。每个数一行。
- Sample Input
11
22
33
44
511
- Sample Output
11
22
33
44
512
使用动态规划，un[i] 表示第 i 个丑数。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <vector>
5#include <algorithm>
6
7
8using namespace std;
9
10int main() {
11 int n, i, ptr2, ptr3, ptr5, ptr7, nxt2, nxt3, nxt5, nxt7;
12 while (scanf("%d", &n) && n != 0) {
13 vector<int> un(n);
14 un[0] = 1;
15 nxt2 = 2;
16 nxt3 = 3;
17 nxt5 = 5;
18 nxt7 = 7;
19 ptr2 = 0;
20 ptr3 = 0;
21 ptr5 = 0;
22 ptr7 = 0;
23
24 for (i = 1; i < n; i++) {
25 un[i] = min({nxt2, nxt3, nxt5, nxt7});
26
27 if (un[i] == nxt2) {
28 ptr2++;
29 nxt2 = 2 * un[ptr2];
30 }
31 if (un[i] == nxt3) {
32 ptr3++;
33 nxt3 = 3 * un[ptr3];
34 }
35 if (un[i] == nxt5) {
36 ptr5++;
37 nxt5 = 5 * un[ptr5];
38 }
39 if (un[i] == nxt7) {
40 ptr7++;
41 nxt7 = 7 * un[ptr7];
42 }
43 }
44
45 printf("%d\n", un[n - 1]);
46 }
47 return 0;
48}
Problem 575 | 矩形
- Description
在测试超大规模集成电路时，对给定的一个设计，专家要检测元件是否相互遮盖。一个元件可视为一个矩形，假设每个矩形都是水平排列的（边与x轴或y轴平行），所以长方形由最小的和最大的x，y坐标表示。
编程计算完全被覆盖的矩形个数。
- Input
输入有多组长方形实例。对每组长方形，第一个数字是长方形的数量，然后是长方形的最小和最大x，y坐标（最小x，最大x，最小y，最大y）。
- Output
对每组输入数据，输出一行，是被完全覆盖的长方形数量。
- Sample Input
13
2100 101 100 101
30 3 0 101
420 40 10 400
54
610 20 10 20
710 20 10 20
810 20 10 20
910 20 10 20
- Sample Output
10
24
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <vector>
5
6using namespace std;
7
8struct Rect {
9 int xmin, ymin, xmax, ymax;
10};
11
12int main() {
13 vector<Rect> chips;
14 int n, cnt;
15
16 while (scanf("%d", &n) != EOF) {
17 cnt = 0;
18 chips.clear();
19 while (n--) {
20 Rect r;
21 scanf("%d %d %d %d", &r.xmin, &r.xmax, &r.ymin, &r.ymax);
22 chips.push_back(r);
23 }
24
25 for (int i = 0; i < chips.size(); i++) {
26 for (int j = 0; j < chips.size(); j++) {
27 if (i != j) {
28 if (chips[j].xmin <= chips[i].xmin &&
29 chips[j].xmax >= chips[i].xmax &&
30 chips[j].ymin <= chips[i].ymin &&
31 chips[j].ymax >= chips[i].ymax) {
32 cnt++;
33 break;
34 }
35 }
36 }
37 }
38
39 printf("%d\n", cnt);
40 }
41
42 return 0;
43}
最开始我的思路是，如果矩形 A 能够被矩形 B 完全覆盖，那么 A 的面积必然小于等于 B 的面积，因此先将所有矩形按照面积从小到大排序，然后使用两层循环，不重不漏两两比较。但是这样做的问题是，两个面积和形状相等的矩形无法排序，并且按照题意他们互相“完全覆盖”，所以应该算两次。
Problem 1639 | 抽奖
- Description
公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚会的每位员工都有一张带有号码的抽奖券。现在，主持人依次公布 n 个不同的获奖号码，小谢看着自己抽奖券上的号码 num，无比紧张。请编写一个程序，如果小谢获奖了，请输出他中的是第几个号码；如果没有中奖，请输出 0。
- Input
第一行一个正整数 n，表示有 n 个获奖号码，$2<n≤100$。
第二行包含 n 个正整数，之间用一个空格隔开，表示依次公布的 n 个获奖号码。
第三行一个正整数 num，表示小谢抽奖券上的号码。
1≤获奖号码，num<10000。
- Output
一行一个整数，如果小谢中奖了，表示中奖的是第几个号码；如果没有中奖，则为 0。
- Sample Input
17
217 2 3 4 9555 6 1
33
- Sample Output
13
- Hint
暴力
单组输入
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4
5int n, i, num, nums[10005] = { 0 };
6
7int main() {
8 scanf("%d", &n);
9 for (int i = 1; i <= n; i++) {
10 scanf("%d", &num);
11 nums[num] = i;
12 }
13 scanf("%d", &num);
14 printf("%d\n", nums[num]);
15 return 0;
16}
Problem 1640 | 比身高
- Description
有 N 个人排成一排，假设他们的身高均为正整数，请找出其中符合以下条件的人：排在他前面且比他高的人数与排在他后面且比他高的人数相等。
- Input
第一行为一个正整数 N，$1<N<1000$，表示有多少个人。
下面 N 行，每行一个正整数，表示从前往后每个人的身高，假设每个人的身高≤10000。
- Output
一行一个整数，表示满足这个条件的人数。
- Sample Input
14
21
32
41
53
- Sample Output
12
- Hint
第 3、第 4 个人满足条件。 单组输入
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4
5int main() {
6 int n;
7 int p[1001] = { 0 };
8 int front = 0, rear = 0, cnt = 0;
9 int i, j;
10 scanf("%d", &n);
11
12 for (i = 0; i < n; i++) {
13 scanf("%d", &p[i]);
14 }
15 for (i = 0; i < n; i++) {
16 front = 0;
17 rear = 0;
18 for (j = 0; j < i; j++) {
19 if (p[j] > p[i]) {
20 front++;
21 }
22 }
23 for (j = i + 1; j < n; j++) {
24 if (p[j] > p[i]) {
25 rear++;
26 }
27 if (rear > front) {
28 break;
29 }
30 }
31 if (rear == front) {
32 cnt++;
33 }
34 }
35 printf("%d", cnt);
36 return 0;
37}
Problm 1642 | 楼层编号
- Description
小林在 NOIP 比赛期间住在“新世界”酒店。和其他酒店不一样的是，这个酒店每天都有一个高能的数字 t，这个数字在楼层中是不会出现的，以 t=3 为例，则 3、13、31、33 等楼层是不存在的，楼层编号为 1，2，4，5，…所以实际上的 4 楼才是 3 楼。
已知小林预订了编号为 m 层的房间，并且当天高能数字是 t，现在他想知道房间所在的真实楼层是多少。
- Input
一行两个整数 m 和 t，1≤m≤100000，0≤t≤9，保证 m 对 t 合法。
- Output
一行一个整数，表示真实楼层。
- Sample Input
114 3
- Sample Output
112
- Hint
单组输入
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <string>
5
6using namespace std;
7
8int main()
9{
10 int m;
11 char t;
12 scanf("%d %c", &m, &t);
13 int leap = 0;
14 for (int i = 1; i <= m; i++) {
15 if (to_string(i).find(t) != string::npos) {
16 leap++;
17 }
18 }
19 printf("%d\n", m - leap);
20 return 0;
21}
Problem 1643 | 比例简化
- Description
在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某观点表示支持的有 1498 人，反对的有 902 人，那么其比例可以简单地记为1498∶902。
因该比例的数值太大，难以一眼看出它们的关系。若把比例记为 5∶3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。
现给出支持人数 A 和反对人数 B，以及一个上限 L，请将 A 比 B 化简为 A′ 比 B′，要求在 A′和 B′ 均不大于 L，且 A′ 和 B′ 互质（两个整数的最大公约数为 1）的前提下，A′/B′≥ A/B 且 A′/B′-A/B 的值尽可能小。
- Input
一行三个整数 A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。
- Output
一行两个整数 A′ 和 B′，中间用一个空格隔开，表示化简后的比例。
- Sample Input
11498 902 10
- Sample Output
15 3
- Hint
单组输入,$1\leq A,B;eq1000000,1\leq L\leq100,\frac{A}{B}\leq L$
由于 $L\leq100$，可以尝试遍历 A' 和 B'。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4
5using namespace std;
6
7int gcd(int a, int b) {
8 return b == 0 ? a : gcd(b, a % b);
9}
10
11int main()
12{
13 double a, b, ratio, e, emin = 1000001.0;
14 int l, p, q;
15 scanf("%lf%lf%d", &a, &b, &l);
16 ratio = a / b;
17 for (int i = 1; i <= l; i++) {
18 for (int j = 1; j <= l; j++) {
19 e = (i * 1.0) / (j * 1.0) - ratio;
20 if (e >= 0 && e < emin && gcd(i, j) == 1) {
21 emin = e;
22 p = i;
23 q = j;
24 }
25 }
26 }
27 printf("%d %d\n", p, q);
28 return 0;
29}
这里要注意误差 e 是可以为 0 的。
让 A' B' 都遍历 1 到 L 之间的所有数，会在一些绝对没有用的数据上浪费时间，比如 $A=1498,B=902,L=10$ 时绝对不会得到 $A'=1,B'=10$ 的结果。根据要求 $\frac{A}{B}\geq\frac{A'}{B'}$ 得到 $A'\leq\frac{A}{B}\cdot B'$。因此只需要遍历 B'，随后根据原比例求出 A'，再比较出最合适的比例。这样就将时间复杂度从 O(n^2) 降低到 O(n)。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <cmath>
5
6using namespace std;
7
8int gcd(int a, int b) {
9 return b == 0 ? a : gcd(b, a % b);
10}
11
12int main() {
13 int A, B, L;
14 int i, j, p, q;
15 double e, emin = 1000001.0;
16 scanf("%d%d%d", &A, &B, &L);
17 double ratio = (A * 1.0) / B;
18 for (j = 1; j <= L; j++) {
19 i = ceil(j * ratio);
20 if (i > L) {
21 break;
22 }
23 e = (i * 1.0) / j - ratio;
24 if (e < emin && gcd(i, j) == 1) {
25 emin = e;
26 p = i;
27 q = j;
28 }
29 }
30 printf("%d %d", p, q);
31 return 0;
32}
今天是周二也刚好是除夕，收工！