post on 23 Feb 2025 about 7476words require 25min
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
22222
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int n = s.size();
for(int i = 0; i < n; i++){
if(s[i] == '2'){
cout << 2 ;
}
}
return 0;
}
cat
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
// 包含C++标准库的头文件
#include <bits/stdc++.h>
// 使用标准命名空间
using namespace std;
int main(){
// 声明变量n用于存储输入的字符串个数
int n;
cin >> n;
// 创建一个大小为n的字符串向量s用于存储输入的字符串
vector<string> s(n);
// 循环读入n个字符串
for(int i = 0; i < n; i++){
cin >> s[i];
}
// 创建一个pair向量a,用于存储字符串及其长度
vector<pair<string,int>> a;
// 遍历字符串向量s,将每个字符串及其长度作为pair存入向量a
for(int i = 0; i < n; i++){
a.pushback(makepair(s[i],s[i].size()));
}
// 使用lambda表达式对向量a按照字符串长度进行升序排序
// sort(a.begin(), a.end(), [](const pair<string,int>& x, const pair<string,int>& y){
// return x.second < y.second;
// });
// const 和 & 是为了提高效率，可以暂时不用太关注
sort(a.begin(), a.end(), [](pair<string, int> x, pair<string, int> y)
{ return x.**second** < y.**second**; });
// 按顺序输出排序后的字符串
for(int i = 0; i < n; i++){
cout << a[i].**first**;
}
return 0;
}
Debug
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
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
vector<char> chars(s.begin(), s.end());
bool changed = true;
while (changed)
{
changed = false;
vector<char> next = chars;
for (int i = 0; i < chars.size() - 1; i++)
{
if (next[i] == 'W' && next[i + 1] == 'A')
{
next[i] = 'A';
next[i + 1] = 'C';
changed = true;
i++; // 跳过下一个字符，因为已经处理过了
}
}
chars = next;
}
for (char c : chars)
{
cout << c;
}
cout << endl;
return 0;
}
Colorful Bracket Sequence
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
#include <bits/stdc++.h>
using namespace std;
// 将函数定义移到 main 函数外部
int bracketmatch(string &s1, string &s2)
{
if (s1 == "(" && s2 == ")")
{
return 1;
}
else if (s1 == "[" && s2 == "]")
{
return 1;
}
else if (s1 == "{" && s2 == "}")
{
return 1;
}
return 0;
}
int main()
{
string bracket;
cin >> bracket;
stack<string> bracketstack;
for (int i = 0; i < bracket.size(); i++)
{
string current(1, bracket[i]); // 将 char 转换为 string
if (current == "(" || current == "[" || current == "{")
{
bracketstack.push(current);
}
else if (current == ")" || current == "]" || current == "}")
{
if (bracketstack.empty())
{
cout << "No" << endl;
return 0;
}
if (bracketmatch(bracketstack.top(), current))
{
bracketstack.pop();
}
else
{
cout << "No" << endl;
return 0;
}
}
}
// 最后检查栈是否为空
if (!bracketstack.empty())
{
cout << "No" << endl;
}
else
{
cout << "Yes" << endl;
}
return 0;
}
Palindromic Shortest Path
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
#include <bits/stdc++.h>
// 定义一个简化的循环宏
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
// 定义一个表示无穷大的常量
int inf = 1000000010;
int main()
{
// 读入矩阵大小n
int n;
cin >> n;
// 创建n*n的字符矩阵c用于存储输入
vector<vector<char>> c(n, vector<char>(n));
rep(i, n) rep(j, n) cin >> c[i][j];
// 创建n*n的距离矩阵a，初始化为无穷大
vector<vector<int>> a(n, vector<int>(n, inf));
// 创建队列用于BFS搜索
queue<pair<int, int>> que;
// 对角线元素距离初始化为0
rep(i, n)
{
que.push({i, i});
a[i][i] = 0;
}
// 直接相连的元素距离初始化为1
rep(i, n) rep(j, n)
{
if (i == j or c[i][j] == '-')
continue;
que.push({i, j});
a[i][j] = 1;
}
// BFS搜索计算所有点对之间的最短距离
while (!que.empty()) // 当队列不为空时继续搜索
{
auto q = que.front(); // 获取队首元素
que.pop(); // 弹出队首元素
int i = q.**first**, j = q.**second**; // 获取当前处理的点对(i,j)的坐标
// 遍历所有可能的新点对(k,l)
rep(k, n) rep(l, n)
{
// 判断是否可以通过当前点对(i,j)构建到新点对(k,l)的路径:
// 1. c[k][i]不是'-' - 表示k到i有边
// 2. c[j][l]不是'-' - 表示j到l有边
// 3. c[k][i] == c[j][l] - 两条边的字符相同
// 4. a[k][l] == inf - 点对(k,l)还未被访问过
if (c[k][i] != '-' && c[j][l] != '-' && c[k][i] == c[j][l] && a[k][l] == inf)
{
// 新路径的距离 = 当前点对的距离 + 2
// +2是因为需要经过两条新的边(k->i和j->l)
a[k][l] = a[i][j] + 2;
que.push({k, l}); // 将新的点对加入队列以继续搜索
}
}
}
// 输出结果矩阵
rep(i, n)
{
rep(j, n)
{
// 如果距离仍为无穷大，输出-1，否则输出实际距离
cout << (a[i][j] == inf ? -1 : a[i][j]) << " \n"[j == n - 1];
}
}
}
Alkane
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
#include <bits/stdc++.h> // 包含C++标准库
using namespace std; // 使用标准命名空间
#define mp makepair // 定义makepair的简写
#define pb pushback // 定义pushback的简写
#define fi first // 定义first的简写
#define se second // 定义second的简写
#define li long long // 定义long long的简写
#define pii pair<int, int> // 定义pair<int,int>的简写
#define vi vector<int> // 定义vector<int>的简写
#define forn(i, n) for (int i = 0; i < (int)n; i++) // 定义从0到n-1的循环宏
#define fore(i, b, e) for (int i = (int)b; i <= (int)e; i++) // 定义从b到e的循环宏
#define all(x) (x).begin(), (x).end() // 定义容器的begin和end迭代器
int ans = 0; // 存储最终答案
vector<vi> edges; // 存储图的邻接表
vi f; // 存储每个节点的状态值
void dfs(int v, int p) // 深度优先搜索函数，v是当前节点，p是父节点
{
for (int u : edges[v]) // 遍历当前节点的所有邻接点
{
if (u != p) // 如果邻接点不是父节点
{
dfs(u, v); // 递归处理子节点
}
}
f[v] = 1; // 初始化当前节点的状态值为1
if (edges[v].size() >= 4) // 如果当前节点的度数大于等于4
{
vi children; // 存储子节点的状态值
for (int u : edges[v]) // 遍历所有邻接点
{
if (u != p) // 如果不是父节点
{
children.pb(f[u]); // 添加子节点的状态值
}
else
{
children.pb(1); // 父节点贡献值为1
}
}
sort(all(children), greater<int>()); // 对子节点状态值降序排序
forn(j, 3) // 选择前3大的值
{
f[v] += children[j]; // 累加到当前节点的状态值
}
int here = 1; // 计算包含4个子节点的路径长度
forn(j, 4)
{
here += children[j];
}
ans = max(ans, here); // 更新最大答案
}
else if (p == -1) // 如果是根节点
{
for (int u : edges[v]) // 遍历所有子节点
{
f[v] = max(f[v], f[u] + 1); // 更新根节点状态值
}
}
// printf("f[%d] = %d edges count = %d\n", v, f[v], (int)edges[v].size());
ans = max(ans, f[v] + (p == -1 ? 0 : 1)); // 更新最大答案
}
int main()
{
int n; // 节点数量
cin >> n;
edges.resize(n + 1); // 初始化邻接表大小
forn(i, n - 1) // 读入n-1条边
{
int u, v;
cin >> u >> v;
edges[u].pb(v); // 添加无向边
edges[v].pb(u);
}
f.resize(n + 1); // 初始化状态数组大小
dfs(1, -1); // 从节点1开始深度优先搜索
if (ans < 5) // 如果最大路径长度小于5
{
ans = -1; // 输出-1
}
cout << ans; // 输出答案
}
Dense Buildings
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
// 包含C++标准库和atcoder的并查集库
#include <bits/stdc++.h>
#include <atcoder/dsu>
// 使用标准命名空间和atcoder命名空间
using namespace std;
using namespace atcoder;
// 定义常量
#define H 500 // 最大高度
#define W 500 // 最大宽度
#define Q (int)2e+5 // 最大查询次数
#define F (int)1e+6 // 最大权值
int main(void)
{
int h, w, q; // h,w为网格大小,q为查询次数
int f[H][W]; // f[i][j]存储网格中每个位置的权值
int a[Q], b[Q], y[Q]; // 每个查询的起点坐标(a,b)和权值y
int c[Q], d[Q], z[Q]; // 每个查询的终点坐标(c,d)和权值z
int l[Q], r[Q]; // 二分查找的左右边界
vector<pair<int, int>> e[F + 1]; // e[i]存储权值为i的边
vector<int> check[F + 1]; // check[i]存储需要在权值i处检查的查询
// 读入网格大小
cin >> h >> w;
// 读入网格中的权值
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
cin >> f[i][j];
// 读入查询次数和查询信息
cin >> q;
for (int i = 0; i < q; i++)
{
cin >> a[i] >> b[i] >> y[i] >> c[i] >> d[i] >> z[i];
a[i]--, b[i]--, c[i]--, d[i]--; // 坐标从0开始
}
// 构建边集合
// 添加竖直方向的边
for (int i = 0; i < h - 1; i++)
for (int j = 0; j < w; j++)
e[min(f[i][j], f[i + 1][j])].pushback({i * w + j, (i + 1) * w + j});
// 添加水平方向的边
for (int i = 0; i < h; i++)
for (int j = 0; j < w - 1; j++)
e[min(f[i][j], f[i][j + 1])].pushback({i * w + j, i * w + (j + 1)});
// 初始化二分查找的边界
for (int i = 0; i < q; i++)
l[i] = 1, r[i] = F + 1;
// 二分查找过程
while (true)
{
bool flag = true;
// 清空check数组
for (int i = 0; i <= F; i++)
check[i].clear();
// 对每个查询,如果二分区间未收敛,则加入check数组
for (int i = 0; i < q; i++)
{
if (r[i] - l[i] > 1)
{
check[(l[i] + r[i]) / 2].pushback(i);
flag = false;
}
}
if (flag) break; // 如果所有查询都已收敛,退出循环
// 使用并查集检查连通性
dsu uf(h * w);
// 从大到小遍历权值
for (int i = F; i >= 0; i--)
{
// 合并权值为i的所有边
int sz = e[i].size();
for (int j = 0; j < sz; j++)
uf.merge(e[i][j].**first**, e[i][j].**second**);
// 检查需要在权值i处判断的查询
sz = check[i].size();
for (int j = 0; j < sz; j++)
{
int idxs = a[check[i][j]] * w + b[check[i][j]]; // 起点在一维数组中的索引
int idxt = c[check[i][j]] * w + d[check[i][j]]; // 终点在一维数组中的索引
// 根据连通性更新二分边界
if (uf.same(idxs, idxt))
l[check[i][j]] = i;
else
r[check[i][j]] = i;
}
}
}
// 输出每个查询的结果
for (int i = 0; i < q; i++)
cout << (y[i] + z[i] - 2 * min(l[i], min(y[i], z[i]))) << endl;
return 0;
}
Related posts