p1045麦森数
学习到了一个大数 P 的位数可以用 log10（P）+1 表示，以及十进制的运算效率太慢可以用高进制如万进制来加快运行效率，对于万进制我认为可以类比于十进制来学习，数组的一个元素储存一个四位数的整数，后面打印时可以拆成十进制的数来表示
排序1271学生会选举
学习了 qsort 函数，这个函数需要输入指向数组首元素的地址，数组元素的多少，每个数组元素的内存大小，和一个比较函数，这个比较函数的要是这个类型 int compare（const a，const b），后面有一个操作，如果是整数则 num1=（int）a；num2=*（int *）b，如果是升序则 return num1-num2，逆序则 return num2-num1，qosrt 比较函数如果返回负数：第一个参数应该排在第二个参数前面 返回零：两个参数相等 返回正数：第一个参数应该排在第二个参数后面 a[0] 是在 a[1] 的前面
排序1068分数线划定
学会了输入一个浮点数 x，ceil 函数返回不小于 x 的最小整数和 floor 函数返回不大于 x 的最大整数
排序1104生日
学会了 qosrt 对二维数组的排序，对于二维数组，我的理解是每一行是一个连续的内存块，要根据二维数组的某个元素来排序二维数组只需要定义一个指针数组，先让指针数组 b[n] 的每一个元素指向二维数组，然后用 qsort 函数（b，n，sizeof（int），compare），然后定义一个子函数
int compare(const void *a, const void *b) {
const int c = (const int **)a;
const int d = (const int **)b;
return c[i] - d[i];
}（i 指的是要根据二维数组哪个元素排序）
暴力枚举1036选数
写的我好痛苦，我的思路是先从 n 个数中选 k 个数到一个数组里，然后相加再判断是不是素数，初始化 start 和 depth 均为 0，然后用递归的思想不断进行下去，
void tj(int start, int depth) {
if (depth == k) {
result[count] = 0;
for (int j = 0; j < depth; j++) {
result[count] += b[j];
}
if (pd(result[count])) {
m++;
}
count++;
return;
}
for (int i = start; i < n; i++) {
b[depth] = a[i];
tj(i + 1, depth + 1);
}
}判断是不是素数也让我学到很多，判断是不是素数首先判断是不是小于或等于 1，接着判断是不是 2 或 3，然后判断是不是 2 和 3 的倍数，如果都不是就用这个循环
for (int j = 5; j * j <= v; j += 6) {
if (v % j == 0 || v % (j + 2) == 0) {
flag = 0;
break;
}
}学习到了所有的素数都可以用 6k+1 或 6k-1 来表示，锁以判断一个数是不是素数只需要判断这个数是不是 2 或 3 或其他质数的倍数即可
暴力枚举1088火星人
学会了给 next_permutation，给定一个数的所有位数，通过组合将它变大，首先从数值从右边往左边找到第一个 a[i]<a[i+1]，接着从右往左边寻找第一个 a[j]>a[i] 的，然后将 a[i] 与 a[j] 调换，接着将 a[i] 右边的数字变成升序即可 我还学会了 qsort 函数可以指定数组的某个片段来排序
暴力枚举3799小y拼木棒
我一开始想用深度搜索例举出所有的四根木棒的可能，但效率太低了，应该用数学优化来
暴力枚举2392 零时抱佛脚
一开始我是将所有的可能枚举出来，但效率低下，时间复杂度是 o（n的三次方），后面问了 deepseek 学会了子集枚举，就是一个给定一个数组，数组的元素要么是 1 要么是 0，用 2 进制的位运算可以穷举出所有可能
for (int mask = 0; mask < total_mask; mask++) {
int left = 0;
for (int j = 0; j < s[i]; j++) {
if (mask & (1 << j)) {
left += a[i][j];
}
}
}a[i][j] 是那个数组，s[i] 则是数组的大小，total_maskz 是含有的可能的总数，每一个 mask 的二进制都是一种方案 ，后面我自己用递归写了一遍也是可以的 这是二进制方案代码，递归代码在题目里
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
int main() {
int s[4], a[4][20], sum[4], target, total_mask, best, max, i, j, mask;
int total = 0;
// 读入四科的题目数量
scanf("%d%d%d%d", &s[0], &s[1], &s[2], &s[3]);
// 读入每科题目时间并计算总和
for (i = 0; i < 4; i++) {
sum[i] = 0;
for (j = 0; j < s[i]; j++) {
scanf("%d", &a[i][j]);
sum[i] += a[i][j];
}
}
// 对每科求最短时间
for (i = 0; i < 4; i++) {
target = sum[i] / 2;
best = 0;
// 枚举所有子集
total_mask = 1 << s[i];
for (mask = 0; mask < total_mask; mask++) {
int left = 0;
for (j = 0; j < s[i]; j++) {
if (mask & (1 << j)) {
left += a[i][j];
}
}
// 找最接近 target 的
if (abs(left - target) < abs(best - target)) {
best = left;
}
}
// 该科耗时 = 两边中较大的
int right = sum[i] - best;
max = (right > best) ? right : best; // ✅ 用 best 而不是 left
total += max;
}
printf("%d\n", total);
return 0;
}3.6和3.7（日期）
递归你赢了，我被你难死了，外星密码和幂次方这两条题将我狠狠的击碎了
贪心1803yy的烦恼
学会了安排最多活动数只需要将结束最早的且符合条件的计数即可得到安排活动最大值
贪心1090合并果子
学习了最小堆，类似完全二叉数，先将每一个输入的值插入堆尾巴里(也就是数组的最后一个)，父亲节点=（i-1）/2，左子节点为 i2+1，右子节点为 i+2，（i 是在数组的序数，比如 a[3] 的话 i=3）然后比较插入的值与它的父亲节点的大小作比较，然后上浮，这是插入操作：
void push(int val) {
int i = size++; // 先赋值再size自增
while (i > 0) {
int parent = (i - 1) / 2;
if (heap[parent] <= val) break;
heap[i] = heap[parent];
i = parent;
}
heap[i] = val;
}接着是出堆操作，每一次弹出堆首（也就是数组第一个元素）因为这是最小值，接着将 size 自减，然后将堆尾的元素放到堆首然后进行下浮的操作，这是出堆操作：
int pop() {
int ret = heap[0];
int val = heap[--size];
int i = 0;
while (i2 + 1 < size) // 之所以用i2+1<size来判断是因为有左子节点不一定会有右子节点，如果用右子节点来判断的话，那么如果最后一个元素是左子节点，那么这个子节点会被省略掉
{
int left = i2 + 1;
int right = i2 + 2;
int child = (right < size && heap[right] < heap[left]) ? right : left; // 这一行是我觉得非常精妙的操作，它能够判断是否有右子节点，并正确的给child赋值出最小的子节点
if (heap[child] >= val) break;
heap[i] = heap[child];
i = child;
}
heap[i] = val;
return ret;
}贪心1106删数问题
一个数按照原来的序列排序，删除指定的数目 k 的位数得到最小值，先构建一个栈（数组）用来储存，然后每次从最高位遍历加入我们输入的数的那一位数，并将目前遍历到的数与栈顶的数比较，如果小于栈顶的数则将栈顶的数丢掉加上我们这个数，k—，如果遍历完了 k 都没有为 0，则从栈的尾巴开始删数
搜索1443马的遍历
一开始我用的深度搜索，用递归来找出每一种从某点到某一点的所有路径，然后挑最小的来赋值，但花太多时间了，然后问了 ai 用 bfs
BFS 的特点
数据结构：队列（Queue） 访问顺序：按层（按距离） 适用问题： 无权图/网格中的最短路径 / 最少步数 连通性判断（从 A 能不能到 B） 分层遍历（比如二叉树的层序遍历） 优点： 第一次到达目标时的路径一定是最短的（步数最少）。 缺点： 要把同一层节点都暂存起来，空间开销可能比较大。
我对于这个的理解，用 queuex[100]、queuey[100] 储存队列某一节点的横坐标和纵坐标，然后 front 指向某一层的起点，rear 指向某一层的终点，然后遍历这每一层，得到下一层的结果 dist[100] 用来储存某一点到其它点的距离，先初始化为 -1，然后 dist[x][y]=0 初始化为 0，是因为某点到自己的距离为 0，当 front＝rear 时变已经到头了，可以直接结束
（哈希表）数据结构线性表寄包柜
用了 c＋＋会了哈希表，用 unordered_map<键（key）对应的类型，值对应的类型>mp（哈希表的名字），用了这个就不用开太大的内存，只能访问到已经存入哈希表的值，省了很多空间，如果想要删除哈希表的某个键对应的值可以用 mp.erase(key)，这个哈希表可以起到一维数组也可以二维，甚至多维的储存效果，比如 key=i 是一维的效果，那么 key=i10000000+j 就是二维效果，那么 key=i10000000000000+j*100000000+z 就是三维效果，以此类推，以及计算 string 类型的 a 的长度可以用 a.sizeof() 和 a,length，这两个的返回值都是 a 的长度，但不包括结束符，然后访问 a 这个字符串类型的某个字符可以用 a.at(i)，这个可以区分边界
今天学习c++有关类的感悟
今天主要学历构造函数，拷贝构造函数，构析函数，以及拷贝赋值运算符，我先定义了一个类数组 Student c[3]，就已经说明了这个对象已经存在了，然后你想用一个类来赋值给这个 C[i]，那么就要用到拷贝运算符函数将临时对象赋值给 c[i]，赋值一个临时对象给另一个对象时需要先检查这两个对象的地址是否一样，防止自己给自己赋值，但赋值里如果类里有指针类型的数据（name）则需要将这个数据内存释放出来先，后面再重新开辟一个数据（name），但如果你是 Student b（a） 或者 Student b=a，那这个对象 b 还没有初始化，那么你需要用对象 a 来初始化对象 b，然后再用拷贝赋值运算符函数将临时对象 a 赋值给 b，拷贝构造函数例如 Student(const Student& 随意名字（这里用other）) 是将类型为 const Student& 的临时对象给绑定到名字为上述参数里的 other，然后用 other 给要赋值的数组初始化，再用拷贝赋值函数将这个对象传递到我 c[i] 取，这个 operator 是重载运算符，operator 说明我要重载运算符，这个函数里会有个 this 指针指向 c[i] 即可；
#include <bits/stdc++.h>
using namespace std;
class Student {
private:
int num;
char* name;
int year;
public:
Student() : num(0), name(nullptr), year(0) {}
Student(int n, string a, int m) : num(n), year(m) {
name = new char[a.length() + 1];
strcpy(name, a.c_str());
}
Student(const Student& other) // 等价于当前对象
{
num = other.num;
year = other.year;
if (other.name != nullptr) {
name = new char[strlen(other.name) + 1];
strcpy(name, other.name);
} else {
name = nullptr;
}
}
Student& operator=(const Student& other) {
if (this == &other) {
return *this;
}
delete[] name;
num = other.num;
year = other.year;
if (other.name != nullptr) {
name = new char[strlen(other.name) + 1];
strcpy(name, other.name);
} else {
name = nullptr;
}
return *this;
}
void show() {
cout << "学号" << num << endl;
cout << "姓名" << name << endl;
cout << "年龄" << year << endl;
}
~Student() {
delete[] name;
}
};
int main() {
Student c[3];
for (int i = 0; i < 3; i++) {
int n, m;
string a;
cout << "请输入:学号 " << "姓名 " << "年龄" << endl;
cin >> n >> a >> m;
c[i] = Student(n, a, m);
}
for (int i = 0; i < 3; i++) {
c[i].show();
}
}关于c++的双向链表感悟（1160，队列安排）
首先定义一个双向链表，list<链表的数据类型>p（）链表的名字，然后定义一个链表的迭代器 list
for (auto res : link) {
cout << res << " ";
}auto 是系统自动识别数据类型，res 是 link 里的一个整数数据，link 会将节点的元素赋值给 res，它会自动遍历完整个链表，然后打印出来 ios::sync_with_stdio(false); 这一行是因为 c＋＋与 c 有兼容型，所以每一次 cin 都会去问一下 scanf 有没有没读取的数据所以会慢，但加了这一行就不能同时使用 cin 和 scanf 了 cin.tie(0); 这一行是为了解除 cin 与 count 的绑定，因为每一次的输入都会刷新一下缓冲区让 count 打印出没打印的数据，但做算法题时都是一堆数据输入以后再输出，因此没必要频繁的刷新缓冲区； 打印换行时尽量不要 <<endl，用 <<“\n” 更快
有关二叉树和结构体的感悟（数据结构美国的血缘）
让我知道了定义结构体可以在结构体里面初始化，
struct jd {
char val;
jd *left;
jd *right;
jd(char v) : val(v), left(nullptr), right(nullptr) {}
};其次是有关 new 的用法，我之前认为 new 只能这样用，new+类型[]，现在我知道可以 jd *root=new jd(m)；让这个节点有一个存储空间来储存数据，m 是对结构体成员的初始化值
有关红黑二叉树的理解与感悟
红黑二叉树某一节点的右子树的所有节点都是大于该节点的，某一节点的左子树的所有节点都是小于该节点的 学习了一种类型叫枚举类型 enum{类型1，类型2…} 可以在该类型里对类型赋值，这样子当定义某个是该类型是可以默认类型等价于它的赋值 关于红黑二叉树的建立，首先要定义一个哨兵节点
RedBlackTree() {
NIL = new Node(0); // 定义哨兵节点是一个空
NIL->color = BLACK; // 给哨兵节点赋值颜色
root = NIL;
}让所有的空节点都指向哨兵节点，这样子，当访问的节点不存在的时候也不会报错，空节点的颜色也是黑色，符合红黑树的规则，同时也意味这我门可以用（b！=NIL）来代替（b！=nullptr），root = NIL 意味着刚开始这颗树是空的
有关插入节点：先为这个节点开辟一块内存 Node *z = new Node(data)；然后因为没有找到 z 的父亲节点所以 z->parent = nullptr；然后定义一个节点指向整颗树的根节点（Node *x = root;）再定义一个节点为空（Node *y = nullptr;）来寻找 z 的父亲节点，先将 y 这个空节点指向 x，然后通过 x 的 data 和 z 的 data 比较大小，如果 x 比 z 的 data 大，那么将 x 左移，反之则右移，当 x 走到叶节点，即空节点时循环停止；代码：
while (x != NIL) {
y = x;
if (z->data < x->data) x = x->left;
else x = x->right;
}因为每一个节点都需要双向连接，走到了该空节点了，自然要 z->parent = y，然后根据 y 的情况来判断 z 是属于 y 的左节点还是右节点还是 root，下面再判断如果 z==root 或者 z->parent==root 那么就返回插入下一个值，否则就开始维护红黑二叉树
维护红黑二叉树：如果该节点 z 的父亲节点是红色则是违背了红红相连的情况，那么则需要根据叔叔节点（和爸爸同根的另一个子节点）的颜色来判断怎么维护了
- 如果叔叔也是红色，那么只需要将叔叔节点和父亲节点的颜色改为黑色同时将爷爷节点的颜色改为红色，然后将 z=z->parent->parent，因为爷爷节点改成红色以后可能会和相对于爷爷的叔叔节点（爷爷的同根的另一个子节点）发生颜色冲突
- 如果叔叔是黑色，那么先判断 z 节点是在父亲节点的左边还是右边来分两种情况： （1）如果是在左边，则需要以 z->parent->parent 为轴节点来一次右旋； （2）如果是在右边则需要将先以 z->parent 为轴来一次左旋，然后将 z 节点染黑色再将 z 节点的爷爷然成红色，然后再以 z 节点的爷爷为轴来一次右旋
初始： 左旋： 右旋：
A(black) A(red) Z(black)
/ \ / \ / \
B(red) C(黑) Z(红) C(黑) B(red) A(red)
| /
Z(红) B(red) |
C(black)同时，左旋以后要将轴节点的父亲节点的原来的左子节点成为轴节点的右节点，然后轴节点成为父亲节点的左节点，右旋以后则是将轴节点的父亲节点的原来的右节点成为轴节点的左子节点，然后轴节点成为父亲节点的右节点；
// 左旋：右重变左重
void leftRotate(Node *x) {
Node *y = x->right;
x->right = y->left; // 1. 将 y 的左子树接到 x 的右边
if (y->left != NIL) y->left->parent = x;
y->parent = x->parent; // 2. y 顶替 x 的位置
if (x->parent == nullptr) root = y;
else if (x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
y->left = x; // 3. x 变成 y 的左子树
x->parent = y;
}左旋和右旋的代码差不多，挑着左旋来讲，初始先定义一个指针指向插入的轴节点（x），然后定义一个节点（y）指向轴节点的右子节点，然后将轴节点的左子节的右子节点给到轴节点的右节点（x->right=y->left），然后判断该节点是不是空节点，如果是不是空节点，因为节点直线要双向的，所以 if (y->left != NIL) y->left->parent = x;，这样子轴节点的右节点变和 y 节点的左子节点联系上了，然后将 y 的父亲节点指向轴节点的父亲节点，接下来便是判断轴节点的父亲节点是不是空节点，如果是空节点，那么 x 便是根节点，那么 y 便成为根节点 if (x->parent == nullptr) root = y; 如果轴节点是父亲节点的左子节点，那么便将 y 变成轴节点的父亲节点的左字节点 else if (x == x->parent->left) x->parent->left = y; 如果轴节点是父亲节点的右子节点，那么便将 y 变成轴节点的父亲节点的右子节点 else if (x == x->parent->right) x->parent->right = y; 这样便是建立了 y 与轴节点的父亲节点的联系了，然后将轴节点成为 y 节点的左节点 y->left = x;，轴节点的父亲节点变成 y 这是代码：
#include <iostream>
using namespace std;
// 颜色枚举
enum Color { RED, BLACK };
// 节点结构体
struct Node {
int data;
Color color;
Node *left, *right, *parent;
Node(int data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};
class RedBlackTree {
private:
Node *root;
Node *NIL; // 哨兵节点，所有叶子指向它，颜色恒为黑
// --- 核心旋转函数 ---
// 左旋：右重变左重
void leftRotate(Node *x) {
Node *y = x->right;
x->right = y->left; // 1. 将 y 的左子树接到 x 的右边
if (y->left != NIL) y->left->parent = x;
y->parent = x->parent; // 2. y 顶替 x 的位置
if (x->parent == nullptr) root = y;
else if (x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
y->left = x; // 3. x 变成 y 的左子树
x->parent = y;
}
// 右旋：左重变右重
void rightRotate(Node *y) {
Node *x = y->left;
y->left = x->right; // 1. 将 x 的右子树接到 y 的左边
if (x->right != NIL) x->right->parent = y;
x->parent = y->parent; // 2. x 顶替 y 的位置
if (y->parent == nullptr) root = x;
else if (y == y->parent->left) y->parent->left = x;
else y->parent->right = x;
x->right = y; // 3. y 变成 x 的右子树
y->parent = x;
}
// --- 核心修复函数 ---
void insertFixup(Node *z) {
// 只要父节点是红色，就违反了规则 4
while (z->parent->color == RED) {
// 情况 A：父亲是祖父的左孩子
if (z->parent == z->parent->parent->left) {
Node *u = z->parent->parent->right; // 叔叔节点
// Case 1: 叔叔是红色 -> 变色
if (u->color == RED) {
z->parent->color = BLACK;
u->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent; // 冲突上移到祖父
} else {
// Case 2: 叔叔是黑色，且 z 是右孩子 -> 左旋变直线
if (z == z->parent->right) {
z = z->parent;
leftRotate(z);
}
// Case 3: 叔叔是黑色，且 z 是左孩子 -> 染色 + 右旋
z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(z->parent->parent);
}
}
// 情况 B：父亲是祖父的右孩子（与 A 完全对称）
else {
Node *u = z->parent->parent->left;
if (u->color == RED) {
z->parent->color = BLACK;
u->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
rightRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
leftRotate(z->parent->parent);
}
}
if (z == root) break;
}
root->color = BLACK; // 规则 2：根节点强制黑
}
public:
RedBlackTree() {
NIL = new Node(0);
NIL->color = BLACK;
root = NIL;
}
// 标准 BST 插入
void insert(int data) {
Node *z = new Node(data);
z->left = z->right = NIL;
z->parent = nullptr;
Node *y = nullptr;
Node *x = root;
while (x != NIL) {
y = x;
if (z->data < x->data) x = x->left;
else x = x->right;
}
z->parent = y;
if (y == nullptr) root = z;
else if (z->data < y->data) y->left = z;
else y->right = z;
// 如果是第一个节点，直接变黑退出
if (z->parent == nullptr) {
z->color = BLACK;
return;
}
// 如果没有祖父节点，说明父节点是根，不需要修复
if (z->parent->parent == nullptr) return;
insertFixup(z);
}
// 中序遍历打印（验证是否有序）
void inorder(Node *node) {
if (node != NIL) {
inorder(node->left);
cout << node->data << "(" << (node->color == RED ? "R" : "B") << ") ";
inorder(node->right);
}
}
void printTree() {
inorder(root);
cout << endl;
}
};
int main() {
RedBlackTree rbt;
// 测试数据
int arr[] = {10, 20, 30, 15, 25, 5, 1};
for (int x : arr) {
rbt.insert(x);
cout << "插入 " << x << " 后: ";
rbt.printTree();
}
return 0;
}floyd(弗洛伊德算法)二叉树医院的设置
知道每个点到令一个点的距离，然后通过三个循环来求出每两个节点的最短距离
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dis[i][k] != INF && dis[k][j] != INF) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}这个外层 k 循环是算法的核心，这个三个循环是求出每两个连接的点的最短的距离，k 循环不能放在最内部，因为这样子会导致两点之间只经过一个中转站，而放在最外层则是会有多个中转站；
数据结构二叉树（遍历的问题~二叉树问题）的收获
《遍历的问题》的收获：
这条题目是根据前序遍历和后序遍历求出中序遍历有多少种可能，前序遍历加中序遍历和中序遍历加后序遍历可以得到唯一的后序遍历和前序遍历，但前序遍历加后序遍历却可以有好几种中序遍历，如何计算有多少总中序遍历呢，只需要遍历前序遍历：
for (int i = 0; i < n - 1; ++i) {
char u = qx[i];
char v = qx[i + 1];
auto h = find(hx.begin(), hx.end(), u);
auto j = find(hx.begin(), hx.end(), v);
if (j + 1 == h) {
k++;
}
}如果在前序遍历遍历到的 u 后面的是 v，就去后序遍历查找 v 的后面是不是 u 如果是说明 u 有两个节点，然后 k++，最后得到的 2 的 k 次方 就是中序遍历的可能数
《新二叉树》的收获：
这题目是建立一棵二叉树然后前序遍历，是用了一个 map（unordered_map<char,node*>treemap;）来确认输入的三个节点的值 a、b、c 是否存在，键对应的是节点字符，值对应的是节点的地址，如果 a 不存在（treemap.find(a)==treemap.end()）的话就开一个新节点，然后让一个 node current=treemap[a]；让这个指针指向了该节点后就可以对该节点左右子节点操作了，如果这个节点是第一个节点便讲它的地址赋予根节点，然后判断输入的 b、c 是否存在，如果不存在就开辟一个新内存，然后讲 current 指针的左右指针分别指向左右节点的地址
if (b != '') {
if (treemap.find(b) == treemap.end()) treemap[b] = new node(b);
current->left = treemap[b];
}
if (c != '*') {
if (treemap.find(c) == treemap.end()) treemap[c] = new node(c);
current->right = treemap[c];
}《求先序排列》：
没有收获，还是建立树然后在按照先序遍历打印。
《二叉树问题》：
这题目让我学会了怎么求二叉树的深度和宽度，定义一个 depth[] 数组和 kd[] 数组还有一个 fa 数组和 ch 容器来记录父亲和儿子（vector<int>ch[105];int fa[105]，），这样子定义每个 ch[i] 都是一个容器，因为每一节点都可能有两个儿子，但每个儿子只有一个父亲，统计了父亲和儿子以后，先定义 depth[1]=1，用一个 bfs 来遍历每一个节点的子节点，先定义一个队列 k（queue<int>k;），然后先讲 1 存入队列，进入循环将队列的第一个值取出作为当前的父亲以后再弹出，然后用一个循环遍历这个父亲的子节点并将该节点储存进队列里，再用 depth[字节点]=depth{父亲节点}+1 来计算子节点的深度，然后 kd[depth[c]]++ 来计算当前层的宽度，后面再遍历这个 kd 数组取最大值来作为宽度，depth 数组取对大值当深度，然后输入两个点求距离，用一个循环来即可，不难
int up = 0, down = 0;
while (x != y) {
if (depth[x] > depth[y]) {
x = fa[x];
up++;
} else if (depth[x] < depth[y]) {
y = fa[y];
down++;
} else {
x = fa[x];
y = fa[y];
up++;
down++;
}
}数据结构集合（亲戚~家谱）的收获
《亲戚》：
先初始化每个人的亲戚都是自身，后面每当输入一对亲戚关系的时候，都让输入的第二个人指向第一个人的亲戚，这样，后面辨别是否为亲戚的时候只需要找，它门的第一个亲戚是否为同一个人即可；
《村村通》：
初始化每条村道路通往自身，后面每输入两个村道路相通时，让第二个村道路通向最先开始的节点指向第一个村庄最开始的节点，这样子两个部分的道路都指向第一个村最开始的节点，就说明这些节点都通了，但第一个节点还是自身指向自身，后面判断有多少个自身指向自身的节点然后减一就是孤立节点 count，所以要建 count 条路；
《字符串哈希》：
学会了一个容器 unordered_map，它是储存一个键，存储不是按照输入顺序储存，而是按照哈希顺序储存，它的的储存具有唯一性和无序性，以及它的查找（set.count(键)），插入（set.insert(键)）和删除（set.erase(键)）都非常的块，时间复杂度是 o（1），通常来判断某个东西是否存在，如果插入的键存在就不会插入了，所以这题就用这个来插入每一个输入的字符串，然后最后统计这 set 的大小（set.size）即可；
《Cities and States S》：
学会了 unordered_map，这也是一个容器，一个键对应一个值，这个键可以是任何数据类型，值可以是任何数据类型或者结构体或者其它容器或者地址，这里用键对应输入城市的前两个字符+代码（提取一个 string 类型的前两个字符生成一个新的字符串用到函数 string m=g.substr(首位置,字符个数)，两个字符串相加等于一个新的字符串 string current=m+k;），值对应输入城市的前两个字符相同的个数，后面再将 map 对应的输入字符串的值加一即可，后面用 sun 加上 map 中目标字符串对应的值就可以统计了。
《木材厂库》：
用一棵红黑树储存输入的木材，然后先用 set.find(需要的木材长度)，如果存在则输出并将值为需要的木材长度的节点给删除 set.erase(需要的木材的长度)，如果不存在则用 set.lower_bound(需要的木材长度) 找到大于所需木材长度的最小值，如果没有那么就输入 set.lower_bound(需要的木材长度) 返回的迭代器减一指向地址的值，如果有，那就先判断有没有前驱指针，如果没有则输入 set.lower_bound(需要的木材长度) 返回的迭代器指向地址的值，如果有则先判断前驱指针指向的地址的值和 set.lower_bound(需要的木材长度) 返回的迭代器指向地址的值与所需木材长度的误差，如果误差不一样则输出误差小那课，一样则输出小的那颗树。
《学籍管理》：
用一个 unordered_map 来储存数据，键对应姓名，值对应成绩，执行插入，删除，查早，统计没什么难度。
《保龄球》：
用一个 unordered_map 存储数据，键对应的球数量，值对应位置即可；
《关押罪犯》：
这题用到了贪心算法，先将每一对关系用一个 vector<int,int>a 储存一个结构体，结构体成员为两名罪犯和怒气值，储存数据时要 a.push_back({p,q,w});，然后根据怒气值从大到小排序，然后再定义一个数组 emeny 用来储存某个罪犯的第一个敌人，后面遍历容器 a，先判断遍历到的结构体的两个罪犯是否连接的同一个节点，如果是说明是在同一个监狱，因为排序是降序，所以这个是怒气值最大则直接输出然后停止遍历，如果不是一个节点的话就先判断第一个罪犯有没有 enemy，如果没有则将第二个罪犯变成第一个罪犯的 enemy，如果有则将第一个罪犯和第二个罪犯整合到同一个监狱（即连接同一个节点），然后判断第二个罪犯有没有 enemy，如果没有，那么便将第一个罪犯成为第二个罪犯的 enemy，如果有那么将第二个罪犯的 enemy 与第一个罪犯整合到一起。这题我学到了一个 sort 函数用来排序，
sort(a.begin(), a.end(), [](const three& q, const three& e) {
return q.w > e.w;
});它将排序的结构也写出来了，不用额外写一个比较函数 [] 表示不使用外部变量 const three& e 表示引用一个 three 类型的结构体，这样子省了拷贝，return q.w>e.w; 这是比较逻辑，如果大于那么 q 在前面。
《集合》：
学会了一个找出某个范围内的质数，代码：
bool is_prime[1000000];
vector<int> prime;
void slive(int n) {
fill(is_prime, is_prime + n + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if (is_prime[i] == true) {
prime.push_back(i);
for (int j = 2; ji <= n; j++) {
is_prime[ji] = false;
}
}
}
}int first=(a+op-1)/op*op; 这个是找出某个质数乘以一个在该范围内的第一个，这挺有趣的；一开始先让该范围内的每一个数都指向自身，sum++，后面找出该范围的所有质数以后，便将该质数乘以多个整数的值在该范围内就合并起来，每次合并都 sum—；
《团伙》：
可以先初始化每个人 py 都是指向自身，或者在 find 的逻辑上加上 if (py.find(m)==py.end()) return py[m]=m; 如果没有 py 则是指向自身并饭回自身，输入一组数据 opt、p、q 先判断是朋友还是敌人，如果是朋友直接整合，让他们指向同一个节点，如果是敌人，那么先判断第一个人是否有敌人即 dr.find(p) 是否存在，如果存在便将 dr[p] 与 q 整合，不存在便将 q 作为 p 的敌人，然后判断 q 是否有敌人，如果有便将 dr[q] 与 p 整合，不存在便将 p 变成 q 的敌人，最后面判断如果 py[i]==i 或者 py[i]==0 便是一个团伙计数即可。
《程序自动分析》：
先将题目中给出等价的用一个类型为结构体的容器 vecrot 储存，然后将不等价的用一个类型为结构体的容器 vector 储存，先根据等价来建立结合，让等价的指向同一个节点，后面再遍历不等价的容器，如果在关系中输入的两个数是等价的说明不成立跳出循环，如果一直没有输出不成立那么便是成立
《不重复的数字》：
用一个 unordered_set 来判断输入的数字有没有重复，再用一个 vector 储存输入的数字，后面输出即可。
《阅读理解》：
用一个 unordered_map 来储存数据，键是一个字符，值是一个容器用来储存位置，如果位置已经存在了，那么改行就不要储存了，后面根数输入的键输出对应值即可。
《家谱》：
和前面的集合一样，先根据第一个字符判读输入的是父亲还是儿子，然后将儿子连向父亲指向的那个节点即可 n=n.substr(1); 这个的意思是跳过第一个字符，生成一个新的字符赋值给 n。