Tommy's Blog
TommyZeng
2024-01-25
目录

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
1
2
3
4
5
6
7
8
1
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
1
2
3
4
5
6
7
1
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;
}
1
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
1
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

# 问题思考：

  1. +=和+运算符的区别

    在上文的代码中有一行是

    s += "/";
    1
    1

    其效果是把API路径的末尾额外再加一个/符号，但如果单纯是实现这个效果，使用以下代码也可以，但实际上这样会导致运行出错。

    s + "/";
    1
    1

    在C语言的运行过程中，采用+=只会在原字符串的基础上进行修改，而+则是在原字符串的基础上进行运算后生成新的字符串，在上面代码的逻辑中，只需要改变 s 本身，而不是创建一个新的、未使用的字符串。

  2. 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
    7
    1
    2
    3
    4
    5
    6
    7

# LG B2004 对齐输出

题目描述

读入三个整数，按每个整数占 88 个字符的宽度，右对齐输出它们，按照格式要求依次输出三个整数，之间以一个空格分开。

输入格式

只有一行，包含三个整数 a,b,ca,b,c。整数之间以一个空格分开。

输出格式

只有一行，按照格式要求依次输出三个整数，之间以一个空格分开。

样例 #1

样例输入 #1

123456789 0 -1
1
1

样例输出 #1

123456789        0       -1
1
1

提示

对于 100%100 \% 的数据，−231≤a,b,c<231-2^{31} \le a, b, c < 2^{31}。

# 通过代码

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# LG B2012 甲流疫情死亡率

题目描述

甲流并不可怕，在中国，它的死亡率并不是很高。请根据截止 20092009 年 1212 月 2222 日各省报告的甲流确诊数 aa 和死亡数 bb，计算甲流在各省的死亡率。

输入格式

输入共两行，第一行一个整数为确诊数 aa，第二行一个整数为死亡数 bb。

输出格式

输出仅一行，甲流死亡率，以百分数形式输出，精确到小数点后 33 位。

样例 #1

样例输入 #1

10433
60
1
2
1
2

样例输出 #1

0.575%
1
1

提示

数据规模与约定

对于全部的测试点，保证 1≤a,b≤1041 \leq a, b \leq 10^4。

提示

在 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
1
2
3
4
5
6
7
8
9
10
11
12

# 问题思考

  1. C++的运算赋值写法使用不当

    #include <iostream>
using namespace std;
int main() {
    // 正确的赋值操作
    c = b / a;
    // 错误的赋值操作
    b / a = c;

}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

# LG P1002 [NOIP2002 普及组] 过河卒

题目描述

棋盘上 AA 点有一个过河卒，需要走到目标 BB 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，AA 点 (0,0)(0, 0)、BB 点 (n,m)(n, m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 AA 点能够到达 BB 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 BB 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

样例 #1

样例输入 #1

6 6 3 3
1
1

样例输出 #1

6
1
1

数据范围：

对于 100%100 \% 的数据，1≤n,m≤201 \le n, m \le 20，0≤0 \le 马的坐标 ≤20\le 20。

【题目来源】

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;
}
1
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
1
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,2,3,4,…1,2,3,4,\dots。

每一盏灯只有两种可能的状态，开或者关。如果按一下某一盏灯的开关，那么这盏灯的状态将发生改变。如果原来是开，将变成关。如果原来是关，将变成开。

在刚开始的时候，所有的灯都是关的。小明每次可以进行如下的操作：

指定两个数，a,ta,t（aa 为实数，tt 为正整数）。将编号为 ⌊a⌋,⌊2×a⌋,⌊3×a⌋,…,⌊t×a⌋\lfloor a\rfloor,\lfloor 2 \times a\rfloor,\lfloor3 \times a\rfloor,\dots,\lfloor t \times a\rfloor 的灯的开关各按一次。其中 ⌊k⌋\lfloor k \rfloor 表示实数 kk 的整数部分。

在小明进行了 nn 次操作后，小明突然发现，这个时候只有一盏灯是开的，小明很想知道这盏灯的编号，可是这盏灯离小明太远了，小明看不清编号是多少。

幸好，小明还记得之前的 nn 次操作。于是小明找到了你，你能帮他计算出这盏开着的灯的编号吗？

输入格式

第一行一个正整数 nn，表示 nn 次操作。

