总结

高精度加减乘除

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
#include <iostream>
#include <string>
#include <algorithm> // std::reverse

using namespace std;

// 计算两个大整数的和
string addLargeNumbers(string num1, string num2) {
    // 逆序字符串以便从最低位开始加
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());
    
    int n = max(num1.length(), num2.length()); // 找到更长的数字长度
    string sum(n, '0'); // 初始化结果字符串
    
    int carry = 0; // 初始化进位为0
    for (int i = 0; i < n; ++i) {
        // 如果某一位不存在，则用0代替
        int digit1 = i < num1.length() ? num1[i] - '0' : 0;
        int digit2 = i < num2.length() ? num2[i] - '0' : 0;
        
        // 计算当前位的和加上前一位的进位
        int currentSum = digit1 + digit2 + carry;
        sum[i] = currentSum % 10 + '0'; // 更新结果字符串
        carry = currentSum / 10; // 计算新的进位
    }
    
    // 如果最后还有进位，需要加到结果的最前面
    if (carry > 0) {
        sum.push_back(carry + '0');
    }
    
    // 将结果逆序回正常的顺序
    reverse(sum.begin(), sum.end());
    return sum;
}

// 计算两个大整数的积
string multiply(string num1, string num2) {
    int n1 = num1.size();
    int n2 = num2.size();
    vector<int> result(n1 + n2, 0);
    
    // 从个位开始遍历两个数的每一位
    for (int i = n1 - 1; i >= 0; --i) {
        for (int j = n2 - 1; j >= 0; --j) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            // 加上之前这一位的累加结果
            int sum = mul + result[i + j + 1];
            
            // 更新当前位
            result[i + j + 1] = sum % 10;
            // 处理进位
            result[i + j] += sum / 10;
        }
    }
    
    // 将结果vector转换为字符串
    string resultStr;
    for (int num : result) {
        // 跳过结果前面的0
        if (!(resultStr.empty() && num == 0)) {
            resultStr.push_back(num + '0');
        }
    }
    
    // 如果结果为空，说明两个数的乘积为0
    return resultStr.empty() ? "0" : resultStr;
}


// 判断num1是否小于num2
bool isSmaller(string num1, string num2) {
    int n1 = num1.length(), n2 = num2.length();
    
    if (n1 < n2) return true;
    if (n2 < n1) return false;
    
    for (int i = 0; i < n1; i++) {
        if (num1[i] < num2[i]) return true;
        else if (num1[i] > num2[i]) return false;
    }
    
    return false; // 相等
}

// 实现大数减法，假设num1大于等于num2
string subtract(string num1, string num2) {
    string result;
    // 使num1和num2的长度相同
    while (num1.length() < num2.length()) num1 = "0" + num1;
    while (num2.length() < num1.length()) num2 = "0" + num2;
    
    // 从低位到高位逐位相减
    int carry = 0;
    for (int i = num1.length() - 1; i >= 0; i--) {
        int sub = ((num1[i]-'0') - (num2[i]-'0') - carry);
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        } else {
            carry = 0;
        }
        result.insert(result.begin(), sub + '0');
    }
    
    // 去除结果前面的0
    while (result.length() > 1 && result[0] == '0') result.erase(result.begin());
    
    return result;
}

// 处理可能的负结果
string subtractNumbers(string num1, string num2) {
    bool negative = false;
    
    if (isSmaller(num1, num2)) {
        swap(num1, num2);
        negative = true;
    }
    
    string result = subtract(num1, num2);
    
    if (negative) result.insert(result.begin(), '-');
    
    return result;
}


// 高精度除以低精度（B较小，可以直接用int类型）
pair<string, int> divide(string A, int B) {
    string quotient; // 商
    int remainder = 0; // 余数
    int n = A.length();
    for (int i = 0; i < n; i++) {
        // 将A的每一位与当前余数拼接，形成新的被除数
        remainder = remainder * 10 + (A[i] - '0');
        quotient += (remainder / B) + '0'; // 计算当前位的商，并加到商的结果字符串中
        remainder %= B; // 更新余数
    }
    
    // 去除商字符串前面的0
    int start = 0;
    int l = quotient.length();
    while (start < l && quotient[start] == '0') {
        start++;
    }
    if (start == l) { // 如果商为0
        quotient = "0";
    } else {
        quotient = quotient.substr(start);
    }
    
    return {quotient, remainder};
}




int main() {
    string num1, num2;
    // 输入两个大整数
    cin >> num1 >> num2;
    
    // 计算和并输出
    cout << addLargeNumbers(num1, num2) << endl;
    
    // 计算差
    cout << subtractNumbers(num1, num2) << endl;
    
    // 输出乘积
    cout << multiply(num1, num2) << endl;
    
    
    auto [quotient, remainder] = divide(num1, stoi(num2));
    
    cout << quotient << endl; // 输出商
    cout << remainder << endl; // 输出余数
    return 0;
}

Acwing

数据结构

包括单链表，双链表，栈，队列，单调栈，单调队列，KMP，Trie，并查集，堆，哈希表等内容。

826. 单链表

原题链接：https://www.acwing.com/problem/content/828/

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
/*
    2024/3/11 11:56 Acwing826单链表

    使用两个数组来进行单链表数据结构的模拟,其中一个数组存储实际的值,
    另一个数组存储其下标对应节点的next指针指向的节点
    同时使用一个current指针逐步后移
*/he

#include <iostream>
using namespace std;
const int N = 100010;

