D - Stamp Rally

整体二分 + 并查集常规操作

不过记得每次仅将当前递归时使用的并查集删去即可，之前的保留，所以对于那些被忽略的答案的位置，也需要递归到然后加入并查集

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 1e05 + 10;
const int MAXM = 1e05 + 10;
const int MAXQ = 1e05 + 10;

int N, M, Q;
pair<int, int> edge[MAXM];

int answer[MAXQ]= {0};
struct querySt {
	int index;
	int x, y;
	int lim;

	querySt (int find = 0, int fx = 0, int fy = 0, int flim = 0) :
		index (find), x (fx), y (fy), lim (flim) {}
} ;
querySt query[MAXQ];

querySt q1[MAXQ], q2[MAXQ];
int father[MAXN], subsize[MAXN];
pair<int, int> stack[MAXM];
int top = 0;
int find (int x) {
	return father[x] == x ? x : find (father[x]);
}
void merge (int x, int y) {
	int fx = find (x), fy = find (y);
	if (fx == fy) return ;
	if (subsize[fx] > subsize[fy]) swap (fx, fy);
	father[fx] = fy, subsize[fy] += subsize[fx];
	stack[++ top] = make_pair (fx, fy);
}
void solve (int left, int right, int l, int r) {
	// if (left > right || l > r) return ; 注意若 l > r 就退出那么有一些点无法加入并查集
	top = 0;
	if (left == right) {
		// cout << "Test: " << left << ' ' << l << ' ' << r << endl;
		for (int i = l; i <= r; i ++)
			answer[query[i].index] = left;
		merge (edge[left].first, edge[left].second);
		top = 0;
		return ;
	}
	int mid = (left + right) >> 1;
	for (int i = left; i <= mid; i ++) {
		int u = edge[i].first, v = edge[i].second;
		merge (u, v);
	}
	int t1 = 0, t2 = 0;
	for (int i = l; i <= r; i ++) {
		int x = query[i].x, y = query[i].y;
		int lim = query[i].lim;
		int fx = find (x), fy = find (y);
		if (fx == fy) {
			if (subsize[fx] >= lim) q1[++ t1] = query[i];
			else q2[++ t2] = query[i];
		}
		else {
			if (subsize[fx] + subsize[fy] >= lim) q1[++ t1] = query[i];
			else q2[++ t2] = query[i];
		}
	}
	for (int i = 1; i <= t1; i ++)
		query[l + i - 1] = q1[i];
	for (int i = 1; i <= t2; i ++)
		query[l + t1 + i - 1] = q2[i];
	while (top > 0) {
		int x = stack[top].first, y = stack[top].second;
		top --;
		father[x] = x, subsize[y] -= subsize[x];
	}
	solve (left, mid, l, l + t1 - 1), solve (mid + 1, right, l + t1, r);
}

int getnum () {
	int num = 0;
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}

int main () {
	// freopen ("stamp.in", "r", stdin);
	// freopen ("stamp.out", "w", stdout);

	N = getnum (), M = getnum ();
	for (int i = 1; i <= M; i ++) {
		int u = getnum (), v = getnum ();
		edge[i] = make_pair (u, v);
	}
	Q = getnum ();
	for (int i = 1; i <= Q; i ++) {
		int x = getnum (), y = getnum (), z = getnum ();
		query[i] = querySt (i, x, y, z);
	}
	for (int i = 1; i <= N; i ++)
		father[i] = i, subsize[i] = 1;
	solve (1, M, 1, Q);
	for (int i = 1; i <= Q; i ++)
		printf ("%d\n", answer[i]);

	return 0;
}

/*
5 6
2 3
4 5
1 2
1 3
1 4
1 5
6
2 4 3
2 4 4
2 4 5
1 3 3
1 3 4
1 3 5
*/

/*
10 13
8 5
5 7
1 3
7 8
5 6
10 9
4 8
7 10
7 1
2 7
4 2
8 10
6 9
5
4 9 11
6 2 2
5 4 5
10 8 4
2 4 3
*/

E - Candy Piles

神仙博弈论 + 模型转化

算是目前做过的为数极少的博弈论题之一，然而并不用 $SG$ 函数什么的

注意 $2$ 操作是对于每一堆都吃一个而不是任选一堆吃，然而我看完题解才发现我题目看错了。。。

将糖果堆按照个数排序后，得到如下图

000

000

0000

00000

将其看做以左下角为点 $(1, 1)$ 的坐标系，那么，对于吃最大的一堆糖果，就相当于向上移一格，对于每堆吃一个糖果，就相当于向右移一格，然后吃到不能吃为止，即到达点 $(3, 4), ~ (4, 2), ~ (1, 5)$ 的其中一个

显然，上述无法继续走动的三点是必输点，那么就可以通过上述点扩张将整幅图的必赢必输状态表示出来

根据定理

若一个点是必赢点当且仅当其可转移的状态中存在必输点；若一个点是必输点当且仅当其可转移的状态中皆是必赢点

就可以实现

当然，这样还是 $T$ 的，所以经过观察，可以发现

  • 一个点的必赢必输状态与其左上角的状态相同

证明的话枚举然后简单反证一下就好了