接下来有 nn 行，每行两个数，ai,tia_i,t_i。其中 aia_i 是实数，小数点后一定有 66 位，tit_i 是正整数。

输出格式

仅一个正整数，那盏开着的灯的编号。

样例 #1

样例输入 #1

3
1.618034 13
2.618034 7
1.000000 21
1
2
3
4
1
2
3
4

样例输出 #1

20
1
1

提示

记 T=∑i=1nti=t1+t2+t3+⋯+tnT=\sum \limits_{i=1}^n t_i = t_1+t_2+t_3+\dots+t_n。

  • 对于 30%30\% 的数据，满足 T≤1000T \le 1000；
  • 对于 80%80\% 的数据，满足 T≤200000T \le 200000；
  • 对于 100%100\% 的数据，满足 T≤2000000T \le 2000000；
  • 对于 100%100\% 的数据，满足 n≤5000n \le 5000，1≤ai<10001 \le a_i<1000，1≤ti≤T1 \le t_i \le T。

数据保证，在经过 nn 次操作后，有且只有一盏灯是开的，不必判错。而且对于所有的 ii 来说，ti×ait_i\times a_i 的最大值不超过 20000002000000​。

# 通关代码

#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;
}
1
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
1
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 小玉在游泳

题目描述

小玉开心的在游泳，可是她很快难过的发现，自己的力气不够，游泳好累哦。已知小玉第一步能游 22 米，可是随着越来越累，力气越来越小，她接下来的每一步都只能游出上一步距离的 98%98\%。现在小玉想知道，如果要游到距离 ss 米的地方，她需要游多少步呢。请你编程解决这个问题。

输入格式

输入一个实数 ss（单位：米），表示要游的目标距离。

输出格式

输出一个整数，表示小玉一共需要游多少步。

样例 #1

样例输入 #1

4.3
1
1

样例输出 #1

3
1
1

提示

数据保证，0≤s<1000 \leq s < 100，且 ss 小数点后最多只有一位。

# 通关代码

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1
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 非常的不爽。他宁可忍受北极的寒冷，也不愿忍受厦门的夏天。最近，他开始研究天气的变化。他希望用研究的结果预测未来的天气。

经历千辛万苦，他收集了连续 N(1≤N≤106)N(1 \leq N \leq 10^6) 天的最高气温数据。

现在，他想知道最高气温一直上升的最长连续天数。

输入格式

第 1 行：一个整数 NN 。1≤N≤1061 \leq N \leq 10^6

第 2 行：NN个空格隔开的整数，表示连续 NN 天的最高气温。0≤0 \leq 最高气温 ≤109\leq 10^9 。

输出格式

1 行：一个整数，表示最高气温一直上升的最长连续天数。

样例 #1

样例输入 #1

10
1 2 3 2 4 5 6 8 5 9
1
2
1
2

样例输出 #1

5
1
1

# 通关代码

#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;
}
1
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
1
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

# 问题思考

  1. Max函数其实是头文件#include <algorithm>中的，这个头文件很多编译器会隐式引用，所以即使不写在最前头，也能正常运行，但如果严谨来看，最好还是写上，以保证多平台的运行能力。
  2. 代码中使用到了vector头文件以运用vector动态数组，动态数组的好处很多，使用比较简单，但相比较普通数组，会占用更多运算资源，在数组规模可预测的情况下，使用普通数组是性能最优的。

# LG P1427 小鱼的数字游戏

题目描述

小鱼最近被要求参加一个数字游戏，要求它把看到的一串数字 aia_i（长度不一定，以 00 结束），记住了然后反着念出来（表示结束的数字 00 就不要念出来了）。这对小鱼的那点记忆力来说实在是太难了，你也不想想小鱼的整个脑袋才多大，其中一部分还是好吃的肉！所以请你帮小鱼编程解决这个问题。

输入格式

一行内输入一串整数，以 00 结束，以空格间隔。

输出格式

一行内倒着输出这一串整数，以空格间隔。

样例 #1

样例输入 #1

3 65 23 5 34 1 30 0
1
1

样例输出 #1

30 1 34 5 23 65 3
1
1

提示

数据规模与约定

对于 100%100\% 的数据，保证 0≤ai≤231−10 \leq a_i \leq 2^{31} - 1，数字个数不超过 100100。

