天梯赛合集

算法

临时抱佛脚中，可能已经两三个月不写代码了。要比赛了其实有些担心。但是没有关系，成绩不好也没关系，因为我一定下次会更好。我应当取得的成绩是一定会得到的。现在是临时抱佛脚的总结。

接下来我会把题目按照三个等级整理，L1,L2,L3

L1

L1-5 这是字符串题

image-20260313230850389

其实就是一个映射题目啦，第一个输入用string读入，第二个输入对应的是第i个字母的美观值。那直接用一个数组存。要求计算第i个小写字母出现了多少次，用一个数组来计数，把字母映射为字母的数字顺序（s[i]-‘a’+1）。得分就是两个映射，先映射为数字，再用美观值数组映射美观值。代码附上

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
#include <bits/stdc++.h>
using namespace std;
int ch[10000];
int ans[10000];
void solve()
{
    string s;
    int sum = 0;
    cin >> s;
    for (int i = 1; i <= 26; i++) {
        int x;
        cin >> x;
        ch[i] = x;
    }
    for (int i = 0; i < s.size(); i++) {
        sum += ch[s[i] - 'a' + 1];
        ans[s[i] - 'a' + 1]++;
    }
    for (int i = 1; i <= 26; i++) {
        if(i==26){
            cout <<ans[i];
        }
        else{
           cout << ans[i] << " "; 
        }
        
    }
    cout << endl
         << sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

L1-7 大幂数

image-20260313232345212

当你试图寻找某些规律时，就会发现没有规律，所以这道题只能枚举了。暴力呢，也要有策略的暴力，这道题是有两个变量的，底数个数和幂k。因为k越大，枚举项数越小，而且k有上限31，所以从31开始从大到小遍历。如果内层遍历项数的循环大于所给数了，break掉这层循环开始尝试下一个k。

但是这里涉及时间的问题，是的我们需要用到快速幂。

补一下快速幂模板，这是原理

image-20260313233639524

这是代码

1
2
3
4
5
6
7
8
9
10
11
long long fast_pow(long long base, int exp)
{
    long long result = 1;
    while (exp > 0) {
        if (exp & 1)
            result *= base;
        base *= base;
        exp >>= 1;
    }
    return result;
}

但是呢你用这个写就会wa。为什么呢

  • i=100, k=10 → 100^10 ≈ 10^20，已经超过 long long 最大值。

但我们真正关心的是：i^k 是否已经超过 n。如果 i^k > n，那么 sum = 1^k + 2^k + ... + i^k 一定大于 n（因为所有项都是正数），所以我们可以提前停止循环，不需要继续计算更大的 i。

所以我们进行一个剪枝

1
2
3
4
5
6
7
8
9
10
11
long long safe_pow(long long base, int exp, long long limit)
{
    long long result = 1;
    for (int i = 0; i < exp; ++i) {
        if (limit / base < result) {
            return limit + 1;   // 表示幂结果已经超过 limit
        }
        result *= base;
    }
    return result;
}

ok，附上完整代码

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
#include <bits/stdc++.h>
using namespace std;

long long safe_pow(long long base, int exp, long long limit)
{
    long long result = 1;
    for (int i = 0; i < exp; ++i) {
        if (limit / base < result) {
            return limit + 1;   // 表示幂结果已经超过 limit
        }
        result *= base;
    }
    return result;
}

void solve()
{
    long long n;
    cin >> n;

    for (int k = 30; k >= 1; k--) {
        long long sum = 0;

        for (int i = 1;; i++) {
            long long power = safe_pow(i, k, n);
            sum += power;

            if (sum == n) {
                for (int j = 1; j <= i; j++) {
                    if (j > 1) cout << "+";
                    cout << j << "^" << k;
                }
                cout << endl;
                return;
            }

            if (sum > n || power > n) {
                break;
            }
        }
    }
    cout << "Impossible for " << n << "." << endl;
}

int main()
{
    solve();
    return 0;
}

L1-8 现代战争

image-20260313235724009

嗯一道语法题

  1. 数据结构设计
    • 使用结构体数组存储每个建筑的位置和价值
    • 使用row和col数组标记被炸掉的行和列
  2. 核心算法流程
    • 读取地图数据，同时将所有建筑信息存入结构体数组
    • 按建筑价值排序（从小到大）
    • 从大到小选择k个未被炸掉的最高价值建筑进行轰炸
    • 输出剩余的行和列组成的缩小后地图
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
struct node
{
	int x;
	int y;
	int w;
}nodes[ 1000005 ];
 
int mp[ 1005 ][ 1005 ];
int row[ 1005 ];
int col[ 1005 ];
 
int cmp( node a, node b )
{
	return a.w < b.w;
}
 
int n, m, k;
int length = 0;
 
int main ( )
{
	memset( row, 0, sizeof ( row ) );
	memset( col, 0, sizeof ( col ) );
	cin >> n >> m >> k;
 
	for ( int i = 0; i < n; ++ i )
	{
		for ( int j = 0; j < m; ++ j )
		{
			cin >> mp[ i ][ j ];
			nodes[ length ].x = i;
			nodes[ length ].y = j;
			nodes[ length ].w = mp[ i ][ j ];
			++ length;
		}
	}
	sort ( nodes, nodes + length, cmp );
 
	int x, y;
	while ( k )
	{
		-- length;
		x = nodes[ length ].x;
		y = nodes[ length ].y;
		if ( row[ x ] || col[ y ] )
			continue;
		++ row[ x ];
		++ col[ y ];	
		-- k;
	}
    int flag;
	for ( int i = 0; i < n; ++ i )
	{
		if ( row[ i ] )
			continue;
        flag = 1;
		for ( int j = 0; j < m; ++ j )
		{
			if ( col[ j ] )
				continue;
            if ( flag )
            {
                cout << mp[ i ][ j ];
                flag = 0;
            }
            else
                cout << " "<< mp[ i ][ j ];
		}
		cout << endl;
	}
 
	return 0;
}

map用法

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
#include <bits/stdc++.h>
using namespace std;

// 1. 不同的定义方式
void map_definition() {
    // 默认升序 map (按键从小到大)
    map<int, string> m1;
    
    // 降序 map (按键从大到小)
    map<int, string, greater<int>> m2;
    
    // 自定义排序规则
    struct cmp {
        bool operator()(int a, int b) const {
            return a % 10 < b % 10;  // 按个位数排序
        }
    };
    map<int, string, cmp> m3;
}

// 2. 插入元素
void map_insert() {
    map<int, string> m;
    
    // 方法1: 使用 [] 操作符 (如果键不存在则创建，存在则修改)
    m[1] = "one";
    m[2] = "two";
    m[1] = "ONE";  // 修改键1的值
    
    // 方法2: 使用 insert (如果键已存在则插入失败)
    m.insert({3, "three"});
    m.insert(pair<int, string>(4, "four"));
    m.insert(make_pair(5, "five"));
    
    // 方法3: 批量插入
    vector<pair<int, string>> v = {{6, "six"}, {7, "seven"}};
    m.insert(v.begin(), v.end());
}

// 3. 访问元素
void map_access() {
    map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}};
    
    // 方法1: 使用 [] (如果键不存在会创建)
    string s1 = m[1];  // s1 = "one"
    string s2 = m[4];  // 键4不存在，创建空字符串
    
    // 方法2: 使用 at (如果键不存在会抛出异常)
    try {
        string s3 = m.at(2);  // s3 = "two"
        string s4 = m.at(5);  // 抛出 out_of_range 异常
    } catch (const out_of_range& e) {
        cout << "键不存在" << endl;
    }
    
    // 方法3: 使用 find (安全访问，不创建新元素)
    auto it = m.find(3);
    if (it != m.end()) {
        cout << "找到: " << it->first << " -> " << it->second << endl;
    }
}

