https://vjudge.net/contest/413140

J - Spy

 

题意：a[i]a[i] 表示对手的每个队伍战斗力，p[i]p[i] 表示打败对手后获得的分数，b[i]b[i] 表示我方第一种人的战斗力，c[i]c[i] 表示我方第二种人的战斗力。定义我方一组选手的战斗力为 b[i]+c[j]b[i]+c[j] ，第一种选手与第二种选手某种顺序两两组队后，与对方进行pk，共有 n!n! 种pk顺序，求 最大期望×n×n。

KM最大权完备匹配

对于两种个人，即两种点集之间连边，关键在于边权的设定。

两个人结成一队，则该队的能力值确定了，可以算出以这个队面对对面的队伍的贡献的数学期望，即若他与对面所有队伍交手，它的胜负情况可以确定，且可以贡献的值也可以 O(nlog⁡n)O(n\log n) 确定，把对面所有队伍按照能力值排序，由小到大求前缀和即可，再每次二分找到位置。

若一个队伍能战胜的所有队伍的和为 sumsum，则总的贡献为 sum⋅Pn−1n−1sum\cdot P^{n-1}_{n-1} ，期望为 sum⋅Pn−1n−1/Pnnsum\cdot P^{n-1}_{n-1}/P^n_n，答案要求乘以 nn ，则刚好剩下 sumsum ，即前缀和。

则边权定为这两人结对后对队伍的贡献 sumsum。

本题卡dfs的KM，只能用bfs KM。

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
79
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;
const int MAXN = 410;
const int INF = 0x3f3f3f3f;
int w[maxn][maxn];
int lx[maxn], ly[maxn];
int linker[maxn];
int slack[maxn];
int n;
bool visy[maxn];
int pre[maxn];
void bfs(int k) {
	int x, y = 0, yy = 0, delta;
	memset(pre, 0, sizeof(pre));
	for (int i = 1; i <= n; i++) slack[i] = INF;
	linker[y] = k;
	while (1) {
		x = linker[y]; delta = INF; visy[y] = true;
		for (int i = 1; i <= n; i++) {
			if (!visy[i]) {
				if (slack[i] > lx[x] + ly[i] - w[x][i]) {
					slack[i] = lx[x] + ly[i] - w[x][i];
					pre[i] = y;
				}
				if (slack[i] < delta) delta = slack[i], yy = i;
			}
		}
		for (int i = 0; i <= n; i++) {
			if (visy[i]) lx[linker[i]] -= delta, ly[i] += delta;
			else slack[i] -= delta;
		}
		y = yy;
		if (linker[y] == -1) break;
	}
	while (y) linker[y] = linker[pre[y]], y = pre[y];
}

int KM() {
	memset(lx, 0, sizeof(lx));
	memset(ly, 0, sizeof(ly));
	memset(linker, -1, sizeof(linker));
	for (int i = 1; i <= n; i++) {
		memset(visy, false, sizeof(visy));
		bfs(i);
	}
	int res = 0;
	for (int i = 1; i <= n; i++) {
		if (linker[i] != -1) {
			res += w[linker[i]][i];
		}
	}
	return res;
}

const LL inf = 0x3f3f3f3f3f3f3f3f;
LL b[MAXN], c[MAXN];
pii a[MAXN];

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> a[i].first;
	for (int i = 0; i < n; ++i) cin >> a[i].second;
	for (int i = 0; i < n; ++i) cin >> b[i];
	for (int i = 0; i < n; ++i) cin >> c[i];
	sort(a, a + n);
	for (int i = 1; i < n; ++i) a[i].second += a[i - 1].second;
	for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
		auto it = lower_bound(a, a + n, pii(b[i] + c[j], -inf));
		if (it != a) {
			--it;
			w[i][j] = it->second;
		}
		else w[i][j] = 0;
	}
	cout << KM() << endl;
	return 0;
}

 

F - Paper Grading

 

题意：给定 n 个字符串，m 次操作，两种操作：交换第 xx，yy 个字符串；给定一个字符串，询问与它的公共前缀长度 ≥k\ge k 且下标在 [l,r][l,r] 的串的个数。

做法一：

离线+Trie+CDQ分治+树状数组

先把所有串都插到字典树里，则要找与某个串公共前缀大于等于 k 的串只需要在字典树上走 k 步，子树里的所有串都可以。子树的特点就在于dfs序是一个区间，所以就只要找到区间中的串的个数。

但是又要下标在 [l,r][l,r]，所以变成 in[u]≤dfn[v]≤out[u]in[u]\le dfn[v]\le out[u] 且 l≤i≤rl\le i\le r，这可以通过二维容斥变成求 dfn[v]≤in[u]∧i≤ldfn[v]\le in[u]\wedge i\le l，dfn[v]≤in[u]∧i≤rdfn[v]\le in[u]\wedge i\le r，dfn[v]≤out[u]∧i≤ldfn[v]\le out[u]\wedge i\le l，dfn[v]≤out[u]∧i≤rdfn[v]\le out[u]\wedge i\le r。就变成了四个二维偏序问题。

