hydd的博客

博客

Tags
None

Rikka with zombies 题解

2020-08-28 14:20:05 By hydd

题目大意

  • 给定一棵 n 个点的无根树,每条边有一堵墙,高度在 [li,ri] 等概率出现。
  • m 个僵尸,第 i 只僵尸初始出生在 xi 点,能力值为 hi,表示可以走过墙的高度 $
  • 称一个点是安全的,当且仅当它不能被任何一个僵尸走到。
  • 求树上至少有一个点是安全的概率,对 998244353 取模,有 T 组数据。

    • T,保证 r_i-l_i+1\neq 998244353
    • \texttt{source:[Nowcoder2018 ACM多校第十场 I] Rikka with Zombies}https://ac.nowcoder.com/acm/contest/148/I)。

Read more...

Array Solution

2020-05-14 17:05:38 By hydd

考虑从左往右逐个加入数字,如果线索必须是从左往右怎么做?首先考虑状压已经出现过的线索,线索出现的位置可能重叠,那么我们考虑一条线索开始时的位置,此时若有别的线索还没结束,那么一定需要满足完成新的线索之时或之前能够完成旧的线索。

f(S,i,j) 为已经出现了线索集合 S ,当前最后一个开始的线索为 i 且匹配到第 j 位时最短的序列长度,预处理 a(i,j,k) 表示匹配到第 i 条线索的第 j 位时能否换到第 k 条线索进行匹配。

转移时往下再匹配,或者枚举一条新的满足条件的线索,这是一个边权只有 0 和 1 的最短路,时间复杂度 O(n^2 \cdot 2^n)

如果只有从右往左的线索呢,从左往右的时候我们考虑线索开始的时刻,那么现在就考虑线索结束的时刻,结束的时候枚举下一条线索计算最多能够重叠多少,即记 b(i,j) 为第 i 条线索结束时接第 j 条线索最多可以匹配到第 j 条线索的第几位,状态和转移类似,时间复杂度 O(n^2 \cdot 2^n)

接下来就是考虑如何把向左的和向右的结合在一起,设 f(S,i,j,k,l) 为当前出现了集合 S 中的线索,从左到右的第 i 条线索匹配到第 j 位,从右到左的第 k 条线索匹配到第 l 位的答案,特殊地当 ik 等于 0 表示当前没有这个方向的线索正在匹配。转移的时候往一边扩展一位,或者枚举一个新的线索替换某一跟方向的线索,注意扩展一位的时候处理好另一个方向的变化,同样是边权为 0/1 的最短路。时间复杂度 O(n^3 \cdot 2^n)

图论入门教程

2020-05-02 23:18:55 By hydd

0513上午

1、子图

