寒假第一讲：C++ 基础

一.Long Loong

1.对应思路

思路较为简单，就是先固定输出L，再根据输入的N得到应该输出多少o，最后再固定输出ng。

2.代码

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	cout << 'L';
	for (int i = 0; i < n; i++)
		cout << 'o';
	cout << "ng";
	return 0;
}

3.学习总结

学到了for循环的基本用法，对我帮助极大，受益良多。

二.YES or YES?

1.对应思路

思路就是将输入的字符串全部大写，然后判断是否等于YES，如果等于就输出YES，不等于就输出NO。

2.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <string>
#include <algorithm> 
using namespace std;
int main() {
    int t; 
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        transform(s.begin(), s.end(), s.begin(), ::toupper);
        if (s == "YES") {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

3.学习总结

  1. 字符串处理：通过 transform 配合 tolower 或 toupper，可以快速将字符串统一为小写或大写，便于比较。
  2. 循环与分支：利用 while (t--) 循环高效处理多组输入，结合 if-else 判断分类处理逻辑。
  3. 时间复杂度：转换大小写或比较字符串的复杂度为 O(字符串长度)O(\text{字符串长度})O(字符串长度)。整体复杂度为 O(t)O(t)O(t)，适用于测试用例较多的情况。
  4. STL 使用：标准库函数如 transform 和字符串直接比较提升了代码简洁性和可靠性。

三.Even? Odd? G

1.对应思路

这个程序的主要任务是根据输入的一组超大整数，判断每个整数的奇偶性（即最后一位数字是偶数还是奇数）。由于数的范围可能非常大（高达 106010^{60}1060），无法直接使用普通整数类型（如 int 或 long long），所以采用字符串处理的方式。

2.代码

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
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {

    int N;
    cin >> N;

    vector<string> results;

    for (int i = 0; i < N; ++i) {
        string number;
        cin >> number;

        char lastDigit = number[number.length() - 1];
        if ((lastDigit - '0') % 2 == 0) {
            results.push_back("even");
        } else {
            results.push_back("odd");
        }
    }

    for (const string& result : results) {
        cout << result << endl;
    }

    return 0;
}

3.学习总结

字符串处理大数：

  • 当数字的范围超过内置类型的支持时，可以用字符串表示并处理。
  • 判断奇偶性只需关注数字的最后一位，简化了大数的操作。

模运算的应用：

  • 奇偶性的本质是看数字能否被 222 整除，通过 mod  2\mod 2mod2 运算即可实现。

四.Problem Generator

1.对应思路

  1. 输入处理
  • 读取测试用例数量 t。
  • 对于每个测试用例，读取两个整数 n（题库题目数量）和 m（比赛轮次），以及一个字符串 a 表示题库中的题目难度。
  1. 统计题目数量
  • 使用7个变量 n1 到 n7 分别记录每种难度（A到G）的题目数量。
  • 遍历字符串 a，通过比较字符 c 是否为 ‘A’ 到 ‘G’ 来对每种难度的题目计数。
  1. 每种难度的最大需求
  • 每轮比赛需要一个完整的难度级别（A到G），即每种难度最多需要 mmm 道题。
  1. 计算需要补充的题目数量

  • 每轮比赛需要7种难度的题目，因此总需求为 7×m7 \times m7×m。

  • 当前已有的题目总量为 n1+n2+⋯+n7n1 + n2 + \dots + n7n1+n2+⋯+n7。

  • 需要补充的题目数量为： 需要补充=max⁡(0,7×m−当前已有的题目总量)\text{需要补充} = \max(0, 7 \times m - \text{当前已有的题目总量})需要补充=max(0,7×m−当前已有的题目总量)

  • 如果已有题目足够，则补充为0；否则补充缺少的题目数量。

  1. 输出结果
  • 将每个测试用例的结果输出在单独的一行。

2.代码

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
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main() {
    int t;
    cin >> t;   
 
    while (t--) {
        int n, m;
        cin >> n >> m;
        string a;
        cin >> a;
        int n1 = 0, n2 = 0, n3 = 0, n4 = 0, n5 = 0, n6 = 0, n7 = 0;
        for (char c : a)
        {
            if (c == 'A')
                n1++;
            if (c == 'B')
                n2++;
            if (c == 'C')
                n3++;
            if (c == 'D')
                n4++;
            if (c == 'E')
                n5++;
            if (c == 'F')
                n6++;
            if (c == 'G')
                n7++;
        }
        if (n1 > m)
            n1 = m;
        if (n2 > m)
            n2 = m;
        if (n3 > m)
            n3 = m;
        if (n4 > m)
            n4 = m;
        if (n5 > m)
            n5 = m;
        if (n6 > m)
            n6 = m;
        if (n7 > m)
            n7 = m;
        cout << max(0, 7 * m - n1 - n2 - n3 - n4 - n5 - n6 - n7) << endl;
    }
 
    return 0;
}

3.学习总结

  • 本题通过统计每种难度题目的数量解决问题。这是字符频率统计的典型应用。

  • 通过遍历字符串并比较字符，可以有效统计各类别出现次数。

五.rules

1.对应思路

这段代码解决的问题是考察规则是否符合民意，主要步骤如下：

  1. 输入数据：首先读取居民总数 n、记录天数 m 以及规则代号 k。

  2. 统计符合民意的天数：

    循环 m 次，表示逐天处理记录。

    对每一天，统计有多少居民遵守了规则 k（计数器 c2）。

    如果遵守规则 k 的人数大于等于一半 (c2 * 2 >= n)，则该天规则符合民意，符合民意的天数计数器 c1 加一。

  3. 判断规则正确性

    ：如果符合民意的天数大于等于记录天数的一半 (c1 * 2 >= m)，输出 “YES” 表示规则正确，否则输出 “NO”。

2.代码

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
#include <iostream>
using namespace std;
int main()
{
	int m, n, k;
	int c1 = 0, c2 = 0;
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++)
	{
		c2 = 0;
		for (int j = 0; j < n; j++) {
			int t;
			cin >> t;
			if (t == k)
			{
				c2++;
			}
			
			
		}
		if ( c2*2 >=  n)
			{
				c1++;
				
			}
	}if ( c1*2 >=  m)
			{
				cout << "YES";
				
			}
	else
	cout << "NO";
	return 0;
}

3.学习总结

这道题目涉及多重循环的处理，是学习数组与条件判断的重要练习。通过这段代码可以总结如下：

  1. 理解核心逻辑

    问题的核心在于两层判断：一是某天规则是否符合民意，二是统计符合民意的天数是否达到要求。这种多层嵌套条件是常见的编程模式。

  2. 优化循环效率

    本代码通过双重循环按天和按人处理问题，时间复杂度为 O(m×n)O(m \times n)O(m×n)。这种结构在处理范围较大时可能需要优化。

  3. 掌握计数逻辑

    使用计数器 c2 和 c1 逐步累积数据，并通过条件判断更新状态。这种逻辑清晰、简洁，适合复杂问题分步解决。

六.Many Replacement

1.对应思路

  1. 初始化映射表：

    创建一个 mapping 数组，长度为 26（表示字母表），初始化为 'a' 到 'z' 的对应字母。这个表将用于记录字母替换关系。

  2. 处理替换操作：

    对每个替换指令 (c, d)，遍历 mapping 数组，将所有值等于 c 的项替换为 d。

    这种方式确保了间接替换链条也能正确生效。例如，如果先将 a 替换为 b，再将 b 替换为 c，最终 a 也会被替换为 c。

  3. 修改字符串：

    遍历字符串 S 的每个字符，根据 mapping 数组中的映射关系，将字符替换为最终映射的目标字符。

  4. 输出结果：

    输出修改后的字符串 S。

通过使用 mapping 数组记录全局映射关系，避免直接修改字符串多次，提高了处理效率。

2.代码

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
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int N, Q;
    cin >> N;
    string S;
    cin >> S;
    cin >> Q;

    vector<char> mapping(26);
    for (int i = 0; i < 26; i++) {
        mapping[i] = 'a' + i; 
    }

    for (int i = 0; i < Q; i++) {
        char c, d;
        cin >> c >> d;
        for (int j = 0; j < 26; j++) {
            if (mapping[j] == c) {
                mapping[j] = d;
            }
        }
    }

    for (char &ch : S) {
        ch = mapping[ch - 'a']; 
    }

    cout << S << endl;
    return 0;
}

