分类存档：默认分类

[Link]

给定一个二分图，问你哪些边永远不可能成为最大匹配的边。

比赛的时候全败在题上了……
这道题我见过三次，第一次在上一年训练的时候见到，随便YY一下全手写花了不到1小时就过了；第二次在多校见少考虑了一种情况WA全场；第三次，hopcroft karp模板右边不能匹配居然match2不是-1而是n，直接又WA全场，把-1改成n立马过了。我简直不能再蠢……
实际这题还是很简单的(多校那个解题报告的解法要加各种边还得匹配两次感觉很不科学……)
做法就是先匹配，然后匹配边先排除这是肯定的。
然后匹配边从右往左连，非匹配边从左往右连。做强连通。
最后如果一条边符合下面三种情况之一就是可以作为匹配边的。

1. 
   这个的意思是要连的边两个点在同一个强连通分量。具体换边的方法就是沿着到彼此的路径交替互换就行了。
2. 
   左边的点被左边一个未被匹配的空点可达，换边的方法就是从空点一直走过来，交替互换。
3. 
   右边的点可达一个右边未被匹配的空点，换边的方法就是沿着这条路径一直走到空点，然后交替互换。

所以思路就明确了，SCC以后判连通性即可。
本来模块不能外传……但是想到我们的模块已经落后别人10条街了，而且网络赛本来就公开了代码……

#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define foreach(it,v) for (__typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
typedef pair <int, int> PII;
typedef long long ll;
const int MAXN = 100005;
int n, m, e;
int match1[MAXN], match2[MAXN];
int Q[MAXN], D1[MAXN], D2[MAXN];
vector <int> E[MAXN];

inline bool bfs() {
    int s = 0, t = 0, u, v;
    memset(D1, -1, sizeof(D1));
    memset(D2, -1, sizeof(D2));
    for (int i = 0; i < n; i++)
        if (match1[i] == -1)
            Q[t++] = i, D1[i] = 0;
    while (s != t)
        if ((u = Q[s++]) != n)
            for (int i = 0; i < (int)E[u].size(); i++)
                if (D2[v = E[u][i]] == -1) {
                    D2[v] = D1[u] + 1;
                    if (D1[match2[v]] == -1)
                        D1[Q[t++] = match2[v]] = D2[v] + 1;
                }
    return D1[n] != -1;
}

bool dfs(int u) {
    for (int i = 0, v; i < (int)E[u].size(); i++)
        if (D2[v = E[u][i]] == D1[u] + 1 && (D2[v] = -1) && (match2[v] == n || dfs(match2[v]))) {
            match1[u] = v;
            match2[v] = u;
            D1[u] = -1;
            return true;
        }
    D1[u] = -1;
    return false;
}

inline int hopcroft_karp() {
    memset(match1, -1, sizeof(match1));
    for (int i = 0; i < m; i++)
        match2[i] = n;
    int ret = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0, u; j < (int)E[i].size(); j++)
            if (match2[u = E[i][j]] == n) {
                match1[i] = u;
                match2[u] = i;
                ret++;
                break;
            }
    while (bfs())
        for (int i = 0; i < n; i++)
            if (match1[i] == -1 && dfs(i))
                ret++;
    return ret;
}

int toNum(char c) {
	if (c >= '0' && c <= '9') return c - '0';
	return c - 'A' + 10;
}

int trans(char *s) {
	return toNum(s[0]) * 32 * 32 + toNum(s[1]) * 32 + toNum(s[2]);
}

struct SCC_T {
	int n;
	int dfn[MAXN], low[MAXN], id[MAXN], num, st[MAXN], top, in[MAXN], tot; 
	vector <int> E[MAXN];
	int come[MAXN], go[MAXN];

