structure.cpp

ACM经典算法ACM经典算法ACM经典算法

	int i, j, len, na;
	na = (n < 256 ? 256 : n);
	memset(top, 0, na * sizeof(int));
	for (i = 0; i < n ; i++) top[ rank[i] = s[i] & 0xff ]++;
	for (i = 1; i < na; i++) top[i] += top[i - 1];
	for (i = 0; i < n ; i++) sa[ --top[ rank[i] ] ] = i;
	for (len = 1; len < n; len <<= 1) {
		for (i = 0; i < n; i++) {
			j = sa[i] - len; if (j < 0) j += n;
			tmp[ top[ rank[j] ]++ ] = j;
		}
		sa[ tmp[ top[0] = 0 ] ] = j = 0;
		for (i = 1; i < n; i++) {
			if (rank[ tmp[i] ] != rank[ tmp[i-1] ] ||
				rank[ tmp[i] + len ] != rank[ tmp[i-1] + len ])
				top[++j] = i;
			sa[ tmp[i] ] = j;
		}
		memcpy(rank, sa , n * sizeof(int));
		memcpy(sa  , tmp, n * sizeof(int));
		if (j >= n - 1) break;
	}
}
void lcp()                          // O(4 * N)
{
	int i, j, k;
	for (j = rank[ height[i = k = 0] = 0 ]; i < n - 1; i++, k++)
		while (k >= 0 && s[i] != s[ sa[j-1] + k ])
			height[j] = (k--), j = rank[ sa[j] + 1 ];
}
/*============================================================*\
 | 后缀数组 O(N)                                              |
 | INIT: n = strlen(s) + 1;                                   |
 | CALL: makesa()求sa[];                                      |
\*============================================================*/
char s[N];
int n, sa[4*N], rank[N], height[N];
int buf[4*N], ct[N], sx[N], sax[N];

inline bool leq(int a, int b, int x, int y)
{ return (a < x || a == x && b <= y); }
inline bool leq(int a, int b, int c, int x, int y, int z)
{ return (a < x || a == x && leq(b, c, y, z)); }
inline int geti(int t, int nx, int sa[])
{ return (sa[t]<nx ? sa[t]*3+1 : (sa[t]-nx)*3+2); }