对于交换操作，不能让它影响到它之前的询问，需要离线下来，并增加维度 tt，变成三维偏序问题，CDQ分治解决。

CDQ分治通过先按照一维排序，并分治，使得满足条件 tj<tit_j<t_i，再通过类似归并排序的方法使得第二维有序，最后通过树状数组处理第三维。

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m;
char s[N];
int ch[N][30], tot, id[N];
int ins() {
	int rt = 0;
	for (int i = 0; s[i]; i++) {
		int bt = s[i] - 'a';
		if (!ch[rt][bt]) {
			ch[rt][bt] = ++tot;
		}
		rt = ch[rt][bt];
	}
	return rt;
}
int dfn[N], out[N], clk;
void dfs(int u) {
	dfn[u] = ++clk;
	for (int i = 0; i < 26; i++) {
		if (ch[u][i])dfs(ch[u][i]);
	}
	out[u] = clk;
}
int sum[N];
void add(int p, int x) {
	for (int i = p; i < N; i += (i&-i))sum[i] += x;
}
int qry(int r) {
	int res = 0;
	for (int i = r; i; i -= (i&-i))res += sum[i];
	return res;
}
int getrt(int k) {
	int rt = 0;
	for (int i = 0; i < k; i++) {
		if (!ch[rt][s[i] - 'a'])return -1;
		rt = ch[rt][s[i] - 'a'];
	}
	return rt;
}
struct X
{
	int t, op, df, idx, x;
	bool operator<(const X& b)const {
		return t < b.t;
	}
}q[N];
int ans[N], cnq;
X tmp[N];
void cdq(int l, int r) {
	if (l == r)return;
	int mid = (l + r) / 2;
	cdq(l, mid); cdq(mid + 1, r);
	int p1 = l, p2 = mid + 1;
	int p = l;
	while (p1 <= mid || p2 <= r) {
		if (p1 <= mid && p2 <= r) {
			if (q[p1].df <= q[p2].df) {
				tmp[p++] = q[p1];
				if (q[p1].op == 1)add(q[p1].idx, q[p1].x);
				p1++;
			}
			else {
				tmp[p++] = q[p2];
				if (q[p2].op == 2)ans[q[p2].t] += q[p2].x*qry(q[p2].idx);
				p2++;
			}
		}
		else if (p1 <= mid) {
			tmp[p++] = q[p1];
			if (q[p1].op == 1)add(q[p1].idx, q[p1].x);
			p1++;
		}
		else if (p2 <= r) {
			tmp[p++] = q[p2];
			if (q[p2].op == 2)ans[q[p2].t] += q[p2].x*qry(q[p2].idx);
			p2++;
		}
	}
	for (int i = l; i <= mid; i++)if (q[i].op == 1) {
		add(q[i].idx, -q[i].x);
	}
	for (int i = l; i <= r; i++)q[i] = tmp[i];
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%s", s);
		id[i] = ins();
	}
	dfs(0);
	for (int i = 1; i <= n; i++) {
		q[++cnq] = { 0,1,dfn[id[i]],i,1 };
	}
	memset(ans, -1, sizeof(ans));
	for (int i = 1; i <= m; i++) {
		int op;
		scanf("%d", &op);
		if (op == 1) {
			int x, y;
			scanf("%d%d", &x, &y);
			q[++cnq] = { i,1,dfn[id[x]],x,-1 };
			q[++cnq] = { i,1,dfn[id[y]],y,-1 };
			swap(id[x], id[y]);
			q[++cnq] = { i,1,dfn[id[x]],x,1 };
			q[++cnq] = { i,1,dfn[id[y]],y,1 };
		}
		else {
			scanf("%s", s);
			int k, l, r;
			scanf("%d%d%d", &k, &l, &r);
			int u = getrt(k);
			ans[i] = 0;
			if (u == -1)continue;
			else {
				q[++cnq] = { i,2,out[u],r,1 };
				q[++cnq] = { i,2,dfn[u] - 1,l - 1,1 };
				q[++cnq] = { i,2,out[u],l - 1,-1 };
				q[++cnq] = { i,2,dfn[u] - 1,r,-1 };
			}
		}
	}
	sort(q + 1, q + cnq + 1);
	cdq(1, cnq);
	for (int i = 1; i <= cnq; i++)if (ans[i] != -1)printf("%d\n", ans[i]);
	return 0;
}

 

做法二：

主席树+树状数组

这里就不需要离线了。

还是dfn和下标作为两个维度。

以下标作为主席树的根，dfn作为每棵线段树的范围。

由于主席树是前缀和，所以每次对一个单点修改时需要对下标 ii 到 nn 的所有线段树都修改，这可以通过套树状数组实现。

查询时对两个主席树树根查询，每个查询的范围都是 [inu,outu][in_u,out_u]。