// 4. 遍历元素
void map_traversal() {
    map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}};
    
    // 方法1: 范围for循环 (C++11)
    for (const auto& p : m) {
        cout << p.first << " : " << p.second << endl;
    }
    
    // 方法2: 迭代器遍历
    for (auto it = m.begin(); it != m.end(); ++it) {
        cout << it->first << " : " << it->second << endl;
    }
    
    // 方法3: 反向遍历 (从大到小)
    for (auto it = m.rbegin(); it != m.rend(); ++it) {
        cout << it->first << " : " << it->second << endl;
    }
}

// 5. 删除元素
void map_erase() {
    map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}};
    
    // 方法1: 按键删除
    m.erase(2);  // 删除键为2的元素
    
    // 方法2: 用迭代器删除
    auto it = m.find(3);
    if (it != m.end()) {
        m.erase(it);  // 删除迭代器指向的元素
    }
    
    // 方法3: 删除范围内的元素
    auto start = m.find(1);
    auto end = m.find(4);
    if (start != m.end() && end != m.end()) {
        m.erase(start, end);  // 删除从start到end(不包括end)的元素
    }
    
    // 方法4: 清空所有元素
    m.clear();  // 删除所有元素
}

// 6. 查找和统计
void map_find() {
    map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}};
    
    // find: 查找键，返回迭代器
    auto it = m.find(2);
    if (it != m.end()) {
        cout << "找到键2，值为: " << it->second << endl;
    } else {
        cout << "未找到键2" << endl;
    }
    
    // count: 统计键出现的次数 (对于map只能是0或1)
    if (m.count(3)) {
        cout << "键3存在" << endl;
    }
    
    // lower_bound: 返回第一个键 >= 给定键的迭代器
    auto lb = m.lower_bound(2);  // 指向键2
    
    // upper_bound: 返回第一个键 > 给定键的迭代器
    auto ub = m.upper_bound(2);  // 指向键3
    
    // equal_range: 返回一对迭代器，表示键等于给定值的范围
    auto range = m.equal_range(2);
    // range.first 指向键2，range.second 指向键3
}