int head;
int current;
// 存储值以及对应下标的next
int value[N], next_node[N];

void init()
{
    head = 0;
    current = 1;
}

void add_k(int k, int x)
{
    value[current] = x;                // 将值存入curr指针位置
    next_node[current] = next_node[k]; // 让该元素对应next指向其位置的下一个元素位置
    next_node[k] = current++;          // 让原来的元素的指针指向自己并将curr指针后移
}

void del_k(int k)
{
    next_node[k] = next_node[next_node[k]];
}

int main()
{
    init();
    int m;
    cin >> m;

    while (m--)
    {
        char op;
        int k, x;
        cin >> op;
        if (op == 'H')
        {
            cin >> x;
            add_k(0, x);
        }
        else if (op == 'I')
        {
            cin >> k >> x;
            add_k(k, x);
        }
        else
        {
            cin >> k;
            del_k(k);
        }

        cout << "\nValues:\n";
        for (int j = next_node[0]; j; j = next_node[j])
        {
            cout << value[j] << ' ';
        }
        cout << endl;

        cout << "\nPointers:\n";
        for (int i = 0; i < 10; i++)
        {
            cout << next_node[i] << ' ';
        }
        cout << endl;
    }

    // for (int j = next_node[0]; j; j = next_node[j])
    // {
    //     cout << value[j] << ' ';
    // }
    // cout << endl;

    // for (int i = 0; i < 10; i++)
    // {
    //     cout << next_node[i] << ' ';
    // }
    // cout << endl;
    return 0;
}

827. 双链表

原题链接：

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

const int N = 1e6 + 10; // 定义常量用于数组大小上限

int value[N], prev_node[N], next_node[N], current; // 定义数组和变量用于双向链表

// 在节点k之后插入一个值为x的节点
void insert(int k, int x)
{
    value[current] = x; // 给当前节点赋值为x
    prev_node[current] = k; // 将当前节点的前一个节点设置为节点k
    next_node[current] = next_node[k]; // 将当前节点的后一个节点设置为节点k的后一个节点
    prev_node[next_node[k]] = current; // 更新节点k的后一个节点的前一个节点为当前节点
    next_node[k] = current++; // 更新节点k的后一个节点为当前节点，并递增current
}

// 删除位置为k的节点
void remove(int k)
{
    prev_node[next_node[k]] = prev_node[k]; // 更新节点k的后一个节点的前一个节点
    next_node[prev_node[k]] = next_node[k]; // 更新节点k的前一个节点的后一个节点
}

int main()
{
    int m;
    cin >> m; // 输入操作次数

    next_node[0] = 1; // 将头节点的下一个节点设置为第一个节点
    prev_node[0] = 0; // 将头节点的前一个节点设置为头节点本身
    current = 2; // 将current索引设置为2，因为0和1用于头节点和尾节点

    while (m--)
    {
        string op;
        cin >> op; // 输入操作类型
        int k, x;
        if (op == "L")
        {
            cin >> x; // 输入要插入的值
            insert(0, x); // 在开头插入
        }
        else if (op == "R")
        {
            cin >> x; // 输入要插入的值
            insert(prev_node[1], x); // 在末尾插入
        }
        else if (op == "D")
        {
            cin >> k; // 输入要删除的位置
            remove(k + 1); // 删除位置为k的节点
        }
        else if (op == "IL")
        {
            cin >> k >> x; // 输入要插入的位置和值
            insert(prev_node[k + 1], x); // 在位置k之前插入
        }
        else
        {
            cin >> k >> x; // 输入要插入的位置和值
            insert(k + 1, x); // 在位置k之后插入
        }
    }

    // 输出链表的值
    for (int i = next_node[0]; i != 1; i = next_node[i])
        cout << value[i] << ' ';
    cout << endl;

    return 0;
}

828. 模拟栈

原题链接：https://www.acwing.com/problem/content/830/

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
/*
    2024/3/11 12:11 Acwing828模拟栈
    同样使用数组,没什么多说的
*/

#include <iostream>
using namespace std;
const int N = 1e6 + 10;

int stack[N], top;

void push(int x)
{
    stack[++top] = x;
}

void pop()
{
    top--;
}

bool isempty()
{
    bool ans;
    top ? ans = false : ans = true;
    return ans;
}

int query()
{
    return stack[top];
}

int main()
{
    int m;
    cin >> m;
    while (m--)
    {
        string op;
        int x;

        cin >> op;
        if (op == "push")
        {
            cin >> x;
            push(x);
        }
        else if (op == "pop")
            pop();
        else if (op == "empty")
            cout << (isempty() ? "YES" : "NO") << endl;
        else
            cout << query() << endl;
    }
    return 0;
}

829. 模拟队列

原题链接：https://www.acwing.com/problem/content/831/

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

const int MAX_SIZE = 100010; // 定义队列的最大大小

int m; // 操作次数
int queue[MAX_SIZE]; // 定义队列数组
int front_index, rear_index = -1; // 定义队列的头部和尾部指针

int main()
{
    cin >> m; // 输入操作次数

    while (m--)
    {
        string op; // 操作类型
        int x; // 用于push操作的值

        cin >> op; // 输入操作类型
        if (op == "push") // 如果是push操作
        {
            cin >> x; // 输入要入队的值
            queue[++rear_index] = x; // 将值入队，尾部指针后移
        }
        else if (op == "pop") // 如果是pop操作
        {
            front_index++; // 头部指针后移，表示出队
        }
        else if (op == "empty") // 如果是empty操作
        {
            cout << (front_index <= rear_index ? "NO" : "YES") << endl; // 判断队列是否为空并输出结果
        }
        else // 如果是其他操作，如front
        {
            cout << queue[front_index] << endl; // 输出队头元素
        }
    }

    return 0;
}