故现在可以将点 $(1, 1)$ 一直向右上角移动到直到无法移动为止的点 $(k, k)$，那么它现在必处于图形的“边缘”上，显然，对于边缘的情况，一个点的状态必与其右（上）的点相反，那么只要判断一下 $(k, 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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 1e05 + 10;

int N;
int a[MAXN];

bool comp (const int& a, const int& b) {
	return a > b;
}

int getnum () {
	int num = 0;
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}

int main () {
	N = getnum ();
	for (int i = 1; i <= N; i ++)
		a[i] = getnum ();
	sort (a + 1, a + N + 1, comp);
	for (int i = 1; i <= N; i ++)
		if (a[i + 1] <= i) {
			bool win = false;
			if ((a[i] - i) & 1)
				win = true;
			if (! win && a[i + 1] == i) {
				int cnt = 1;
				for (int j = i + 1; j <= N; j ++) {
					if (a[j] < i) break;
					cnt ++;
				}
				if (! (cnt & 1))
					win = true;
			}
			win ? puts ("First") : puts ("Second");
			return 0;
		}

	return 0;
}

/*
2
1 3
*/

/*
3
1 2 1
*/

/*
3
1 2 3
*/

F - Leftmost Ball

动态规划

一开始我是按照常规思路想，并且将一个白球与一类颜色球当做一个整体来处理的，即设 $f_{i, j}$ 表示前 $i$ 个位置放置 $j$ 个白球的方案数，然而首先这样会 $T$，并且容易算重，于是我去康了眼题解

然后发现实际上白球不能与类颜色球整体考虑，不然会算重，但是显然一类颜色球是可以整体考虑的，故设状态 $f_{i, j}$ 表示放了 $i$ 个白球和 $j$ 个类颜色球的方案数 $(j \le i)$

那么问题来了，要如何知道每个球在当前状态下的位置关系呢？因为感觉不知道没法确定球的可放置方案数

当然假如真的要知道位置关系是不可能的，所以仔细思考一下，可以发现，若当前你要放一个白球，那么在你放当前白球的位置之前的位置必须已经被完全填满，不然必会存在该白球之后的类颜色球放置在当前白球前，使得方案不合法，故当前白球放置的相对位置一定只有一个，即 $f_{i, j} += f_{i - 1,j }$

对于放置类颜色球，由于当前类颜色球的白球已经放置完毕，故它还剩下 $n \times k - i - (k - 1) \times(j - 1)$ 个位置放其 $k - 1$ 个球，且当前还剩下 $n - (j - 1)$ 个颜色可供选择，故得 $f_{i, j} += f_{i, j - 1} \times (n - j + 1) \times \dbinom{n \times k - i - (k - 1) \times (j - 1)}{k - 1}$

然而你会发现这样连样例都过不了，因为你又算重了

比如对于

{0, 0, 1, 2}

就会存在先放 $\{0, 1\}$ 还是 $\{0, 2\}$ 的问题，然后会放两遍，所以理论上只要是存在连续的 $0$ 的都会算重

于是一时脑抽，又只能瞄题解了

其实解决方案极其简单，只要满足当前放的类颜色球的第一个一定是最接近 $0$ 的就行了，也就是规定其放置顺序

故综上所述，转移方程为
$$
f_{i, j} = f_{i - 1, j} + f_{i, j - 1} \times (n - j + 1) \times \dbinom{n \times k - i - (k - 1) \times (j - 1) - 1}{k - 2}
$$

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
#include <iostream>
#include <cstdio>
#include <cstring>

#define MOD 1000000007

using namespace std;

typedef long long LL;

const int MAXN = 2000 + 10;
const int MAXM = MAXN * MAXN;

int N, K;

LL fact[MAXM]= {0}, invfact[MAXM]= {0};
void init () {
	fact[0] = fact[1] = invfact[0] = invfact[1] = 1;
	for (int i = 2; i <= N * K; i ++) {
		fact[i] = fact[i - 1] * i % MOD;
		invfact[i] = (MOD - MOD / i) * invfact[MOD % i] % MOD;
	}
	for (int i = 1; i <= N * K; i ++)
		invfact[i] = invfact[i - 1] * invfact[i] % MOD;
}
inline LL C (int n, int m) {
	if (n < 0) return 0;
	if (m == 0) return 1;
	return fact[n] * invfact[m] % MOD * invfact[n - m] % MOD;
}

LL f[MAXN][MAXN]= {0};

int main () {
	scanf ("%d%d", & N, & K);
	if (K == 1) {
		puts ("1");
		return 0;
	}
	init ();
	f[0][0] = 1;
	for (int i = 1; i <= N; i ++)
		for (int j = 0; j <= i; j ++) {
			LL delta = f[i][j - 1] * (N - j + 1) % MOD * C (N * K - i - (K - 1) * (j - 1) - 1, K - 2) % MOD;
			if (j == 0) delta = 0;
			f[i][j] = (f[i][j] + f[i - 1][j] + delta) % MOD;
		}
	cout << f[N][N] << endl;

	return 0;
}

/*
2 2
*/

/*
3 1
*/

/*
2 3
*/

/*
2000 2000
*/