GDUT-21级排位赛第一场 - G. Board Game(暴力搜索)
题意Feras bought to his nephew Saleem a new game to help him learning calculating. The game consists of a board with 4 rows and 4 columns with 16 cubes. Every cube has a number from 1 to 16. Let’s define the power of a column as the sum of its elements. In the same way, the power of a row is the sum of its elements. Saleem should arrange the cubes in the board such that the power of all columns and all rows are equal. To make the game easier, the nice uncle, Feras, will help him arranging 7 cubes, ...
L2-1 点赞狂魔
题意微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。
输入格式输入在第一行给出一个正整数N（≤100），是待统计的用户数。随后N行，每行列出一位用户的点赞标签。格式为“Name K F₁⋯Fₖ”，其中Name是不超过8个英文小写字母的非空用户名，1≤K≤1000，Fᵢ（i=1,⋯,K）是特性标签的编号，我们将所有特性标签从 1 到 10⁷ 编号。数字间以空格分隔。
输出格式统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用-补齐缺失，例如mike jenny -就表示只有2人。
输入样例
5bob 11 ...
L2-2 小字辈(搜索/并查集)
题意本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。
输入格式输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。
输出格式首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。
样例1
input
9 2 6 5 5 -1 5 6 4 7
output
4 1 9
思路这道题就是开vector二维数组存父子关系，然后就搜呗。感觉深搜比广搜直接。
具体做法都是先把每个爹的儿子们记录下来，其中是-1的那个是老祖宗，我们从老祖宗开始往下搜。用maxd更新最大辈分。
第3种思路：用并查集存爹，然后边打标记边枚举每个儿子，分别递归找爹。
思路1（DFS）1234567891011121314151617181920212223242 ...
L2-4 部落（并查集）
题意在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。
输入格式输入在第一行给出一个正整数N（≤10⁴），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：
K P[1] P[2] ⋯ P[K]
其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过10⁴。
之后一行给出一个非负整数Q（≤10⁴），是查询次数。随后Q行，每行给出一对被查询的人的编号。
输出格式首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。
输入样例4 3 10 1 2 2 3 4 4 1 5 7 8 3 9 6 4 2 10 5 3 7
输出样例10 2 Y N
思路并查集模板题。用set存人，方便去重和统计。
代码1234567891011121314151617181920212 ...
专题学习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 - 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 - ...
专题训练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* ...
专题训练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, ...
专题训练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 ...
专题训练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 ...