Stamp Rally
一张连通图，\(q\) 次询问从两个点 \(x\) 和 \(y\) 出发，希望经过的不重复点数量等于 \(z\)，经过的边最大编号最小是多少
在 \(Kruskal\) 重构树上倍增二分即可
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
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = - 1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 3e5+5;
int n, m, q, root;
tuple<int, int, int> edge[N];
int f[N], w[N], ac[20][N], size[N];
int find(int x) { return x == f[x]?x:f[x] = find(f[x]); }
int find(int x, int d)
{
for(int i = 19; ~i; --i) if(w[ac[i][x]] <= d) x = ac[i][x];
return x;
}
bool valid(int x, int y, int z, int mid)
{
x = find(x, mid), y = find(y, mid);
if(x == y) return size[x] >= z;
else return size[x]+size[y] >= z;
}
int main()
{
n = read(), m = read(), root = n, w[0] = m+1;
for(int i = 1; i <= m; ++i)
{
int x = read(), y = read();
edge[i] = make_tuple(i, x, y);
}
for(int x = 1; x <= n; ++x) f[x] = x, size[x] = 1;
sort(edge+1, edge+1+m);
for(int i = 1; i <= m; ++i)
{
int x = get<1>(edge[i]), y = get<2>(edge[i]), z = get<0>(edge[i]);
x = find(x), y = find(y); if(x == y) continue;
f[x] = f[y] = ++root, f[root] = root, w[root] = z;
size[root] = size[x]+size[y];
ac[0][x] = root, ac[0][y] = root;
}
for(int x = root; x; --x)
for(int i = 1; i < 20; ++i)
ac[i][x] = ac[i-1][ac[i-1][x]];
q = read();
while(q--)
{
int x = read(), y = read(), z = read();
int l = 1, r = m, ans = 0;
while(l <= r)
{
int mid = (l+r)>>1;
if(valid(x, y, z, mid)) ans = mid, r = mid-1;
else l = mid+1;
}
printf("%d\n", ans);
}
return 0;
}
Candy Piles
两人在玩游戏，轮流进行，每次进行将当前最大的那堆糖果全部吃完或将每堆糖果吃掉一个，吃完的人输,假设两人足够聪明，问谁能必胜
将糖果从大到小排列，以下标作为横轴，个数作为数轴，那么这个游戏就转化为从 \((0,\ 0)\)，每个人可以向上或向右走，不能走的人输
对于这类博弈问题，有一个结论是对角线上的局面相同，简单证明一下，若 \((x,\ y)\) 必输，那么处在 \((x-1,\ y-1)\) 的人不管怎么走，依旧可以到达 \(SG(x,\ y)\)，反之亦然
1 |
|
Leftmost Ball
给你 \(n\) 种不含白色颜色的球，每个球有 \(m\) 个，把这 \(n\times m\) 个球排成一排，把每一种颜色的最左边出现的球涂成白色，求有多少种不同的颜色序列
问题转换，有 \(n+1\) 种颜色，其中白色有 \(n\) 个，其他有 \(m-1\) 个，求颜色序列满足任何前缀白色的个数不少于其他颜色的种数的方案数
序列计数 \(DP\) 一般可以考虑枚举位置和枚举元素，这里用到后者，考虑状态 \(f_{i,\ j}\) 为在 \(n\times m\) 个位置上已填了 \(i\) 个白球和 \(j\) 种其他颜色的球
则有转移方程
\[ f_{i,j}\ =\ f_{i-1,j}+f_{i,j-1}\times(n-j+1)\times\binom{n\times m-i-(m-1)\times (j-1)-1}{m-2} \]
为了不重不漏，我们每次强制让球填在第一个空的位置上，所以 \(f_{i,\ j}\) 可以由 \(f_{i-1,\ j}\) 多填一个白球转移，也可以由 \(f_{i,\ j-1}\) 从剩下 \(n-j+1\) 个颜色选择一种颜色填完转移
1 |
|