static void radix(int a[], int b[], int s[], int n, int k)
{   // sort a[0..n-1] to b[0..n-1] with keys in 0..k from s
	int i, t, sum;
	memset(ct, 0, (k + 1) * sizeof(int));
	for (i = 0; i < n;  ++i) ct[s[a[i]]]++;
	for (i = 0, sum = 0; i <= k;  ++i) {
		t = ct[i]; ct[i] = sum; sum += t;
	}
	for (i = 0; i < n; i++) b[ct[s[a[i]]]++] = a[i];
}
void suffix(int s[], int sa[], int n, int k)
{	// !!! require s[n] = s[n+1] = s[n+2] = 0, n >= 2.
	int i, j, e, p, t;
	int name = 0, cx = -1, cy = -1, cz = -1;
	int nx = (n+2)/3, ny = (n+1)/3, nz = n/3, nxz = nx+nz;
	int *syz = s + n + 3, *sayz = sa + n + 3;

	for (i=0, j=0;  i < n + (nx - ny);  i++)
		if (i%3 != 0) syz[j++] = i;
	radix(syz , sayz, s+2, nxz, k);
	radix(sayz, syz , s+1, nxz, k);
	radix(syz , sayz, s  , nxz, k);
	for (i = 0;  i < nxz;  i++) {
		if (s[ sayz[i] ] != cx || s[ sayz[i] + 1 ] != cy ||
			s[ sayz[i] + 2 ] != cz) {
			name++;  cx = s[ sayz[i] ];
			cy = s[ sayz[i] + 1 ];  cz = s[ sayz[i] + 2 ];
		}
		if (sayz[i] % 3 == 1) syz[ sayz[i] / 3 ] = name;
		else syz[ sayz[i]/3 + nx ] = name;
	}
	if (name < nxz) {
		suffix(syz, sayz, nxz, name);
		for (i = 0; i < nxz;  i++) syz[sayz[i]] = i + 1;
	} else {
		for (i = 0; i < nxz;  i++) sayz[syz[i] - 1] = i;
	}
	for (i = j = 0; i < nxz;  i++)
		if (sayz[i] < nx) sx[j++] = 3 * sayz[i];
	radix(sx, sax, s, nx, k);
	for (p=0, t=nx-ny, e=0;  e < n;  e++) {
		i = geti(t, nx, sayz); j = sax[p];
		if ( sayz[t] < nx ?
			 leq(s[i], syz[sayz[t]+nx], s[j], syz[j/3]) :
			 leq(s[i], s[i+1], syz[sayz[t]-nx+1],
				 s[j], s[j+1], syz[j/3+nx]) ) {
				sa[e] = i;
				if (++t == nxz) {
					for (e++; p < nx; p++, e++) sa[e] = sax[p];
				}
		} else {
			sa[e] = j;
			if (++p == nx) for (++e; t < nxz; ++t, ++e)
				sa[e] = geti(t, nx, sayz);
		}
	}
}
void makesa()
{
	memset(buf, 0, 4 * n * sizeof(int));
	memset(sa, 0, 4 * n * sizeof(int));
	for (int i=0; i<n; ++i)
		buf[i] = s[i] & 0xff;
	suffix(buf, sa, n, 255);
}
/*============================================================*\
 | RMQ离线算法 O(N*logN)+O(1)                                 |
 | INIT: val[]置为待查询数组; initrmq(n);                     |
\*============================================================*/
int st[20][N], ln[N], val[N];
void initrmq(int n)
{
	int i, j, k, sk;
	ln[0] = ln[1] = 0;
	for (i = 0; i < n; i++) st[0][i] = val[i];
	for (i = 1, k = 2; k < n; i++, k <<= 1) {
		for (j = 0, sk = (k >> 1); j < n; ++j, ++sk) {
			st[i][j] = st[i-1][j];
			if (sk < n && st[i][j] > st[i-1][sk])
				st[i][j] = st[i-1][sk];
		}
		for (j = (k>>1)+1; j <= k; ++j) ln[j] = ln[k>>1] + 1;
	}
	for (j = (k>>1)+1; j <= k; ++j) ln[j] = ln[k>>1] + 1;
}
int query(int x, int y) // min of { val[x] ... val[y] }
{
	int bl = ln[y - x + 1];
	return min(st[bl][x], st[bl][y-(1<<bl)+1]);
}
/*============================================================*\
 | LCS离线算法 O(E)+O(1)                                      |
 | INIT: id[]置为-1; g[]置为邻接矩阵;                         |
 | CALL: for (i=0; i<n; ++i) if (-1==st[i]) dfs(i, n);        |
 |     LCS转化为RMQ的方法: 对树进行DFS遍历, 每当进入或回溯到  |
 | 某个结点i时, 将i的深度存入数组e[]最后一位. 同时记录结点i在 |
 | 数组中第一次出现的位置, 记做r[i]. 结点e[i]的深度记做d[i].  |
 | LCA(T, u, v)，就等价于求E[RMQ(d, r[u], r[v])], (r[u]<r[v]).|
\*============================================================*/
int id[N], lcs[N][N], g[N][N];
int get(int i)
{
	if (id[i] == i) return i;
	return id[i] = get(id[i]);
}
void unin(int i, int j)
{
	id[get(i)] = get(j);
}
void dfs(int rt, int n) {   // 使用邻接表可优化为 O(E)+O(1)
	int i;
	id[rt] = rt;
	for (i = 0; i < n; ++i) if (g[rt][i] && -1 == id[i]) {
		dfs(i, n); unin(i, rt);
	}
	for (i = 0; i < n; ++i) if (-1 != id[i])
		lcs[rt][i] = lcs[i][rt] = get(i);
}
/*============================================================*\
 | 带权值的并查集                                             |
 | INIT: makeset(n);                                          |
 | CALL: findset(x); unin(x, y);                              |
\*============================================================*/
struct lset
{
	int p[N], rank[N], sz;
	void link(int x, int y) {
		if (x == y) return;
		if (rank[x] > rank[y]) p[y] = x;
		else p[x] = y;
		if (rank[x] == rank[y]) rank[y]++;
	}
	void makeset(int n) {
		sz = n;
		for (int i=0;i<n;i++) {
			p[i] = i; rank[i] = 0;
		}
	}
	int findset(int x) {
		if (x != p[x]) p[x] = findset(p[x]);
		return p[x];
	}
	void unin(int x, int y) {
		link(findset(x), findset(y));
	}
	void compress() {
        for (int i = 0; i < sz; i++) findset(i);
	}
};
/*============================================================*\
 | 快速排序                                                   |
\*============================================================*/
void ksort(int l, int h, int a[])
{
	if (h < l + 2) return;
	int e = h, p = l;
	while (l < h) {
		while (++l < e && a[l] <= a[p]);
		while (--h > p && a[h] >= a[p]);
		if (l < h) swap(a[l], a[h]);
	}
	swap(a[h], a[p]);
	ksort(p, h, a); ksort(l, e, a);
}
/*============================================================*\
 | 2台机器工作调度                                            |
\*============================================================*/
   2台机器, n件任务, 必须先在S1上做, 再在S2上做. 任务之间先做后
