最小割小结

《浅析一类最小割问题(pty)》
这算是个解决最小割问题比较统一的方法吧 感觉是很厉害O.O
这个就是把最小割模型都转化成二元关系:(x,y)
x,y都取 代价为v1
x,y都不取 代价为v2
x取y不取 代价为v3
x不取y取 代价为v4
对于这个图233

a + b = v1
c + d = v2
a + d + f = v3
b + c + e = v4

令K = v3 + v4 – v1 – v2

如果 K < 0 那么关系图要是二分图就能做 把一侧的定义相反即可(这个的题目很少 不详写= = 首先要保证边权是非负的 K >= 0 e和f一定是非负的
可以看到每个等式中都出现了a、c中的一个 b、d中的一个
如果a、c中有边权是负的 可以把它们同时加上一个数 最后再扣掉
b、d同理
还有最好保证他们都是整数
如果出现小数 可以把所有边权都*=分母的最小公倍数 最后再除掉 (这个最小公倍数一般是2什么的= =)
然后就可以直接建图了

对于一些一元关系 某个点取有多少获利 不取有多少获利什么的 最后直接建边即可
这里对每对二元和一元关系的建边是独立的 最后再把边权加起来作为边权(不加也可以) 而不是比如对于每个二元关系s->p的权值都是一样的

注意这里求的是最小割 是最小值 有的题目求的是最大获利
有两种转化方法
一是把权值取负 然后求最小获利
二是比如你取了某个点 说明你不能不取这个点 就失去了不取这个点能获得的获利 这样就变成了最小代价了 然后最后把权值和-最小代价就是最大收益
↑其实这两个方法好像是等价的 看你怎么理解罢了=-=

==========BZOJ 3438: 小M的作物===========
这题是一个多元关系 但是也可以转成一元的
对于每个作物 s到它的边表示这个作物选择A 到t的边表示选择b
对于每个组合 新建两个点
一个点表示这些点是否全部选了A 这个点选择是的收益是c1i 否的收益是0
另外一个表示这些点是否全部选了B 这个点选择是的收益是c2i 否的收益是0
s到第一个点的边表示 是全部取A 到第二个点的边表示 不是全部取B
第一个点到t的边表示 不是全部取A 第二个点到t的边代表 是全部取B
如果第一个点选择了全部取了A 但是组合里的某个作物选择了B 这样的代价就是inf 因为是不可行的= =
对于B同理
这样就把多元关系转成了二元关系 很多多元关系的题目都可以用这个思路
然后把这个方程列啊列 最后建出来的图是一个类似最大权闭合子图的东西O.O

==========BZOJ 2127: happiness===========
这个就是非常模板的题
说一点0 0
在很多情况下可以设e=f(比如这题)
但是也有的时候设两个变量比较方便(比如上面那题) 自己看着办吧233

==========BZOJ 3218: a + b Problem===========
这题是厉害啊 我决定为这题独立开一篇文章 以表(pian)敬(I)意(P)

fnt

fnt就是把fft看为在fft mod p系下的解
相对与fft 把单位元换成g^((p-1)/n)
如果满足g^(p-1)=1且g^i(0 <= i <= p-1)双射0~p-1的整数集合 即g为p的原根 又p可以表示为p=2^k+1则这个p是一个合法的p 如 p=2^21*479+1 g=3 其余和fft程序差不多 在做ifft的时候 /len 换为 *len^-1 再把[y+1, y+len]reverse即可 fnt:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void fnt(ll y[], const ll b[], ll n, ll rev = 1)
{
  ll len = 1 << n;
  for (ll i = 0; i < len; ++i)
    y[i] = b[bit_reverse(i, n)];
  for (ll i = 1; i <= n; ++i)
  {
    ll m = 1 << i;
    ll wn = power(g, (p - 1) / m, p);
    for (ll j = 0; j < len; j += m)
    {
      ll w = 1;
      for (ll k = j; k < j + m / 2; ++k)
      {
        ll u = y[k], v = (w * y[k + m / 2]) % p;
        y[k] = (u + v) % p, y[k + m / 2] = (u - v) % p;
        w = (w * wn) % p;
      }
    }
  }
  if (rev == 1) return;
  ll re = power(len, p - 2, p);
  for (ll i = 0; i < len; ++i) y[i] = (y[i] * re % p + p) % p;
  reverse(y + 1, y + len);
}

converlution:

1
2
3
4
5
6
  ll len = 1, n = 0;
  for (; len < nn * 2; ++n, len = 1LL << n);
  fnt(tmp1, a, n);
  fnt(tmp2, b, n);
  for (ll i = 0; i < len; ++i) b[i] = (tmp1[i] * tmp2[i]) % p;
  fnt(a, b, n, -1);

左偏树

左偏树 会让人联想到平衡树 其实毫无关系= =
只不过一个很平衡 一个很不平衡而已~
左偏树其实是可并堆 主要操作是merge(int, int)
传入两个根 把这以这两个为根的子树合并 返回新根

这个数据结构的node类:

1
2
3
4
struct MHnode
{
  int l, r, dis, v;
}

l,r就是左右儿子的指针
v是这个节点的权值
dis就是左偏树的关键 表示从这个点 一直走右儿子 要走多少步能走到头
左偏树就是用这个保持左偏性质

以下是merge程序 这里是大根堆
[/cc lang = “cpp”]
int merge(int a, int b)
{
if (!a) return b;
if (!b) return a; //如果某个点为空 就返回另外一个点
if (t[a].v < t[b].v) swap(a, b); //以a为根 t[a].r = merge(t[a].r, b); //合并a.r和b if (t[t[a].l].dis < t[t[a].r].dis) swap(t[a].l, t[a].r); //如果左边的dis<右边的dis 那么就交换 这样可以保持左偏性质 t[a].dis = t[t[a].r].dis + 1; //更新dis return a; //返回根 } [/cc] 删除只能删除根 就是把根弄掉 然后合并左右子树 插入就是把一个只有一个点的树和原堆合并 合并就是合并了 一个性价比很高的数据结构 虽然他能做的 启发式合并平衡树都能做 但是代码复杂度不是一个级别。。

fft算法

fft(快速傅里叶变换)是可以在nlogn时间计算向量卷积的算法
向量卷积即计算向量f
f[i] = Σ(g[k] * h[i – k])
对于一个普通的算法 需要用n^2的时间进行计算

fft的思想是对于一个n元向量g 可以表示为n-1次多项式
这个多项式在x=1时=g[1], x=2时=g[2]….
其实两个向量的卷积 就是这两个多项式的乘积
对于一个k次多项式 需要k+1个点就可以确定
我们把g和h转为点值表示 并对他们的y值分别数乘 就可以得到f的点值表示
然后把点值表示的f转换为多项式形式 就可以得出f[]
但是注意到把多项式转为点值表示 及把点值表示转换为多项式表示都需要O(n^2)的时间
而中间的数乘步骤只需要O(n)

fft主要是解决在O(nlogn)的时间对多项式和点值的互换
先解决把多项式转为点值表示
现在要把g转为点值表示 设g为l-1次多项式 且l=2^n(如不足可以补0)
先选取采样点 我们选取e^(2πi/l * j) 其中i为sqrt(i), e为自然对数
因为:
1.e^(ix)=cosx+isinx
2.当x=π时,得到欧拉恒等式 e^(iπ)=-1 ==> e^(2iπ)=1
我们称wn=e^(2iπ/n)为n次单位复根
因为wn^n = 1
复平面上的N次单位复根N条半径可以理解为等分一个半径为1的圆
g(x) = a1 + a2x + a3x^2 + … + anx^(n-1)

g0(x) = a1 + a3x + a5x^2…
g1(x) = a2 + a4x + a6x^2…

可以发现
g0(x^2) = a1 + a3x^2 + a5x^4….
g1(x^2) = a2 + a4x^2 + a6x^4….
=>g(x) = g0(x^2) + x * g1(x^2)
设g[i][j] = g(e^(2iπ/(2^i) * j))

我们要求的是g[n][j] 这就是以wn^j为x的对应的y值 即g的点值表示
g[n][j] = g[n – 1][j] + wn^j * g[n – 1][j + (1 << (n - 1))] g[n][j + (1 << (n - 1))] = g[n - 1][j] - wn^j * g[n - 1][j + (1 << (n - 1))] (0~(1 << (n - 1))为g0 ((1 << (n - 1)) ~ (1 << n)) 为g1 证明: g[n][j] = g[n - 1][j] + wn^j * g[n - 1][j + (1 << (n - 1))]: 对于g[n - 1] wn[n - 1] = wn[n]^2 (指数为1/2) 所以g[n - 1][j] = g0(j^2)... g[n][j + (1 << (n - 1))] = g[n - 1][j] - wn^j * g[n - 1][j + (1 << (n - 1))]: 对于n - 1 只要(1 << (n - 1))就是一个循环 所以g0(j + (1 << (n - 1))) = g0(j) 有wn^j = -wn^(j + (1 << (n - 1))) 所以成立 关于非递归 就是直接从g[0]开始做 可以发现g[0][i] = a[bitre(i)] bitre(i) = 把i的二进制位翻转 然后推上去即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void fft(complex y[], const complex a[], int n)
{
  int len = 1 << n;
  for (int i = 0; i < len; ++i) y[i] = a[bitre(i, n)];
  for (int i = 1; i <= n; ++i)
  {
    int d = 1 << i;
    complex wn = complex(cos(2 * pi / d), sin(2 * pi / d));
    for (int j = 0; j < len; j += d)
    {
      complex w = complex(1, 0);
      for (int k = j; k < j + d / 2; ++k)
      {
        complex t = y[k], p = y[k + d / 2] * w;
        y[k] = t + p, y[k + d / 2] = t - p;
        w = w * wn;
      }
    }
  }
}

这样就求出了g和h的点值表示 数乘后进行ifft
可以证明 只要把上面程序改为以下即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void fft(complex y[], const complex a[], int n, int v)
{
  int len = 1 << n;
  for (int i = 0; i < len; ++i) y[i] = a[bitre(i, n)];
  for (int i = 1; i <= n; ++i)
  {
    int d = 1 << i;
    complex wn = complex(cos(2 * pi / d * v), sin(2 * pi / d * v));
    for (int j = 0; j < len; j += d)
    {
      complex w = complex(1, 0);
      for (int k = j; k < j + d / 2; ++k)
      {
        complex t = y[k], p = y[k + d / 2] * w;
        y[k] = t + p, y[k + d / 2] = t - p;
        w = w * wn;
      }
    }
  }
  if (v == -1)
    for (int i = 0; i < len; ++i) y[i].real /= len;
}

v传入1为转点值
v传入-1为ifft

以下是bzoj2194

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const int maxn = 1010000;
const double pi = acos(-1);
 
struct complex
{
  double real, imag;
  complex(double r = 0, double i = 0) : real(r), imag(i) {}
}a[maxn], b[maxn], t1[maxn], t2[maxn], ans[maxn];
 
complex operator+(complex a, complex b) { return complex(a.real + b.real, a.imag + b.imag); }
complex operator-(complex a, complex b) { return complex(a.real - b.real, a.imag - b.imag); }
complex operator*(complex a, complex b) { return complex(a.real * b.real - a.imag * b.imag, a.real * b.imag + a.imag * b.real); }
 
int n, m, len, l;
 
int bitre(int a, int n)
{
  int ans = 0;
  for (int i = 0; i < n; ++i)
    ans += (1 << i) * ((a & (1 << (n - i - 1))) ? 1 : 0);
  return ans;
}
void fft(complex y[], complex a[], int n, int rev)
{
  int len = 1 << n;
  for (int i = 0; i < len; ++i) y[i] = a[bitre(i, n)];
  for (int i = 1; i <= n; ++i)
  {
    int d = 1 << i;
    complex wn = complex(cos(2 * pi / d * rev), sin(2 * pi / d * rev));
    for (int j = 0; j < len; j += d)
    {
      complex w = complex(1, 0);
      for (int k = j; k < j + d / 2; ++k)
      {
        complex t = y[k], p = y[k + d / 2] * w;
        y[k] = t + p, y[k + d / 2] = t - p;
        w = w * wn;
      }
    }
  }
  if (rev == -1)
    for (int i = 0; i < len; ++i) y[i].real /= len;
}
 
int main()
{
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    scanf("%lf%lf", &a[n - i - 1].real, &b[i].real);
  for (; (1 << l) <= n * 3; ++l);
  len = 1 << l;
  fft(t1, a, l, 1);
  fft(t2, b, l, 1);
  for (int i = 0; i < len; ++i) t1[i] = t1[i] * t2[i];
  fft(ans, t1, l, -1);
  for (int i = n - 1; i >= 0; --i) printf("%d\n", (int)floor(ans[i].real + 0.5));
}

后缀自动机小结②

【cxjyxx_me是个大沙茶 他连后缀自动机这个pj算法都不会。。】
后缀自动机的应用 我觉得最重要的是要知道这些性质:
①所有的子串都能由起始点走到
②加入前缀#后 在fail树上的叶子代表串各不相同 且共同组成串s的所有前缀
③从起始点走到所有”接受态点”的所有路径各不相同 且共同构成串s的所有后缀
[注:所谓接受态点 即last点及其所有祖先 即 last t[last].f t[t[last].f].f……..]

知道这几个性质感觉就所向披靡了~~
这里就讲一下clj课件里提到的题目吧<这些题我大多没写过。。只是讲下思路>
——————————–
最小循环串

给一个字符串S,每次可以将它的第一个字符移到最后面,求这样能得到的字典序最小的字符串。
——————————-
好吧这里的题目是直接copyCLJ的课件的。。所以字体有点奇葩、、 不要在意细节~~
这题其实是后缀数组的题啊= =
只要把s copy一个接在s的后面
求出最小的 起始点<=原s的length的后缀
这里顺便讲下怎么用sam线性构造sa吧
其实很简单 做一次dfs 对于一个节点 从它的ch[0]开始循环即可
然后如果到达一个接受态点即可吧当前串(可以用这个串的长度表示) 加入sa[]数组
因为按这样的循环方式进行dfs可以保证串的值是递增的 这个很显然
最后就可以得到sa数组了~
线性!
——————————-

SPOJ NSUBSTR
给一个字符串S,令F(x)表示S的所有长度为x的子串中,出现次数的最大值。求F(1)..F(Length(S))

——————————-
在fail树上 我们定义叶子节点的权值为1 其他节点权值为0
对于一个节点所代表串的出现次数就是以这个节点为根的子树权值和
为什么是这样呢?
我们知道每个叶子代表了一个前缀
且对于一个节点的代表串 一定是其子孙节点代表串的后缀
那么他的子孙中有几个是前缀就代表了这个节点的代表串出现了几次
然后对于每个节点i 用它的子树权值和去更新F(t[i].l)
最后再用每个F(i) 去更新F(i – 1)即可
为什么是对的?
这不是很显然么= =
一个长度是k的串出现了x次 那么它的长度为1~k的子串一定最少也可以出现x次- –
——————————-
BZOJ2555 SubString
——————————-
【因为这题是bzoj的 所以我有做(毫无节操- -)、后面的题解会写 这里就不写了】
——————————-
SPOJ SUBLEX
给一个长度不超过90000的串S,每次询问它的所有不同子串中,字典序第K小的,询问不超过500个。
———————————-
我们知道sam从起点开始走
可以走到所有子串
对于一个点i 它能走到的节点个数(一个节点以不同路径被走两次算两次)就代表了以它为前缀的子串个数
所以我们可以求出所有i的能走到的节点个数 记在num数组里
如果num[t[i].ch[0]] >= k那么就走到t[i].ch[0]否则k-= num[t[i].ch[0]] 然后循环下一个ch[1]
这个过程可以类比在平衡树上找k大
———————————-
还有两题LCS就不写了 【太难了不能直视(大雾】
END
然后等等放几题我刷的题的题解。。

后缀自动机小结①

【cxjyxx_me是个大沙茶 他连后缀自动机这个pj算法都不会。。】
后缀自动机。。
这个算法我看了<仅是看 没包括写> 近一个星期= =
肯定是我太沙茶了=、=
先推荐几篇文章吧,,

①显然是clj的论文                              《陈立杰营员交流资料.pptx》
②后缀自动机初窥                                http://blog.sina.com.cn/s/blog_7812e98601012cim.html
③后缀自动机与线性构造后缀树          http://fanhq666.blog.163.com/blog/static/8194342620123352232937/

④后缀自动机(FHQ+Neroysq补完)   http://hi.baidu.com/myidea/item/142c5cd45901a51820e25039
⑤后缀自动机的应用                            http://blog.sina.com.cn/s/blog_7812e98601012dfv.html

因为我太弱了、  用了一个星期的时间吧他们每个至少看了三遍才大概理解sam(Suffix Automaton)..<其实好像还是不是很理解。。>

先说下我对后缀自动机的理解吧。。(其实只是阐述一些性质。。)
如果说AC自动机可以识别所有前缀 那么 后缀自动机则可以识别所有子串!
也就是从s的sam的根开始走
走到每一个节点的路径形成的字符串各不相同
且构成了串s的所有子串!<=这个性质很科学有木有~

用fail指针构成的树就是一棵后缀树 (其实是前缀树。。但是用起来没什么差)

构造的时间复杂度根据势能分析是线性 (势能分析是什么? 我怎么知道。。。)

然后我们要做得就是构造一个满足这些性质的图。。。<恕我沙茶的理解。。>

先给一个串aabbab的sam图
psb (44)

(蓝边代表fail指针)
一个节点代表的字符串集为从s到这个点的所有路径集合
可以发现对于一个节点 他代表的串集在s上区间如下
[l, r]
[l + 1, r]
[l + 2, r]

[l + k, r]
如节点4 他代表的字符串集:
[1, 4] = aabb
[2, 4] = abb
[3, 4] = bb
这里定义min和max为l的取值区间
如 min[4] = 1, max[4] = 3
定义right为r
如right[4] = 4

介绍一下fail指针
对于fail[u]=v
有right[u] = right[v], max[u] + 1 = min[v]
可以类比kmp里的fail数组
就是fail[u]就是跟u的后面一坨一样的点
如fail[4]=5
5代表
[4, 4] = b

这样我们发现fail构出了一颗”前缀树”
和后缀树相同 为了使每个前缀都是叶子节点 我们不妨在串s前加入一个没出现的字符’#’
这里为了配合上面的图 就不加这个#了 下面给出串aabbab按fail构出的前缀树
psb (47)
(红色为路径上的值 蓝色为从根到这个点 经过的路径串拼起来 即为点的值 注意 这里的拼起来是往前加。。 看一下应该能理解)

如果加上#的话 就会有这样一个性质:每个叶子都不一样 且构出所有前缀
而#并不影响sam的构造

构造一个sam 我们要知道一个结构体:
struct node
{
int l, f, ch[26];
}t[maxn];

其中
l表示 这个点代表的字符串集里最长的长度
f表示 fail指针
至于ch数组 在fail树上不妨这样理解:
对于t[i].ch[j] 定义串k为i这个节点代表的最长串后面加入字符j所得的字符串
t[i].ch[j]是一个以k为后缀(严格包含  即len[k] <= t[t[i].ch[j]].l)的l值最小的节点
比如ch[ab]在aab和aaab中会选aab
看下这个图吧。。 有点乱。。。
psb (50)

sam的构造方法是逐个字符添加 也就是说你在添加第i个字符时 1~i-1个字符的sam已经建立了
现在考虑怎么在这个以建立的sam上添加一个字符
这里记录一个变量last 表示上次添加的节点是哪个 比如这个sam的last=7

现在考虑在这个sam上添加一个字符b 即新加入一个值为aabbabb的节点
他应该找到一个是他的后缀的节点作为他的父亲节点 然后插入进去
怎么找这个呢?
如果t[last].ch[‘b’]有节点 那么就是他了
不然就是
t[t[last].f].ch[‘b’]
t[t[t[last].f].f].ch[‘b’]
…..(即last的一堆祖先).ch[‘b’]
直到找到一个ch[‘b’]是有节点的。。
另外要把一路上的last, t[last].f, t[t[last].f].f…的ch[‘b’]都设为now (now为新节点编号)
如果一直到根 连根的ch[‘b’]都没有节点 那就直接把t[now].f设为根
否则对于一个节点p他有ch[‘b’] 设c=t[p].ch[‘b’] (如图p=8 c=4)
如果c是now的后缀 那就喜闻乐见直接把now的fail设为c就可以了
否则 可以知道的是c和now共享长度为t[p].l + 1的后缀
那么就新建一个节点r 表示这个被共享的后缀
再把now和c都弄成r的儿子即可~(即把t[now].f和t[c].f赋为r)
然后还要把所有p及祖先的ch[‘b’]==c的ch[‘b’]全部赋为r(满足l最小定理)
这样就完成了一次添加操作。。
然后把整个字符串一个个加进来就行了。。。
代码如下:
—————————————-

void add(int k, int len)
{
  int now = ++l, p = last;
  last = now;
t[now].l = len;
  for (; p && !t[p].ch[k]; p = t[p].f) t[p].ch[k] = now;   //找到ch[k]不为空的节点 且边把路上的节点的ch[k]赋为now
  if (!p) t[now].f = 1;
  else
    if (t[t[p].ch[k]].l == t[p].l + 1) t[now].f = t[p].ch[k];
    else
    {
      int c = t[p].ch[k], r = ++l;
      t[r] = t[c];
      t[r].l = t[p].l + 1;
      t[now].f = t[c].f = r;
      for (; p && t[p].ch[k] == c; p = t[p].f) t[p].ch[k] = r;   //可以证明对于某个节点到根的路径上的点的ch[k]值 一样的一定连续
    }

}
———————————————
好像比我的sa短了一行。。难道不是莫大的讽刺?=、=
终于写完了。。 写得好像有点略乱= =
题目、应用什么的明天再说吧。。 有点晚了- –

后缀数组小结②

【cxjyxx_me是个大沙茶 他连后缀数组这个pj算法都不会。。】
h[i]      表示sa[i]和sa[i – 1]的最长公共前缀

O(n^2)的朴素就很傻×了
但是按lsq的话说  这 样 做 并 没 有 利 用 字 符 串 的 性 质 。
可以证明(论文里。。)
h[i] >= h[i – 1] – 1
所以只要按0~n-1的顺序求h值就可以达到O(n)的时间出解
void get_h(int n)
{
  for (int i = 0; i < n; ++i) rank[sa[i]] = i;
  for (int i = 0, k = 0; i < n; h[rank[i++]] = k)
  if (rank[i])
    for (k = k ? k – 1 : 0; s[i + k] == s[sa[rank[i] – 1] + k]; ++k);
  else k = 0;
}

h[i]      表示sa[i]和sa[i – 1]的最长公共前缀
rank[i] 表示第i个后缀的rank值
这个代码貌似就没什么好解释的了了。。
就是比lsq的代码多判了一个rank
因为的的sa下标是从0开始、
————————————
另附一个预处理方法
o(nlogn)的预处理 可以在O(1)查询任意两个后缀的最长公共前缀
dp[i][j]  表示从h[i]开始的1<<j个h值的min
这个可以nlogn求出来

然后要求h[l]~h[r]的最小值时
设k为floor(log_2(r – l))
最小值为min(dp[l][k], dp[r – (1 << k)][k])
这只是思路 具体下标好像有点不一样、、
———————应用———————-
这些基本就是概述下论文里的应用了。。

最长公共前缀
min(h[rank[l]+1]~h[rank[r]])
可重叠最长重复子串
h数组max值
不可重叠最长重复子串
二分长度 可以用mid把h数组分成好几块
如果在一块中出现两个坐标绝对值>=mid则返回true
可重叠的最长重复k次子串
     二分长度 分块后如果有一块元素个数>=k个则返回true
不相同的子串的个数
按rank值从小到大循环后缀
考虑一个后缀对不同子串的贡献是len-h[i]
最长回文子串
把s翻转后接接在s串后面 中间要加一个没出现过的字符作为分隔
考虑以第i个字符为中心的回文串长度即为后缀i和后缀len-i的最长公共前缀
奇数偶数都要考虑
奇偶使用的后缀是不一样的
连续重复子串
枚举长度为i 考虑后缀0和后缀i的最长公共前缀 可以在预处理后O(1)判断是否合法
重复次数最多的连续重复子串
枚举这个子串的长度为L
那么这个子串必定包含0, L*1, L* 2, …, L*m
枚举这几个位置
求出 L * i 和 L*(i + 1)  的最长公共前缀和最长公共后缀
设长度为k 则重复了k/L+1次 更新ans

2串最长公共子串
把第二个串接到第一个串后面 并在中间加入一个没出现的分隔符
求出sa和h后
枚举第一个串的每一位
如果sa[rank[i] + 1]是第二个串的后缀 则可以用h[rank[i + 1]]更新答案
如果sa[rank[i] – 1]是第二个串的后缀 则可以用h[rank[i ]]更新答案

长度不小于 k 的公共子串的个数
这个也是用h数组乱搞一下就行了 由于我对这题的定义不是很理解 就不写了。。
不小于 k 个字符串中的最长子串
对于多字符串问题 一般的处理方法是把所有字符串连接起来并每两个间用不一样的字符隔开
二分长度 对h分块 如果一块中出现k个字符串则返回true
每个字符串至少出现两次且不重叠的最长子串
二分长度 如果一块对每个字符串都出现了坐标绝对值>=mid的两个后缀 则返回true

出现或反转后出现在每个字符串中的最长子串
二分长度 如果一块对每个字符串都出现了后缀或反转后的后缀 则返回true
————————————————
终于写完了=、=。。 还有写的一些题目 放在后几篇吧- -‘

后缀数组小结①

【cxjyxx_me是个大沙茶 他连后缀数组这个pj算法都不会。。】
后缀数组其实就是一个用O(nlogn) 甚至O(n)(好像一般只用nlogn的)的时间求出一个字符串的所有后缀的排序顺序的算法
由于cxjyxx_me过于沙茶 以至于他直到3天前还不会这个算法。。<后缀数组推荐看lsq论文《后缀数组——处理字符串的有力工具》>
求出排序顺序后 还是不能很好的解决很多问题 所以又引入了h数组这个东西
h[i]表示第i名的后缀和第i-1名的后缀的最长公共前缀
可以用O(n)的时间求出 具体求法==再说、
先说nlogn求出排序顺序的方法吧,,
基本思想是倍增
对于第j次比较
以第i个字符开头的后缀只考虑s[i]s[i + 1]…s[i + (1 << j)]这个串
求出所有i的rank后
对于下一个++j
第i个字符开头的后缀的value就相当于是一个二元组(rank[i], rank[i +(1 << j – 1)])
在对每个i关于各自的二元组求出新的rank。。。
如果每次求rank是O(n)
显然整体复杂度最多O(nlogn)
那么怎么用O(n)求出每次的rank值呢?
其实要是只要求nlogn的方法就很显然了- – 直接双关键字排序就行了。。 这个程序后面会贴
O(n)的算法主要是用了基数排序
它先对第二关键字排序
然后就能保证在第一关键字相同时它们是按第二关键字排序的

怎么用基数排序做稳定排序呢?
记录基数数组cnt的前缀和
倒着循环 对于第i个数 可以知道第–cnt[v[i]]名是i
这样如果下次再出现v值跟这个v[i]一样的时候 他就会是前一名~

然后每次再把各自的rank作为新的value

先贴一个程序吧。
bool same(int a, int b, int j) { return t[a] == t[b] && t[a + j] == t[b + j]; }

void get_sa(int n, int m)
{
  for (int i = 0; i < n; ++i) ++cnt[v[i] = s[i]];
  for (int i = 1; i < m; ++i) cnt[i] += cnt[i – 1];
  for (int i = n – 1; i >= 0; –i) sa[–cnt[v[i]]] = i;
  for (int j = 1, p = 1, i; p < n; j <<= 1, m = p)
  {
    for (i = n – j, p = 0; i < n; ++i) sa_t[p++] = i;
    for (i = 0; i < n; ++i) if (sa[i] >= j) sa_t[p++] = sa[i] – j;
    for (i = 0; i < m; ++i) cnt[i] = 0;
    for (i = 0; i < n; ++i) ++cnt[v_t[i] = v[sa_t[i]]];
    for (i = 1; i < m; ++i) cnt[i] += cnt[i – 1];
    for (i = n – 1; i >= 0; –i) sa[–cnt[v_t[i]]] = sa_t[i], t[i] = v[i];
    for (i = 1, v[sa[0]] = 0, p = 1; i < n; ++i)
      v[sa[i]] = same(sa[i], sa[i – 1], j) ? p – 1 : p++;
  }
}

lsq的程序的一些地方太高端洋气了。。我就自己改了一点(我不会说我从来没写过指针、= =)
解释下数组

cnt 是基数数组
sa[i] 表示第i名是谁(这的是谁是指以第几个字符开头的后缀)
sa_t[i] 第二关键字第i名的是哪个
v[i] 就是value 也是上次的rank值
v_t[i] 表示第二关键字第i名的第一关键字的值
t 数组是存放v值 只用于same函数里面的比较

分段来解释吧

  for (int i = 0; i < n; ++i) ++cnt[v[i] = s[i]];
  for (int i = 1; i < m; ++i) cnt[i] += cnt[i – 1];
  for (int i = n – 1; i >= 0; –i) sa[–cnt[v[i]]] = i;
这个相当于求出j=0时的sa和v要预处理 (v值 即 rank值 可以离散 这没有影响)
———————————————————————————-
    for (i = n – j, p = 0; i < n; ++i) sa_t[p++] = i;

    for (i = 0; i < n; ++i) if (sa[i] >= j) sa_t[p++] = sa[i] – j;
求出第二关键字的sa值
可以发现n-j ~ n-1这几个后缀是没有第二关键字的 就当是0
然后按rank从小到大循环
如果一个后缀可以是某个后缀的第二关键字 就可以把那个后缀加入sa_t
———————————————————————————-

    for (i = 0; i < m; ++i) cnt[i] = 0;
    for (i = 0; i < n; ++i) ++cnt[v_t[i] = v[sa_t[i]]];
    for (i = 1; i < m; ++i) cnt[i] += cnt[i – 1];
    for (i = n – 1; i >= 0; –i) sa[–cnt[v_t[i]]] = sa_t[i], t[i] = v[i];
跟第一段差不多 就是要清空cnt数组
还有这句

for (i = n – 1; i >= 0; –i) sa[–cnt[v_t[i]]] = sa_t[i], t[i] = v[i];
可能比较难理解
其实就是按第二关键字从大到小循环加入sa
可以发现后循环到的后缀(即第二关键字比较小的后缀) 在第一关键字相同时会被放在前面
还有就是顺便把t数组赋了下值
———————————————————————————-

    for (i = 1, v[sa[0]] = 0, p = 1; i < n; ++i)
      v[sa[i]] = same(sa[i], sa[i – 1], j) ? p – 1 : p++;
求出新的v值长得比较不科学的就是那个三目操作符
其实就是判断下是不是有rank值相等的情况
———————————————————————————-
可以发现如果rank值都不一样就说明找出了ans 此时p会=n
否则也可以发现行的v数组的数值上限变为p
所以就有了外面这个循环:

for (int j = 1, p = 1, i; p < n; j <<= 1, m = p)
———————————————————————————-
看下直接用双关键字排序做得程序吧。。

bool cmp(int a, int b) { return v[a] < v[b] || (v[a] == v[b] && v[a + k] < v[b + k]); }
bool same(int a, int b, int j) { return t[a] == t[b] && t[a + j] == t[b + j]; }
void get_sa(int n)
{
  for (int j = 0, p = 1, i; p < n; j = !j ? 1 : (j << 1),k = j)
  {
    for (i = 0; i < n; ++i) sa[i] = i, t[i] = v[i];
    sort(sa, sa + n, cmp);
    for (i = p = 1, v[sa[0]] = 0; i < n; ++i)
      v[sa[i]] = same(sa[i], sa[i – 1], j) ? p – 1 : p++;
  }
}

是不是有种呵呵的感觉?~
那就呵呵吧、
这个的复杂度是O(n*log(n)^2 )
我不会说我昨天晚上写一题写到12点
最后发现t了 TAT
然后发现他的范围是50w,,,
就改成nlogn的算法。。
9.3s险过。。
———————————————————————————-
然后h数组的求法和后缀数组的一些应用扔到下一篇写吧。。

网络流小结②

负权环的处理。。
这是个比较蛋疼的东西。。
其实也不是很蛋疼。。
不过。。
按队长的话说。。
如果你建的图出现负环 那一般就是你建错图了 或可以避免。。
但是那是一般。。
so。。
而且处理负环的这个思想十分的重要。。
这几天我唯一没有想出来的(其他题 至少网络流的部分想出来了。。)就是这个思想。。
其实也不叫思想吧。。
网络流的性质啊。。
noi2008 志愿者招募。。
流量平衡。。
呵呵。。
呵。。
。。

好吧不蛋疼了- –
处理负环的思想就是先把负权边满流 类似上下界流处理下界 不同的是这个在流后要加反向容量
这样会有一些点不满足流量平衡 设vi = 流入点i流量-点i流出流量为

然后建一个超级源 对所有vi>0的点连边 容量为vi
建一个超级汇 对所有vi<0的点连边 容量为-vi
以超级源为源 以超级汇为汇 跑一次最大流 然后剩余网络就是满足没有负费用环的图
直接跑费用流即可
这个操作称为退流

另外退流还可以解决有上下界的网络流问题
对于一条边有上下界的边 改为只有上界 为原上界-下界
建超级源汇的操作一样
称这个新网络为附加网络

① 有源汇的上下界最大流
1.构造附加网络

     2.对ss、tt求最大流(ss、tt满流则有解)
     3.若有解,对s、t求最大流 即为ans
② 有源汇的上下界最小流
1.构造附加网络
2.加边(t, s, inf)
3.对ss、tt求最大流
4.满流即有解 解为t, s边的流量
③ 无源汇的上下界最大最小流

最大:
1.构造附加网络
2.加边(t, s, l, inf)(是有上下界的边)
3.二分l
4.用最大流是否满流判断是否有解

最小:
更最小差不多 就是把加边改成(t, s, 0, r) 然后二分r 判定

———————————–
一共A了6、7题还是多少的 题解放在下篇

网络流小结①

其实网络流去年就刷了很多题 感觉也还不错
但是因为去年刷完网络流专题不知道为什么后面就一直没刷到网络流的题
导致noi那题水爆了的网络流(比起其他题= =)都没做出来!!!
唉╮(╯▽╰)╭
so这几天刷了一些网络流题目
也在和队长的交流(单方面询问。。 在这感谢下队长~)中学了一点东西
一个是zkw费用流 还有强制满流处理负费用环 退流使之达到流量收支平衡 也可以处理上下界流的问题

在这里做一个小结<这里只放zkw 剩下到下篇吧。。>
————————–zkw费用流————————
这个算法我去年看了一下 感觉好像很碉堡 又看不懂 今年在队长的讲解后终于懂了。。
它的思想就是先用一次spfa处理出每个点的dist值 再用sap的多流增广去增广
另附spfa三个优化
①(这个只针对于zkw费用流)正常的求dist是求离s的dist 但是如果求对t的dist会更快
这看似挺科学的 因为你在sap的时候是从s开始增广 如果是求对t的dist 就会有很对点的dist是inf 可以省一点时间
②SLF(Small Label First  ) 优化:思想是把spfa原来的单纯队列环成双端队列
每次插入元素时 比较新元素和当前队首元素的dist 如果新dist<队首dist 就插在队首 否则插在队尾
③LLL(Large Label Last)优化:思想是对于一个将被松弛的节点 如果它的dist > 平均dist 就把它扔到队尾 以后再松弛
直到有一个节点的dist<=平均dist 就进行松弛

因为③比较难打(其实就多了10多行吧 就是写起来比较蛋疼= = 后面有两个的程序) 所以一般只用①② 如果被卡了就上③吧。。

然后直接上程序吧。。
————–spfa(①②③)———–

int spfa()
{
  memset(dist, 0x7f, sizeof(dist));
  memset(b, 0, sizeof(b));
  q.push_front(t);
  dist[t] = 0;
  b[t] = 1;
  int sum = 0;
  while (!q.empty())
  {
    int now = q.front();
    while (dist[now] * q.size() > sum)
    {
      q.pop_front();
      q.push_back(now);
      now = q.front();
    }
    q.pop_front();
    sum -= dist[now];
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (!li[li[i].opt].v || dist[to] <= dist[now] – li[i].c) continue;
      if (b[to])
      {
        sum -= dist[to];
        dist[to] = dist[now] – li[i].c;
        sum += dist[to];
      }
      else
      {
        dist[to] = dist[now] – li[i].c;
        sum += dist[to];
        b[to] = 1;
        if (q.empty() || dist[to] < dist[q.front()]) q.push_front(to);
        else q.push_back(to);
      }
    }
    b[now] = 0;
  }
  return dist[s];

}

//41行
—————spfa(①②)———–

int spfa()
{
  memset(dist, 0x7f, sizeof(dist));
  memset(b, 0, sizeof(b));
  q.push_front(t);
  dist[t] = 0;
  b[t] = 1;
  while (!q.empty())
  {
    int now = q.front();
    q.pop_front();
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (!li[li[i].opt].v || dist[to] <= dist[now] – li[i].c) continue;
      dist[to] = dist[now] – li[i].c;
      if (!b[to])
      {
        b[to] = 1;
        if (q.empty() || dist[to] < dist[q.front()]) q.push_front(to);
        else q.push_back(to);
      }
    }
    b[now] = 0;
  }
  return dist[s];

}
//26行
——————–sap——————-

int sap(int now, int maxf)
{
  if (now == t) return maxf;
  int tot = 0;
  b[now] = 1;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (!b[to] && dist[to] == dist[now] – li[i].c && li[i].v)
    {
      int t = sap(to, min(maxf – tot, li[i].v));
      li[i].v -= t;
      li[li[i].opt].v += t;
      tot += t;
    }
  }
  return tot;
}

—————–ZKE_CF—————
int ZKW_CF()

{
  int ans = 0, m;
  while (spfa() != inf)
    while (m = sap(s, inf))
    {
      memset(b, 0, sizeof(b));
      ans += m * dist[s];
    }
  return ans;
}