并查集
并查集并查集（Disjoint Set Union, DSU）是一种数据结构，用于处理不相交集合（disjoint sets）的合并（union）和查询（find）操作。并查集特别适用于动态连通性问题，例如判断两个元素是否在同一个集合中或合并两个集合。广泛应用在图论算法中，比如 Kruskal 最小生成树算法。 并查集的概念并查集主要支持两个操作： 查找（Find）：确定元素所属的集合。通常返回集合的“代表元素”。 合并（Union）：将两个集合合并成一个集合。 并查集使用树结构来表示集合，每个集合中的元素都指向一个根节点，根节点代表该集合。为优化效率，通常使用以下两种技术： 路径压缩（Path Compression）：在查找操作中，将树的高度降低，使得查找的时间复杂度接近常数。 按秩合并（Union by Rank）：在合并操作中，将较小的树合并到较大的树上，避免树变得过于深。 并查集的性质 时间复杂度：使用路径压缩和按秩合并的并查集可以将单次操作的平均时间复杂度优化到几乎为常数，接近 $O(\alpha(n))$ ，其中 $(\alpha)$...
树
树在数据结构中，树（Tree）是一种分层的非线性数据结构，它由节点（node）和边（edge）组成，并且具有以下性质： 树的概念 节点和边：树包含一组节点，通过边连接，节点之间呈现出层级关系。 根节点：树的起始节点称为根节点（root），通常位于树的顶端。 父节点和子节点：每个节点可以连接其他节点，称为子节点（children）；连接它们的节点称为父节点（parent）。 叶子节点：没有子节点的节点称为叶子节点（leaf）。 层级：树的每一层从根节点开始，按层级关系排列。 路径：节点之间的路径由节点和边组成，从根节点到某个特定节点的路径是节点之间的唯一路径。 树的性质 唯一根节点：树中只有一个根节点，没有父节点。 节点数量关系：有 ( n ) 个节点的树，边的数量为 ( n - 1...
哈希表
哈希表（Hash Table）是一种用于存储键值对的数据结构，可以通过哈希函数快速地根据键找到对应的值。哈希表的查找、插入和删除操作在平均情况下具有 O(1) 的时间复杂度，非常高效。 1. 哈希表的基本概念哈希表的核心思想是将键通过一个哈希函数（Hash Function）映射到一个哈希表的索引位置上。若两个键映射到同一位置（即出现哈希冲突），则需要解决冲突以保证数据存储的正确性。 哈希表的术语 哈希函数：将键映射到表中某个位置的函数。 哈希冲突：两个不同的键被映射到同一个位置。 装载因子：表中已填充元素的数量与哈希表大小的比值。较高的装载因子会增加冲突发生的可能性。 2. 哈希表的实现方式哈希表的常用实现方式主要有两种： 开放寻址法：在发生冲突时，通过寻找其他空闲位置来存储元素。常见的开放寻址方法包括线性探测、二次探测和双重哈希。 链地址法（拉链法）：在每个哈希表位置存储一个链表，在发生冲突时将新元素插入到链表中。 3. 哈希表的 C++ 实现使用链地址法（拉链法）的 C++...
栈与队列
1. 栈的基本概念与操作栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构，最后插入的元素最先被删除。 栈的基本操作 初始化：创建一个空栈。 入栈（Push）：将一个元素压入栈顶。 出栈（Pop）：从栈顶删除一个元素。 取栈顶元素（Top）：获取栈顶元素的值，但不删除它。 判断是否为空：检查栈是否为空。 2. 队列的基本概念与操作队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构，最先插入的元素最先被删除。 队列的基本操作 初始化：创建一个空队列。 入队（Enqueue）：将一个元素加入到队尾。 出队（Dequeue）：从队头删除一个元素。 取队头元素（Front）：获取队头元素的值，但不删除它。 判断是否为空：检查队列是否为空。 3. 栈的顺序存储结构栈的顺序存储结构通常使用数组实现，栈顶指针 top 用于指向栈顶元素。 栈的顺序存储结构的 C++...
线性表
线性表线性表是一种数据结构，表示由同一类型的元素按顺序排列的有限集合。线性表中的元素有顺序关系，可以通过顺序号访问。它是最常用的结构之一，常用于实现数据的顺序存储和查找操作。 线性表的定义一个线性表 $( L )$ 可以定义为一个具有相同类型的元素集合，其中第一个元素为 $( a_1 )$，第二个元素为 $( a_2 )$，依次排列，直到第 $( n )$ 个元素 $( a_n )$。线性表的长度是元素的个数，当长度为 0 时，称其为空表。 在数学上可以表示为：$[ L = { a_1, a_2, \dots, a_n }...
CCSP2024 赛后回忆
CCSP2024 赛后回忆这次是在浙江金华的浙江师范大学，虽然说这里可能有一点点偏僻，但是店铺什么的基本都有，奶茶店，肯德基什么的甚至开在了校内。 这应该是我大学最后一次参加国家级的赛事了吧。 题目I/O 任务调度队列按来的时间排个序，奇数放第一个队列，偶数放第二个队列，保证每个任务等待的时间最小就可以了，签到题。 12345678910111213141516171819202122232425262728293031323334353637#include<bits/stdc++.h>using namespace std;const int mxlen = 1e3+5;int t[mxlen];int n;int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T = 1; while(T--){ cin>>n; for(int i=1;i<=n;i++){ ...
HDU 4870 概率DP
HDU 4870 概率DPProblem Link 题意新账号打rank，rank从0开始，打到1000分结束。每场rank增加50的概率为p，否则rank-100。新人用两个信号去打，每次用rank值低的账号，问任意一个账号达到rank1000分，新人要打的期望场数。 解答参考博客 将分数离散为赢了加1分，输了减2分。用dp[i]表示从i-1分到i分需要打的期望场数。 每次比赛有两种情况，一是p概率赢了加1分，二是(1-p)概率输了减2分。 dp[i]=1*p+(1-p)(1+dp[i-2]+dp[i-1]+dp[i]) 期望等于所有情况乘以概率的和。 一场就赢了，则是1*p 一场输了，则需要(1+dp[i-2]+dp[i-1]+dp[i])场才能赢回来。其中1是输了这场，然后从i-3打到i-2,从i-2打到i-1，从i-1打到i分。 化简得 dp[i]=(1+(1-p)*(dp[i-2]+dp[i-1]))/p dp[1] = 1/p, dp[2] =...
HDU 1024 M子段和最大
M子段和最大问题Problem Link Given an array and divide into m sequences. One sequences at least has one number and the sequences can’t contain the number with same index. And the index of the numbers in one sequence should be continuous. Notice that we don’t have to use all the numbers. N between 1 to 1e6. SOLUTIONDynamic programming. Let d[i][j] denote the maximum sum of the current array that is divided into i segments and the last segment ends with the jth number. When comes to the jth number,...
HDU 1029 寻找数列主元素
寻找数列主元素Problem link Finding a integer that appears at least (N+1)/2 times in the array. 摩尔投票法The Boyer-Moore Voting Algorithm (Moore’s Voting Algorithm) is a highly efficient method to find the majority element in a sequence (an element that appears more than half the time). It operates in O(n) time and uses O(1) space. Key Idea:The algorithm works by maintaining a candidate for the majority element and a counter to track its occurrences. It leverages a “pairing” or “cancellation” mechanism...
HDU 1465 (错位排列问题)
Derangement Problemproblem link Problem DescriptionYou have n letters, each with a different recipient. However, all the letters are delivered to the wrong recipients, meaning no one receives the letter intended for them. You need to determine how many possible ways this can happen. This problem can be simplified to a case where you have an array of numbers from 1 to n. For each position in the array(starting from index 1), the number in that position is different from its index. The goal is...
Notes of Lecture 23: Computational Complexity
Notes of Lecture 23: Computational Complexityvideo link P,EXP,RP = {problems solvable in at most(<=) polynomial time} EXP = {problems solvable in exponential(2^$n^c$) time} R = {problems solvable in finite time} The axis is computational difficulty. Most problems uncomputableExamples: negative-weight cycle detection (P) NxN Chess (EXP&!P) Tetris (EXP, don’t know whether is P) halting problem: given program, does it ever halt/stop? (not in R) Most decision problems are uncomputable...
HDU 1085 multiple knapsack problem
Multiple Knapsack Problemproblem link The Meaning of the problemYou have three kinds of coins. Their face values are 1,2 and 5. Of cause you only have a limited number of coins. You need to find the minimum value that you can’t represent exactly with these coins. SolutionThere are lots of people solve this problem using Generating function. That way is too hard to understand. We just need to think of this problem as a multiple knapsack problem. I learned from this blog dp[j] = 1 means that...
HDU 1025 longest increasing subsequence
Constructing Roads In JGShining’s Kingdomproblem link The meaning of the problemSo why this is longest increasing subsequence Problem ? Look at the picture below: As the problem described, we can’t have crossed lines. Each line has two endpoints. One is the “rich” endpoint above and the other is the “poor” endpoint below. The rich endpoints’ number of the lines we finally pick up should be monotonically increasing. The corresponding poor endpoints should be monotonically increasing too....
HDU 1023 Train Problem II 高精度卡特兰数
High-precision Catalan numberproblem link This is a classic problem of finding the number of stack push ans pop sequences. The only headache is that it requires high precision. How to determine whether it is a Catalan numberFor a more detailed introduction to the Catalan number,see oi-wiki and wikipedia I think there is another simple way to judge, which is to see whether the first few numbers are consistent with the Catalan number. If they are the same, then it is likely to be a correct...
HDOJ 1010 Tempter of the Bone 深搜&剪枝
细心和智慧并存的解答题目链接 题的大致意思是能不能从起点经过T时间精准到达终点，图中有一些障碍不能走，走过的格子也不能再走。 其中数据是最大7*7的迷宫，最多50个迷宫。 智慧之处——精准的剪枝类似全排列的深搜时间复杂度是O(n!)，7*7的数据是过不去的。 首先就是普通地剪枝： 如果时间已经大于T，就不用再走了 如果已经有正确答案，要及时地退出搜索 然后是奇偶剪枝，这里参考了其他博客 这里我重新画了一张图，如下： 图中的S可以代表任何你走到的位置，不一定是起点。就如图中的红色和蓝色路径，这两条路径是最少需要的时间。如果剩余时间少于最短路径长度，那么是一定不能到达终点的。 既然时间不够一定不能到达，时间刚好和剩余最少时间相等也能到达，那么还剩一种情况，就是时间大于剩余最少时间。这也应该是大概率会遇到的情况。根据题意我们只能在第T秒精准到达终点，我们时间多出来的怎么办呢？——我们需要在终点周围“徘徊”。 如图中的绿色和黄色箭头所示，你比最短路径多走出来的路径，一定是先“出去”，再“回来”。多走的路径是“对称的”，那多出来的路径长度一定是偶数。 ...
HDOJ 1007 Quoit Design 圆环设计
一道经典的分治题目链接 题意是套圈游戏要设计一款尺寸最大的圆环，满足圆环不会一次套中两个物品。每个物品有一个摆放坐标。我们要求的是这些物品中相邻最近的两个物品之间的距离，这个距离就是我们要求的圆环的直径。 这个类型网上常称为寻找最近点对问题。 ...
更有效地解决括号匹配问题
这是力扣上一道非常简单的问题，是经典的解决括号匹配问题。当然做法是用一个栈即可解决问题。有效的括号 这是我的代码：123456789101112131415161718192021222324class Solution { public boolean isValid(String s) { Stack<Character> st = new Stack(); boolean flag = true; for(int i=0;i<s.length();i++){ Character nowC = s.charAt(i); if(nowC=='('||nowC=='{'||nowC=='['){ st.push(nowC); }else { ...
博客的免费图床方案
博客的免费图床方案（Cloudflare R2 + PicGo）参考博客 这个博客写的已经非常详细清楚了，这里不再赘述实现步骤。 这里记录一下我是怎么发现这篇博客的。 在一个很无聊的时间段，我打开了Inoreader看RSS订阅的博客列表有没有更新，其中有一篇少数派的博客吸引了我，是这个博客。 这里博主提到了他的推特账号。其中很近的时间里他发布了上面提到的免费图床方案的博文。 这篇博客解决了我正在苦恼的问题，那就是博文中图片的插入。如果是只有一个github pages的静态网站还好说，直接传在相对文件夹里即可。但是如果面对多平台，比如我还想在csdn中发布，那就变得很麻烦，因为markdown里写的相对路径将不可用，最直接的办法就是更改每个图片链接。 然而如果是有自己的图床就很方便了，不用担心网络上的图片会突然失效，多平台发布也不用更改自己的截图路径。上方的图片就是用我自己实现的图库。 ...
Eloquent JavaScript 09 Exercises
正则表达式To the book page Regexp golf注意这里如果写对的话，应该什么都不会输出。 正则表达式中的\b是单词边界的标志，它用来匹配一个单词的边界。 123456789101112131415161718192021222324252627282930313233343536373839404142// Fill in the regular expressions// 正则表达式应该匹配“car”和“cat”，但不匹配其他字符串。verify(/ca[rt]/, ["my car", "bad cats"], ["camper", "high art"]);// 正则表达式应该匹配“pop”和“prop”，但不匹配其他字符串。verify(/pr?op/, ["pop culture", "mad props"], ["plop",...