做任意. 求最早的完工时间. 这是一个经典问题: 2台机器的情况下有多
项式算法(Johnson算法), 3台或以上的机器是NP-hard的. Johnson算法:
(1)	把作业按工序加工时间分成两个子集,
    第一个集合中在S1上做的时间比在S2上少,
	其它的作业放到第二个集合.
	先完成第一个集合里面的作业, 再完成第二个集合里的作业.
(2)	对于第一个集合, 其中的作业顺序是按在S1上的时间的不减排列;
	对于第二个集合, 其中的作业顺序是按在S2上的时间的不增排列.
/*============================================================*\
 | 比较高效的大数                                             |
 | < , <= , + , - , * , / , %(修改/的最后一行可得)            |
\*============================================================*/
const int base = 10000;	   // (base^2) fit into int
const int width = 4;       // width = log base
const int N  = 1000;       // n * width: 可表示的最大位数
struct bint
{
	int ln, v[N];
	bint (int r = 0) {
		for (ln = 0; r > 0; r /= base) v[ln++] = r % base;
	}
	bint& operator = (const bint& r) {
		memcpy(this, &r, (r.ln + 1) * sizeof(int));  // !
		return *this;
	}
} ;
bool operator < (const bint& a, const bint& b)
{
	int i;
	if (a.ln != b.ln) return a.ln < b.ln;
	for (i = a.ln - 1; i >= 0 && a.v[i] == b.v[i]; i--);
	return i < 0 ? 0 : a.v[i] < b.v[i];
}
bool operator <= (const bint& a, const bint& b)
{
	return !(b < a);
}
bint operator + (const bint& a, const bint& b)
{
	bint res; int i, cy = 0;
	for (i = 0; i < a.ln || i < b.ln || cy > 0; i++) {
		if (i < a.ln) cy += a.v[i];
		if (i < b.ln) cy += b.v[i];
		res.v[i] = cy % base; cy /= base;
	}
	res.ln = i;
	return res;
}
bint operator - (const bint& a, const bint& b)
{
	bint res; int i, cy = 0;
	for (res.ln = a.ln, i = 0; i < res.ln; i++) {
		res.v[i] = a.v[i] - cy;
		if (i < b.ln) res.v[i] -= b.v[i];
		if (res.v[i] < 0) cy = 1, res.v[i] += base;
		else cy = 0;
	}
	while (res.ln > 0 && res.v[res.ln - 1] == 0) res.ln--;
	return res;
}
bint operator * (const bint& a, const bint& b)
{
	bint res; res.ln = 0;
	if (0 == b.ln) { res.v[0] = 0; return res; }
	int i, j, cy;
	for (i = 0; i < a.ln; i++) {
		for (j = cy = 0; j < b.ln || cy > 0; j++, cy/= base) {
			if (j < b.ln) cy += a.v[i] * b.v[j];
			if (i + j < res.ln) cy += res.v[i + j];
			if (i + j >= res.ln) res.v[res.ln++] = cy % base;
			else res.v[i + j] = cy % base;
		}
	}
	return res;
}
bint operator / (const bint& a, const bint& b)
{   // ! b != 0
	bint tmp, mod, res;
	int i, lf, rg, mid;
	mod.v[0] = mod.ln = 0;
	for (i = a.ln - 1; i >= 0; i--) {
		mod = mod * base + a.v[i];
		for (lf = 0, rg = base -1; lf < rg; ) {
			mid = (lf + rg + 1) / 2;
			if (b * mid <= mod) lf = mid;
			else rg = mid - 1;
		}
		res.v[i] = lf;
		mod = mod - b * lf;
	}
	res.ln = a.ln;
	while (res.ln > 0 && res.v[res.ln - 1] == 0) res.ln--;
	return res;          // return mod 就是%运算
}
int digits(bint& a)			         // 返回位数
{
	if (a.ln == 0) return 0;
	int l = ( a.ln - 1 ) * 4;
	for (int t = a.v[a.ln - 1]; t; ++l, t/=10) ;
	return l;
}
bool read(bint& b, char buf[])  // 读取失败返回0
{
	if (1 != scanf("%s", buf)) return 0;
	int w, u, ln = strlen(buf);
	memset(&b, 0, sizeof(bint));
	if ('0' == buf[0] && 0 == buf[1]) return 1;
	for (w = 1, u = 0; ln; ) {
		u += (buf[--ln] - '0') * w;
		if (w * 10 == base) {
			b.v[b.ln++] = u; u = 0; w = 1;
		}
		else w *= 10;
	}
	if (w != 1) b.v[b.ln++] = u;
	return 1;
}
void write(const bint& v)
{
    int i;
	printf("%d", v.ln == 0 ? 0 : v.v[v.ln - 1]);
	for (i = v.ln - 2; i >= 0; i--)
		printf("%04d", v.v[i]);  // ! 4 == width
	printf("\n");
}
/*============================================================*\
 | 最长公共递增子序列 O(n^2)                                  |
 | f记录路径，DP记录长度, 用a对b扫描，逐步最优化              |
\*============================================================*/
int f[N][N], dp[N];
int gcis(int a[], int la, int b[], int lb, int ans[])
{
    int i, j, k, mx;
    memset(f, 0, sizeof(f));
    memset(dp, 0, sizeof(dp));
    for (i = 1; i <= la; i++) {
        memcpy(f[i], f[i-1], sizeof(f[0]));
        for (k = 0, j = 1; j <= lb; j++) {
            if (b[j-1] < a[i-1] && dp[j] > dp[k]) k = j;
            if (b[j-1] == a[i-1] && dp[k] + 1 > dp[j])
				dp[j] = dp[k] + 1, f[i][j] = i * (lb + 1) + k;
        }
    }
    for (mx = 0, i = 1; i <= lb; i++)
		if (dp[i] > dp[mx]) mx = i;
    for (i=la*lb+la+mx, j=dp[mx]; j; i=f[i/(lb+1)][i%(lb+1)],j--)
		ans[j-1] = b[i % (lb + 1) - 1];
    return dp[mx];
}
/*============================================================*\
 | 0-1分数规划                                                |
\*============================================================*/
    t1 * x1 + t2 * x2 + ... + tn * xn
r = ---------------------------------
    c1 * x1 + c2 * x2 + ... + cn * xn
给定t[1..n], c[1..n], 求x[1..n]使得sigma(xi)=k且r最大(小).
为了让r最大, 先设计子问题z(r):
z(r) = (t1 * x1 + .. + tn * xn) - r * (c1 * xn + .. + cn * xn);
假设r的最优值为R. 则有:
z(r) < 0 当且仅当 r > R;
z(r) = 0 当且仅当 r = R;
z(r) > 0 当且仅当 r < R;
于是可二分求R.