导出子图(Induced subgraph

  • G=(V,E)Gv_1 上的导出子图 G_1=(V_1,E_1),E_1=\{e\in E\mid u,v\in v_1\}
  • 相当于在图中去掉一些点。n 阶导出子图有 2^n 个。

生成子图(Spanning subgraph

  • G=(V,E)G_1G 生成子图是指 V(G_1)=V(G),E(G_1)\subseteq E(G)
  • 相当于在图中去掉一些边。生成子图有 2^{|E|} 个。
\color{red}{\texttt{Note: }}
  • 导出子图和生成子图都不限定是否为简单图。
  • 既是导出子图又是生成子图为原图。

2、Mantel 定理、托兰定理

Mantel's thm
  • 如果图 G=(V,E) 中没有三角形,则 |E|\leq [\frac{n^2}4]
  • 等号成立条件 \Longleftrightarrow G=K_{\lfloor \frac n2\rfloor\lceil \frac n2\rceil}
Turan's thm
  • GK_k 子图,G 的边数取最大值的图唯一,为G=K_{x_1,x_2,...,x_{k-1}},其中\sum_{i=1}^{k-1} x_i=n,同时 |x_i-x_j|\leq 1
  • 形式化的,G=K_{[\frac n{k-1}][\frac {n+1}{k-1}]...[\frac{n+k-2}{k-1}]}\sum_{i=0}^{r-1} [\frac{x+i}r]=[x]

3、二分图

二分图(Bipartite Graph) 定义

  • G=(V,E),V=A\cup B
  • \forall u,v\in A,(u,v)\notin E\forall u,v\in B,(u,v)\notin E
  • 则称 G 为二分图。

二分图判定定理

  • 一个图 G 是二分图,当且仅当图 G 无奇环。
  • 命题①:G 是二分图
  • 命题②:G 无奇环
  • 命题③:G 无奇数长的回路
  • 通过 ①\Rightarrow\Rightarrow\Rightarrow① 可证得三个命题相互等价,在此略去。

4、完美匹配、Hall定理、Tutte定理

匹配(Matching

  • G=(V,E)E 的子集 E_1 的顶点两两不重合。则 E_1G 的匹配。
完美匹配(Perfect Matching,PM
  • 匹配 E_1 的顶点覆盖 VGPM \Rightarrow |G|\equiv 0(\operatorname{mod} 2)
二分图完美匹配
  • G 为二分图 (x,y,E)
  • GPM ,则 |X|=|Y|XY 有双射。
  • f 称为由 PM E 诱导(induce) 的双射。
  • 满足 f(x_i)=y_i,(x_i,y_i)\in E(E_1=\{(x_i,y_i)\mid 1\leq i\leq |X|\})

Hall 定理

  • 二分图有完美匹配的充要条件为:\forall S\subseteq X,|N(S)|\geq |S|(有匹配覆盖 X 的所有顶点),\forall S\subseteq Y,|N(S)|\geq |S|(有匹配覆盖 Y 的所有顶点)。

Tutte 定理

  • 对于图 GGPM的充要条件为 \forall S\subseteq VGV-S 上的导出子图 M 的有奇数个顶点的连通分支的个数 \leq |S|

5、正则图的定义

正则图

  • 一个图为 k-\texttt{正则} 的,定义为 \forall v\in V,d(v)=K

0513下午

1、欧拉图的定义

欧拉图 Euler Graph

  • 存在一条回路,经过图 G 的全部的边恰好一次。(欧拉回路)

2、一笔画的算法,欧拉图的充要条件

  • 若一个图 G 存在 0 个或 2 个奇点,则这个图可以一笔画。
  • 欧拉图充要条件:\forall v\in V,2\mid d(v)

3、哈密顿(Hamilton)图、哈密顿链的定义

哈密顿图

  • 一个图 G 为哈密顿图 \Longleftrightarrow 存在一条回路包含图 G 的全部顶点,这个回路被称为 Hamilton 圈。

哈密顿链

  • 若一条链 P 遍历了图 G 的全部顶点,则称 P 为哈密顿链。

4、Hamilton 性质、必要条件

必要条件

  • SG 的一个顶点子集,若 GV-S 上导出子图的连通分量个数大于 |S| (|S|+1) ,则 G 无哈密顿图(链)。
  • 二分图有哈密顿圈(链),必要条件为 ||X|-|Y||\leqslant 01)。

5、哈密顿图(链)的一些充分条件:Ore条件、Dirac条件

Ore 条件

  • G 为哈密顿图,设 |G|=n,则 \forall v,d(v)\geqslant \frac{n}{2}

Dirac 条件

  • G 为哈密顿图,设 |G|=n,则 \forall u,v,若 (u,v)\notin Ed(u)+d(v)\geqslant n
  • G 存在哈密顿链,则 d(u)+d(v)\geqslant n-1

6、图的笛卡尔积的定义

  • 集合的笛卡尔积: A\times B=\{(a,b)\mid a\in A,b\in B\}
  • 图的笛卡尔积: G=(V,E)\space ,\space H=(U,F)
  • 定义 G\times H=(V\times U,E')E'=\{(v_1,u)(v_2,u)\mid v_1,v_2\in E,u\in U\}\cup\{(v,u_1)(v,u_2)\mid u_1,u_2\in F,v\in V\}

0514上午

1、图的顶点染色

染色的定义

  • 一般染色:f:x\rightarrow \{1,2,3,\cdots,k\}。其中,1\cdots k 是颜色集合。(高联一般不考虑无穷染色)
  • 图的顶点染色:G=(V,E)
    • 无限制的染色:f:V\rightarrow \{1,2,3,\cdots,k\}
    • 一般意义上的图染色:f:V\rightarrow \{1,2,3,\cdots,k\},且对于 \forall(a,b)\in E,a\neq b,f(a)\neq f(b)

染色数的定义

  • 最小使得染色映射 f 存在的 k 称为图 G 的色数,记为 \chi(G)。(chromatic number
\color{red}{\texttt{Note: }}
  • n 阶图一定可以用 n 种颜色染色。随机图算色数较为困难。
  • 答题方法:考试时将颜色标在图上,再证明不存在更少的色数。
  • 常用结论:
  • \chi(K_n)=nn 阶完全图 )
  • \chi (C_n)=\begin{cases} 2, &2\mid n \\ 3, &2\nmid n \end{cases}n 个点的环)
  • \chi (T)=2\ (n\geqslant 2)n(n\geqslant 2)个点的树)

2、色数的简单估计

估计色数上下界

下界
  • 团数(clique number):设团数 \omega(G)G 中最大完全子图的阶数。
  • 明显的下界:\chi (G)\geqslant \omega(G)

  • 最大独立集:一个图的最大独立集 S\subseteq V,是指点数最大的两两不连的顶点集合。

  • 独立数(independence number):设独立数 \alpha(G) 为图 G 的最大独立集顶点数。
  • 另一个下界:\chi(G)\geqslant \frac{n}{\alpha(G)}
上界
  • 上界:\chi(G)\leqslant 1+\Delta(G)

3、Brooks 定理简介

Brook's Thm

  • G 为连通图且不是完全图或奇圈。则必有 \chi(G)\leqslant \Delta(G)
  • 前提的等价表述:\Delta\geqslant 3,且\exists\ u,v\in V,(u,v)\notin E

4、色多项式(chromatic polynomial

  • 我们考虑一张一般的图 G ,将它 k 染色的方案数。
  • 我们在图 G 上任取一条边 e=(u,v),把 e 去掉。
  • 然后我们对 G\setminus e(从 G 中删去边 e)的任一种染色 f
    1. 对于 f(u)\neq f(v)f,则 f 也是 G 的染色。
    2. 对于 f(u)=f(v)f,则f 是图 G\cdot e 的染色(把 Ge 的端点合并,去掉重边)
  • 反之,G 的染色均是 G\setminus e 的使 f(u)\neq f(v) 的染色,G\cdot e 的染色均是 G\setminus e 的使 f(u)=f(v) 的染色。
  • 于是,我们定义 F_G(k)k 种颜色对 G 染色的方案数。
  • 此时,F_{G\setminus e}(k)=F_G(k)+F_{G\cdot e}(k),即 F_G(k)=F_{G\setminus E}-F_{G\cdot E}(k)
  • 对边数归纳可证对于任意的 GF_G 为关于 kn 次多项式。F_\texttt{n个点,没边}=k^n
  • F 首项系数=1,次高项系数=-|E|
  • k<\chi(G) 时,F_G(k)=0(x-k)|F_G(k)

5、平面图的定义

  • 可以画在平面上,使边与边只在顶点处相交(边可以为曲线或折线)。

6、库拉托夫斯基定理

Kuratowski's Thm

  • 一个图是平面图当且仅当 G 无同胚与 K_5K_{3,3} 的子图。
  • 同胚:如果两个图 G_1G_2 同构,或经过反复插入(将 e=(u,v) 拆成 e_1=(u,w),e_2=(w,v))或消去 2 度顶点后同构,则称 G_1G_2 同胚。

7、欧拉公式(多面体/平面图)

  • 连通图 G 为平面图,|G|=n,||G||=e,面数=f,则 n-e+f=2

0514下午

1、Ramsey 问题

前置知识

  • G=(V,E) ,图的一个边染色指映射 f:E\rightarrow \{1,2,3,\cdots\}
  • \forall e_i,e_j ,若 e_i\cap e_j\neq \varnothing,则 f(e_i)\neq f(e_j)
  • 所需最小色数 k 称为图 G 的边染色数 \chi'(G),显然 \chi'(G)\geqslant \Delta(G)

Viking Thm

  • \chi'(G)\leqslant 1+\Delta(G)

Ramsey's Thm

  • \forall s,t\in \mathbb{N}^+,对 K_n 的边 2 染色,当 n 足够大时,存在红色 K_s 或 蓝色 K_t 子图。
  • 最小满足上述条件的 n 称为 Ramsey 数 r(s,t)
\color{red}{\texttt{Note: }}
  • 常用结论:
    1. r(s,t)=r(t,s),显然。
    2. \forall x\quad r(x,1)=r(1,x)=1,证明显然。
    3. \forall x\quad r(x,2)=r(2,x)=x,证明显然。
    4. r(s,t)\leqslant r(s,t-1)+r(s-1,t),证明可以对 s+t 归纳,在此略去。
    5. ④的推论:r(s,t)\leqslant \binom{s+t-2}{s-1},显然。

2、简单的 Ramsey 数

r(3,3)=6

  1. 根据结论⑤,有r(3,3)\leqslant \binom{4}{2}=6
  2. 证明 5 不可以,请读者自行证明。

r(3,4)=9

  • 请读者自行证明。

r(3,5)=14

  1. r(3,5)\leqslant r(3,4)+r(2,5)=9+5=14
  2. 证明 13 不可以,给出简要思路:循环构造,将 i-j\equiv \pm 1 \operatorname{or} \pm 5 连红边,否则连蓝边。

3、范德瓦尔登定理

Vander Waerden's Thm

  • \forall m\in \mathbb{N}^+,\exists N,使集合 \{1,2,3,4,\cdots,N\} 的任意 2 染色必定存在同色,长度为 m 的等差数列。
  • 上面的表述等价于 \exists N_1,\{1,\cdots ,N_1\} 2 染色存在长为 N 的同色等差数列。

4、同色角,异色角方法

  • 我们将角的两条边颜色相同的角称为 同色角 ,将角的两条边颜色不同的角称为 异色角 。

  • 显然,有同色 \Delta+ 异色 \Delta=\binom n3

同色\Delta 异色\Delta \sum
同色角 3 1 3\times \texttt{同色}+1\times {异色}
异色角 0 2 2\times \texttt{异色}
3 3 /
  • 我们考虑顶点在 v 处的 \Delta 。同色角数=\binom{d_\texttt{红}(v)}2+\binom{d_\texttt{蓝}(v)}2。异色角数=d_\texttt{红}(v)\times d_\texttt{蓝}(v)。所有角数=\binom{d_\texttt{红}(v)+ d_\texttt{蓝}(v)}2

  • 整个图 \sum_{v\in V} \binom{d_\texttt{红}(v)}2+\sum_{v\in V} \binom{d_\texttt{蓝}(v)}2+\sum_{v\in V}d_\texttt{红}(v)\times d_\texttt{蓝}(v)

  • 即我们可以将 同/异色\Delta 与 顶点的红蓝度 相互转化。

字符串入门

2019-11-09 07:54:23 By hydd
  • 1\leq r\leq |S|S_{1..r}=S_{|S|-r+1..|S|},则称 S_{1..r}Sborder,长度为 r
  • border 的性质:字符串 s 的所有 border 长度排序后可分成不超过 \log_2 |S| 段,每段是一个等差数列。
  • 引理 1:若存在一个 border 长度为 k ,那么 |S|-kS 的一个周期。
  • 引理 2:若 p,qS 的周期,且 p+q\leq |S|,那么 \gcd(p,q) 也为S 的周期。
  • 引理 3S 的所有 \geq\frac{|S|}{2}border 长度组成一个等差数列。

Proof

  • 引理 1 是显然的,根据定义,对于 i+|S|-k\leq |S|i\leq k,有 S[i]=S[i+(|S|-k)]
  • 引理 2 [^1]
    • p < q,d=q-p
    • |S|-q\leq i\leq |S|-dS_i=S_{i-p}=S_{i-p+q}=S_{i+d}
    • 0\leq i < |S|-qS_i=S_{i+p}=S_{i+q-p}=S_{i+d}
    • 那么 d=q-p 也为 S 的周期。由欧几里得算法可知 \gcd(p,q) 也为 S 的周期。
  • 引理 3 [^2]
    • S 长度最大的 border 的长度为 n-p,(p\leq \frac{|S|}2)
    • 设另外某个 border 的长度为 n-q,(q\leq \frac{|S|}2)
    • 由引理 2,有 \gcd(p,q)S 的周期,那么 n-\gcd(p,q)sborder 的长度。
    • 则有 n-p\geq n-\gcd(p,q),于是 \gcd(p,q)\geq p,即 p\mid q
  • 根据引理 3,有:
  • 考虑更小的 border,对其进行按长度的二进制分组,即 [1,2),[2,4),[4,8)\cdots,[2^k,n) 各分为一类。
  • 对于在某个类中的 border,考虑其最长的,那么剩下的所有 border 一定是最长的那个 borderborder。(正确性证明类似于 kmp)。
  • 故以最长的 border 为母串(称之为T),而类内所有 border 的长度必定 >\frac{|T|}2。根据引理 3 ,故一类的 border 长度为一个等差数列。
  • 故字符串 S 的所有 border 能划分成 \log_2 S 个等差数列。

参考文献:

  1. 钟子谦,《串串 解题报告》引理 5.1,2019 年信息学奥林匹克中国国家集训队队员作业
  2. 金策,《字符串算法选讲》Border的结构,WC2017课件

最小割入门

2019-11-04 23:17:25 By hydd
  • cut(x,y)x,y 的最小割的值。
  • 以下的 “连通” :存在一条 x,y 的路径,其路径上边权最小值非负(等价定义为 cut(x,y)>0)。

一个结论

  • x 的最小割集割掉之后,那么原图 y 将被分为两个集合。(不考虑原图中与 x,y 不连通的点)
  • 一个集合为 x 所在的连通块集合 A,一个集合为 y 所在的集合 B

证明

  • 假设存在一些点不属于这两个连通块之一。
  • 则这些点中必有点和 AB 在原图中有非零边,不妨设有点与 A 在原图中有非零边。
  • 那么将这个连通块中与 A 的边全部连回去(即不割这些边),那么 x,y 依旧不连通。
  • 而不割这些边后,最小割的值变小了,矛盾。
  • 证毕。
  • 推论0:对于 u\in A,v\in B,有 cut(u,v)\leq cut(x,y),因为 x,y 的最小割也是 u,v 的割。

定理

  • 任取不同的三点 x,y,z
  • 那么有 \min(cut(x,z),cut(y,z))\leq cut(x,y)

证明

  • cut(x,y)=0,那么 cut(x,z),cut(y,z) 中也必定有一个为 0
  • cut(x,y)\neq 0
    • 不妨设将 x,y 的最小割集割掉之后,z 属于 x 所在的连通块。
    • 那么 x,y 的最小割集同时也是 z,y 的最小割集,即 cut(y,z)\leq cut(x,y)
    • z 属于 y 所在的连通块时,有 cut(x,z)\leq cut(x,y)
  • 证毕。

推论1

  • 任取不同的三点 x,y,z
  • cut(x,y) 满足是 cut(x,z),cut(y,z),cut(x,y) 中最小时,有 \min(cut(x,z),cut(y,z))=cut(x,y)
  • 此命题等价于任意三点两两最小割值必有相同。

证明

  • 显然。

推论2

  • 任取不同的 k\geq 2 个点 c_1,c_2,\cdots,c_k,那么有 \min(cut(c_1,c_2),cut(c_2,c_3),\cdots,cut(c_{k-1},c_k))\leq cut(c_1,c_k)

证明

  • cut(c_1,c_k)\geq \min(cut(c_1,c_2),cut(c_2,c_k)),而 cut(c_2,c_k)\geq \min(cut(c_2,c_3),cut(c_3,c_k)),以此类推即证。

推论3

  • 任取不同的 k\geq 3 个点 c_1,c_2,\cdots,c_k
  • cut(c_1,c_k) 满足是 cut(c_1,c_2),cut(c_2,c_3),\cdots,cut(c_{k-1},c_k),cut(c_1,c_k) 中最小时,那么有 \min(cut(c_1,c_2),cut(c_2,c_3),\cdots,cut(c_{k-1},c_k))=cut(c_1,c_k)
  • 此命题等价于任意 k\geq 3 个点两两最小割值必有相同。即最小割值互不相同的边不可能成环。

证明

  • 显然。

终极目标

  • 任意一张图,任意两点的最小割最多有 n-1 种不同的值。

证明

  • 把最小割的值当做边权建立一张完全图。不妨考虑图的任意一棵生成树。
  • 依次考虑每一条在树中没出现过的权值的非树边,看它对应的树上的路径必定至少有两条边权值相同(推论3),删除其中一条边后接上这条边。
  • 可以发现,做完后可以使所有完全图中权值不同的边都在生成树上,而生成树为 n-1 条边,所以权值不同的边的数量也只有 n-1 条。

最小割树

定义

  • 如果对于树上的所有边 (u,v),树上去掉 (u,v) 后产生的两个集合恰好是原图上 (u,v) 的最小割把原图分成的两个集合,且边 (u,v) 的权值等于原图上 (u,v) 的最小割。

构造

  • 首先任意选择两个点,跑最小割。
  • 那么把图分成的两个部分,由推论0,两个部分之间的最小割是没有影响的。
  • 然后继续求解两个部分的最小割树。

性质

  • 原图上 u,v 两点最小割就是最小割树上 uv 的路径上权值最小的边。
  • 不妨设 uv 的路径上的点(不包括 u,v)依次为 c_1,c_2,\cdots,c_k
  • 由推论 3 ,有 \min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))\leq cut(u,v)
  • 而对于每一条边,由推论0,cut(u,v)\leq cut(u,c_1),cut(u,v)\leq cut(c_1,c_2),\cdots,cut(u,v)\leq cut(c_k,v)
  • 可得 \min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))=cut(u,v)

[JZOJ5495]【清华集训2017模拟12.09】MiniumCut

  • 而这道题其实就是求最小割树,两两点的最小割等于这两点在最小割树上的路径边权最小值。
  • 考虑从大到小加入边,新加入一条边时,这条边比之前所有边都要小。
  • 如果这条边连接的两个点已经连通了,那么两点路径上的边权最小值 \min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))\geq cut(u,v)
  • 又根据推论 3,有 \min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))\leq cut(u,v)
  • \min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))=cut(u,v),得证。
  • 最后需要判断是否合法,因为中间的推论 3 是假设现在满足最小割树的性质的。
共 15 篇博客
  • 1
  • 2