ChrisPang 的博客

摘要： 前言 题目传送门。 左偏树就是可并堆的一种。 顾名思义，就是左边比较长的一种树（即左儿子到叶节点的链比右儿子到叶节点的链长） 左偏树是一种特殊的堆数据结构。它不严格遵守堆的定义，比如可以不是一棵完全二叉树。但满足堆的其他各种性质： \(O(1)\) 时间求最优值 \(O(\log n)\) 插入、删 阅读全文

摘要： 前言 请问一下，\(\textup{Link-Cut Tree}\) 与李超树不是同一个东西吗？它们好像都是 \(\textup{LCT}\)，那应该没区别吧（迷雾） 当然今天讲的不是大名鼎鼎的 \(\textup{Link-Cut Tree}\)，不过名气与它也差不多。OK，废话不多说，开始进入我 阅读全文

摘要： 题目传送门。 题目大意 给定一个包含 \(n\) 个结点的树，一个消防站能够覆盖与他距离小于 \(2\) 的点。 要求每个结点都能被覆盖到，问至少需要多少个消防站。 \(1\le n\le 10^3\)。 题目分析 由于以前做个一个要求距离为 \(1\) 的版本，因此场上推了 \(60+\) 行，到 阅读全文

摘要： 前言 感觉这次 CSP 打的还可以，达到超过分数线 \(10\) 分的目标了。希望复赛也能拿到可观的分数。 当然，You have no egg!。 考前三天 考前三天。一到机房就和 yanzixuan2024 它们打术士，真不错。 考前两天 下午 4:00，竞赛生颁奖啦！ 然而这个蒟蒻只有三等奖. 阅读全文

摘要： 本文在洛谷专栏中进行审核且通过，大家点个赞支持一下吧！ 最近学了些新算法，过来做下笔记，以免以后忘了。 前置知识 Tarjan 算法的时间复杂度为 \(O(n + m)\)。 在除了求最近公共祖先的 Tarjan 算法里，都会用到两个数组和一个概念，在这里写清楚一点，以免后面讲得云里雾里。 对图深搜 阅读全文

摘要： 题目传送门 说明 “哞林匹克”运动会中的一大亮点就是滑雪比赛。滑雪比赛的场地是一个 \(n \times m\) 的矩阵（\(1<=n,m<=500\)），每一个点有对应的海拔(海拔均在 \(0\) 到 \(10^9\) 的范围内)。 主板方指定了若干个点作为路标。同时，主办方还要规定一个比赛系数 阅读全文

摘要： 每次找到最高点，进行 BFS 染色，每次染色之后答案 \(+1\) 就可以了 #include <bits/stdc++.h> #define int long long using namespace std; int n, m, k, ans; char a[55][55]; //地图 bool 阅读全文

摘要： 思路 当一个数是完全平方数的时候，它的所有质因子的次数都是偶数。 记 \(x\) 的质因子为 \(p_1^{q1} \times p_2^{q2} \times p_3^{q3} ... \times p_v^{qv}\)。这些数可以通过次数的奇偶性用一个 \(v\) 位的二进制串 \(B\) 表示 阅读全文

摘要： 本题其实是一个 \(01\) 背包的板子题，除了题目背景不同以外，其它的都一模一样！ \(1\)、状态： 定义一个二维数组 f，\(f_{i\ j}\)表示前 \(i\) 种采药，时间为 \(j\) 时可以获得的最大价值。 \(2\)、状态转移方程： 我们设当前时间为 \(j\) 采完这个草药需要的 阅读全文