# 通关代码

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 问题思考

  1. numbers.push_back(num);:

    push_back 是 std::vector 的一个成员函数，用于在 vector 的末尾添加一个新元素。 当你调用 numbers.push_back(num); 时，num 的值被添加到 vector numbers 的末尾。 这意味着你不需要预先知道 vector 中将存储多少个元素，因为 vector 会根据需要动态地调整其大小。

  2. 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 冰雹猜想

题目描述

给出一个正整数 nn，然后对这个数字一直进行下面的操作：如果这个数字是奇数，那么将其乘 33 再加 11，否则除以 22。经过若干次循环后，最终都会回到 11。经过验证很大的数字（7×10117\times10^{11}）都可以按照这样的方式比变成 11，所以被称为“冰雹猜想”。例如当 nn 是 2020，变化的过程是 20→10→5→16→8→4→2→120\to 10\to 5\to 16\to 8\to 4\to 2\to 1。

根据给定的数字，验证这个猜想，并从最后的 11 开始，倒序输出整个变化序列。

输入格式

输入一个正整数 nn。

输出格式

输出若干个由空格隔开的正整数，表示从最后的 11 开始倒序的变化数列。

样例 #1

样例输入 #1

20
1
1

样例输出 #1

1 2 4 8 16 5 10 20
1
1

提示

数据保证，1≤n≤1001 \le n\le 100。

通关代码

#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;
    
}
1
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
1
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 校门外的树

题目描述

某校大门外长度为 ll 的马路上有一排树，每两棵相邻的树之间的间隔都是 11 米。我们可以把马路看成一个数轴，马路的一端在数轴 00 的位置，另一端在 ll 的位置；数轴上的每个整数点，即 0,1,2,…,l0,1,2,\dots,l，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入格式

第一行有两个整数，分别表示马路的长度 ll 和区域的数目 mm。

接下来 mm 行，每行两个整数 u,vu, v，表示一个区域的起始点和终止点的坐标。

输出格式

输出一行一个整数，表示将这些树都移走后，马路上剩余的树木数量。

样例 #1

样例输入 #1

500 3
150 300
100 200
470 471
1
2
3
4
1
2
3
4

样例输出 #1

298
1
1

提示

【数据范围】

  • 对于 20%20\% 的数据，保证区域之间没有重合的部分。
  • 对于 100%100\% 的数据，保证 1≤l≤1041 \leq l \leq 10^4，1≤m≤1001 \leq m \leq 100，0≤u≤v≤l0 \leq u \leq v \leq l。

【题目来源】

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;
    
}
1
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
1
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】旗鼓相当的对手

题目描述

现有 NN 名同学参加了期末考试，并且获得了每名同学的信息：语文、数学、英语成绩（均为不超过 150150 的自然数）。如果某对学生 ⟨i,j⟩\lang i,j\rang 的每一科成绩的分差都不大于 55，且总分分差不大于 1010，那么这对学生就是“旗鼓相当的对手”。现在想知道这些同学中，有几对“旗鼓相当的对手”？同样一个人可能会和其他好几名同学结对。

输入格式

第一行一个正整数 NN。

接下来 NN 行，每行三个整数，其中第 ii 行表示第 ii 名同学的语文、数学、英语成绩。最先读入的同学编号为 11。

输出格式

输出一个整数，表示“旗鼓相当的对手”的对数。

样例 #1

样例输入 #1

3
90 90 90
85 95 90
80 100 91
1
2
3
4
1
2
3
4

样例输出 #1

2
1
1

提示

数据保证，2≤N≤10002 \le N\le 1000 且每科成绩为不超过 150150 的自然数。

# 通关代码

#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;
}
1
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
1
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 设为6，设为6， k $ 设为2，然后代入公式计算。

# 【深基5.例7】工艺品制作(难度较高，暂未解决)

题目描述

现有一个长宽高分别为 w,x,hw,x,h 组成的实心玻璃立方体，可以认为是由 1×1×11\times1\times1 的数个小方块组成的，每个小方块都有一个坐标 $ ( i,j,k ) $。现在需要进行 qq 次切割。每次切割给出 (x1,y1,z1),(x2,y2,z2)(x_1,y_1,z_1),(x_2,y_2,z_2) 这 6 个参数，保证 x1≤x2x_1\le x_2，y1≤y2y_1\le y_2，z1≤z2z_1\le z_2；每次切割时，使用激光工具切出一个立方体空洞，空洞的壁平行于立方体的面，空洞的对角点就是给出的切割参数的两个点。