154. 滑动窗口

原题链接：https://www.acwing.com/problem/content/156/

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>

using namespace std;

const int N = 1000010;
int a[N];

int main() {
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++)
        cin >> a[i]; // 读入数据

    deque<int> q; // 双端队列存储窗口内元素的索引

    // 求滑动窗口的最小值
    for (int i = 1; i <= n; i++) {
        // 维护单调递增队列，将队列尾部小于当前元素的元素出队
        while (q.size() && a[q.back()] > a[i])
            q.pop_back();
        q.push_back(i); // 将当前元素索引入队

        // 判断队首元素是否已经滑出窗口，如果是则出队
        if (i - k >= 1 && q.front() == i - k)
            q.pop_front();

        // 输出窗口中的最小值
        if (i >= k)
            cout << a[q.front()] << " ";
    }
    q.clear(); // 清空队列

    cout << endl;

    // 求滑动窗口的最大值
    for (int i = 1; i <= n; i++) {
        // 维护单调递减队列，将队列尾部大于当前元素的元素出队
        while (q.size() && a[q.back()] < a[i])
            q.pop_back();
        q.push_back(i); // 将当前元素索引入队

        // 判断队首元素是否已经滑出窗口，如果是则出队
        if (i - k >= 1 && q.front() == i - k)
            q.pop_front();

        // 输出窗口中的最大值
        if (i >= k)
            cout << a[q.front()] << " ";
    }

    return 0;
}

3302. 表达式求值

原题链接：https://www.acwing.com/problem/content/3305/

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

stack<int> num;
stack<char> op;

// 优先级表
unordered_map<char, int> h{ {'+', 1}, {'-', 1}, {'*',2}, {'/', 2} };

void eval()
{
    int a = num.top();
    num.pop();

    int b = num.top();
    num.pop();

    char p = op.top();
    op.pop();

    int r = 0;

    //计算结果
    if (p == '+') r = b + a;
    if (p == '-') r = b - a;
    if (p == '*') r = b * a;
    if (p == '/') r = b / a;

    num.push(r);//结果入栈
}

int main()
{
    string s;//读入表达式
    cin >> s;

    for (int i = 0; i < s.size(); i++)
    {
        // 数字入栈
        if (isdigit(s[i]))
        {
            // 这里是为了两位数以上的数转为整数型
            int x = 0, j = i;
            while (j < s.size() && isdigit(s[j]))
            {
                x = x * 10 + s[j] - '0';
                j++;
            }
            num.push(x);
            i = j - 1;
        }
        else if (s[i] == '(')
        {
            op.push(s[i]);
        }
        else if (s[i] == ')')//右括号
        {
            while(op.top() != '(')//一直计算到左括号
                eval();
            op.pop();//左括号出栈
        }
        else
        {
            while (op.size() && h[op.top()] >= h[s[i]])//待入栈运算符优先级低，则先计算
                eval();
            op.push(s[i]);//操作符入栈
        }
    }
    while (op.size()) eval();//剩余的进行计算
    cout << num.top() << endl;//输出结果
    return 0;
}

836. 合并集合

原题链接：https://www.acwing.com/problem/content/838/

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

const int N = 1e5 + 10; // 定义集合的最大大小

int set[N]; // 记录集合的父节点

// 查找节点x所在集合的根节点，并进行路径压缩
int find(int x)
{
    if (set[x] != x) // 如果当前节点不是根节点
        set[x] = find(set[x]); // 递归查找其父节点的根节点，并将其父节点设为当前节点的根节点，实现路径压缩
    return set[x]; // 返回根节点的编号
}

int main()
{
    int n, m; // 输入的节点数和操作次数
    cin >> n >> m; // 输入节点数和操作次数

    // 初始化每个节点为单独的集合，父节点为自己
    for (int i = 1; i <= n; i++)
    {
        set[i] = i;
    }

    // 处理每个操作
    for (int i = 1; i <= m; i++)
    {
        char op[2]; // 操作类型
        int a, b; // 涉及的节点编号

        cin >> op >> a >> b; // 输入操作类型和涉及的节点编号
        if (*op == 'M') // 如果是合并集合操作
        {
            set[find(a)] = find(b); // 将a所在集合的根节点指向b所在集合的根节点
        }
        else // 如果是查询是否属于同一集合的操作
        {
            if (find(a) == find(b)) // 如果两个节点在同一集合中，即它们的根节点相同
            {
                cout << "Yes\n"; // 输出Yes
            }
            else
            {
                cout << "No\n"; // 输出No
            }
        }
    }
    return 0;
}

837. 连通块中点的数量

原题链接：https://www.acwing.com/problem/content/839/

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

const int N = 100010; // 定义最大节点数

int n, m; // 输入的节点数和操作次数
int p[N], cnt[N]; // 记录节点的父节点和集合大小

// 查找节点x所在集合的根节点，并进行路径压缩
int find(int x)
{
    if (p[x] != x) // 如果当前节点不是根节点
        p[x] = find(p[x]); // 递归查找其父节点的根节点，并将其父节点设为当前节点的根节点，实现路径压缩
    return p[x]; // 返回根节点的编号
}