	void clear(int _n) {
		n = _n;
		rep (i, n) E[i].clear();
		memset(dfn, 0, sizeof(int) * n); 
		memset(low, 0, sizeof(int) * n); 
		memset(in, 0, sizeof(int) * n); 
		memset(id, 0xff, sizeof(int) * n); 
		memset(come, 0, sizeof(int) * n);
		memset(go, 0, sizeof(int) * n);
	}

	void addedge(int x, int y) {
		E[x].push_back(y);
	}
 
	void tarjan(int now){ 
		in[st[top++] = now] = true; 
		dfn[now] = low[now] = ++tot;
		int i; 
		for (int ii = E[now].size() - 1; ii >= 0; --ii){ 
			i = E[now][ii]; 
			if (!dfn[i]){ 
				tarjan(i); 
				low[now] = min(low[now], low[i]);
			}
			else if (in[i]) 
				low[now] = min(low[now], dfn[i]); 
		}
		if (dfn[now] == low[now]){
			do{
				i = st[--top];
				in[i] = false;
				id[i] = num;
			}while (i != now);
			++num;
		}
	}
	void gao() { 
		for (int i = top = num = tot = 0; i < n; ++i) 
			if (!dfn[i]) 
				tarjan(i); 
	}

	void bfs(int (&vis)[MAXN], const vector <int> (&E)[MAXN]) {
		static int Q[MAXN];
		int qh = 0, qt = 0;
		rep (i, n)
			if (vis[i])
				Q[qt++] = i;
		while (qh < qt) {
			int u = Q[qh++];
			rep (i, E[u].size()) {
				int v = E[u][i];
				if (!vis[v]) {
					vis[v] = 1;
					Q[qt++] = v;
				}
			}
		}
	}

	void calc() {
		bfs(come, E);
		static vector <int> E2[MAXN];
		rep (i, n) E2[i].clear();
		rep (i, n) rep (j, E[i].size()) E2[E[i][j]].push_back(i);
		bfs(go, E2);
	}
}SCC;

int main() {
	while (scanf("%d%d%d", &n, &m, &e) != EOF) {
		static map <int, int> id[MAXN];
		rep (i, n) E[i].clear(), id[i].clear();
		rep (i, e) {
			char s[10];
			scanf("%s", s);
			int u = trans(s);
			int v = trans(s + 3);
			E[u].push_back(v);
			assert(!id[u].count(v));
			id[u][v] = i;
		}
		hopcroft_karp();
		SCC.clear(n + m);
		rep (u, n) {
			if (match1[u] != -1) SCC.addedge(match1[u] + n, u);
			rep (i, E[u].size()) {
				int v = E[u][i];
				if (v != match1[u]) SCC.addedge(u, v + n);
			}
		}
		SCC.gao();
		rep (i, m)
			if (match2[i] == n)
				SCC.go[n + i] = 1;
		rep (i, n)
			if (match1[i] == -1)
				SCC.come[i] = 1;
		SCC.calc();
		vector <int> ans;
		rep (u, n) rep (i, E[u].size()) {
			int v = E[u][i];
			if (SCC.come[u] || SCC.go[v + n] || SCC.id[u] == SCC.id[v + n] || match1[u] == v) continue;
			ans.push_back(id[u][v]);
		}
		sort(ans.begin(), ans.end());
		printf("%d\n", (int)ans.size());
		rep (i, ans.size()) {
			if (i) putchar(' ');
			printf("%d", ans[i]);
		}
		puts("");
	}
}

【Link】

求串A和串B偏序匹配的所有位置。偏序匹配就是保持大小关系的离散化后两个串一模一样。\[1 \leq |A|, |B| \leq 10^5, 1 \leq A_i, B_i \leq 25 \]

昨天网络赛的B题，我们当时随便弄了个$$25*(|A| + |B|)$$的hash就过了，后来在Vani那听说有n lg k(k为字符集大小)的做法，想了一下总算明白了。记录一下。
其实满足以下两条性质的匹配关系都能KMP：

