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$ 就是表示像素。 上面的那个就是笔者博客比较适合的情况。

Problem - 1603E - Codeforces 找找性质的好玩题。 首先考虑顺序对于题目的要求是没有关系的 对于一个排好序的序列，如果其符合条件那么其排列也肯定符合条件。 考虑对于这个排好序的序列进行操作，可以得到如果这个序列的每一个前缀都符合条件那么这个序列肯定符合条件。 既然是排好序了我们考虑对于每一个数是否有限制，限制肯定是存在的，如何找到呢？ 明显发现对于 ${1, 1,1, 1, 1}$ 是不符合条件的，考虑 $\sum_{i = 1} ^ n a_i \le a_1 \times a_n$ 的限制。 $$\begin{aligned}\sum_{i = 1} ^ n (a_i - a_1) \le a_1 \times (a_n - n) \\\end{aligned}$$ 当 $a_n = n$ 时，$\forall i \le n, a_i = i$。 $a_n \ge n$。 我们考虑 $a_n \ge n+ 1$ 的情况，考虑边界 $a_n = n+ 1$，同样是上面的式子可以得到 $\su ...