int main()
{
    cin >> n >> m; // 输入节点数和操作次数

    // 初始化每个节点为单独的集合
    for (int i = 1; i <= n; i++)
    {
        p[i] = i; // 初始时每个节点的父节点为自己
        cnt[i] = 1; // 初始时每个集合只包含一个节点
    }

    while (m--)
    {
        string op; // 操作类型
        int a, b; // 操作涉及的节点编号

        cin >> op; // 输入操作类型
        if (op == "C") // 如果是合并集合操作
        {
            cin >> a >> b; // 输入要合并的两个节点
            a = find(a), b = find(b); // 找到两个节点所在集合的根节点

            // 如果两个节点不在同一集合中，即根节点不同，则将其中一个根节点指向另一个根节点，
            // 并更新集合大小
            if (a != b)
            {
                p[a] = b; // 将a所在集合的根节点指向b所在集合的根节点
                cnt[b] += cnt[a]; // 更新b所在集合的大小，将a所在集合的大小加到b所在集合的大小上
            }
        }
        else if (op == "Q1") // 如果是查询是否属于同一集合的操作
        {
            cin >> a >> b; // 输入要查询的两个节点
            if (find(a) == find(b)) // 如果两个节点在同一集合中，即它们的根节点相同
                puts("Yes"); // 输出Yes
            else
                puts("No"); // 输出No
        }
        else // 如果是查询集合大小的操作
        {
            cin >> a; // 输入要查询的节点
            cout << cnt[find(a)] << endl; // 输出该节点所在集合的大小
        }
    }

    return 0;
}

240. 食物链

原题链接：

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
#include <iostream>

using namespace std;

const int N = 50010;

int n, m;
//  p 用于存储每个元素的父节点
//  d 用于存储每个元素与其父节点的关系深度
int p[N], d[N];

int find(int x)
{
    if (p[x] != x)
    {
        int t = find(p[x]);
        // 更新关系深度
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ ) 
        p[i] = i;

    int res = 0;
    while (m--)
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);

        // 当前的话中 X 或 Y 比 N 大，就是假话；
        if (x > n || y > n)
            res++ ;
        else
        {
            int px = find(x), py = find(y);
            if (t == 1)
            {
                // 两数到根节点距离之差的模不为 0，说明不是同一类，是假话
                if (px == py && (d[x] - d[y]) % 3) 
                    res++ ;
                else if (px != py)
                {
                    // 则 x 与 y 不在同一个集合中
                    // x 所在集合合并到 y 所在集合
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                // 若 x 与 y 在同一个集合中
                // 若 X 吃 Y，则 d[x] 比 d[y] 大 1
                if (px == py && (d[x] - d[y] - 1) % 3) 
                    res++ ;
                else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }

    printf("%d\n", res);

    return 0;
}

838. 堆排序

原题链接：https://www.acwing.com/problem/content/840/

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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int h[N], mySize;
int n, m;

// 维护生成一个最小堆
void down(int u)
{
    int t = u;
    // 判断左子节点
    if (2 * u <= mySize && h[t] > h[2 * u])
        t = 2 * u;
    // 判断右子节点
    if (2 * u + 1 <= mySize && h[t] > h[2 * u + 1])
        t = 2 * u + 1;
    // u!=t,说明当前节点不是最小值或者最大值,需要进行交换
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

int main()
{
    // n为数列长度
    // m为前m小的数
    cin >> n >> m;
    mySize = n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &h[i]);

    // 在一个完全二叉树中，叶子节点的索引范围是 [n/2+1, n]
    // 而非叶子节点的索引范围是 [1, n/2]
    // 只需要对非叶子节点进行下沉操作(叶子结点不需要下沉)
    // 就能保证整个树的堆性质被维护
    for (int i = n / 2; i; i--)
        down(i);

    while (m--)
    {
        // 输出栈顶元素
        cout << h[1] << " ";
        // 将堆顶元素替换为堆的最后一个元素
        // 并对堆顶元素进行下沉操作
        h[1] = h[mySize--];
        down(1);
    }

    return 0;
}

839. 模拟堆

原题链接：https://www.acwing.com/problem/content/841/

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
#include <iostream>

using namespace std;

int const maxn = 1e5 + 10;

int h[maxn], kp[maxn], pk[maxn], idx, len;

void h_swap(int a, int b)
{
    swap(h[a], h[b]);           // 交换数值
    swap(pk[a], pk[b]);         // 交换pk映射
    swap(kp[pk[a]], kp[pk[b]]); // 交换kp映射
}

void down(int u) // 需要down的根节点
{
    int t = u; // t用来存储u的最小儿子
    if (2 * u <= len && h[u * 2] < h[t])
        t = u * 2;
    if (2 * u + 1 <= len && h[u * 2 + 1] < h[t])
        t = u * 2 + 1;

    if (t != u) // 如果t不相等意味着u还不满足小堆的条件于最小儿子交换后继续down
    {
        h_swap(t, u); // 当有映射关系时需要用这个自定义函数
        down(t);      // 递归
    }
}

void up(int u)
{
    int t = u; // up中的t保存的是父结点
    if (u / 2 > 0 && h[u / 2] > h[t])
        t = u / 2; // up操作中只需要判断up儿子与根的大小就可

    if (t != u) // 递归操作
    {
        h_swap(t, u);
        up(t);
    }
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        string aim;
        cin >> aim;
        if (aim == "I")
        {
            int x;
            cin >> x;
            // insert(int x)操作
            h[++len] = x;
            pk[len] = ++idx;
            kp[idx] = len;
            up(len);
        }
        else if (aim == "PM")
        {
            cout << h[1] << endl;
        }
        else if (aim == "DM")
        {
            h_swap(1, len--);
            down(1);
        }
        else if (aim == "D")
        {
            int k;
            cin >> k;

            int u = kp[k]; 

            h_swap(kp[k], len--);
            up(u);
            down(u);
        }
        else if (aim == "C")
        {
            int k, x;
            cin >> k >> x;
            h[kp[k]] = x;
            up(kp[k]);
            down(kp[k]);
        }
        // for(int i=1;i<=len;i++) cout<<h[i]<<" ";
        // cout<<"---------"<<endl;
    }
}

