Yuzhen's Blog

Yuzhen Qin

最新文章

2024 青岛中考游记

抽象。
36
0
0
2024-06-17

数据结构 #2:替罪羊树

这篇文章介绍了替罪羊树的数据结构及实现。替罪羊树是一种平衡二叉搜索树,当发现某个子树不平衡时,通过中序遍历拉平该子树并重建新的二叉搜索树,保证树的整体平衡。文章还提供了相关的代码模板。
10
0
0
2024-06-18

数据结构 #1:二叉搜索树

这篇文章介绍了二叉搜索树这种数据结构,它是一种特殊的二叉树,具有特定的性质:左子树上所有点的值小于根节点,右子树上所有点的值大于根节点,且左右子树本身也是二叉搜索树。文章还提到了在理想情况下,二叉搜索树能以对数时间复杂度O(logn)完成插入、删除、查询排名、查询指定排名的数、求前驱和后继等操作。
4
0
0
2024-06-18

题解:P10449 费解的开关

这篇文章介绍了如何使用 C++ 中的 std::bitset 和 DFS 搜索算法解决一个特定的逻辑问题,该问题涉及对多个灯进行开关操作以达到所有灯亮起的目标。文章首先预处理了按下一个开关所影响的所有灯的状态变化,然后使用 DFS 遍历所有可能的开关组合,通过按位异或操作更新灯的状态。在搜索过程中,利用 std::bitset 的 count() 函数来计数亮着的灯的数量,当计数达到 25,即表示所有灯都已亮起,解决问题。
4
0
0
2024-06-17

题解:P10447 最短 Hamilton 路径

这篇文章介绍了最短Hamilton路径的问题,即在n个点的带权无向图中,寻找起点0到终点n-1的最短Hamilton路径。Hamilton路径的定义是恰好经过每个点一次。文章提到了暴力搜索的时间复杂度为O(n!),会爆炸,因此考虑使用状压DP(动态规划)来解决问题。dp[i][j]表示目前在j号点,访问过的点的方案为i的最小费用,其中i是一个2^n的状态。通过枚举起点、终点和当前状态,并注意边界和限制,如当前状态是否与枚举的点冲突(起点没来过或者终点去过),可以找到最短Hamilton路径。
5
0
0
2024-06-17

题解:P10466 邻值查找

这篇文章介绍了算法题 P10466 邻值查找的题意、做法和完整代码。题目给定一个长度为 n 的序列 A,A 中的数各不相同。对于 A 中的每一个数 Ai,需要求出满足条件的最小绝对值差和对应的 j 值,即 min{|Ai - Aj|},以及使 |Ai - Aj| 取到最小值时,Aj 的前驱和后继。可以使用 std::set 和 std::map 数据结构来存储序列和查询前驱后继。
9
0
0
2024-06-17

题解:P10473 表达式计算4

这篇文章介绍了Python三行代码解决P10473表达式计算4问题。利用字符串替换乘方和除法符号,计算左右括号数量差,通过在字符串末尾添加相应括号实现完整表达式,最后利用eval()函数求值。
10
0
0
2024-06-17

题解:P10480 可达性统计

这篇文章介绍了算法题解:P10480 可达性统计。题目要求给定一张有向无环图,统计从每个点出发能够到达的点的数量。文章提供了完整的代码,使用了深度优先搜索(DFS)算法,并用 `std::bitset` 记录访问状态,最终通过 `bitset::count()` 方法统计每个点可达的点的数量。图的规模为 1≤N,M≤30,000。
7
0
0
2024-06-17

题解:P5763 [NOI1999] 内存分配

这篇文章介绍了NOI1999内存分配问题。题目有N个内存单元,1≤10^4个进程,每个进程有三个整数T,M,P,分别表示申请内存的时刻、长度和占用内存的时间,数据已按T从小到大排序。进程的T,M,P<10^9。进程申请内存时,如果当前存在长度为M的空内存,就分配给它,否则放入等待队列。输出全部进程运行完毕的时刻和被放入过等待队列的进程总数。题目中有两种操作:分配内存操作和释放内存操作。我们可以使用一个std::set来维护内存,使用一个堆(std::priority_queue)来维护内存释放的信息。需要写一个函数void release(int t),代表释放时刻≤T时应该释放的内存。在main函数中,需要注意插入内存边界等待所有内存分配请求处理完之后,应该把所有进程运行结束。
10
0
0
2024-06-17

C++/STL 笔记 #1: 伪随机数生成和计时

这篇文章介绍了C++中伪随机数生成和计时的相关知识。首先,文章讲解了C风格的std::rand函数以及C++11中的随机数生成设施,如std::random_device、std::mt19937和std::mt19937_64。然后,文章介绍了计时方法,包括C风格的std::clock、chrono库中的系统时钟、单调时钟和高分辨率时钟,以及如何使用chrono::duration来存储和转换时间单位。
29
0
0
2024-05-28
阅读更多