1. 匹配的前缀性质。也就是说：若$$A_{1..n}$$和$$B_{1..n}$$匹配，那么对于任意$$i=1..n$$，有$$A_{1..i}$$和$$B_{1..i}$$匹配。
2. 偏序匹配符合传递性。假设用\(\approx\)表示两个串符合偏序匹配，那么$$A \approx B , B \approx C \Rightarrow A \approx C$$

既然能KMP了，关键就在于判断他们什么时候能往后面加一个字符。
考虑两个相同长度的串$$A_{1..n}, B_{1..n}$$他们已经能够构成偏序匹配，那么假设现在新增了一个元素，构成了$$A_{1..n+1}, B_{1..n+1}$$，那么他们同样能构成偏序匹配的充要条件是什么呢？
仔细想想不难YY到：
\(count(A_i < A_{n+1}) = count(B_i < B_{n + 1}), i = 1..n\) \(count(A_i = A_{n + 1}) = count(B_i = B_{n + 1}), i = 1..n\) \(count(A_i > A_{n + 1}) = count(B_i > B_{n + 1}), i = 1..n\)
因为n是固定的，所以只关注前两个条件即可。
然后这东西可以用树状数组维护。
KMP维护的实际是两个指针j和i，表示$$A_{j..i}$$ 和 $$B_{1..i-j+1}$$匹配，本质上i和j都是递增的，所以i加的时候把a[i]放进BIT，j加的时候扔出树状数组即可。
而模式串因为只和前缀比较，所以可以预处理出low和eq数组

时间复杂度 $$O(n \log_2 k)$$
空间复杂度 $$O(n)$$

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define foreach(it,v) for (__typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
typedef pair <int, int> PII;
typedef long long ll;
const int N = 100005;
int n, m, p;
int a[N], b[N];
int Tr[30];
int low[N], eq[N];
int Next[N];
bool mat[N];

int get(int i) {
	int res = 0;
	for (; i; i -= i & -i) res += Tr[i];
	return res;
}

void add(int i, int x) {
	for (; i < = p; i += i & -i) Tr[i] += x;
}

void init() {
	fill(Tr, Tr + p + 1, 0);
	low[0] = eq[0] = 0;
	for (int i = 1; i <= m; i++) {
		low[i] = get(b[i] - 1);
		eq[i] = get(b[i]) - low[i];
		add(b[i], 1);
	}
}

int last;

bool ok(int *a, int lim, int x, int j) {
	while (last < lim) add(a[last++], -1);
	int l = get(x - 1), e = get(x) - l;
	return l == low[j] && e == eq[j];
}

int f[N];

void kmp() {
	fill(Tr, Tr + p + 1, 0);
	fill(mat, mat + n + 1, 0);
	int j = 0;
	Next[1] = 0;
	last = 1;
	add(b[1], 1);
	for (int i = 2; i <= m; i++) {
		while (j && !ok(b, i - j, b[i], j + 1)) {
			j = Next[j];
		}
		if (j == 0 || ok(b, i - j, b[i], j + 1)) j++;
		Next[i] = j;
		add(b[i], 1);
	}
	fill(Tr, Tr + p + 1, 0);
	j = 0;
	last = 1;
	for (int i = 1; i <= n; i++) {
		while (j && !ok(a, i - j, a[i], j + 1)) {
			j = Next[j];
		}
		if (j == 0 || ok(a, i - j, a[i], j + 1)) {
			j++;
		}
		if (j == m) {
			mat[i] = 1;
			j = Next[j];
		}
		add(a[i], 1);
	}
}

int main() {
	while (scanf("%d%d%d", &n, &m, &p) != EOF) {
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
		for (int i = 1; i <= m; i++) {
			scanf("%d", &b[i]);
		}
		init();
		kmp();
		fill(f, f + n + 1, 0);
		for (int i = 1; i <= n; i++) {
			f[i] = f[i - 1];
			if (i - m >= 0) f[i] = max(f[i], f[i - m] + mat[i]);
		}
		printf("%d\n", f[n]);
	}
}