时间竟然比CDQ分治快了一倍。

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m;
char s[N];
int ch[N][30], tot, id[N];
int ins() {
	int rt = 0;
	for (int i = 0; s[i]; i++) {
		int bt = s[i] - 'a';
		if (!ch[rt][bt]) {
			ch[rt][bt] = ++tot;
		}
		rt = ch[rt][bt];
	}
	return rt;
}
int dfn[N], out[N], clk;
void dfs(int u) {
	dfn[u] = ++clk;
	for (int i = 0; i < 26; i++) {
		if (ch[u][i])dfs(ch[u][i]);
	}
	out[u] = clk;
}
int getrt(int k) {
	int rt = 0;
	for (int i = 0; i < k; i++) {
		if (!ch[rt][s[i] - 'a'])return -1;
		rt = ch[rt][s[i] - 'a'];
	}
	return rt;
}
#define mid ((l+r)>>1)
#define lson l,mid,lc[rt]
#define rson mid+1,r,rc[rt]
int	sum[N * 40], lc[N * 40], rc[N * 40], T[N], cnt;
void build(int l, int r, int& rt) {
	if (!rt)rt = ++cnt;
	if (l == r)return;
	build(lson);
	build(rson);
}
void upd(int q, int x, int l, int r, int& rt) {
	if (!rt)rt = ++cnt;
	sum[rt] += x;
	if (l == r)return;
	if (q <= mid)upd(q, x, lson);
	else upd(q, x, rson);
}
int qry(int ql, int qr, int l, int r, int rt) {
	if (ql <= l && qr >= r) {
		return sum[rt];
	}
	int res = 0;
	if (ql <= mid)res += qry(ql, qr, lson);
	if (qr > mid)res += qry(ql, qr, rson);
	return res;
}
void add(int x, int p, int d) {
	for (int i = x; i < N; i += (i&-i)) {
		upd(p, d, 1, tot + 1, T[i]);
	}
}
int ask(int x, int l, int r) {
	int res = 0;
	for (int i = x; i; i -= (i&-i)) {
		res += qry(l, r, 1, tot + 1, T[i]);
	}
	return res;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%s", s);
		id[i] = ins();
	}
	dfs(0);
	build(1, n, T[0]);
	for (int i = 1; i <= n; i++) {
		add(i, dfn[id[i]], 1);
	}
	while (m--) {
		int op;
		scanf("%d", &op);
		if (op == 1) {
			int x, y;
			scanf("%d%d", &x, &y);
			add(x, dfn[id[x]], -1);
			add(y, dfn[id[y]], -1);
			swap(id[x], id[y]);
			add(x, dfn[id[x]], 1);
			add(y, dfn[id[y]], 1);
		}
		else {
			int k, l, r, u;
			scanf("%s%d%d%d", s, &k, &l, &r);
			if ((u = getrt(k)) == -1) { puts("0"); continue; }
			printf("%d\n", ask(r, dfn[u], out[u]) - ask(l - 1, dfn[u], out[u]));
		}
	}
	return 0;
}

 

I - Space Station

 

题意：给定一个数组，初始有数 xx， 如果已有的数大于等于 aia_i，则能跳到 ii，跳过去后已有的数加上 aia_i，问每点经过恰一次的方案数。0≤x,ai≤500\le x,a_i\le 50

当已有的数 ≥50\ge 50，之后就可以直接得到答案了。

所以直接dfs暴力枚举每一个数字，累加到已有数中，当已有数 ≥50\ge 50 时return。

但这样会T。

考虑记忆化搜索，map保存数组 cc，记录每个数字还有几个，则状态相同等价于 cc 数组相同，因为这时已有的数必定也相同。

不能直接map存数组，否则还是T，要先数组hash再存。

map也不能用，要用unordered_map。

还要优化，对于数字0，不论什么时候跳都行，所以先不管，最后处理。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int n;
int a[N], c[N], cur;
ll fac[N], inv[N];
ll power(ll a, int x) {
	ll ans = 1;
	while (x) {
		if (x & 1) ans = (ans * a) % mod;
		a = (a * a) % mod;
		x >>= 1;
	}
	return ans;
}
void init() {
	fac[0] = 1;
	for (int i = 1; i < N; i++) {
		fac[i] = fac[i - 1] * i %mod;
	}
	inv[N - 1] = power(fac[N - 1], mod - 2);
	for (int i = N - 2; i >= 0; i--) {
		inv[i] = inv[i + 1] * (i + 1) % mod;
	}
}
unordered_map<ull, ll>mp;
ll dfs(int cur, int cnt) {
	if (cur >= 50) {
		return fac[cnt];
	}
	if (!cnt) {
		return 1;
	}
	ull hsh = 0;
	for (int i = 1; i <= 50; i++)hsh = hsh * 233 + c[i];
	if (mp.count(hsh))return mp[hsh];
	ll ans = 0;
	for (int i = 1; i <= cur; i++) {
		if (!c[i])continue;
		c[i]--;
		ans = (ans + (c[i] + 1)*dfs(cur + i, cnt - 1) % mod) % mod;
		c[i]++;
	}
	return mp[hsh] = ans;
}
int main() {
	init();
	scanf("%d", &n);
	scanf("%d", &cur);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		c[a[i]]++;
	}
	ll ans = dfs(cur, n - c[0]);
	printf("%lld\n", ans*fac[n] % mod*inv[n - c[0]] % mod);
	return 0;
}