http://codeforces.com/gym/102040

F - Path Intersection

 

题意：给定一棵树，多次询问，每次给定 k 条路径，问有几个点被所有这 k 条路径覆盖。

树链刨分

把路径转化成 O(log⁡n)O(\log n) 个区间，暴力做 k 次区间集合并，最终区间长度就是答案。

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
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l, i##end = r; i <= i##end; ++i)
#define repo(i, l, r) for (int i = l, i##end = r; i < i##end; ++i)
#define per(i, l, r) for (int i = l, i##end = r; i >= i##end; --i)
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
typedef long long LL;
typedef long long ll;
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
int T, tt;
int n, q, k;
vector<int>G[N];
int siz[N], fa[N], dep[N], son[N], topf[N], dfn[N], clk;
void dfs1(int u, int _fa) {
	siz[u] = 1; fa[u] = _fa;
	for (int v : G[u]) {
		if (v == _fa)continue;
		dep[v] = dep[u] + 1;
		dfs1(v, u);
		siz[u] += siz[v];
		if (siz[v] > siz[son[u]])son[u] = v;
	}
}
void dfs2(int u, int topfa) {
	topf[u] = topfa;
	dfn[u] = ++clk;
	if (!son[u])return;
	dfs2(son[u], topfa);
	for (int v : G[u]) {
		if (!topf[v])dfs2(v, v);
	}
}
typedef pair<int, int>pii;
vector<pii>vc[3];
int d[N];
void dfs3(int u, int v) {
	while (topf[u] ^ topf[v]) {
		if (dep[topf[u]] < dep[topf[v]]) {
			vc[1].push_back({ dfn[topf[v]],dfn[v] });
			v = fa[topf[v]];
		}
		else {
			vc[1].push_back({ dfn[topf[u]],dfn[u] });
			u = fa[topf[u]];
		}
	}
	vc[1].push_back({ min(dfn[u],dfn[v]),max(dfn[u],dfn[v]) });
}

bool intersect(pii p1, pii p2, pii &ans) {
	ans = pii(max(p1.first, p2.first), min(p1.second, p2.second));
	return ans.first <= ans.second;
}
vector<pii>dd;
void merge() {
	vc[2] = vc[0];
	vc[0].clear();
	pii rst;
	for (auto p1 : vc[1]) {
		for (auto p2 : vc[2]) {
			if (intersect(p1, p2, rst)) vc[0].push_back(rst);
		}
	}
}
int main(){
	scanf("%d", &T);
	while (++tt <= T) {
		printf("Case %d:\n", tt);
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)G[i].clear();
		clk = 0;
		for (int i = 1; i <= n; i++) {
			siz[i] = fa[i] = dep[i] = son[i] = topf[i] = dfn[i] = 0;
			d[i] = 0;
		}
		vc[0].clear(); vc[1].clear(); vc[1].clear();
		for (int i = 1; i < n; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		dfs1(1, 0);
		dfs2(1, 1);
		for (int i = 1; i <= n; i++) {
			d[topf[i]] = max(d[topf[i]], dfn[i]);
		}
		for (int i = 1; i <= n; i++) {
			if (topf[i] == i) {
				vc[0].push_back(pii(dfn[i], d[i]));
			}
		}
		dd = vc[0];
		scanf("%d", &q);
		while (q--) {
			scanf("%d", &k);
			vc[0] = dd;
			for (int i = 1; i <= k; i++) {
				vc[1].clear();
				vc[2].clear();
				int u, v;
				scanf("%d%d", &u, &v);
				dfs3(u, v);
				merge();
			}
			int ans = 0;
			for (pii p : vc[0]) {
				ans += p.second - p.first + 1;
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

 

B - Counting Inversion

 

题意：对于一个数，f(x)f(x) 为它十进制表示下数位的逆序对数（逆序对指高位值小于低位值），求 [l,r][l,r] 中所有数的 f(x)f(x) 之和。1≤l≤r≤10141\le l\le r\le 10^{14}。

数位dp

维护 pos,limit,leadpos,limit,lead，以及已经有的各个数字的个数。

用 array<int,10>array<int,10> 作为状态转移，杭电多校有类似题。

注意处理前导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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
typedef long long LL;
typedef long long ll;
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
typedef array<int, 10> arr10;
int T, tt;
ll x, y, p[N];
int a[N];
map<array<int, 10>, ll>dp[20];
ll cal(ll x, int n, int lim, int lead, array<int, 10> b) {
	if (n == -1) {
		return 0;
	}
	if (!lim && !lead&&dp[n].count(b))return dp[n][b];
	ll ans = 0;
	int up = (lim ? a[n] : 9);
	for (int i = 0; i <= up; i++) {
		ll tmp = 0;
		for (int j = 0; j < i; j++)tmp += b[j];
		if (lim && (i == up)) {
			ans += tmp * (x%p[n] + 1);
		}
		else {
			ans += tmp * p[n];
		}
		if (!(lead && (i == 0)))b[i]++;
		ans += cal(x, n - 1, lim&(i == up), lead&(i == 0), b);
		if (!(lead && (i == 0)))b[i]--;
	}
	if (!lim && !lead)dp[n][b] = ans;
	return ans;
}
int tot;
void pre(ll x) {
	tot = 0;
	do {
		a[tot++] = x % 10;
		x /= 10;
	} while (x);
}
int main() {
	p[0] = 1;
	for (int i = 1; i <= 20; i++)p[i] = p[i - 1] * 10;
	scanf("%d", &T);
	while (++tt <= T) {
		printf("Case %d: ", tt);
		scanf("%lld%lld", &x, &y);
		pre(y);
		ll ans = cal(y, tot - 1, 1, 1, arr10{ 0,0,0,0,0,0,0,0,0,0 });
		x--;
		pre(x);
		ans -= cal(x, tot - 1, 1, 1, arr10{ 0,0,0,0,0,0,0,0,0,0 });
		printf("%lld\n", ans);
	}
	return 0;
}