831. KMP字符串

原题链接：https://www.acwing.com/problem/content/833/

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
#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main() {
    // p+1和s+1的目的是令字符串的下标从1开始
    cin >> n >> (p + 1) >> m >> (s + 1);

    // 求next数组
    // 从2开始，因为第一个字符next值必0
    // 其中 i 表示当前位置，j 表示当前位置的最长前缀后缀匹配长度。
    for (int i = 2, j = 0; i <= n; i++ ) {
        // 利用 ne[j]，即前一个位置 j 对应的最长前缀后缀匹配长度，
        // 寻找当前位置 i 对应的最长前缀后缀匹配长度
        // 如果 p[i] 和 p[j+1] 不相等，回退 j 的位置
        // 直到找到一个匹配的前缀或者 j 到达了起始位置。
        while (j && p[i] != p[j + 1])
            j = ne[j];

        // 如果 p[i] 和 p[j+1] 相等，增加 j 的值
        if (p[i] == p[j + 1])
            j++ ;

        // 将当前位置 i 对应的 j 的值存储到 ne[i] 中。
        ne[i] = j;
    }

    // 使用next数组进行匹配
    // i 表示当前在长字符串 s 中的位置
    // j 指向模式串 p 的当前匹配位置。
    for (int i = 1, j = 0; i <= m; i++ ) {
        // 当前长字符串s的位置i和模式串p的位置j+1上的字符不匹配时
        // 利用 ne 数组回退 j 的位置
        while (j && s[i] != p[j + 1])
            j = ne[j];

        // 如果匹配，则j向前移动
        if (s[i] == p[j + 1])
            j++ ;

        // 已经找到了一个完整的匹配。
        if (j == n) {
            //  i-n 表示匹配的起始位置在长字符串中的索引。
            printf("%d ", i - n);
            // 回退j，继续寻找下一个匹配
            j = ne[j];
        }
    }

    return 0;
}

835. Trie字符串统计

原题链接：https://www.acwing.com/problem/content/837/

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
#include <iostream>

using namespace std;

const int N = 1e5 + 10; // 定义最大节点数

int son[N][26], cnt[N], index; // 存储儿子节点、节点计数和索引
char str[N]; // 输入字符串

// 插入字符串到字典树中
void insert(char *str) {
    int p = 0; // 初始节点为根节点
    for (int i = 0; str[i]; i++) // 遍历字符串直到结束符'\0'
    {
        int u = str[i] - 'a'; // 计算字符相对于'a'的偏移量，以便映射到对应位置
        if (!son[p][u]) // 如果当前节点的某个儿子节点不存在
        {
            son[p][u] = ++index; // 则创建新的节点
        }
        p = son[p][u]; // 移动到下一个节点
    }
    cnt[p]++; // 计数节点末尾的字符串
}

// 查询字符串在字典树中出现的次数
int query(char *str) {
    int p = 0; // 初始节点为根节点
    for (int i = 0; str[i]; i++) // 遍历字符串直到结束符'\0'
    {
        int u = str[i] - 'a'; // 计算字符相对于'a'的偏移量，以便映射到对应位置
        if (!son[p][u]) // 如果当前节点的某个儿子节点不存在
        {
            return 0; // 则字符串不存在于字典树中
        }
        p = son[p][u]; // 移动到下一个节点
    }
    return cnt[p]; // 返回节点末尾字符串出现的次数
}

int main() {
    int n;
    cin >> n; // 输入操作次数

    while (n--) {
        char op[2]; // 操作类型
        cin >> op >> str; // 输入操作类型和字符串

        if (*op == 'I') // 如果是插入操作
        {
            insert(str); // 调用插入函数
        } else {
            cout << query(str) << endl; // 输出查询结果
        }
    }

    return 0;
}

143. 最大异或对

原题链接：https://www.acwing.com/problem/content/145/

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
#include <iostream>
#include <algorithm>
using namespace std;
// N表示数组大小最大值，M表示Trie节点数量最大值
const int N = 1e5 + 10, M = 31 * N;

int n;
// a存储输入数据，son构建Trie树，curr表示当前节点数
int a[N], son[M][2], curr;

void insert(int x) {
    // 当前从根结点开始
    int p = 0;

    // 从数的最高位开始逐位向下处理
    for (int i = 30; i >= 0; i--) {
        // 引用s，指向 Trie 树中的下一个节点
        // 获取每一位是0还是1
        int &s = son[p][x >> i & 1];
        // 忽略前导0
        if (!s)
            // 插入节点时，curr递增
            s = ++curr;
        // 根据移动后的位置更新 p 的值，直到插入完成
        p = s;
    }
}

int search(int x) {
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i-- ) {
        int s = x >> i & 1;
        if (son[p][!s]) {
            res += 1 << i;
            p = son[p][!s];
        } else p = son[p][s];
    }
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++ ) {
        scanf("%d", &a[i]);
        insert(a[i]);
    }

    int res = 0;
    for (int i = 0; i < n; i++ )
        res = max(res, search(a[i]));

    printf("%d\n", res);

    return 0;
}