换句话说，所有满足 x1≤i≤x2x_1\le i\le x_2，$y_1\le j \le y_2 ，，z_1\le k\le z_2$ 的小方块 (i,j,k)(i,j,k) 的点都会被激光蒸发。例如有一个 4×4×44\times4\times 4 的大方块，其体积为 6464；给出参数 (1,1,1),(2,2,2)(1,1,1),(2,2,2) 时，中间的 88 块小方块就会被蒸发，剩下 5656 个小方块。现在想知道经过所有切割操作后，剩下的工艺品还剩下多少格小方块的体积？

输入格式

第一行三个正整数 w,x,hw,x,h。

第二行一个正整数 qq。

接下来 qq 行，每行六个整数 (x1,y1,z1),(x2,y2,z2)(x_1,y_1,z_1),(x_2,y_2,z_2)。

输出格式

输出一个整数表示答案。

样例 #1

样例输入 #1

4 4 4
1
1 1 1 2 2 2
1
2
3
1
2
3

样例输出 #1

56
1
1

提示

数据保证，1≤w,x,h≤201\le w,x,h\le 20，1≤q≤1001 \leq q\le 100。1≤x1≤x2≤w1 \leq x_1 \leq x_2 \leq w，1≤y1≤y2≤x1 \leq y_1\leq y_2 \leq x，1≤z1≤z2≤h1 \leq z_1 \leq z_2 \leq h​​。

# 通关代码

#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;
}
1
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
1
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 的大脑反应灵敏，仿佛真实地看到了她数过的一个又一个数。她开始注意每一个数码（0…90 \ldots 9）：每一个数码在计数的过程中出现过多少次？

给出两个整数 MM 和 NN，求在序列 [M,M+1,M+2,…,N−1,N][M, M + 1, M + 2, \ldots, N - 1, N] 中每一个数码出现了多少次。

输入格式

第 11 行: 两个用空格分开的整数 MM 和 NN。

输出格式

第 11 行: 十个用空格分开的整数，分别表示数码 0…90 \ldots 9 在序列中出现的次数。

样例 #1

样例输入 #1

129 137
1
1

样例输出 #1

1 10 2 9 1 1 1 1 0 1
1
1

提示

数据保证，1≤M≤N≤2×1091 \leq M \leq N \leq 2 \times 10^9，N−M≤5×105N-M \leq 5 \times 10^5。

# 通关代码

#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;
}
1
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
1
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
1
1

使用了&这个符号，这个符号的意思是引用符号，意味着这个动态数组将会直接被引用，在这个特定的情况下，如果你在 countDigits 函数的参数中不使用 &（即不使用引用传递），程序仍然可以运行，但它将无法按预期工作。原因在于不使用引用传递意味着函数将接收 digitCount 向量的一个副本，而非原始向量本身。

不使用引用传递的后果是：

  1. 副本创建：当 digitCount 作为参数传递给 countDigits 函数时，将创建它的一个副本。这意味着在函数内部对 digitCount 所做的任何更改都只会影响这个副本，而不会影响原始向量。

  2. 无法更新原始向量：由于 digitCount 在函数中是一个副本，因此函数内对其的修改不会反映到调用函数时使用的原始向量中。这意味着尽管函数可能正确地计算了数字的出现次数，但这些计算结果不会被保存到原始的 digitCount 向量中。

  3. 性能问题：对于大型数据结构（如向量），创建副本可能会导致不必要的性能开销。

因此，如果你希望 countDigits 函数能够实际更新传递给它的 digitCount 向量，你应该使用引用传递（即在参数前加上 &）。这确保了函数内对向量所做的任何更改都会直接反映到原始向量上，从而使得这些更改在函数外部也是有效的。

在线编辑 (opens new window)
#C++刷题
最近编辑时间: 2024/01/27 20:20:23
头文件资料库
P5735

← P5735→

最近更新
01
本站维护方法(防止遗忘)
01-27
02
Speaking Corpus
04-28
03
Speaking Reference
04-24
更多文章>
Theme by Vdoing | Copyright © 2021-2025 | 备案信息:10086号