置顶
什么？你也玩原神！？
2023-09-07 3.2k 字 10 分钟

什么？你也玩原神！？

困至极点 故作此文 以振精神 引言 我有一个惊为天人的特性，很多人都有，但是他们都没有发现过。然而就在今天，我，发现了！每个人都是由许许多多的原子构成的。这样好呀！我是由原子构成的！好耶好耶！咳咳，既然这样，我们就是有正电荷的生物。那么为什么我们对外不显电性呢？上过幼儿园的小朋友们应该都知道，原子核外有电子，电子带负电荷，正电荷吸引着负电荷围着它转，又或者两个原子之间有公共电子，这样整个环境就会成电中性，我们也就不带电。 但是！重点来了！ 首先说一些前置芝士： 电流是电子在导体中做定向移动产生的； 石墨的导电原理是其平面六边形结构可以使得一个电子在原子之间移动，去替换本身原子周
Tarjan 基础用法
2023-09-07 5k 字 22 分钟

Tarjan 基础用法

求最近公共祖先 前置芝士 ** 最近公共祖先(Lowest Common Ancestor , LCA) **：一棵树中两个结点的 公共祖先里面，离根最远的那个被称为最近公共祖先。我们记点集 的最近公共祖先为 或 。 ** 性质 **： ； 是 的祖先当且仅当 ； 若 和 互相都不是对方的祖先，则 分别处于 的两棵不同子树中； 前序遍历， 出现在所有 中元素之前，后序遍历， 出现在所有 中元素之后； 两点集的并的最近公共祖先为两点集各自最近公共祖先的最近公共祖先，即； 两结点的最近公共祖先一定在其这两点最短路上 设 为树上两点间的距离
最短路径基础总结
2023-09-07 3.4k 字 14 分钟

最短路径基础总结

（全源最短路） 我们定义一个数组 表示只经过节点 ~ 的情况下， 到 的最短路长度，那么显然的，当一个图中节点个数为 时， 就是我们所要求的答案。实现 算法需要我们从 时的情况逐渐递推到 。 时， 和 ​ 不相等的情况下不可能通过任何情况联通，而一个点到自己的距离显然为 ，所以我们认为： 于是我们就得到了递推式的第一项，我们考虑动态规划。对于每一个点，我都有两种选择：第一种是经过这个点，即 ；而第二种是不经过这个点，即 。我们寻找最短路时只要判断经过当前的点的代价和不经过当前点的代价哪个更小就可以了，所以 都从 开始枚举一遍就可以得出答案，下面是具
题解 CF1413D Shurikens
2023-08-18 708 字 2 分钟

题解 CF1413D Shurikens

题解 CF1413D Shurikens 简要题意 给定一个 和 个操作，第一种操作 "+" 表示从 ~ 中选择一个数插入序列，第二种操作 " - " 表示从当前序列中删除 且 为当前序列里的最小值，根据给出的操作来推断将数插入序列的合法顺序。 策略分析 不合法情况 不合法的情况有两种。第一种是当在连续取出的两个值中，后取出的值比前取出的值小，因为每次必须取出序列里最小的值，所以这种情况显然是不符合要求的。第二种情况是取出的操作数比放入的操作数多，这样显然也是不合法的。 如何处理合法情况 我们看到这种有进有出的结构能够想到什么，怎么才能反转操作呢？我们很自然地想到
题解 洛谷 CF958E1 Guard Duty (easy)
2023-08-18 257 字 1 分钟

题解 洛谷 CF958E1 Guard Duty (easy)

题解 CF958E1 Guard Duty (easy) 这是一道诈骗题 简要题意 给你 个 点和 个 点，现在给你这些点的坐标，问能否在这两类点间连线来构造出一种情况使得一个线段两边分别是 和 。 策略分析 不合法情况 当 时，我们顺次连接 和 ，先不考虑相交不相交，发现连到最后要么 和 相连，要么 和 相连，一定不合法。 合法情况 当 时，答案一定合法 正确性证明 我们设有点 ，那么我们加上边 ，发现相交了，如下图： 但我们发现，当这种相交情况出现时，我们只需要改连边 ，就一定能变成不相交的情况，如下图： 于是我们做完了，下
题解 洛谷 P3514 [POI2011] LIZ-Lollipop
2023-08-18 846 字 3 分钟