840. 模拟散列表

原题链接：https://www.acwing.com/problem/content/842/

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
#include <cstring>
#include <iostream>

using namespace std;

const int HASH_SIZE = 100003;  // 取大于1e5的第一个质数，冲突概率最小

int hashTable[HASH_SIZE];  // 哈希表的槽数组
int elements[HASH_SIZE];   // 存储哈希表中的元素
int nextIndex[HASH_SIZE];  // 存储下一个节点的索引
int currentIndex;          // 当前节点的索引
int operationCount;         // 操作次数

// 插入元素到哈希表
void insertElement(int x) {
    int hashValue = (x % HASH_SIZE + HASH_SIZE) % HASH_SIZE;  // 计算哈希值
    elements[currentIndex] = x;
    nextIndex[currentIndex] = hashTable[hashValue];
    hashTable[hashValue] = currentIndex++;
}

// 在哈希表中查找元素
bool findElement(int x) {
    int hashValue = (x % HASH_SIZE + HASH_SIZE) % HASH_SIZE;  // 计算哈希值
    for (int i = hashTable[hashValue]; i != -1; i = nextIndex[i]) {
        if (elements[i] == x) {
            return true;  // 找到元素 x
        }
    }
    return false;  // 未找到元素 x
}

int main() {
    cin >> operationCount;  // 读入操作次数
    memset(hashTable, -1, sizeof hashTable);  // 初始化哈希表

    while (operationCount--) {
        string operation;
        int element;
        cin >> operation >> element;
        if (operation == "I") {
            insertElement(element);  // 执行插入操作
        } else {
            if (findElement(element)) {
                puts("Yes");  // 输出 Yes
            } else {
                puts("No");  // 输出 No
            }
        }
    }
    return 0;
}

841. 字符串哈希

原题链接：https://www.acwing.com/problem/content/843/

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

const int MAX_LEN = 1e5 + 5;  // 字符串最大长度
const int BASE = 131;         // 哈希计算的基数，可以选取为 131 或 13331

typedef unsigned long long ULL;  // 定义无符号长长整型 ULL

ULL prefixHash[MAX_LEN];  // 前缀哈希数组
ULL basePower[MAX_LEN];   // 不同位置的进制数

// 计算子串的哈希值
ULL calculateHash(int left, int right) {
    return prefixHash[right] - prefixHash[left - 1] * basePower[right - left + 1];
}

int main() {
    int strLen, queryCount;
    cin >> strLen >> queryCount;  // 读入字符串长度和查询次数
    string str;
    cin >> str;  // 读入字符串

    basePower[0] = 1;
    prefixHash[0] = 0;
    for (int i = 0; i < strLen; i++) {
        basePower[i + 1] = basePower[i] * BASE;            // 计算不同位置的进制数
        prefixHash[i + 1] = prefixHash[i] * BASE + str[i]; // 计算前缀哈希值
    }

    while (queryCount--) {
        int left1, right1, left2, right2;
        cin >> left1 >> right1 >> left2 >> right2;  // 读入查询范围
        if (calculateHash(left1, right1) == calculateHash(left2, right2)) {
            cout << "Yes" << endl;  // 输出 Yes
        } else {
            cout << "No" << endl;   // 输出 No
        }
    }

    return 0;
}

搜索与图论

包括DFS，BFS，树与图的深度优先遍历，树与图的广度优先遍历，拓扑排序，Dijkstra，bellman-ford，spfa，Floyd，Prim，Kruskal，染色法判定二分图，匈牙利算法等内容。

842. 排列数字

原题链接：https://www.acwing.com/problem/content/844/

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;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{
    if(u > n)//数字填完了，输出
    {
        for(int i = 1; i <= n; i++)//输出方案
            cout << path[i] << " ";
        cout << endl;
    }
    
    for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n
    {
        if(!state[i])//如果数字 i 没有被用过
        {
            path[u] = i;//放入空位
            state[i] = 1;//数字被用，修改状态
            dfs(u + 1);//填下一个位
            state[i] = 0;//回溯，取出 i
        }
    }
}

int main()
{
    
    cin >> n;
    dfs(1);
}

843. n-皇后问题

原题链接：https://www.acwing.com/problem/content/845/

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
#include <iostream>
using namespace std;
const int N = 20;

int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N]; // 因为是一个个搜索，所以加了row

// s表示已经放上去的皇后个数
void dfs(int x, int y, int s)
{
    // 处理超出边界的情况
    if (y == n) y = 0, x ++ ;
    
    if (x == n) { // x==n说明已经枚举完n^2个位置了
        if (s == n) { // s==n说明成功放上去了n个皇后
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return;
    }
    
    // 分支1：放皇后
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }
    
    // 分支2：不放皇后
    dfs(x, y + 1, s);
}


int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';
    
    dfs(0, 0, 0);
    
    return 0;
}

845. 八数码

原题链接：https://www.acwing.com/problem/content/description/847/

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
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cstring>

using namespace std;