// 7. 大小和容量
void map_capacity() {
    map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}};
    
    cout << "大小: " << m.size() << endl;        // 3
    cout << "是否为空: " << m.empty() << endl;   // 0 (false)
    cout << "最大容量: " << m.max_size() << endl;
}

// 8. 交换和比较
void map_swap_compare() {
    map<int, string> m1 = {{1, "one"}, {2, "two"}};
    map<int, string> m2 = {{3, "three"}, {4, "four"}};
    
    // 交换两个map的内容
    m1.swap(m2);
    
    // map的比较 (按键的顺序)
    if (m1 < m2) {
        cout << "m1 < m2" << endl;
    }
}

// 9. 自定义类型作为键
struct Student {
    string name;
    int id;
    
    // 需要定义比较运算符
    bool operator<(const Student& other) const {
        if (name != other.name) return name < other.name;
        return id < other.id;
    }
};

void map_custom_key() {
    map<Student, int> scores;
    scores[{"Alice", 1001}] = 95;
    scores[{"Bob", 1002}] = 87;
}

// 10. multimap (允许重复键)
void multimap_example() {
    multimap<int, string> mm;
    
    // 插入 (允许重复键)
    mm.insert({1, "one"});
    mm.insert({1, "uno"});
    mm.insert({2, "two"});
    
    // 遍历指定键的所有值
    auto range = mm.equal_range(1);
    for (auto it = range.first; it != range.second; ++it) {
        cout << it->second << endl;  // 输出: one, uno
    }
    
    // count 可能大于1
    cout << "键1出现次数: " << mm.count(1) << endl;  // 2
}

// 11. unordered_map (哈希表，无序，更快)
void unordered_map_example() {
    unordered_map<int, string> um;
    
    // 基本操作和map类似，但元素无序
    um[1] = "one";
    um[2] = "two";
    um[3] = "three";
    
    // 遍历顺序不保证
    for (const auto& p : um) {
        cout << p.first << " : " << p.second << endl;
    }
}

// 12. 综合示例：统计单词频率
void word_count() {
    vector<string> words = {"apple", "banana", "apple", "orange", "banana", "apple"};
    
    map<string, int> freq;
    
    // 统计频率
    for (const string& word : words) {
        freq[word]++;  // 键不存在时自动创建，值为0，然后++
    }
    
    // 按频率从高到低输出
    vector<pair<string, int>> sorted(freq.begin(), freq.end());
    sort(sorted.begin(), sorted.end(), 
         [](const auto& a, const auto& b) {
             return a.second > b.second;
         });
    
    for (const auto& p : sorted) {
        cout << p.first << ": " << p.second << endl;
    }
}

int main() {
    // 调用各种示例函数来测试
    map_definition();
    map_insert();
    map_access();
    map_traversal();
    map_erase();
    map_find();
    map_capacity();
    map_swap_compare();
    map_custom_key();
    multimap_example();
    unordered_map_example();
    word_count();
    
    return 0;
}

vector基本用法

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
#include <bits/stdc++.h>
using namespace std;

// ==================== 1. vector 基本操作 ====================

void vector_basic() {
    // 1.1 创建和初始化
    vector<int> v1;
    vector<int> v2(10);
    vector<int> v3(10, 5);
    vector<int> v4 = {1, 2, 3, 4, 5};
    vector<int> v5(v4);
    vector<int> v6(v4.begin(), v4.begin() + 3);

    // 1.2 添加元素
    v1.push_back(10);
    v1.emplace_back(20);
    v1.insert(v1.begin(), 5);
    v1.insert(v1.begin() + 2, 15);
    
    // 1.3 访问元素
    int a = v1[0];
    int b = v1.at(1);
    int c = v1.front();
    int d = v1.back();
    
    // 1.4 删除元素
    v1.pop_back();
    v1.erase(v1.begin() + 1);
    v1.erase(v1.begin(), v1.begin() + 2);
    v1.clear();
    
    // 1.5 大小和容量
    cout << "大小: " << v1.size() << endl;
    cout << "容量: " << v1.capacity() << endl;
    cout << "是否为空: " << v1.empty() << endl;
    
    // 1.6 调整大小
    v1.resize(20);
    v1.resize(25, 100);
    v1.reserve(100);
}