题解 洛谷 P3514 [POI2011] LIZ-Lollipop

P3514 [POI2011] LIZ-Lollipop 简要题意 给定一个只有 和 的序列，给出 次询问，每次询问给出一个数 ，查询序列中有没有一个子串和为 ，如果有则输出区间两端点，如果没有输出 NIE。 策略分析 本题最重要的条件就是该序列中只含有 和 ，因为这个条件，我们就可以得到下面这个性质：若 可以被表示，则 也一定可以被表示。这个性质很容易被证明。我们很容易发现，一个区间的两端点有三种情况，全为 ，全为 以及一边 一边 。那么当两边存在 时，只需要减掉这个 即可；如果是两个 ，那么把这两个 一起减掉即可。 现在我们知道了上面这个性质，开始考
题解 BNDS OJ 1575 哈夫曼
2023-08-18 741 字 3 分钟

题解 BNDS OJ 1575 哈夫曼

题解 BNDS OJ 1575 哈夫曼 前置芝士： 哈夫曼树 简要题意： 给定一个仅包含小写字母的字符序列，要求输出这个序列的哈夫曼编码 分析/求解： 哈夫曼建树时要求每次配对权值最小的两个儿子，它们配对所产生的父亲也要重新与其它的树进行比较，所以我们很容易可以想到通过优先队列来维护当前所有的树，具体细节见代码 AC代码： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
题解 洛谷 P1045 [NOIP2003 普及组] 麦森数
2023-08-18 488 字 2 分钟

题解 洛谷 P1045 [NOIP2003 普及组] 麦森数

题解 洛谷 P1045 [NOIP2003 普及组] 麦森数 简要题意： 给定一个数，求-1的位数和后500位的值，其中。 策略分析： 我们可以将这个问题分为两步来处理，第一步求出位数，第二步求后位 ### 求出位数： 首先有一个非常平凡的结论：的位数为。那么一个的数的位数也等于，设，因为不存在最后一位为的的数，所以的位数一定与的位数相同。我们希望能够将所具有的性质应用在中，设，那么，所以，所以，那么的位数就等于的位数，即，那这不就简单多了，直接库里随便一搞就出来了 求后500位的值： 我们发现一个朴素的高精度乘法的时间复杂度是，那么就寄了，所以我们要用超级快速的高精乘法，C+
题解 AT_arc132_a Permutation Grid
2023-08-18 352 字 1 分钟

题解 AT_arc132_a Permutation Grid

题解 AT_arc132_a Permutation Grid 简要题意： 给定两个数列 和 ， 和 内均有 个元素，要求根据 和 对一个 的矩阵进行染色，使得第 行有 个黑色块，第 列有 个黑色块。最后， 和 均为 的一个排列。 反思分析： 有个伸臂和一个神犇在赛时没有看到最后一个条件导致两个人想出了各种各样复杂又奇葩的做法，我不说是谁 有了排列那这不成水题了，我们以样例为例（这什么话）把它按顺序重新排列一下，就会变成这样（我们用表示白色，表示黑色）： $ $ 我们稍加观察，然后惊奇地发现，坐标为的块是黑色当且仅当，然后我们恢复原序列
题解 洛谷 U327217 寻找千泷の小翼龙
2023-08-18 868 字 4 分钟

题解 洛谷 U327217 寻找千泷の小翼龙

题解 洛谷 U327217 寻找千泷の小翼龙 本题题面 原题（本题由该题数据加强而来）： USACO Training 6.1.1 Postal Vans Tiring of their idyllic fields, the cows have moved to a new suburb. The suburb is a rectangular grid of streets with a post office at its Northwest corner. It has four avenues running East-West and streets runnin