3.学习总结

1.高效处理替换链：

使用一个映射表 (mapping 数组) 将字符替换逻辑统一管理，避免了直接在字符串中进行多次替换操作，降低了时间复杂度。

2.间接替换链的处理：

通过在处理替换指令时遍历整个映射表，确保链式替换得到正确结果。这种方法适用于有依赖关系的替换问题。

3.复杂度优化：

替换操作遍历 mapping 的复杂度为 O(Q×26)O(Q \times 26)O(Q×26)，字符串替换为 O(N)O(N)O(N)，整体复杂度约为 O(Q+N)O(Q + N)O(Q+N)，足以处理较大输入规模。

4.边界条件考虑：

替换字符可以是相同的（c = d），这种情况不会影响映射表。

某些字符可能不存在于字符串中，但替换逻辑依然可以正常处理。

更好的交换

1.对应思路

  1. 输入与初始化：

    读取矩阵大小 n 和操作次数 m。

    读取矩阵内容并存储在 matrix 中。

    初始化两个数组 row_map 和 col_map，分别记录行和列的映射关系，初始值为 [0, 1, 2, ..., n-1]。

  2. 操作处理：

    遍历每个操作，根据操作类型：

    若 op == 1（交换行），则交换 row_map[x] 和 row_map[y]。

    若 op == 0（交换列），则交换 col_map[x] 和 col_map[y]。

    通过修改 row_map 和 col_map 的映射关系，而非直接修改矩阵，节省了时间复杂度。

  3. 输出矩阵：

    根据最终的 row_map 和 col_map，重新按映射顺序输出矩阵。matrix[row_map[i]][col_map[j]] 得到正确的映射值。

通过这种间接映射法，避免了每次交换直接操作矩阵，提高了效率，适合大规模输入。

2.代码

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
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> matrix[i][j];
        }
    }
    vector<int> row_map(n), col_map(n);
    for (int i = 0; i < n; ++i) {
        row_map[i] = i; 
        col_map[i] = i; 
    }

    for (int i = 0; i < m; ++i) {
        int op, x, y;
        cin >> op >> x >> y;
        --x; 
        --y;
        if (op == 1) {
            swap(row_map[x], row_map[y]); 
        } else {
            swap(col_map[x], col_map[y]); 
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << matrix[row_map[i]][col_map[j]] << " ";
        }
        cout << endl;
    }

    return 0;
}

3.学习总结

间接映射优化：

​ 直接交换矩阵行列会带来高昂的时间复杂度，间接通过映射数组调整顺序是一种高效的解决方式。

空间与时间的平衡：

​ 增加两个映射数组 row_map 和 col_map，用空间换取了时间的优化。

​ 在 mmm 次操作和 n2n^2n2 次矩阵访问中，复杂度降低为 O(n2+m)O(n^2 + m)O(n2+m)，适合处理大规模 n,mn, mn,m。