6.824 Lab1 MapReduce

前前后后做了15个小时, 看到PASSED ALL 30 TESTING TRIALS的那一刻, 太爽!

概述

这个实验要求实现经典论文MapReduce的模型。MapReduce在Google内部是跑在一个服务器集群里的, 这些服务器共享一个分布式文件系统GFS。这个实验只要求实现运行在本机多个进程上的、本地文件系统上的MapReduce模型, 省去了与分布式文件系统的交互 (要做负载均衡这个很重要, 而且应该很麻烦) 。

实现过程流水账

先读论文花了3h左右, 内心活动: 这论文真简单。

然后开始实现。我并不会go语言, 官网那个tour我也就做了一点点, 事实证明全做完比较省时间。第一次写的代码全是if-else, 我还没有加入容错机制的时候代码已经复杂到我读不懂了。内心活动: 工业界实现这玩意的人是神仙吧! 然后我把3个小时码的200多行代码全都回滚掉了:-(

第二次写代码之前, 我决定写一个类似于有限状态自动机的东西。事实证明这个模型还不错, 让我的思路变得比较清晰, 并且便于拓展。然后花了2h画图+搭框架, 就是只写了一堆switch-case, 每种状态对应的转移和转移前需要进行的操作的注释。然后就头晕, 下班了。

今天是第三次碰这个东西, 今天如果再自闭我可能就要对这实验产生心理阴影了。好在我上次的DFA没啥大问题, 只是有些corner case没想到, 缝缝补补搞了一段时间。终于把注释转换成了代码, 最戏剧性的一刻来了: 开码10小时后我终于进行了第一次编译! 我以为会得到巨长无比的报错, 结果报错就八九行。然后就是改完一行错再出现一行错, 改完 “最后一行” 错之后又蹦出来十几个错误, 改了若干年……通过编译之后, 他在起始状态就出错了……然后又改了若干年, 终于输出了结果。

第一个教训: 把语言学明白, 勤编译勤测试。

我查看输出文件的前三行 (共两万行) , 发现与标准输出一样! 然后高兴地去跑测试脚本, 结果第一个正确性测试点就挂了……

第二个教训: 测试要认真严谨。

然后又改了若干年, 期间多次翻阅论文, 发现人家写进论文的东西都是经过取舍和迭代的, 还是非常精华的。后来就是无限改bug, 调试, 按下不表。终于在今天码代码的第8小时通过了所有测试!

做的不错的地方

  1. 画DFA
  2. 头脑不清楚的时候出门转转, 可以花掉长达20分钟的时间, 但是回来之后你就复活了!

想要做得更好的地方

  1. 阶段性编译、测试。例如我的DFA设计好了, 这时候就可以测试下转移有没有问题, 然后再在转移前后加功能。
  2. 有设计测试点的能力。对于这个实验, 我是用户, 而且一定程度上可以说是赶时间, 所以用老师的脚本来测试、调试没有什么错。但是一旦成为真正意义上的开发者, bug都要自己找 (不提开源社区之类) , 需要有能力设计若干测试来检验自己的代码在各方面的正确性/性能。这确实需要写一些 “没用的” 代码, 但是它们通常很简单, 而且很有用 (如算法竞赛里的对拍程序和暴力程序) 。例如, 我尽管知道各个操作的时间/空间复杂度, 但还是不知道我这个实现并发性如何, 究竟有多少CPU时间是overhead。
  3. 证明我的DFA的正确性
  4. Challenge
  5. 阅读老师的测试脚本, 学习写脚本

CF Edu123 题解

F. Basis

题面

考虑一群在操作 2 下可以互相变换的数组, 在其中可以取一个代表元$arr$。假设$arr$$i$种数字组成, 把$arr$中数字$j$所在的下标的集合记作$S_j$, 则这一群数组可以用集合的集合$\{S_1,S_2,...,S_i\}$来表示, 称为一个原型。如果只能做操作2, 答案就是第二类斯特林数$\left\{n\atop i\right\}$的前缀和 (对$i$从1加到$\min(k,n)$) 。出于后面的实现方便, 将对$i$从2加到$\min(k,n)$的前缀和记作$A(n)$。这可以用$O(n\log n)$的复杂度来求, 具体见oi-wiki

接下来考虑操作1。我们发现刚才找到的那些代表元当中有些可以经操作1生成, 现在来删除它们。将原型$arr$改写成连续的相同数个数的数组的形式, 记作$arr'$, 例如将$1,1,2,2,3$改写成$2,2,1$

  1. 如果$arr'$只有一个数, 就是说$arr$中全都是相同的数字, 我们发现$arr$一定可以由某个改写前有至少两个不同数的原型经一次操作1: $F(a, n)$生成, 于是不用对$arr$计数。也就是说, 题目中给的$k>1$时, 不用考虑这种情况。如果$k=1$, 输出1即可。
  2. 如果$arr'$不只有一个数, 去掉$arr'$的最后一个数, 考察前面的那些数。如果它们的$gcd$不为1, 则$arr$可以被别的原型由操作1生成, 不用对$arr$计数。对一个$gcd$, 有$A(\lceil {n\over gcd}\rceil)$个原型可以被别的原型$a$生成 (将$arr$中每连续$gcd$个数绑定, 再计算原型数, 也就是$A(\lceil {n\over gcd}\rceil)$) (注意$A$是从2开始加的, 因为数字全部相同的原型并不能由操作1生成$arr$) 。如果这个$gcd$是合数, 可能这些冗余数组会被它的因子删除多次, 需要控制这个次数, 解决方法是用mobius函数。就是说: 对$gcd$, 我们计$\mu(gcd)$$A(\lceil {n\over gcd}\rceil)$

这里的mobius函数就是在对$gcd$的质因子集合$S$做容斥: 质因子集合$S$的子集$S'\subset S$可以与那些各质因子至多出现一次的$gcd$的因子建立一一映射, 一个子集中有奇数个因子就取$-1$, 偶数个因子就取$1$, 有质因子出现2次就取0。子集为空集时 (对应于因子1) 也取1。

对一个给定的$gcd$, 那些能经操作1: $F(a, gcd)$生成的原型, 也可以被$gcd$的因子$d$们经操作1: $F(F(a,d), gcd/d)$生成。每个这样的原型被计了多少次呢? 答案是

$$\sum_{d|gcd}\mu(d)=\sum_{S'\subset S}(-1)^{|S'|}=\sum_{i=0}^{|S|}\binom{|S|}{i}(-1)^{i}\times 1^{|S|-i}=(-1+1)^{|S|}=[gcd=1] $$

也就是实现了, 若$arr'$除去最后一块外的所有数互质, $arr$就属于, 否则不属于, 这结束了我们的讨论。关于$0^0$不等式和$[gcd=1]$的讨论可以和Trie树维护集合相交性相类比。最后的答案是:

$$\sum_{gcd=1}^n\mu(gcd)A\left(\left\lceil\dfrac{n}{gcd}\right\rceil\right) $$

直接整除分块求这个东西的一个上界是

$$O(\sum_{gcd=1}^n\dfrac{n\log n}{gcd})=O(n\log n\sum_{d=1}^n\dfrac{1}{d})=O(n\log^2 n) $$

注意不是$O(n\sqrt{n}\log n)$。我们还可以合并同一个$\left\lceil\dfrac{n}{gcd}\right\rceil$对应的所有$\mu(gcd)$之和, 前缀和或者开桶统计一下就行。这时, 由于后面那个求和只有其中的$\sqrt{n}$项, 可能还达不到$\log n$, 可以理解为常数很小的$\log n$ (经测试, 对$n=10^5$该和为6.83) 。

Trie树维护集合相交性

这篇文章讲一个 trick, 他可以解决如下问题:

维护一个结构, 可以添加和删除集合, 可以询问: 对询问中给定的新集合, 结构中有多少集合与之不交?

用这个 trick, 可以在 $O(2^{|S|})$ 的时间复杂度内添加或询问一个集合 $S$ , 所以在多个小集合的时候比较有用。

对两个集合 $A$$B$ , 考虑 $B$ 的所有子集, 维护一个计数器 $cnt$ 。对每个子集 $S$ , 如果它也是 $A$ 的子集, 为 $cnt$ 加上 $(-1)^{|S|}$

$$cnt=\sum_{S\subset (A\cap B)}(-1)^{|S|}=\sum_{i=0}^{|S|}\binom{|S|}{i}(-1)^i\times 1^{|S|-i}=(1-1)^{|S|} $$

$A\cap B=\emptyset$ 时形式上是$0^0$不定式, 根据定义式计算, 发现它有由空集贡献的 1 。于是 $cnt$ 就标志着 $A\cap B$ 是否为空: 为空时 $cnt=1$ , 否则 $cnt=0$

现在我们维护一个 Trie 树, 每个节点代表一个集合。当添加集合 $A$ 时, 给它的所有子集对应的节点权值加一。删除时, 就为所有子集对应的节点权值减一。可以注意到空集对应节点的权值就代表当前结构中维护的集合个数。

然后考虑询问: 设在询问 $S$ , 对所有 $S'\subset S$, 如果 Trie 树中有对应 $S'$ 的节点, 就为计数器加上 $(-1)^{|S'|}\times tr ie[S']$。这样, 对结构中维护的每个集合, 若它和 $S$ 不交, 它对计数器的贡献就是 1 , 否则是 0。于是计数器的值就代表了结构中与 $S$ 不交的集合个数。

ARC136题解

这场 ARC 比较考验观察能力, 就是找到切入点的能力。我会尽量在题解里给出一个观察的过程, 至于证明, 比猜到结论简单。这场暴露出来我的容易进死胡同的问题, 也可能是人类本质。就是一种思路做不出来的时候跳不出来, 思维僵化了。以后训练中得注意对想不出来的题尝试 “跳出思维定势” 。也可能只是 trick 掌握得不够, 导致跳出来也不知道想啥。可以先多积累些思路, 毕竟 “思而不学则殆” 。

C - Circular Addition

题面

收获的思路:

  1. 在差分数组上看区间加减
  2. 问最小操作次数时, 找几个下界, 尝试证明其最大值可以取到。证明时可以尝试把创造过程逆转为消除过程, 因为消除时的信息更多, 而创造是在 “创造” 信息。

我看到了第一个切入点 “用差分数组处理区间加减问题” 。如果您对这个题毫无头绪, 可以先对着这句话看自己能想到哪一步。将目标数组看作环并作长为 $n$ 的差分数组, 发现这个差分数组和一定为 0, 而且每次操作一定是使得一个数 +1, 一个数 -1。显然我们可以通过每次选择一正一负的一对位置操作来得到目标差分数组, 操作次数为差分数组中正值之和

然后我发现过不了最后一个样例, 仔细一看发现其实也没能给出前两个样例的具体操作步骤, 不太对劲。具体来说, 就是可以交换差分数组上的操作顺序来获得额外的 “全体 +1” buff, 这个信息在差分数组里被丢掉了。从这时开始, 我就开始想着怎么最大化这个 buff, 以及是不是最大 buff 和零 buff 之间的所有值都能取到, 陷入了苦战。

按照题解来讲的话, 我们已经观察到了一个操作次数下界, 还有另一个显然的下界, 就是数组中的最大值。我们猜想: 他们中的最大值是可以被取到的。然后反过来想将目标数组变为 0 的过程。我们发现这个思路在近达上一场比赛 ARC135D 中就出现过, 需要学习一个。

实际应用中, 这种猜想很可能会错, 尤其是难题。所以姑且提出一个做题步骤:

  1. 观察总结此前得到的事实, 提出猜想
  2. 代入样例, 若有误返回1
  3. 尝试证明, 若证伪返回1
  4. 如果证明或不会证而自信, 开码
  5. 如果没证出来且不太自信, 多造点样例, 再次手玩或对拍, 若有误返回1, 否则开码

按照步骤, 我们应当代入样例。发现没问题, 开始尝试证明。如果我们在每一时刻都能降低这一时刻的 “差分数组下界$L_1$” 和 “最大值下界$L_2$” 中的最大值, 我们就构造性地证明了猜想的正确性。为了降低最大者, 我们需要对$L_1$$L_2$的大小做出假设来进行进一步推理。

  1. $L_1<L_2$: 此时数组中不可能有 0, 否则为了从 0 增加到 $L_2$, 差分数组中正值部分至少是 $L_2$, 这与 $L_1<L_2$ 矛盾。于是全体 -1 即可, 这样能使 $L_2$ 减小 1。
  2. $L_1>L_2$: 如果数组中有 0, 我们只要挑选一段包含最大值的极大非零区间来全体 -1, 这样能使 $L_1$ 减小 1。如果数组中没有 0, 数组中一定有若干 “山谷” , 所以一定可以找一段极大的 “连续最大值区间” (要求其左右不再是最大值) 来减 1, 这能使 $L_1$ 减小 1。
  3. $L_1=L_2$: 如果数组中有 0, 一定是单调增加到 $L_2$ 再单调减小到 0, 将非零部分 -1 即可同时减小 $L_1$$L_2$。如果数组中没有0, 数组中一定有若干 “山谷” 。如果*极大的 “连续最大值区间” *唯一, 那么将其减 1 即可。否则, 一定可以找到一个区间覆盖所有的最大值, 例如除去最小值后获得的区间。将这个区间全体减 1 即可。

把这个过程反过来想会变得更难想, 尤其是 $L_1=L_2$ 时的操作。所以这个 “减小双下限最大值” 的 trick 应该被加入知识库。

D - Without Carry

题面

收获: SOSdp

推荐博文: SOSdp, zeta transform 前者为后者前置知识, 本题只需要学习前者。但是来都来了, 为什么不都学一下呢?

读完博文直接就会做了, 不会就看官方题解, 不必多说。

E - Non-coprime DAG

题面

收获: ~~我观察能力低下? ~~

  1. 不够耐心, 一条思路还没想透彻就放弃
  2. 可以把结论写出来, 更容易发现规律, 形式的不同会影响思考方式

在看题解之前, 您至少应该发现 “不可达” 和 “互质” 并不等价, 例如9可以经12和14到达35。并且经过了一定的思考。

$i<j$ , 考察 $i$ 是否可达 $j$ 。后文同余符号皆模 2 , $f(i)$$i$ 的最小质因子。

  1. $i\equiv 0,\;j\equiv 0$, 此时一定可达。
  2. $i\equiv 0,\;j\equiv 1$, 此时来到了第一个重要观察: 可以尝试经过 $j - f(j)$ 这一偶数到达 $j$ , 所以不超过 $j-f(j)$ 的偶数都 ok , 即要求$i\leq j-f(j)$。而比它大的偶数, 和 $j$ 的差距已经小于其最小质因子了, 没有机会走到 $j$ 了。
  3. $i\equiv 1,\;j\equiv 0$, 类似于 2 , 要求$i+f(i)\leq j$
  4. $i\equiv 1,\; j\equiv 1$, 此时来到了第二个重要观察, 也是我卡住的地方。由于我没有将上面的观察列出来, 我并没有注意经过偶数到达奇数这条路, 或者隐约觉得这效率低下。其实这个类比还是比较明显的, 大脑好用时起码可以猜一个结论出来。先写结论: $i+f(i)\leq j-f(j)$ 即可。首先, 两者都是奇数, 这就决定了只加一个 (一定为奇的) 质因数并不能使 $i$ 到达 $j$ , 至少要加 2 个。如果想由偶数搭桥, 显然i -> i+f(i) -> j-f(j) -> j的路径就是最优的。如果不这样做, 要么 $i,j$ 有公因子 (此时 $i+f(i)\leq j-f(j)$ 必成立, 或者仍然可以理解为从偶数搭桥) , 要么还是需要转到 $j-fac(j)$ 再转到 $j$ , 其中 $fac(j)$$j$ 的某个因子。而这一个转变最少也要加 $f(i)$ , 转变后最少也要再加 $f(j)$ 到达 $j$ , 本质还是从偶数搭桥。

现在我们获得了 “可达” 的数学表达。我又卡在这里了 (我去想 DAG 了并且没跳出来, 悲) 。注意到不等号左右的内容都很相似, 并且右侧可以加1 (因为模2的限制, 两式仍然等价) , 尝试总结为一个式子。可以将不等式变形为:

  1. $i+1\leq j$
  2. $i+1\leq j-f(j)+1$
  3. $i+f(i)\leq j$
  4. $i+f(i)\leq j-f(j)+1$

可以总结为:

$i$ 可达 $j$ $\Leftrightarrow$ $up(i)\leq low(j)$, 其中 $up(i)=(i\equiv0)?i+1:i+f(i)$, (注意这个 $+1$ , 这是因为 $i<j$ 不带等号) $low(j)=(j\equiv0)?j:j-f(j)+1$

再次总结这个表达, 对任意的 $i, j$, 当且仅当 $up(i)\leq low(j)$$up(j)\leq low(i)$ 时他们之间可达, 用区间语言表达就更干净: $[low(i), up(i))$$[low(j),up(j))$ 没有交点时可达 (注意区间开闭) 。于是题目变成: 寻找有公共交点的区间族 $\{[low(i), up(i))\mid i\in\mathbb{N}\}$ , 使得 $\sum_{i}A_i$最大。随便做。

ARC135题解

F暂时有个地方没搞明白, 但我会研究题解和正确代码, 把它搞会。

C - XOR to All

题面

关键在于发现若干次操作一定可以等价于一次操作。

假设进行了多次操作, 考察前两次操作$B_0$$B_1$。由定义, $B_0$一定是原数组中的一个数, 而$B_1$一定是原数组中的某个数$A$$B_0$的异或和, 因为$B_1$取自被$B_0$更新过的数组。我们发现$B_0,B_1$两次操作的结果等价于直接用$A$进行一次操作。现在操作次数减少了1, 可以一直使用这个方法直到将多次操作等价为一次操作。

现在只需要比较选择每个数对数组元素之和的影响, 这可以按位统计做到。对每一位 (最多30位) 统计有多少个数在这一位是1, 然后选择$A_i$对和的影响就是: $A_i$会对数组中所有的数翻转$A_i$中为1的那些位, 翻转的贡献可以由统计的数据计算出来。

E - Sequence of Multiples

题面

赛后自己做出来了, 很高兴。

下面记题目描述的数列本身为$A_i$, 而不论怎样得到它。

初见端倪的朴素算法

观察一个特殊的例子: $X=1,N=1e18$。这时数列就是$1$$n$本身! 然后考察$X=2,N=1e18$, 发现数列是$\{2n\}$。继续观察, 会总结出一个规律: 无论$X$如何, 当$n$充分大时, 数列会变成$\{kn\}$的形式, $k$为常数。

证明: 假设第$n$项是$kn$, 那么第$n+1$项的一个上界是$k(n+1)$, 这比前一项大了$k$。只要$k\leq n+1$, 这个上界就会被取到, 因为更小的$n+1$的倍数已经小于第$n$项了, 这不符合题目要求。

于是我们发现这个$k$的变化趋势是很重要的, 如果我们能搞清楚什么时候$k\leq n+1$, 这之后的内容就可以$O(1)$计算了。为了研究它, 构造新的数组$\{B_n\}:B_i=A_i/i$

在特殊例子上构造$\{B_n\}$会给我们一些最基本的认识, 例如: $\{B_n\}$是不增的。前面的证明过程稍加修改就能证明这个结论。实际上, 我们感到它以类似于反比函数的速度减少。

为了解出$B_i\leq i+1$的时刻, 我们研究$B_i$的变化趋势, 而这可以其定义中的$A_i$入手, 考察$A_i$的变化趋势。我们发现$A_{i+1}-A_i\leq i+1$, 否则$A_{i+1}$会被$A_{i+1}-(i+1)$取代。于是$A_i$大致以$O(n^2)$的速度增加, 具体来说, $A_i-A_1\leq(\sum_{k=2}^{i} k)=(i+2)(i-1)/2$

得到了$\{A_i\}$的变化趋势, 两侧同时除以$i$即可得到$\{B_i\}$的变化趋势上界: $B_i-\frac{X}{i}\leq \frac{(i+2)(i-1)}{2i}\leq i$, $B_i\leq \frac{X}{i}+i$。这个上界是有极小值的, 但我们知道$B_i$不增, 所以我们可以先增加$i$得到极小值, 然后等待$i+1$追上这个极小值。显然, 这个极小值在$i=\sqrt{X}$附近取到, 而$i=2\sqrt{X}$时就一定有$B_i\leq i+1$了。于是我们证明了, 如果我们暴力计算$\{A_i\}$直到$B_i\leq i+1$, 时间复杂度是$O(\sqrt{X})$的。尽管我们没有证明其下界, 但这个算法实际效率也不够高, 对1e18 1e18的输入需要计算20秒, 10组就是200秒, 远不是常数问题。

正解

$B_i$有一个类似于反比函数的, 一开始快速下降, 然后缓慢下降, 最后不变的变化过程。对反比函数的取整求和有整除分块, 对$B_i$能不能也找到某种分块来合并一些计算呢?

在Linux上使用clash

更新: 我火星了, 有现成的GUI…请使用Clash for Windows的Linux版本。

  1. release页面下载 Clash.for.Windows-0.x.x-x64-linux.tar.gz
  2. 解压后执行./cfw
  3. 为了脱离命令行运行, 请看issue

以下为原文。

东方网络为例, 按照机场默认的配置使用clash。如果不够满意 (大概率) , 参考API文档再稍微写一些代码就可以进行规则与节点的配置, 待更新。

步骤

  1. releases页面中下载最新版clash内核, 一般的64位机器下载amd64版本即可。解压后为一个可执行文件, 重命名为clash后执行chmod +x clash为其加上执行权限。
  2. 在机场网站上下载配置文件, 命名为config.yaml, 执行./clash -t -f config.yaml, 如果没有问题说明配置文件正确。
  3. 执行./clash -f config.yaml, 开启代理服务。
  4. 配置系统代理: 选择"use manually specified proxy configuration", 填入代理日志显示的代理地址+端口号
  5. 配置浏览器使用系统代理/配置浏览器代理指向clash。现在应该已经可以访问google了。如果不行, 检查配置文件的mode, 如果是direct, 改成rule或者global。
  6. 按照官方wiki的步骤将其配置为守护进程。

这样就足以支持日常需求了。

页面调度算法

最优调度算法为什么最优

我们发现换页时换入的页总是固定的, 我们要挑选的是换出的页面。优先换出不再被访问的页面是显然的。首先注意换出的页面在下次访问时是一定会被换入的。只要考虑没被换出的页面有没有离开即可。如果不用最优调度算法换出A, 而换出一个下次访问更早的页面B, 那么:

  • 如果A在下次访问A前未被调出, 那么换出A仍能使得下次访问B前B未被调出
  • 如果A在下次访问A前被调出了, 那么换出A有可能可以使得B不用被调出, 因为B的下次访问更早

于是换出A一定不比换出B差, 无论换出B后采用什么策略。

堆栈式算法

堆栈式算法是指: 访问第$t$个页面时, 考虑驻留集大小为$n$时的驻留集$S$和驻留集大小为$n+1$时的驻留集$S'$, 如果可以证明在某种调度算法下无论对什么输入下的哪个$t$, 都有$S\subset S'$成立, 那么这个调度算法就是堆栈式算法。

堆栈式算法的好处

这种算法没有Belady现象, 也就是: 页框增加时缺页中断次数不会增加。

证明: 页框增加时, 由于任何时刻$S\subset S'$, 那么$P\notin S'\Rightarrow P\notin S$, 即某页在页框多时缺页$\Rightarrow$该页在页框少时也缺页, 缺页中断次数不会更少。

最优调度算法/LRU为什么是堆栈式算法

用数学归纳法。初始时$S=S'=\emptyset$

假设对某个访问序列满足$S\subset S'$, 现在再访问一页$P$

$P\notin S'$, 那么$P\notin S$, 同时产生缺页中断。设在$S$中换出页$P_1$, $S'$中换出$P_2$。对OPT/LRU中的每一种, 要么$P_2\in S'-S$, 要么$P_1=P_2$, 无论哪种情形, 换出页后仍满足$S\subset S'$

综上, 对任意输入, 这两种算法都是堆栈式算法。

这个证明的核心在于: 要么$P_2\in S'-S$, 要么$P_1=P_2$。看到网上的一个理解, 说是: 给驻留集里的页面一个与$n$无关的优先级, 选择优先级最高的那个, 于是不会选择$S-\{P_1\}$中的元素。对FIFO算法, 这个优先级是进入时间, 然后我们会发现这个东西不完全取决于驻留集这个集合本身, 还取决于它进入驻留集的时刻。有可能: 驻留集小时的缺页导致一个页面换出后再次换入, 但驻留集大时则总是驻留, 从而它在驻留集小时优先级低而驻留集大时优先级高。这时有可能$P_2$是那个$S'$中总是驻留的页面, 而$P_1$是其他的页面, 于是这个$P_2$现在仍在$S$中而不在$S'$中。

二分图匹配

思路: 先通过交错路和增广路的概念建立起处理最大匹配的工具, 证明匹配最大的充要条件是图中没有增广路。然后证明Hall定理, 顺便证明了婚配定理, 并利用之证明最大匹配与最小点覆盖的对偶性。最后证明最小边覆盖与最大独立集的对偶性, 以及这四者之间的关系。

Read More

Public Transport System

题意

给定一个有向图, 每条边有边权$a_e$$b_e$, $0<a_e,b_e;\;b_e<a_e$。记一条路径由$k$条边$e_1,e_2,...,e_k$组成, 那么这条路径中, 边$e_1$的权值为$a_{e_1}$, $e_i(i>1)$的权值为:

$$\begin{cases} a_{e_i}&a_{e_i}\leq a_{e_{i-1}},\\ a_{e_{i}}-b_{e_i}&a_{e_i}>a_{e_{i-1}}. \end{cases} $$

这条路径的权值是这条路径上边的权值之和。求从点$1$出发到所有点的最短路长度。

$$\begin{align*} n\leq 1\times10^5,\ m\leq 2\times10^5. \end{align*} $$

Read More

Charged Tree

题意: 给定一棵有根带权树。有两种操作下移和上移。下移, 即每个节点将自己的权值均分给各个儿子, 假设叶子结点有一个无限长的儿子链, 即叶子结点每次下移都会把自己和整条儿子链下移一位。每个节点的新值就是它从父亲得到的那个值 (他自己原来的值已经分给了儿子) , 特别地, 一次下移操作后根变成0。上移, 即对每个节点, 将所有儿子的权值加起来赋给自己。

Read More