之前不是很懂我们现在再来了解一下。 三元环首先考虑我们暴力就是枚举一个点之后枚举边看一下是否相连。 那么我们可以考虑枚举一条边 $(u, v)$ 再枚举 $v$ 的出边看一下是否能连接到 $u$，我们只要预先对于 $u$ 的出边打标记就可以了，复杂度是 $O(m ^ 2)$ 的。 但是事实上，三元环是没有方向的，甚至于对于三元环 $(a, b, c)$ 其任意的排列都是同一个三元环。 所以我们考虑对于边能否进行定向，考虑进行根号分治，让每个点的度数尽量小。所以我们让出边少的连接到出边多的点上。 我们还是枚举点，最外层的循环就是 $O(m)$，考虑如果当前的点度数为 $d$，其出边肯定是到比 $d$ 大的点上，最多是 $\frac{m}{d}$ 。 对于度数 $< \sqrt m$ 的点，其出边可以到达 $O(\sqrt m)$ 最多有 $O(m)$ 个。 对于度数 $> \sqrt m$ 的点，其点的个数总共只有 $\sqrt m$ 个。 所以综上复杂度是 $O(m \sqrt m)$。 1234567891011121314151617for(int i = ...

fe45d12ef140a30fdc0b661d0183268497364965149bb64f701b0a9e7f041d60ec8c084ec5ac579309d23eb390b2804b8a0efebc658d7791914eb7f24782ab4a3926a8bea64f4c6a908835726bfbda5141540ca06db4da19435d8bbf5386905224847cd8eb9cee49701ffba963b3c291f7c32ac42c5a87515b437e08ab3c66a797a601e004d39e965f468768b9f3441e61e07f95c33bec822c352662400d30ea4f6c57d8d4ed64cca54fbc7a72ec762ce170e6c5968be88c07865e35eb5a452ceefc8f081eda12f12c33793d4932b3585372c43d74afbb7ffe1107bc2e36a58d26772f765e454c1da75c0b95b7523f8da826ded8ff579902d ...

【清华集训2014】玄学 - 题目 - Universal Online Judge (uoj.ac) 首先暴力很明显，要么是模拟，要么直接树套树来搞。 考虑我们必须要维护时间轴，我们考虑对于区间能否进行一些操作。 考虑区间 $[l, r]$ 我们将其考虑一个位置 $pos$ 能取到什么，因为该操作在 $[1, l-1], [l, r], [r+1,n]$ 的贡献本质是一样的，我们考虑将区间的右端点作为代表点，查询的时候直接二分一个最接近的右端点即可。 这样我们发现我们只需要在叶子节点进行上述操作，但是区间查询呢？ 我们考虑二进制分组的思想，考虑对于两个时间 $a, b, a < b$ 如果说当前满足 $a$ 肯定满足 $b$，我们考虑通过这种情况进行归并即可。 插入的复杂度是 $O(\log n)$ 的，查询是 $O(\log^2 n)$ 的。 话说之后还要学习一下二进制分组。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 ...

考虑题目要求我们求： $$R(v) = \sum_{s \ne v \ne t} \frac{a_sa_t sd_{s, t}(v)}{sd(s, t)}$$ 考虑将上面的东西拆掉得到： $$R(v) = \sum_{s \ne v \ne t} \frac{a_sa_tsd(s, v)sd(v, t)}{sd(s, t)}$$ 考虑枚举开始点 $s$ 可以得到关于 $s$ 的式子： $$R(v) = \sum_{s} a_s \sum_{s \ne v \ne t} \frac{a_tsd(s,v)sd(v, t)}{sd(s, t)}$$ 发现 $n$ 事实上可以让我们跑一遍全源最短路，那么本质上每一条最短路的宽度都是可以处理出来的。 那么我们考虑从后向前进行递推，那么我们的 $t$ 就是结束位置，显然最短路构成的肯定是一个 $DAG$。 设 $f(v) = \sum_t \frac{a_t sd(v, t)}{sd(s,t)}$，剩下的 $sd(s, v)$ 考虑在计算答案的时候乘上。 那么 $f$ 的转移比较显然，考虑加入一个点的时候肯定 ...

P1186 玛丽卡 - 洛谷 容易想到一个很明显的做法，就是考虑随便找出一条最短路，之后考虑删除掉任意一条边，再进行计算，答案取最大值。 但是这个复杂度明显是有问题的，我们考虑这个过程我们在干什么。 本质上就是对一条路径进行更新，或者说考虑对于 $A\to B \to C \to D \to E$ 的路径，我们删除掉 $(B, C)$，让路径变成 $A \to B \to X \to Y \to C \to D \to E$，这样更新。 我们思考，我们本质在做的就是在删掉一条边的时候，尝试求次短路，那么我们可以考虑对于每条不是最短路里的边分别进行更新，考虑求出从 $1 \to n$ 和 $n \to 1$ 的两个数组分别为 $d_1, d_n$ 那么我们可以通过 $d_1 + d_n + w$ 进行更新一段路径。 对于我们当前找到的点对 $(u, v)$ 我们考虑其最优的肯定是通过最短路算法得出的路径，我们设 $pre(i)$ 表示点 $i$ 在最短路算法中得到的前驱，那么我们 $(u, v)$ 进行的更新本质上就是对于 $u, v$ 分别考虑，一直跳 $\tt pre$ 直到和最短路 ...

下面有配套练习： ‘ LCS - Longest Common Substring - 洛谷 LCS2 - Longest Common Substring II - 洛谷 [TJOI2015]弦论 - 洛谷 NSUBSTR - Substrings - 洛谷 [AHOI2013]差异 - 洛谷 【模板】广义后缀自动机（广义 SAM） - 洛谷 [HAOI2016]找相同字符 - 洛谷 Forensic Examination - 洛谷 [ZJOI2015]诸神眷顾的幻想乡 - 洛谷

P4511 [CTSC2015]日程管理 - 洛谷 首先考虑对于第 $i$ 天，一开始在这之前肯定是可以放 $i$ 个任务的。 我们考虑当我们放了一个任务在天数 $t$ 的时候，$[t, T]$ 的可以放的任务数量肯定 $-1$。 我们考虑对于加入一个 $t$ 如果后面存在一个位置是不能放了，也就是可以放的任务数量是 $0$ 的情况，我们才需要考虑对于之前的位置进行取出判断。 显然这个东西是一个区间加的操作，我们考虑使用线段树进行维护。 考虑到我们每个点是可以撤销的，我们考虑对于加入和没有加入的集合分别进行维护即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151 ...

具体语法就是： 1<embed src="pdf-link" type="application/pdf" style="overflow: auto; width: 100%; height: 600px"/>' 其中 $\tt pdf-link$ 表示的是路径，最好是相对路径。 比如说我的文件都存在 $\tt image$ 里面，所以我的相对路径就是 /image/xxx.pdf。 然后后面的部分就是调整大小，$\tt px$ 就是表示像素。 上面的那个就是笔者博客比较适合的情况。