并查集
参考资料:并查集 - OI
Wiki
基本概念
并查集是一种管理元素所属的数据结构,实现为一个森林，每颗树表示一个集合,树中的节点表示对应集合的元素。
显然，并查集支持两种操作:
合并(union): 合并两个元素各自所属的集合
查询(find): 查询某个元素所属的集合
初始化
初始时，每个元素都位于一个单独的集合表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。
1234struct dsu{ vector<size_t> pa; explicit dsu(size_t size):pa(size){iota(pa.begin(),pa.end(),0);}}
查询
我们需要沿着树向上移动，直至找到根节点。由于根节点的父亲是自己本身，因此递归的终止应该是pa[x]
== x。
123size_t dsu::find(size_t x){ return pa[x] == x? x: find(pa[x]);}
路径压缩
查询 ...
![[题解][生贺]洛谷P1005-矩阵取数游戏](/images/2025-3-5/%E7%94%9F%E8%B4%BA.jpg)
[题解][生贺]洛谷P1005-矩阵取数游戏
.red{
color:red;
font-weight:600; //bold为700，normal为400
}
.lbold{
font-weight:bold;
font-size:24px; //默认16px
}
.bold{
font-weight: bold;
}
if (typeof MathJax === 'undefined') {
window.MathJax = { loader: { load: ['$tex', '$svg'], async: true } };
}
主要思路构建: 2025.3.3
最终攻破:2025.3.3
文章撰写:2025.3.3 - 2025.3.4
感谢朋友的生日礼物，如封面图所示，miku可爱捏，晕晕晕。
为了庆祝生日，写了这篇题解，预期于生日当天发布(3.5)。 ...
![[前端]HTML+CSS教程](https://ooo.0x0.ooo/2025/05/25/OdQPQl.png?_r_=e3c24f5a-031c-be4d-d9cc-175aa25f31eb)
web开发
未读HTML
参考视频:前端Web开发HTML5+CSS3+移动web视频教程，前端web入门首选黑马程序员_哔哩哔哩_bilibili
css弹性盒子起，参考菜鸟教程
定义：超文本标记语言
超文本: 链接
编辑器：WebStorm或VsCode
标签语法
双标签：
需要包括文字内容的标签
语法： 开始标签–文字–结束标签
例如: <strong>文字内容</strong>
结束标签比开始标签多 /， 表示结束的地方。
单标签：
不需要文字内容的标签
例如水平线标签hr
HTML的基本骨架
12345678<html> <head> <title>网页标题</title> </head> <body> 网页主体 </body></html>
VS Code快速生成骨架:
在HTML文件中,!+Enter/Tab键
html : 整个网页
head : 网页头部
title ...
前情提要: 数据结构-线性表
| 4FGR の Blog
参考资料: 数据结构与算法分析 –Mark Allen Weiss
栈模型
栈是限制在插入和删除在末端的线性表，这决定了它的特性是“后进先出“(LIFO)。在解决一些问题时，我们很容易想到通过栈这种结构来解决，例如，对多项式的求解。
对于栈而言，基本的操作是Pop和Push,尽管有时通过Top返回栈顶元素的值。
注意：栈顶元素是栈中唯一可见的元素。
栈的实现
由于栈是一个表，因此任何实现表的方法都可以实现栈，这里给出两种方法：
栈的数组实现
为了讲解的便利和简洁，这里我们通过静态数组的方式实现，大家可以自己实现下动态分配的方法。
定义
123456#define MAXSIZE 1000typedef struct { int data[MAXSIZE]; int top;}*stack;
基本操作
123456789101112131415161718192021222324252627282930313233343536373839void in ...
前情提要：数据结构-线性表
| 4FGR の Blog
单链表
线性表的链式存储，其存储并非是一段连续的存储空间，为了能够访问链表中的元素，每个链表节点不仅存储了元素信息，还需要存放一个指向其后继的指针。（本文所有链表实现均有头节点）
结构体定义
1234typedef struct LNode{ int data; struct LNode *next;}LNode, *LinkList;
基本操作的实现
初始化
123456789// 初始化链表bool initList(LinkedList &L){ L = (LNode*)malloc(sizeof(LNode)); if(L == NULL){ return false; } L->next = NULL; return true;}
检查空表
即检查头节点的后继是否为空
1234//检查链表是否为空bool isEmpty(LinkedList L)& ...
数据结构-线性表
本文仅对线性表进行简单叙述，具体实现会专门出教程，并在具体的数据结构后面给出链接。
定义：线性表是具有相同数据类型的n个元素的有限序列
基本操作：
初始化、取值、查找、插入、删除、判空、销毁
线性表的顺序表示-顺序表
我们可以这样定义顺序表
12345#define MAXSIZE 100typedef struct{ int data[MAXSIZE]; //顺序表的元素(假设类型为int，本文元素均以int为例) int lenth; //顺序表的当前长度}SqList;
当然，如果我们想要通过动态分配的顺序表，只需要让data成为一个指针，并且结构体中存在MaxSize描述当前最大容量即可。
特点：逻辑位置与其存储的物理顺序相同
优点：
可随机访问（取值的时间复杂度为O(1)）
存储密度高
缺点：
插入和删除的时间花费较大
线性表的存储表示-链表
为了避免顺序表插入和删除的线性开销，我们可以允许表不连续存储，于是链表应运而生
我们常常使用头节点head置于 ...
数据结构绪论
由于几天后数据结构要期末考试，最近几天会出数据结构相关的教程，以作复习。
参考资料：
数据结构(C语言版) –严蔚敏，吴伟民
数据结构与算法分析 –Mark Allen Weiss
2025年数据结构考研复习指导 –王道论坛
数据结构的基本概念
基本术语
数据元素：数据的基本单位，由若干数据项组成
数据对象：具有相同性质的数据元素的集合
抽象数据类型：一组操作的集合
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素之间的关系称为结构。数据结构包括三方面内容：逻辑结构、存储结构和数据的运算
数据结构三要素
1.数据的逻辑结构
逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，分为线性结构和非线性结构
集合：结构中的数据元素除“同属一个集合”外，别无其他关系。
线性结构：结构中的数据存在一对一的关系
树形结构：结构中的数据存在一对多的关系
图状结构：结构中的数据存在多对多的关系
2.数据的存储结构
存储结构是指数据结构在计 ...
![[题解]P1011 [NOIP1998 提高组] 车站](https://ooo.0x0.ooo/2025/05/25/OdQPQl.png?_r_=b5adcd84-2ea1-b959-4bea-c14587fe3b41)
题目难点
对数学功底的考察，能否根据题目描述建立起数学公式,
解出关键的未知数(第二次上下车的人数)
题目
洛谷链接： [P1011 NOIP1998 提高组] 车站 -
洛谷 | 计算机科学教育新生态
[NOIP1998 提高组] 车站
题目描述
火车从始发站（称为第 \(1\)
站）开出，在始发站上车的人数为 \(a\)，然后到达第 \(2\) 站，在第 \(2\)
站有人上、下车，但上、下车的人数相同，因此在第 \(2\) 站开出时（即在到达第 \(3\) 站之前）车上的人数保持为 \(a\) 人。从第 \(3\) 站起（包括第 \(3\)
站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第
\(n-1\)
站），都满足此规律。现给出的条件是：共有 \(n\) 个车站，始发站上车的人数为 \(a\)，最后一站下车的人数是 \(m\)（全部下车）。试问 \(x\) 站开出时车上的人数是多少？
输入格式
输入只有一行四个整数，分别表示始发站上车人数 \(a\)，车站数 \(n\)，终 ...
题目链接：TUOJ（需有账号）
题目背景
传说每当月光遍布西西艾弗岛，总有一道身影默默守护着居民们的美梦。
题目描述
梦境中的西西艾弗岛由n+1
个区域组成。梦境巡查员顿顿每天都会从梦之源（0 号区域）出发，顺次巡查
1,2,⋯,n 号区域，最后从n 号区域返回梦之源。
在梦境梭需要消耗美梦能量：
从梦之源出发时，顿顿会携带若干初始能量；
从第 i
号区域前往下一区域（0≤i≤n）需要消耗 ai
单位能量，因此从第 i
号区域出发时，顿顿剩余的美梦能量需要大于或等于ai单位；
顺利到达第 i*
号区域（1≤i≤n）后，顿顿可以从当地居民的美梦中汲取
bi 单位能量作为补给。
假设顿顿初始携带 w 单位美梦能量，那么首先需要保证
w*≥a0，这样顿顿便可消耗a0 能量穿梭到 1
号区域、进而获得 b1 单位能量补给。巡查 1
号区域后，顿顿剩余能量为
w−a0+b1，如果该数值大于或等于
a*1，顿顿便可继续前往 2 号区域。依此类推，直至最后消耗
an 单位能量从 n
号区域返回梦之源，便算是顺利完成整个巡查。西西艾弗岛，又迎来 ...
数据结构-散列表(hash table)
参考资料：数据结构与算法分析 –Mark Allen Weiss
一、基本介绍
散列(hashing)
：一种以常数平均时间执行插入、删除和查找的技术，但对元素间进行排序的操作不被支持，例如寻找最大值和最小值。
散列表（hash table）:
一个含有关键字的具有固定大小的数组，通过关键字查找对应值，只需要O(1)的时间复杂度。
散列函数：将每个关键字映射到从0到size-1这个范围中的某个数，并且放到适当的单元。这个映射就叫做散列函数。
二、散列函数
关键字为整数的设置方法:
如果输入的关键字是整数，则一般合理的方法就是直接返回 关键字%
表长,
最好保证表长为素数（质数），以避免某些特殊情况，例如表长为10，而关键字均以0为个位的情况。
关键字为字符串的设置方法:
通常，关键字是字符串，在这种情形下，散列函数需要仔细选择。
用ASCII码直接相加并取余并不合适,
表长很大，就不能均匀地很好地分配关键字。
代码如下
1234567891011int Hash(const char *key ...
