专题学习1 - I - 滑动窗口
专题学习1 - I - 滑动窗口题意给一个长度为 N 的数组，一个长为 K 的滑动窗体从最左端移至最右端，你只能看到窗口中的 K 个数，每次窗体向右移动一位，如下图：
窗口位置
最小值
最大值
[1 3 -1] -3 5 3 6 7
−1
3
1 [3 -1 -3] 5 3 6 7
−3
3
1 3 [-1 -3 5] 3 6 7
-3
5
1 3 -1 [-3 5 3] 6 7
-3
5
1 3 -1 -3 [5 3 6] 7
3
6
1 3 -1 -3 5 [3 6 7]
3
7
你的任务是找出窗体在各个位置时的最大值和最小值。
输入格式第 1 行：两个整数 N 和 K；第 2 行：N 个整数，表示数组的 N 个元素(≤2×10^9)；
输出格式第一行为滑动窗口从左向右移动到每个位置时的最小值，每个数之间用一个空格分开；第二行为滑动窗口从左向右移动到每个位置时的最大值，每个数之间用一个空格分开。
思路单项队列模板题。
代码12345678910111213141516171819202122232425262728293031323334#inc ...
专题训练1 - G - 二分查找
题意给定一个严格单调的数列，询问若干个数分别需要在数列中二分几次才能找到。如果能找到，输出二分的次数；如果不能找到，输出 NONE。二分查找参考程序如下：
（数列单调递增时）
12345678l = 1, r = n, cnt = 0;while (l <= r) { mid = (l + r) / 2; cnt++; if (a[mid] == key) break; if (a[mid] > key) r = mid - 1; else l = mid + 1;}
（数列单调递减时）
12345678l = 1, r = n, cnt = 0;while (l <= r) { mid = (l + r) / 2; cnt++; if (a[mid] == key) break; if (a[mid] > key) l = mid + 1; else r = mid - 1;}
上述程序中结束时 cntcnt 的值即为二分次数。
输入格式第一行两个整数 n* ...
专题训练3-图论 - A - 并查集
题意这是一道模板题。
维护一个 n 点的无向图，支持：
加入一条连接 u 和 v 的无向边
查询 u 和 v 的连通性
由于本题数据较大，因此输出的时候采用特殊的输出方式：用 0 或 1 代表每个询问的答案，将每个询问的答案依次从左到右排列，把得到的串视为一个二进制数，输出这个二进制数 mod 998244353 的值。
请务必使用快读。
输入格式第一行包含两个整数 n,m，表示点的个数和操作的数目。
接下来 mm 行每行包括三个整数 op,u,v。
如果 op=0，则表示加入一条连接 u 和 v 的无向边；
如果 op=1，则表示查询 u 和 v 的连通性。
输出格式一行包括一个整数表示答案。
样例
Input
Output
3 6 1 1 0 0 0 1 1 0 1 1 1 2 0 2 1 1 2 1
5
答案串为 0101。
数据范围与提示n≤4000000, m≤8000000
思路这就是一道并查集的模板题。题中提到“请务必使用快读”，我暂时没发现有需要使用的地方，不过学习了快读的模板：
12345678910C++inline int ...
专题训练2-DP - B - 最长公共子序列
题意给出1∼n 的两个排列P1 和 P2，求它们的最长公共子序列。
输入格式第一行是一个数 n (1≤n≤10^5)。
接下来两行，每行为 n 个数，为自然数1∼n 的一个排列。
输出格式一个数，即最长公共子序列的长度。
思路一开始用朴素的LCS算法（O(n²)）来写，发现数据范围到1e5会超时，然后向大佬学习一种新思路：
将LCS问题转换为求LIS问题，具体做法就是将第一个序列的顺序定义为“升序”，再对第二个序列求最大升序子序列（实际上是第一个序列的子序列），此时求出的子序列就是两个原序列的公共子序列。
代码123456789101112131415161718192021222324252627282930313233343536373839404142#include <iostream>#include <algorithm>using namespace std;const int N = 1e5 + 5;int n, len = 0, x;int a[N], ind[N], q[N];int bound(int x){ int l = 1, ...
专题学习1 - J - 最大连续和
题意给你一个长度为 n 的整数序列{A1,A2,⋯,An}，要求从中找出一段连续的长度不超过 m 的非空子序列，使得这个序列的和最大。
输入格式第一行为两个整数 n,m；
第二行为 n 个用空格分开的整数序列，每个数的绝对值都小于 1000。
输出格式仅一个整数，表示连续长度不超过 m 的最大非空子序列和。
思路单项队列模板题。
代码12345678910111213141516171819202122232425262728#include <iostream>using namespace std;const int N = 2e5 + 10;int n, m, res = -1<<30;int a[N], s[N], q[N];int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) { scanf("%d", &a[i]); s[i] = s[i - ...
专题训练3-图论 - B - Learning Languages（并查集）
题意The “BerCorp” company has got n employees. These employees can use m approved official languages for the formal correspondence. The languages are numbered with integers from 1 to m. For each employee we have the list of languages, which he knows. This list could be empty, i. e. an employee may know no official languages. But the employees are willing to learn any number of official languages, as long as the company pays their lessons. A study course in one language for one employee costs 1 ber ...
专题训练3-图论 - L - Cow Contest （Floyd最短路）
题意FJ的N(1 <= N <= 100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上，奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1 <= A <= N; 1 <= B <= N; A != B) ，那么她们的对决中，编号为A的奶牛总是能胜出。 FJ想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 M(1 <= M <= 4,500)轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。
输入格式第1行: 2个用空格隔开的整数：N 和 M 第2..M+1行: 每行为2个用空格隔开的整数A、B，描述了参加某一轮比赛的奶 牛的编号，以及结果（编号为A，即为每行的第一个数的奶牛为 胜者）
输出格式第1行: 输出1个 ...
专题训练3-图论 - C - The Suspects（并查集）
题意2019冠状病毒病（英语：Coronavirus disease 2019，缩写：COVID-19 ），是一种由严重急性呼吸系统综合症冠状病毒2型（缩写：SARS-CoV-2）引发的传染病。此病在全球各国大规模爆发并急速扩散，成为人类历史上致死人数最多的流行病之一。 很显然，目前最好的办法就是将所有可能的患者都隔离起来。 现在某高校正在排查可能的患者，这个高校中有多个社团，每个社团经常进行内部交流，一名学生可能会加入多个社团。学校认为一旦某个社团里出现一名可疑患者，这整个社团的学生都被视为是可能的患者。 现在请你帮忙找到这所学校的所有可能的患者。
（题面漏了一句话：0号学生带病毒。）
输入格式输入文件包含多组数据。
对于每组测试数据：
第一行为两个整数n和m, 其中n是学生的数量, m是社团的数量。0 < n <= 30000，0 <= m <= 500。
接下来m行，每一行有一个整数k，代表社团中学生的数量。之后，有k个整数代表这个社团里每个学生的编号（在0到n-1之间）。
n = m = 0表示输入结束， ...
G-排解忧伤
12345678910111213141516171819202122232425#include <bits/stdc++.h>using namespace std;int a[100005];int main() { long long n, m, frontier = 0, ans = 0; cin >> n >> m; for (int i = 0; i < m; i++) cin >> a[i]; sort(a, a+m); // 把每个人的心仪座位正序排序 for (int i = 0; i < m; i++) { if (a[i] > frontier) { // 更新边界 frontier = a[i]; } else { ans += frontier-a[i]+1; // 总怒气值增加 frontier++; ...
回溯算法
模板
123456789101112 1 void backtracking(参数) { 2 if (终止条件) { 3 存放结果; 4 return; 5 } 6 7 for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 8 处理节点; 9 backtracking(路径，选择列表); // 递归10 回溯，撤销处理结果;11 }12 }
未优化版本：
1234567891011121314151617181920212223 1 class Solution { 2 private: 3 vector<vector<int>> result; // 存放符合条件结果的集合 4 vector<int> path; // 用来存放符合条件结果 5 void backtracking(int n, int k, int s ...