1.P1886 滑动窗口 /【模板】单调队列 - 洛谷
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=2e6+5;
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n, k;cin >> n >> k;vector<ll> a(n);//不开long long 见祖宗for (int i = 0; i < n; ++i) {cin >> a[i];}// 存储每个窗口的最小值vector<ll> minresult;// 存储每个窗口的最大值vector<ll> maxresult;deque<int> mindeque; // 维护单调递增队列，队首为当前窗口最小值的索引deque<int> maxdeque; // 维护单调递减队列，队首为当前窗口最大值的索引for (int i = 0; i < n; ++i) {// 维护最小值队列// 移除所有大于当前元素的元素，保持队列递增while (!mindeque.empty() && a[i] <= a[mindeque.back()]) {mindeque.pop_back();}mindeque.push_back(i);// 移除超出窗口范围的元素while (mindeque.front() <= i - k) {mindeque.pop_front();}// 维护最大值队列// 移除所有小于当前元素的元素，保持队列递减while (!maxdeque.empty() && a[i] >= a[maxdeque.back()]) {maxdeque.pop_back();}maxdeque.push_back(i);// 移除超出窗口范围的元素while (maxdeque.front() <= i - k) {maxdeque.pop_front();}// 当窗口大小达到k时，开始记录结果if (i >= k - 1) {minresult.push_back(a[mindeque.front()]);maxresult.push_back(a[maxdeque.front()]);}}// 输出最小值结果for (int i = 0; i < minresult.size(); ++i) {if (i > 0) cout << " ";cout << minresult[i];}cout << "\n";// 输出最大值结果for (int i = 0; i < maxresult.size(); ++i) {if (i > 0) cout << " ";cout << maxresult[i];}cout << "\n";return 0;
}
2.P1196 [NOI2002] 银河英雄传说 - 洛谷
#include <iostream>
using namespace std;
using ll =long long ;
const int N = 30010;
// pre[i]：存储第i号战舰的父节点索引
// rank0[i]：存储第i号战舰到其父节点的距离（即中间相隔的战舰数量）
// size0[i]：当i为根节点时，存储该队列的总战舰数量
int pre[N], rank0[N], size0[N];
/*** 初始化并查集* 每个战舰初始时自成一列（父节点为自身）* 距离为0（自身到自身无距离）* 队列大小为1（仅包含自己）*/
void init() {for (int i = 1; i < N; ++i) {pre[i] = i; // 父节点指向自身rank0[i] = 0; // 到自身的距离为0size0[i] = 1; // 初始队列大小为1}
}
/*** 查找根节点并进行路径压缩* 路径压缩过程中会更新距离，确保rank[x]始终表示x到根节点的距离*/
int find(int x) {// 如果x不是根节点，递归查找其父节点的根节点if (pre[x] != x) {// 暂存原父节点，用于后续距离计算int root = find(pre[x]);// 路径压缩：将x的父节点直接指向根节点// 同时更新x到根节点的总距离（x到原父节点的距离 + 原父节点到根节点的距离）rank0[x] += rank0[pre[x]];pre[x] = root;}return pre[x];
}/*** 合并两个战舰队列* 将x所在的整个队列移动到y所在队列的尾部*/
void join(int x, int y) {// 找到x和y所在队列的根节点int rootX = find(x);int rootY = find(y);// 将rootX所在队列合并到rootY所在队列的尾部pre[rootX] = rootY;// rootX到新父节点rootY的距离为rootY队列的大小（排在所有原有战舰之后）rank0[rootX] = size0[rootY];// 更新合并后队列的总大小size0[rootY] += size0[rootX];
}int main() {// 初始化并查集init();int T; // 指令总数cin >> T;while (T--) {char cmd; // 指令类型（M或C）int i, j; // 指令涉及的战舰编号cin >> cmd >> i >> j;if (cmd == 'M') {// 处理合并指令：将i所在队列合并到j所在队列尾部join(i, j);} else {// 处理查询指令：检查i和j是否在同一队列int rootI = find(i);int rootJ = find(j);if (rootI != rootJ) {// 根节点不同，不在同一队列cout << -1 << endl;} else {// 根节点相同，在同一队列// 两艘战舰之间的数量 = 距离差的绝对值 - 1cout << abs(rank0[i] - rank0[j]) - 1 << endl;}}}return 0;
}
3.P1536 村村通 - 洛谷
#include <iostream>
using namespace std;const int MAXN = 1001; // 最大城镇数
int pre[MAXN]; // 存储每个节点的父节点// 查找根节点，带路径压缩
int find(int x) {// 如果x不是根节点，递归查找其父节点的根节点if (pre[x] != x) {// 路径压缩：将x的父节点直接指向根节点pre[x] = find(pre[x]);}return pre[x];
}// 合并两个集合
void join(int x, int y) {int rootX = find(x); // 找到x的根节点int rootY = find(y); // 找到y的根节点if (rootX != rootY) {// 将一个集合的根节点指向另一个集合的根节点，实现合并pre[rootY] = rootX;}
}int main() {int n, m;while (cin >> n && n != 0) { // 读取城镇数，0表示结束cin >> m; // 读取道路数// 初始化并查集：每个节点的父节点是自身for (int i = 1; i <= n; ++i) {pre[i] = i;}// 处理每条道路，合并连通的城镇for (int i = 0; i < m; ++i) {int a, b;cin >> a >> b;join(a, b);}// 统计连通分量的数量int count = 0;for (int i = 1; i <= n; ++i) {// 如果节点是根节点（父节点是自身），说明是一个新的连通分量if (pre[i] == i) {count++;}}// 最少需要建设的道路数 = 连通分量数 - 1cout << count - 1 << endl;}return 0;
}
4.P1901 发射站 - 洛谷
#include <bits/stdc++.h>
using namespace std;
using ll=long long ;
int main() {int n;// 读取发射站的数量ncin >> n;// 定义三个动态数组：// h[i] 存储第i个发射站的高度// v[i] 存储第i个发射站的能量值// sum[i] 存储第i个发射站接收到的总能量// 数组下标从1开始，方便与发射站编号对应vector<int> h(n + 1), v(n + 1), sum(n + 1);// 定义一个栈，用于存储发射站的索引（编号）// 栈中元素对应的发射站高度保持单调递减的特性stack<int> st; // 依次处理每个发射站for (int i = 1; i <= n; i++) {// 读取当前发射站的高度和能量值cin >> h[i] >> v[i];// 栈不为空，且栈顶发射站的高度 < 当前发射站的高度时：// 说明栈顶发射站右边最近的更高发射站就是当前发射站// 因此栈顶发射站的能量会被当前发射站接收while (!st.empty() && h[st.top()] < h[i]) {// 当前发射站接收栈顶发射站的能量sum[i] += v[st.top()];// 弹出栈顶元素：因为它已经找到右边更高的发射站，不会再影响后续元素st.pop(); }// 经过上面的循环后，如果栈不为空：// 说明栈顶发射站的高度 > 当前发射站的高度// 即栈顶发射站是当前发射站左边最近的更高发射站// 因此当前发射站的能量会被栈顶发射站接收if (!st.empty()) {sum[st.top()] += v[i];}// 将当前发射站的索引入栈，供后续发射站判断st.push(i);}// 找出所有发射站中接收能量最多的值int cnt = 0; // 用于存储最大接收能量值for (int i = 1; i <= n; i++) {// 更新最大值cnt = max(cnt, sum[i]);}// 输出结果cout << cnt << endl;return 0;
}
5.U288342 接雨水 - 洛谷
#include <bits/stdc++.h>
using namespace std;
using ll= long long ;
int main() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; ++i) {cin >> a[i];}stack<int> st; // 存储柱子索引，栈中元素对应高度单调递减ll res = 0;for (int i = 0; i < n; ++i) {// 当当前柱子高度大于栈顶柱子高度时，弹出栈顶并计算积水while (!st.empty() && a[i] > a[st.top()]) {ll top = st.top();st.pop();if (st.empty()) break; // 栈空则无法形成积水ll left = st.top(); // 左侧边界索引ll h = min(a[i], a[left]) - a[top]; // 积水高度ll w = i - left - 1; // 积水宽度res += h * w; // 累加积水量}st.push(i);}cout << res << endl;return 0;
}
6.T511831 柱状图中的最大矩形 - 洛谷
#include <iostream>
#include <vector>
#include <stack>
using namespace std;int main() {int n;cin >> n;vector<int> heights(n);for (int i = 0; i < n; ++i) {cin >> heights[i];}// 在数组首尾添加0，简化边界处理（确保所有柱子都能被计算）heights.insert(heights.begin(), 0);heights.push_back(0);stack<int> stk; // 单调栈：存储柱子索引，确保索引对应高度递增int maxarea = 0; // 存储最大矩形面积，变量名改为maxareafor (int i = 0; i < heights.size(); ++i) {// 当当前高度小于栈顶索引对应的高度时，弹出栈顶并计算面积while (!stk.empty() && heights[i] < heights[stk.top()]) {int height = heights[stk.top()]; // 弹出栈顶元素的高度（当前计算的矩形高度）stk.pop();// 宽度 = 当前索引（右边界） - 新栈顶索引（左边界） - 1int width = i - stk.top() - 1;// 更新最大面积maxarea = max(maxarea, height * width);}// 压入当前索引，维持栈的递增特性stk.push(i);}// 输出最终结果cout << maxarea << endl;return 0;
}