int bfs(string start) {
    // * 存储状态的队列q
    queue<string> q;
    // * 存储各状态对应初始状态的距离的哈希表
    unordered_map<string, int> dict;
    // * 目标状态
    string goal = "12345678x";
    // * 移动方式
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    // * 将初始状态加入队列
    q.push(start);
    // * 将初始状态加入哈希表
    dict[start] = 0;

    // * 遍历全部状态
    while (q.size())
    {
        // * 从队列中取出一个状态
        auto t = q.front();
        q.pop();

        int distance = dict[t];

        if (t == goal)
        {
            return distance;
        }

        // 查询x的位置并转为矩阵坐标
        int pos = t.find('x');
        int x = pos / 3;
        int y = pos % 3;

        for (int i = 0; i < 4; i++)
        {
            // 转移后的坐标
            int xi = x + dx[i];
            int yi = y + dy[i];

            // * 修改后的代码
            if (xi >= 0 && xi < 3 && yi >= 0 && yi < 3) {
                int posi = xi * 3 + yi;
                swap(t[pos], t[posi]);

                // 如果是第一次访问该状态
                if (dict[t] == 0) {
                    dict[t] = distance + 1;
                    // 当前状态存入队列
                    q.push(t);
                }
                // 还原状态，继续bfs
                swap(t[pos], t[posi]);
            }

            // ? 代码的问题出在这里
            // if (xi < 0 || xi > 3 || yi < 0 || yi > 3)
            //     continue;
            // int posi = xi * 3 + yi;
            // swap(t[pos], t[posi]);
            // if (t == goal) {
            //     cout << dict[t] + 1 << endl;
            //     return 0;
            // } else {
            //     dict[t]++;
            //     q.push(t);
            //     swap(t[pos], t[posi]);
            // }
            
        }
    }
    return -1;

}

int main()
{
    string c, start;
    //输入起始状态
    for(int i = 0; i < 9; i++)
    {
        cin >> c;
        start += c;
    }

    cout << bfs(start) << endl;
    return 0;

}

846. 树的重心

原题链接：https://www.acwing.com/problem/content/848/

这题就是遍历一棵树的以各个点为根的子树的大小，找到其中最小

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

const int MAX_NODES = 1e5 + 10; // 根据题目的数据范围，预设最大节点数
int num_nodes; // 树的节点数
vector<int> adjacency_list[MAX_NODES]; // 存储树的邻接表
int subtree_sizes[MAX_NODES]; // 存储以每个节点为根的子树的大小
bool visited[MAX_NODES]; // 标记数组，用于DFS
int centroid = MAX_NODES, max_subtree_size = MAX_NODES; // centroid用于存储重心的节点编号，max_subtree_size存储删除重心后的最大连通块大小

// DFS函数，计算以节点u为根的子树大小
void dfs(int node) {
    visited[node] = true; // 标记节点已访问
    subtree_sizes[node] = 1; // 初始化当前节点的子树大小为1
    int max_subtree = 0; // 存储除当前节点外，最大的子树大小
    for (int neighbor : adjacency_list[node]) { // 遍历节点的邻居节点
        if (!visited[neighbor]) { // 如果邻居节点未被访问过
            dfs(neighbor); // 递归调用DFS函数
            subtree_sizes[node] += subtree_sizes[neighbor]; // 更新节点的子树大小
            max_subtree = max(max_subtree, subtree_sizes[neighbor]); // 更新最大的子树大小
        }
    }
    max_subtree = max(max_subtree, num_nodes - subtree_sizes[node]); // 检查除当前节点的子树外的其他部分大小
    if (max_subtree < max_subtree_size) { // 如果当前节点的最大子树大小小于最大连通块大小
        max_subtree_size = max_subtree; // 更新最大连通块大小
        centroid = node; // 更新重心的节点编号
    }
}

int main() {
    cin >> num_nodes; // 输入树的节点数
    for (int i = 1; i < num_nodes; i++) { // 构建树的邻接表
        int node_a, node_b;
        cin >> node_a >> node_b;
        adjacency_list[node_a].push_back(node_b); // 节点a与节点b相连
        adjacency_list[node_b].push_back(node_a); // 节点b与节点a相连
    }

    dfs(1); // 从节点1开始DFS
    cout << max_subtree_size << endl; // 输出结果
    return 0;
}

847. 图中点的层次

原题链接：https://www.acwing.com/problem/content/849/

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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring> // 包含memset函数，用于初始化数组
using std::vector;
using std::queue;
using std::cin;
using std::cout;
using std::endl;

const int MAXN = 100005;

vector<int> graph[MAXN]; // 存储有向图的邻接表
bool visited[MAXN]; // 标记数组，用于标记节点是否已经访问过
int distance[MAXN]; // 存储节点到起始节点的距离

int bfs(int start, int end) {
    memset(visited, false, sizeof(visited)); // 初始化标记数组
    memset(distance, -1, sizeof(distance)); // 初始化距离数组，-1表示未访问到该节点
    queue<int> q; // 定义一个队列，用于BFS
    
    visited[start] = true; // 标记起始节点已经访问过
    distance[start] = 0; // 起始节点到自身的距离为0
    q.push(start); // 将起始节点加入队列
    
    while (!q.empty()) {
        int node = q.front(); // 取出队列的第一个节点
        q.pop(); // 弹出队列的第一个节点
        
        // 遍历当前节点的所有邻居节点
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) { // 如果邻居节点未被访问过
                visited[neighbor] = true; // 标记邻居节点已经访问过
                distance[neighbor] = distance[node] + 1; // 更新邻居节点的距离
                q.push(neighbor); // 将邻居节点加入队列
            }
        }
    }
    
    return distance[end]; // 返回终点到起点的距离
}

