C++题目分享
# HW机考 ACM编程API集群负载统计
时间限制:1s
空间限制:256MB
国限定语言:不限
题目描述:
某个产品的RESTful API集合部署在服务器集群的多个节点上,近期对客户端访问日志进行了采集,需要统计各个API的访问频次,根据热点信息在服务器节点之
间做负载均衡,现在需要实现热点信息统计查询功能。
RESTful API的由多个层级构成,层级之间使用/连接,如/A/B/C/D这个地址,A属于第一级,B属于第二级,C属于第三级,D属于第四级。
现在负载均衡模块需要知道给定层级上某个名字出现的频次,未出现过用0次表示,实现这个功能。
输入描述:
第一行为N,表示访问历史日志的条数,0<N≤100.
接下来N行,每一行为一个RESTful API的URL地址,约束地址中仅包含英文字母和连接符/,最大层级为10,每层级字符串最大长度为10。
最后一行为层级L和要查询的关键字。
输出描述:输出给定层级上,关键字出现的频次,使用完全匹配方式(大小写敏感)。
补充说明:
示例1
输入:
5
/huawei/computing/no/one
/huawei/computing
/huawei
/huawei/cloud/no/one
/huawei/wireless/no/one
2 computing
2
3
4
5
6
7
8
2
3
4
5
6
7
8
输出:2
说明:在第二层级上,computing出现了2次,因此输出2.
5
/huawei/computing/no/one
/huawei/computing
/huawei
/huawei/cloud/no/one
/huawei/wireless/no/one
4 two
2
3
4
5
6
7
2
3
4
5
6
7
输出:0
说明:存在第四层级的URL上,没有出现two, 因此频次是0
# 通过代码:
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, int> mp;//声明了一个 unordered_map,键类型是 string,值类型是 int。这个哈希表用来存储路径和它们的访问次数。
int main() {
int n; // 访问日志条数
cin >> n;//这里会读取输入的第一行中的路径条数
// 多次输入 RESTful API 地址
for (int i = 0; i < n; i++) {
string s;
cin >> s; // 利用for循环一条一条顺序读取输入的地址
s += "/"; // 在路径末尾添加斜杠,确保可以正确处理最后一个路径段
int cnt = 0; // 用于跟踪路径的深度(层级)
string now = ""; // 用于存储当前处理的路径段
// 遍历 API 地址的每个字符
for (auto x : s) {
if (x == '/') {
// 如果遇到斜杠,并且当前路径段(now)不为空
if (now == "") continue; // 如果 now 为空,则跳过
cnt++; // 增加路径深度
mp[to_string(cnt) + " " + now]++; // 在哈希表中更新该路径段的访问次数
now = ""; // 重置当前路径段
} else {
now += x; // 将当前字符添加到 now,构建当前路径段
}
}
}
int dep;
cin >> dep;
string q;
cin >> q;
cout << mp[to_string(dep) + " " + q] << endl;
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 问题思考:
+=
和+
运算符的区别在上文的代码中有一行是
s += "/";
11其效果是把API路径的末尾额外再加一个
/
符号,但如果单纯是实现这个效果,使用以下代码也可以,但实际上这样会导致运行出错。s + "/";
11在C语言的运行过程中,采用
+=
只会在原字符串的基础上进行修改,而+
则是在原字符串的基础上进行运算后生成新的字符串,在上面代码的逻辑中,只需要改变s
本身,而不是创建一个新的、未使用的字符串。cin
命令的执行逻辑这个命令在C++中用的很多,经过实际测试,发现cin命令每次只能读取一行的数据,这就导致如果要读取所有的行的数据必须要配合for循环来进行,这段代码就是执行多次读取命令的。
for (int i = 0; i < n; i++) { string s; cin >> s; // 读取一个 API 地址 s += "/"; // 在地址末尾添加斜杠,确保可以正确处理最后一个路径段 int cnt = 0; // 用于跟踪路径的深度(层级) string now = ""; // 用于存储当前处理的路径段 }
1
2
3
4
5
6
71
2
3
4
5
6
7
# LG B2004 对齐输出
题目描述
读入三个整数,按每个整数占 个字符的宽度,右对齐输出它们,按照格式要求依次输出三个整数,之间以一个空格分开。
输入格式
只有一行,包含三个整数 。整数之间以一个空格分开。
输出格式
只有一行,按照格式要求依次输出三个整数,之间以一个空格分开。
样例 #1
样例输入 #1
123456789 0 -1
样例输出 #1
123456789 0 -1
提示
对于 的数据,。
# 通过代码
#include <iostream>
#include <iomanip> // 用于格式化输出,使用setw命令
using namespace std;
int main() {
int a, b, c;
// 从标准输入读取三个整数
cin >> a >> b >> c;
// 设置每个数字的输出宽度为 8 个字符,并进行右对齐
cout << right << setw(8) << a << " " //right是让cout靠右输出
<< setw(8) << b << " "
<< setw(8) << c << endl;
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# LG B2012 甲流疫情死亡率
题目描述
甲流并不可怕,在中国,它的死亡率并不是很高。请根据截止 年 月 日各省报告的甲流确诊数 和死亡数 ,计算甲流在各省的死亡率。
输入格式
输入共两行,第一行一个整数为确诊数 ,第二行一个整数为死亡数 。
输出格式
输出仅一行,甲流死亡率,以百分数形式输出,精确到小数点后 位。
样例 #1
样例输入 #1
10433
60
2
2
样例输出 #1
0.575%
提示
数据规模与约定
对于全部的测试点,保证 。
提示
在 C 风格输入输出中,百分号 %
可以这样输出:printf("%%");
。
# 通过代码
#include <iostream>
#include <iomanip>
using namespace std;
int main(){
double a, b, c;
cin >> a;
cin >> b;
c = b/a*100;
cout << fixed << setprecision(3)<< c << "%" << endl;
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 问题思考
C++的运算赋值写法使用不当
#include <iostream> using namespace std; int main() { // 正确的赋值操作 c = b / a; // 错误的赋值操作 b / a = c; }
1
2
3
4
5
6
7
8
9
101
2
3
4
5
6
7
8
9
10
# LG P1002 [NOIP2002 普及组] 过河卒
题目描述
棋盘上 点有一个过河卒,需要走到目标 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示, 点 、 点 ,同样马的位置坐标是需要给出的。
现在要求你计算出卒从 点能够到达 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。
输入格式
一行四个正整数,分别表示 点坐标和马的坐标。
输出格式
一个整数,表示所有的路径条数。
样例 #1
样例输入 #1
6 6 3 3
样例输出 #1
6
数据范围:
对于 的数据,, 马的坐标 。
【题目来源】
NOIP 2002 普及组第四题
# 通过代码
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m, x, y;
cin >> n >> m >> x >> y; // 读取 B 点坐标 (n, m) 和马的坐标 (x, y)
vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0)); // 创建一个二维动态规划数组,存储到达每个点的路径数
vector<vector<bool>> horse(n + 1, vector<bool>(m + 1, false)); // 创建一个二维数组,标记马控制的点
// 马控制的点,通过定义整数数组来表示,理想状况下马的可以动点有8个加上自己本来的站位
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2, 0}; // 马移动的横坐标偏移量
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1, 0}; // 马移动的纵坐标偏移量
// 标记所有马控制的点为不可达
for (int i = 0; i < 9; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx <= n && ny >= 0 && ny <= m) //&符号是且的意思
{
horse[nx][ny] = true;
}
}
dp[0][0] = 1; // 在起点 (0, 0) 处初始化路径数量为 1
// 使用动态规划计算到达每个点的路径数
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
if (horse[i][j]) continue; // 如果当前点被马控制,则跳过
if (i > 0) dp[i][j] += dp[i - 1][j]; // 从上方点向下移动
if (j > 0) dp[i][j] += dp[i][j - 1]; // 从左方点向右移动
}
}
cout << dp[n][m] << endl; // 输出到达 B 点的路径总数
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# LG P1161 开灯(难度较高,暂未解决)
题目描述
在一条无限长的路上,有一排无限长的路灯,编号为 。
每一盏灯只有两种可能的状态,开或者关。如果按一下某一盏灯的开关,那么这盏灯的状态将发生改变。如果原来是开,将变成关。如果原来是关,将变成开。
在刚开始的时候,所有的灯都是关的。小明每次可以进行如下的操作:
指定两个数,( 为实数, 为正整数)。将编号为 的灯的开关各按一次。其中 表示实数 的整数部分。
在小明进行了 次操作后,小明突然发现,这个时候只有一盏灯是开的,小明很想知道这盏灯的编号,可是这盏灯离小明太远了,小明看不清编号是多少。
幸好,小明还记得之前的 次操作。于是小明找到了你,你能帮他计算出这盏开着的灯的编号吗?
输入格式
第一行一个正整数 ,表示 次操作。
接下来有 行,每行两个数,。其中 是实数,小数点后一定有 位, 是正整数。
输出格式
仅一个正整数,那盏开着的灯的编号。
样例 #1
样例输入 #1
3
1.618034 13
2.618034 7
1.000000 21
2
3
4
2
3
4
样例输出 #1
20
提示
记 。
- 对于 的数据,满足 ;
- 对于 的数据,满足 ;
- 对于 的数据,满足 ;
- 对于 的数据,满足 ,,。
数据保证,在经过 次操作后,有且只有一盏灯是开的,不必判错。而且对于所有的 来说, 的最大值不超过 。
# 通关代码
#include <iostream>
#include <unordered_map> //哈西表头文件
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
// 使用哈希表存储每盏灯的状态
unordered_map<int, bool> lights;
for (int i = 0; i < n; ++i) {
double a;
int t;
cin >> a >> t;
for (int j = 1; j <= t; ++j) {
int lightNum = floor(j * a);
// 改变灯的状态
lights[lightNum] = !lights[lightNum];
}
}
// 查找亮着的灯
for (auto &light : lights) {
if (light.second) {
cout << light.first << endl;
break;
}
}
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# LG P1423 小玉在游泳
题目描述
小玉开心的在游泳,可是她很快难过的发现,自己的力气不够,游泳好累哦。已知小玉第一步能游 米,可是随着越来越累,力气越来越小,她接下来的每一步都只能游出上一步距离的 。现在小玉想知道,如果要游到距离 米的地方,她需要游多少步呢。请你编程解决这个问题。
输入格式
输入一个实数 (单位:米),表示要游的目标距离。
输出格式
输出一个整数,表示小玉一共需要游多少步。
样例 #1
样例输入 #1
4.3
样例输出 #1
3
提示
数据保证,,且 小数点后最多只有一位。
# 通关代码
#include <iostream>
using namespace std;
int main(){
double a;
cin >> a;
double step = 2.0;
double total = 0;
int count = 0;
for(count=0; total < a; count++){
total = total + step;
step = step * 0.98;
}
cout << count << endl;
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 问题思考
这道题可以使用多个循环来实现,while循环也可以。
同时有一类等价表述,在这种简单程序中,实现的效果是相同的,不过在复杂的地方仍要注意,两个背后的代码含义有区别,详情见:+=/+运算符的区别
total = total + step;
=total += step;
# LG P1567统计天数
题目描述
炎热的夏日,KC 非常的不爽。他宁可忍受北极的寒冷,也不愿忍受厦门的夏天。最近,他开始研究天气的变化。他希望用研究的结果预测未来的天气。
经历千辛万苦,他收集了连续 天的最高气温数据。
现在,他想知道最高气温一直上升的最长连续天数。
输入格式
第 1 行:一个整数 。
第 2 行:个空格隔开的整数,表示连续 天的最高气温。 最高气温 。
输出格式
1 行:一个整数,表示最高气温一直上升的最长连续天数。
样例 #1
样例输入 #1
10
1 2 3 2 4 5 6 8 5 9
2
2
样例输出 #1
5
# 通关代码
#include <iostream>
#include <vector>
#include <algorithm> // 显式包含algorithm头文件,好调用max函数
using namespace std;
int main(){
int DayNum;
cin >> DayNum;
vector<int> DayTemperature(DayNum);
for(int i = 0; i < DayNum; ++i){
cin >> DayTemperature[i];
} // 这一步个循环可以巧妙的把每一个输入填入这个动态数组
int maxLen = 1;//最长气温持续升高至少有1天(题目规律)
int currentLen = 1;//记录每个持续上升天数(至少有1天)
for(int i = 1; i < DayNum ; ++i){
if(DayTemperature[i] > DayTemperature[i-1]){
currentLen++;
maxLen = max(maxLen, currentLen);//用max函数比较大小,并取得更大的哪个数赋值前面的maxLen
}
else{
currentLen =1;
}
}
cout << maxLen << endl;
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 问题思考
Max
函数其实是头文件#include <algorithm>
中的,这个头文件很多编译器会隐式引用,所以即使不写在最前头,也能正常运行,但如果严谨来看,最好还是写上,以保证多平台的运行能力。- 代码中使用到了
vector
头文件以运用vector
动态数组,动态数组的好处很多,使用比较简单,但相比较普通数组,会占用更多运算资源,在数组规模可预测的情况下,使用普通数组是性能最优的。
# LG P1427 小鱼的数字游戏
题目描述
小鱼最近被要求参加一个数字游戏,要求它把看到的一串数字 (长度不一定,以 结束),记住了然后反着念出来(表示结束的数字 就不要念出来了)。这对小鱼的那点记忆力来说实在是太难了,你也不想想小鱼的整个脑袋才多大,其中一部分还是好吃的肉!所以请你帮小鱼编程解决这个问题。
输入格式
一行内输入一串整数,以 结束,以空格间隔。
输出格式
一行内倒着输出这一串整数,以空格间隔。
样例 #1
样例输入 #1
3 65 23 5 34 1 30 0
样例输出 #1
30 1 34 5 23 65 3
提示
数据规模与约定
对于 的数据,保证 ,数字个数不超过 。
# 通关代码
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> Numbers;//Num后面不需要写括号,来让数组的大小根据情况自动拓展
int cnum;
while (cin >> cnum && cnum !=0){//应用且或非来控制到0之后的停止执行写入数据
Numbers.push_back(cnum); //push_back是一个vector的成员函数,用于在动态数组后面添加新元素,括号内意味着是需要被调入进去的cin内容
}
for (int i = Numbers.size()-1; i>= 0; --i){//反向遍历vector,这里的size()也是std::vector的一个成员函数,作用是返回当前数组元素的数量,由于vector的元素索引是从0开始的,也就是说最后一个元素的索引序号是N-1个
cout << Numbers[i] << " ";
}
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 问题思考
numbers.push_back(num);
:push_back
是 std::vector 的一个成员函数,用于在 vector 的末尾添加一个新元素。 当你调用 numbers.push_back(num); 时,num 的值被添加到 vector numbers 的末尾。 这意味着你不需要预先知道 vector 中将存储多少个元素,因为 vector 会根据需要动态地调整其大小。numbers.size() - 1
:size()
是std::vector
的另一个成员函数,它返回 vector 中当前元素的数量。 在 C++ 中,vector 的索引是从 0 开始的。这意味着如果 vector 有 N 个元素,它们的索引将是从 0 到 N-1。因此,
numbers.size() - 1
实际上是获取 vector 中最后一个元素的索引。 在这个问题中,我们需要从 vector 的末尾开始反向遍历,所以我们从索引numbers.size() - 1
(即最后一个元素)开始。
# LG P5727 冰雹猜想
题目描述
给出一个正整数 ,然后对这个数字一直进行下面的操作:如果这个数字是奇数,那么将其乘 再加 ,否则除以 。经过若干次循环后,最终都会回到 。经过验证很大的数字()都可以按照这样的方式比变成 ,所以被称为“冰雹猜想”。例如当 是 ,变化的过程是 。
根据给定的数字,验证这个猜想,并从最后的 开始,倒序输出整个变化序列。
输入格式
输入一个正整数 。
输出格式
输出若干个由空格隔开的正整数,表示从最后的 开始倒序的变化数列。
样例 #1
样例输入 #1
20
样例输出 #1
1 2 4 8 16 5 10 20
提示
数据保证,。
通关代码
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> count;
count.push_back(n); //因为输出包含原输出内容,所以先把cin的数字放在数组的第一位
while(n!=1){//只要n没有变成1,就一直算下去
if(n % 2 != 0 ){
n *= 3;
n += 1;
count.push_back(n); //运用push_back把数据输入到数组的最后一位
}else{
n /= 2;
count.push_back(n); //运用push_back把数据输入到数组的最后一位
}
}
for(int i = count.size()-1;i >= 0; --i){//利用for循环写出倒序排列
cout << count[i] << " ";
}
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# LG P1047 校门外的树
题目描述
某校大门外长度为 的马路上有一排树,每两棵相邻的树之间的间隔都是 米。我们可以把马路看成一个数轴,马路的一端在数轴 的位置,另一端在 的位置;数轴上的每个整数点,即 ,都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上还有多少棵树。
输入格式
第一行有两个整数,分别表示马路的长度 和区域的数目 。
接下来 行,每行两个整数 ,表示一个区域的起始点和终止点的坐标。
输出格式
输出一行一个整数,表示将这些树都移走后,马路上剩余的树木数量。
样例 #1
样例输入 #1
500 3
150 300
100 200
470 471
2
3
4
2
3
4
样例输出 #1
298
提示
【数据范围】
- 对于 的数据,保证区域之间没有重合的部分。
- 对于 的数据,保证 ,,。
【题目来源】
NOIP 2005 普及组第二题
# 通关代码
#include <iostream>
#include <vector>
using namespace std;
int main(){
int road,move_region;
cin >> road >> move_region;
vector<bool> tree_num(road + 1, true);//初始化所有位置都有树
for (int i = 0; i < move_region; ++i) {//++在前,先自增,再返回i值
int u, v;
cin >> u >> v;
for (int j = u; j <= v; ++j){//++在前,先自增,再返回j值
tree_num[j] = false;//砍掉区域内的树
}
}
//计算剩下的树木
int count = 0;
for (int i = 0; i <=road; ++i){
if(tree_num[i]){
//使用if语句会自动检测括号内是不是为true,
//而布尔刚好就有true和false两种状态,
//这么写就等于if (trees[i] == true)
count++;
}
}
cout << count << endl;
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# LG P5728 【深基5.例5】旗鼓相当的对手
题目描述
现有 名同学参加了期末考试,并且获得了每名同学的信息:语文、数学、英语成绩(均为不超过 的自然数)。如果某对学生 的每一科成绩的分差都不大于 ,且总分分差不大于 ,那么这对学生就是“旗鼓相当的对手”。现在想知道这些同学中,有几对“旗鼓相当的对手”?同样一个人可能会和其他好几名同学结对。
输入格式
第一行一个正整数 。
接下来 行,每行三个整数,其中第 行表示第 名同学的语文、数学、英语成绩。最先读入的同学编号为 。
输出格式
输出一个整数,表示“旗鼓相当的对手”的对数。
样例 #1
样例输入 #1
3
90 90 90
85 95 90
80 100 91
2
3
4
2
3
4
样例输出 #1
2
提示
数据保证, 且每科成绩为不超过 的自然数。
# 通关代码
#include <iostream>
#include <vector>
#include <cmath> // 包含cmath库,用于调用abs函数计算绝对值
using namespace std;
// 定义一个结构体用于存储每个学生的三科成绩
struct Student {
int chinese;
int math;
int english;
};
int main() {
int N; // 存储学生的数量
cin >> N; // 从标准输入读取学生数量
vector<Student> students(N); // 创建一个vector,存储所有学生的成绩
// 循环读取每个学生的成绩
for (int i = 0; i < N; ++i) {
cin >> students[i].chinese >> students[i].math >> students[i].english;
}
int count = 0; // 用于计数“旗鼓相当的对手”的对数
// 双层循环比较每两个学生,运用外循环结合内循环,巧妙的把N名孩子的组合数量算了出来,等价于底下的公式。
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
// 检查两个学生之间每科成绩的差距是否都不超过5,且总分差距不超过10
if (abs(students[i].chinese - students[j].chinese) <= 5 &&
abs(students[i].math - students[j].math) <= 5 &&
abs(students[i].english - students[j].english) <= 5 &&
abs(students[i].chinese + students[i].math + students[i].english -
students[j].chinese - students[j].math - students[j].english) <= 10) {
count++; // 如果满足条件,计数器加1
}
}
}
cout << count << endl; // 输出“旗鼓相当的对手”的对数
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 补充知识 组合数公式
两两组合的数量可以通过组合数学中的组合公式来计算。对于从 ( n ) 个不同元素中选取 ( k ) 个元素的组合(不考虑顺序),组合数量可以用以下公式表示:
$ C(n, k) = \frac{n!}{k! \times (n - k)!} $
其中 $ n! n$ 的阶乘,即 $ 1 \times 2 \times 3 \times \ldots \times n $。
如果你要计算6个人中任选2个人的组合数量,即 $ C(6, 2)$,可以将 $ n k $ 设为2,然后代入公式计算。
# 【深基5.例7】工艺品制作(难度较高,暂未解决)
题目描述
现有一个长宽高分别为 组成的实心玻璃立方体,可以认为是由 的数个小方块组成的,每个小方块都有一个坐标 $ ( i,j,k ) $。现在需要进行 次切割。每次切割给出 这 6 个参数,保证 ,,;每次切割时,使用激光工具切出一个立方体空洞,空洞的壁平行于立方体的面,空洞的对角点就是给出的切割参数的两个点。
换句话说,所有满足 ,$y_1\le j \le y_2 z_1\le k\le z_2$ 的小方块 的点都会被激光蒸发。例如有一个 的大方块,其体积为 ;给出参数 时,中间的 块小方块就会被蒸发,剩下 个小方块。现在想知道经过所有切割操作后,剩下的工艺品还剩下多少格小方块的体积?
输入格式
第一行三个正整数 。
第二行一个正整数 。
接下来 行,每行六个整数 。
输出格式
输出一个整数表示答案。
样例 #1
样例输入 #1
4 4 4
1
1 1 1 2 2 2
2
3
2
3
样例输出 #1
56
提示
数据保证,,。,,。
# 通关代码
#include <iostream>
#include <vector>
using namespace std;
int main() {
int w, x, h; // 定义立方体的长宽高
cin >> w >> x >> h; // 从标准输入读取长宽高
// 创建一个三维布尔数组,初始时每个小方块都是存在的(true)
vector<vector<vector<bool>>> cube(w, vector<vector<bool>>(x, vector<bool>(h, true)));
int q; // 存储切割次数
cin >> q; // 从标准输入读取切割次数
while (q--) { // 对每次切割进行处理
int x1, y1, z1, x2, y2, z2; // 存储每次切割的两个对角坐标
cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2; // 读取切割的对角坐标
// 遍历切割区域内的每个小方块,并将其标记为不存在(false)
for (int i = x1 - 1; i < x2; ++i) {
for (int j = y1 - 1; j < y2; ++j) {
for (int k = z1 - 1; k < z2; ++k) {
cube[i][j][k] = false;
}
}
}
}
int count = 0; // 用于计数剩余小方块的数量
// 遍历整个立方体,计算剩余的小方块数量
for (int i = 0; i < w; ++i) {
for (int j = 0; j < x; ++j) {
for (int k = 0; k < h; ++k) {
if (cube[i][j][k]) { // 如果小方块存在,计数加一
count++;
}
}
}
}
cout << count << endl; // 输出剩余小方块的数量
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 梦中的统计
题目背景
Bessie 处于半梦半醒的状态。过了一会儿,她意识到她在数数,不能入睡。
题目描述
Bessie 的大脑反应灵敏,仿佛真实地看到了她数过的一个又一个数。她开始注意每一个数码():每一个数码在计数的过程中出现过多少次?
给出两个整数 和 ,求在序列 中每一个数码出现了多少次。
输入格式
第 行: 两个用空格分开的整数 和 。
输出格式
第 行: 十个用空格分开的整数,分别表示数码 在序列中出现的次数。
样例 #1
样例输入 #1
129 137
样例输出 #1
1 10 2 9 1 1 1 1 0 1
提示
数据保证,,。
# 通关代码
#include <iostream>
#include <vector>
using namespace std;
// 辅助函数,用于拆分数字并统计每位数的出现次数
void countDigits(int num, vector<int>& digitCount) {//"&"是引用符号,代表这个向量是直接被引用的
while (num > 0) {
digitCount[num % 10]++; // 把digitcount数组对应索引位置的参数增加对应数字的计数
num /= 10; // 移除已处理的最后一位数字
}
}
int main() {
int M, N;
cin >> M >> N; // 从标准输入读取两个整数 M 和 N
vector<int> digitCount(10, 0); // 初始化一个大小为10的向量,用于存储每个数字(0-9)的出现次数
// 会得到一个这样的数组{0,0,0,0,0,0,0,0,0,0}
// 遍历从 M 到 N 的所有数字
for (int i = M; i <= N; ++i) {
countDigits(i, digitCount); // 对每个数字进行拆分并统计每位数的出现次数
}
// 打印结果
for (int i = 0; i < 10; ++i) {
cout << digitCount[i] << " "; // 打印每个数字的出现次数
}
cout << endl; // 在最后输出一个换行符
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 知识点思考
在代码开头写了一个辅助函数,用来辅助后面的运算,可以看到在这个位置
vector<int>& digitCount
使用了&
这个符号,这个符号的意思是引用符号,意味着这个动态数组将会直接被引用,在这个特定的情况下,如果你在 countDigits
函数的参数中不使用 &
(即不使用引用传递),程序仍然可以运行,但它将无法按预期工作。原因在于不使用引用传递意味着函数将接收 digitCount
向量的一个副本,而非原始向量本身。
不使用引用传递的后果是:
副本创建:当
digitCount
作为参数传递给countDigits
函数时,将创建它的一个副本。这意味着在函数内部对digitCount
所做的任何更改都只会影响这个副本,而不会影响原始向量。无法更新原始向量:由于
digitCount
在函数中是一个副本,因此函数内对其的修改不会反映到调用函数时使用的原始向量中。这意味着尽管函数可能正确地计算了数字的出现次数,但这些计算结果不会被保存到原始的digitCount
向量中。性能问题:对于大型数据结构(如向量),创建副本可能会导致不必要的性能开销。
因此,如果你希望 countDigits
函数能够实际更新传递给它的 digitCount
向量,你应该使用引用传递(即在参数前加上 &
)。这确保了函数内对向量所做的任何更改都会直接反映到原始向量上,从而使得这些更改在函数外部也是有效的。