【模板】ISAP – 最大流

ISAP卡常成功 🙂

72ms—>60ms

实测BFS会造成玄学优化


 

3+

【APIO2014T1】【模板】回文自动机

算了算了,放弃卡常数,来研究一波各种代码块样式(无助脸)
一些数组的意义
next[][]类似于字典树,指向当前字符串在两段同时加上一个字符
fail[] fail指针,类似于AC自动机,返回失配后与当前i结尾的最长回文串本质上不同的最长回文后缀
cnt[] 在最后统计后它可以表示形如以i为结尾的回文串中最长的那个串在整个串里面的出现次数
num[] 表示以i结尾的回文串的种类数
len[] 表示以i为结尾的最长回文串长度
s[] 存放添加的字符
last 表示上一个添加的字符的位置
n 表示字符数组的第几位
p 表示树中节点的指针

3+

【模板】后缀数组

羊驼羊驼羊驼羊驼羊驼羊驼

为什么又跑的如此之慢啊

哦对我写的是倍增,实在是懒得去写induced_sort的sais算法了

辣鸡字符串,严重不喜欢


 

3+

【模板】后缀自动机

啊啊啊啊啊

啊啊啊啊啊啊啊啊啊啊

为什么我的后缀自动机跑的那么慢啊啊啊啊啊啊啊啊啊


 

2+

Fibonacci博弈

Problem

两个人进行Fibonacci博弈,若先手要有必胜策略,求他第一次至少要取多少个?

Solution

由Fibonacci博弈可知,如果当前石子数是fibonacci数,则先手必败,所以此时当前的先手必须全部取走

齐肯多夫(zeckendorf)定理:任何一正整数都能拆成一堆互不相同的正整数的和,且一定存在一种取法取到不超过它的最大Fibonacci数

1+

Vizing定理

Vizing定理:任意(简单, 无向)图\( G \)的边着色数 (edge chromatic number,\( χ′(G)) \)等于\( Δ(G) \)或\( Δ(G) + 1\),其中\( Δ(G) \)指图\( G \)中最大的度。

由Vizing定理可知\(χ'(G)=Δ(G) \)或\( Δ(G) + 1\)。若为前者,称\(G\)为第一类图(Class 1),否则称为第二类图 (Class 2)。虽然只有两类,但Holyer (1981)证明了,确定任意图属于哪一类是一个NP完全问题。

不过,对于特定类型的图也有部分的解答。比如对于简单平面图,Vizing (1965)自己证明了,如果\(Δ(G)≥8 \)则是第一类的,但对于\(Δ(G)=2,3,4,5 \)的情况则有第二类图存在:把正多面体的其中一边截成两条,即可得到 \(Δ(G)=3,4,5 \)的平面图,他们是第二类的;而任何长度是奇数的圈(比如三角形)就是\( Δ(G)=2 \)的第二类图。对于剩下的两种情况,Vizing提出了猜想:

平面图Vizing猜想:
※任何简单平面图如果\( Δ(G)≥6 \)(或\(7\)),则是第一类的。(Vizing 1965)

在\( Δ(G)≥7 \)的情形,Sanders & Zhao (2001) 给出了肯定的结果。因此只剩下\( Δ(G)≥6 \)的情形尚待解决。

0