// ==================== 2. vector 遍历 ====================

void vector_traversal() {
    vector<int> v = {1, 2, 3, 4, 5};
    
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    
    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        cout << *it << " ";
    }
    
    for (int x : v) {
        cout << x << " ";
    }
    
    for (int& x : v) {
        x *= 2;
    }
}

// ==================== 3. vector 常用算法 ====================

void vector_algorithms() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    sort(v.begin(), v.end());
    sort(v.begin(), v.end(), greater<int>());
    
    auto it = find(v.begin(), v.end(), 5);
    if (it != v.end()) {
        cout << "找到了: " << *it << endl;
    }
    
    if (binary_search(v.begin(), v.end(), 5)) {
        cout << "存在" << endl;
    }
    
    reverse(v.begin(), v.end());
    
    sort(v.begin(), v.end());
    auto last = unique(v.begin(), v.end());
    v.erase(last, v.end());
    
    int maxVal = *max_element(v.begin(), v.end());
    int minVal = *min_element(v.begin(), v.end());
    
    int sum = accumulate(v.begin(), v.end(), 0);
    
    int cnt = count(v.begin(), v.end(), 5);
    
    fill(v.begin(), v.begin() + 5, 100);
    
    random_shuffle(v.begin(), v.end());
}

// ==================== 4. 二维vector ====================

void vector_2d() {
    vector<vector<int>> matrix1;
    
    vector<vector<int>> matrix2(3, vector<int>(4, 0));
    
    vector<vector<int>> matrix3 = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    vector<vector<int>> matrix4;
    matrix4.push_back({1, 2, 3});
    matrix4.push_back(vector<int>(4, 0));
    
    int val = matrix3[1][2];
    matrix3[0][1] = 10;
    
    for (int i = 0; i < matrix3.size(); i++) {
        for (int j = 0; j < matrix3[i].size(); j++) {
            cout << matrix3[i][j] << " ";
        }
        cout << endl;
    }
    
    for (const auto& row : matrix3) {
        for (int x : row) {
            cout << x << " ";
        }
        cout << endl;
    }
}

// ==================== 5. vector实现邻接表 ====================

class Graph {
private:
    int n;
    vector<vector<int>> adj;

    void dfsHelper(int u, vector<bool>& visited) {
        visited[u] = true;
        cout << u << " ";
        for (int v : adj[u]) {
            if (!visited[v]) {
                dfsHelper(v, visited);
            }
        }
    }

public:
    Graph(int vertices) : n(vertices), adj(vertices + 1) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void addDirectedEdge(int u, int v) {
        adj[u].push_back(v);
    }
    
    void removeEdge(int u, int v) {
        auto& neighbors = adj[u];
        neighbors.erase(remove(neighbors.begin(), neighbors.end(), v), neighbors.end());
    }
    
    bool hasEdge(int u, int v) {
        for (int neighbor : adj[u]) {
            if (neighbor == v) return true;
        }
        return false;
    }
    
    vector<int> getNeighbors(int u) {
        return adj[u];
    }
    
    void print() {
        for (int i = 1; i <= n; i++) {
            cout << i << ": ";
            for (int neighbor : adj[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
    
    void dfs(int start) {
        vector<bool> visited(n + 1, false);
        dfsHelper(start, visited);
        cout << endl;
    }
    
    void bfs(int start) {
        vector<bool> visited(n + 1, false);
        queue<int> q;
        
        visited[start] = true;
        q.push(start);
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            cout << u << " ";
            
            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
        cout << endl;
    }
    
    int countComponents() {
        vector<bool> visited(n + 1, false);
        int count = 0;
        
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                count++;
                dfsHelper(i, visited);
            }
        }
        return count;
    }
};

struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

class WeightedGraph {
private:
    int n;
    vector<vector<Edge>> adj;

public:
    WeightedGraph(int vertices) : n(vertices), adj(vertices + 1) {}
    
    void addEdge(int u, int v, int w) {
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    
    void print() {
        for (int i = 1; i <= n; i++) {
            cout << i << ": ";
            for (const Edge& e : adj[i]) {
                cout << "(" << e.to << "," << e.weight << ") ";
            }
            cout << endl;
        }
    }
};

3`