int main() {
    int n, m;
    cin >> n >> m;
    
    // 构建有向图的邻接表
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
    }
    
    int shortest_distance = bfs(1, n); // 求解最短距离
    cout << shortest_distance << endl; // 输出结果
    
    return 0;
}

848. 有向图的拓扑序列

原题链接：https://www.acwing.com/problem/content/description/850/

拓扑排序

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 <iostream>
#include <vector>
#include <stack>
#include <cstring> // 包含memset函数，用于初始化数组
using namespace std;

const int MAXN = 100005;

vector<int> graph[MAXN]; // 存储有向图的邻接表
bool visited[MAXN]; // 标记数组，用于标记节点是否已经访问过
bool on_stack[MAXN]; // 标记数组，用于标记节点是否在递归调用栈上
stack<int> topo_order; // 存储拓扑排序的栈

bool dfs(int node) {
    visited[node] = true; // 标记节点已经访问过
    on_stack[node] = true; // 标记节点在递归调用栈上

    // 遍历当前节点的所有邻居节点
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) { // 如果邻居节点未被访问过
            if (dfs(neighbor)) // 递归调用DFS
                return true;
        } else if (on_stack[neighbor]) { // 如果邻居节点在递归调用栈上
            // 存在环，无法构成拓扑序列
            return true;
        }
    }

    on_stack[node] = false; // 当前节点递归调用结束，从递归调用栈上移除
    topo_order.push(node); // 将节点加入拓扑排序的栈
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;

    // 构建有向图的邻接表
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
    }

    // 初始化标记数组
    memset(visited, false, sizeof(visited));
    memset(on_stack, false, sizeof(on_stack));

    // 对每个未访问过的节点进行深度优先搜索
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            if (dfs(i)) { // 如果存在环，输出-1
                cout << -1 << endl;
                return 0;
            }
        }
    }

    // 输出拓扑序列
    while (!topo_order.empty()) {
        cout << topo_order.top() << " ";
        topo_order.pop();
    }
    cout << endl;

    return 0;
}

849. Dijkstra求最短路 I || 850. Dijkstra求最短路 II

原题链接：https://www.acwing.com/problem/content/851/ https://www.acwing.com/problem/content/852/

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

typedef pair<int, int> pii; // 用于保存边的终点和权值

const int INF = numeric_limits<int>::max(); // 表示无穷大

int dijkstra(const vector<vector<pii>>& graph, int n, int start, int end) {
    vector<int> dist(n + 1, INF); // 初始化距离数组，默认为无穷大
    dist[start] = 0; // 起点到起点的距离为0

    // 创建优先队列保存待处理的节点，队列中的元素为（距离，节点）对
    // 距离小的优先级高
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int d = pq.top().first;
        int node = pq.top().second;
        pq.pop();

        // 如果当前节点的距离比之前记录的距离要长，跳过
        if (d > dist[node]) continue;

        // 遍历当前节点的所有邻居节点
        for (auto& edge : graph[node]) {
            int neighbor = edge.first;
            int weight = edge.second;
            // 如果从起点经当前节点到邻居节点的距离更短，则更新距离数组
            if (dist[node] + weight < dist[neighbor]) {
                dist[neighbor] = dist[node] + weight;
                // 将邻居节点加入优先队列中
                pq.push({dist[neighbor], neighbor});
            }
        }
    }

    // 如果终点的距离仍然是无穷大，则表示无法到达终点
    if (dist[end] == INF) {
        return -1;
    } else {
        return dist[end];
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> graph(n + 1);

    // 构建图的邻接表表示
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        graph[x].push_back({y, z});
    }

    // 使用Dijkstra算法求解最短路径
    int shortest_distance = dijkstra(graph, n, 1, n);
    cout << shortest_distance << endl;

    return 0;
}

853. 有边数限制的最短路

原题链接：https://www.acwing.com/problem/content/855/

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

// 定义边的结构体
struct Edge {
    int from, to, weight;
    Edge(int _from, int _to, int _weight) : from(_from), to(_to), weight(_weight) {}
};

const int INF = INT_MAX; // 定义无穷大值

int main() {
    int n, m, k;
    cin >> n >> m >> k; // 输入节点数量、边数量和最大边数限制

    vector<Edge> edges; // 存储所有边的数组
    for (int i = 0; i < m; ++i) { // 读入边的信息
        int x, y, z;
        cin >> x >> y >> z;
        edges.push_back(Edge(x, y, z)); // 将边的信息存入数组中
    }

    vector<int> dist(n + 1, INF); // 距离数组，存储从起点到各节点的最短距离，初始值为无穷大
    dist[1] = 0; // 起点到起点的距离为0

    // Bellman-Ford算法
    // 迭代k次以确保找到的最短路径是经过k条边的
    for (int i = 0; i < k; ++i) {
        // 使用临时数组存储当前轮次的最短距离，以免在更新过程中影响下一轮的计算
        vector<int> temp = dist;
        // 遍历所有边
        for (const auto& edge : edges) {
            // 如果起点到当前边的起点的距离不为无穷大，且通过当前边可以更新终点的距离
            if (dist[edge.from] != INF && dist[edge.from] + edge.weight < temp[edge.to]) {
                temp[edge.to] = dist[edge.from] + edge.weight; // 更新终点的距离
            }
        }
        dist = temp; // 更新距离数组
    }

    // 输出结果
    if (dist[n] == INF) {
        cout << "impossible" << endl; // 如果终点的距离仍然是无穷大，则表示无法到达终点
    } else {
        cout << dist[n] << endl; // 输出从起点到终点的最短距离
    }

    return 0;
}