http://codeforces.com/contest/1450

B. Balls of Steel

 

题意：二维平面上n个点，每个点可以把与它曼哈顿距离不超过k的点吸过来，问最少吸几次能全都吸到一起，或者不行。

假设最终吸到某点u，那么与 u 曼哈顿距离不超过 k 的点一定不能操作，否则 u 就被吸走了，那么与 u 曼哈顿距离大于 k 的点就永远不会到 u，所以必须初始时所有点与 u 曼哈顿距离不超过 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
#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 = 998244353;
int T;
int n, k;
int x[N], y[N];
int ck() {
	for (int i = 1; i <= n; i++) {
		int c = 0;
		for (int j = 1; j <= n; j++)if (abs(x[i] - x[j]) + abs(y[i] - y[j]) <= k)c++;
		if (c == n)return 1;
	}
	return -1;
}
int main(){
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &k);
		for (int i = 1; i <= n; i++)scanf("%d%d", &x[i], &y[i]);
		printf("%d\n", ck());
	}
	return 0;
}

 

D. Rating Compression

 

题意：给定一个数组，对于 1≤k≤n1\le k\le n，进行最小值池化，即新的数组值等于长为 k 的滑动窗口下原数组的最小值，问对于每个 k，池化结果是否是从 1 开始的排列。

k=1k=1 时是 1 到 n 的排列，k=2k=2 时是 1 到 n-1 的排列，以此类推。

k=ik=i 时是 1 到 p 的排列等价于：

  • 原数组含有 p

  • k=i+1k=i+1 时是排列。假设不是，那么要么缺少某个小的数，那么这个数一定不存在于这个数组里。要么是有数出现了两次，由于窗口变小可以看成大窗口变成了两个子的小窗口，如果原来就有两个大窗口的最小值为 x，那么分裂后至少仍有两个小窗口最小值为 x。

  • p-1 在某一侧。即在k变小的过程中，没有涉及到的范围一定是从两侧不断缩小。

  • 原数组恰含有一个 p-1

当 k=1 时要特判。

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
#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 = 998244353;
int T;
int n;
int a[N], cnt[N];
char ans[N];
bool ck() {
	for (int i = 1; i <= n; i++)if (cnt[i] != 1)return false;
	return true;
}
int main(){
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		fill(cnt, cnt + n + 1, 0);
		for (int i = 1; i <= n; i++)scanf("%d", &a[i]), cnt[a[i]]++;
		if (cnt[1] > 0)ans[1] = '1';
		else ans[1] = '0';
		int l = 0, r = n + 1;
		for (int i = 2; i < n; i++) {
			if (ans[i - 1] == '0' || cnt[i] == 0 || cnt[i - 1] > 1)ans[i] = '0';
			else {
				if (a[l + 1] == i - 1 && a[r - 1] > i - 1) {
					ans[i] = '1';
					l++;
				}
				else if (a[l + 1] > i - 1 && a[r - 1] == i - 1) {
					ans[i] = '1';
					r--;
				}
				else ans[i] = '0';
			}
		}
		if (ck())ans[n] = '1';
		else ans[n] = '0';
		ans[n + 1] = 0;
		reverse(ans + 1, ans + n + 1);
		printf("%s\n", ans + 1);
	}
	return 0;
}

 

F. The Struggling Contestant

 

题意：给定一个数组，要重排使得相邻数字不同，且要最少化在原数组中相邻而在新数组中不相邻的数对个数，求个数。

如果最多的数出现 >⌈n2⌉>\lceil \frac{n}{2}\rceil，则不行。否则可行。

如果相邻两个数相同，则在它们之间插一个隔板，分成若干段。要使得原数组相邻新数组不相邻的数对最少，那么同一段必须要在一起，（但是可以一段整个倒过来）。

设一段以这段的首尾表示，即 (x1,y1),(x2,y2),⋯ ,(xk+1,yk+1)(x_1,y_1),(x_2,y_2),\cdots,(x_{k+1},y_{k+1})。

重排后不能有 yi=xi+1y_i=x_{i+1}。

如果不同段重排时不会有新的冲突，那么答案就是隔板数，设为 kk。

如果有冲突，那么只要最多的数出现次数 ≤k+2\le k+2，就一定可以重排使得消除冲突。

如果最多的数出现次数 >k+2> k+2，则需要再拆分，每次拆分使得 k++k++，且一定能够找到拆分方式使得新的分割点两边都不等于当前出现次数最多的那个数。证明可以考虑极端情况，即拆成每个数自成一段，此时 k=n−1k=n-1，设出现次数最多的数在原数组出现了 vv 次，则在 (x1,y1),(x2,y2),⋯ ,(xk+1,yk+1)(x_1,y_1),(x_2,y_2),\cdots,(x_{k+1},y_{k+1}) 中出现了 2v2v 次，由于最开始判断了 v≤⌈n2⌉v\le \lceil \frac{n}{2}\rceil，所以 2v≤n+1=k+22v\le n+1=k+2。

每次拆分的贡献为 1.

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
#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 = 998244353;
int T;
int n;
int a[N], cnt[N];
int main(){
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		fill(cnt, cnt + n + 1, 0);
		int k = 0, mx = 0, ans = 0;
		for (int i = 1; i <= n; i++)scanf("%d", &a[i]), cnt[a[i]]++, mx = max(mx, cnt[a[i]]);
		if (mx > (n + 1) / 2) { puts("-1"); continue; }
		fill(cnt, cnt + n + 1, 0);
		mx = 0;
		cnt[a[1]]++; cnt[a[n]]++;
		for (int i = 1; i < n; i++) {
			if (a[i] == a[i + 1]) {
				k++;
				cnt[a[i]] += 2;
			}
		}
		for (int i = 1; i <= n; i++)mx = max(mx, cnt[i]);
		printf("%d\n", k + max(0, mx - k - 2));
	}
	return 0;
}

 

C2. Errich-Tac-Toe (Hard Version)

 

题意：给定一张棋盘，每格有 O 或 X 或空着，总棋数为 k ，要用不超过 ⌊k3⌋\lfloor \frac{k}{3}\rfloor 次操作，每次把 O 变 X，或 X 变 O，使得没有横或竖连续三个相同的棋子。

构造

把所有棋子按照 (i+j)%3(i+j)\%3 分组，连续 3 个棋子一定在三个不同的组，所以只要把其中两组改成不同的，就能使得连续三个不可能都相同。

遍历所有情况选择两组，再选一组 O 改成 X，另一组 X 改成 O，反证法易证一定有满足条件的情况。

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
#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 = 998244353;
int T;
int n;
char s[310][310];
int cnt[3][2];
int main(){
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		int k = 0;
		memset(cnt, 0, sizeof(cnt));
		for (int i = 1; i <= n; i++)scanf("%s", s[i] + 1);
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (s[i][j] != '.') {
					k++;
					if (s[i][j] == 'O')cnt[(i + j) % 3][0]++;
					else cnt[(i + j) % 3][1]++;
				}
			}
		}
		bool flg = 0;
		for (int i = 0; i < 3 && !flg; i++) {
			for (int j = i + 1; j < 3 &&!flg; j++) {
				if (cnt[i][0] + cnt[j][1] <= k / 3) {
					for (int x = 1; x <= n; x++) {
						for (int y = 1; y <= n; y++) {
							if ((x + y) % 3 == i && s[x][y] == 'O')s[x][y] = 'X';
							else if ((x + y) % 3 == j && s[x][y] == 'X')s[x][y] = 'O';
						}
					}
					for (int x = 1; x <= n; x++) {
						printf("%s\n", s[x] + 1);
					}
					flg = 1;
				}
				else if (cnt[i][1] + cnt[j][0] <= k / 3) {
					for (int x = 1; x <= n; x++) {
						for (int y = 1; y <= n; y++) {
							if ((x + y) % 3 == j && s[x][y] == 'O')s[x][y] = 'X';
							else if ((x + y) % 3 == i && s[x][y] == 'X')s[x][y] = 'O';
						}
					}
					for (int x = 1; x <= n; x++) {
						printf("%s\n", s[x] + 1);
					}
					flg = 1;
				}
			}
		}
	}
	return 0;
}

 

E. Capitalism

 

题意：给定一张包含有向边和无向边的图，如果 i j 有无向边，则 aj=ai+1a_j=a_i+1，如果有无向边，则两种方向都可能。问能否给无向边定方向，使得 aia_i 符合条件。要求最大化 max⁡1≤i≤nai−min⁡1≤i≤nai\max\limits_{1 \leq i \leq n} a_i - \min\limits_{1 \leq i \leq n} a_i，输出 aia_i。

差分约束+判断二分图

首先看到 aj=ai+1a_j=a_i+1 并且要自己构造 aa 数组，要想到差分约束。

则根据限制条件建图：

  • 如果 (i,j)(i,j) 为有向边，则 aj=ai+1a_j=a_i+1，等价于

    {aj−ai≤1aj−ai≥1\begin{cases} a_j-a_i\le 1\\ a_j-a_i\ge 1\\ \end{cases}

    所以连 (i,j,1),(j,i,−1)(i,j,1),(j,i,-1)

  • 如果 (i,j)(i,j) 为无向边，则 ∣ai−aj∣=1|a_i-a_j|=1，变成

    {aj−ai≤1ai−aj≤1\begin{cases} a_j-a_i\le 1\\ a_i-a_j\le 1\\ \end{cases}

    所以连 (i,j,1),(j,i,1)(i,j,1),(j,i,1)。

floyd求多源最短路，根据 d[i][i]d[i][i] 判断是否有负环。

枚举每个点，赋值为 0，其它点的 a值 就是到该点的距离。

但是还有错误！！

上面第二种情况中 ∣ai−aj∣=1|a_i-a_j|=1 并不等价于下面的不等式组，因为可能存在 ai=aja_i=a_j，例如无向的三元环，差分约束能求出结果，但是这时会有两个点值相同，这就不对了。

如果存在奇环，则不论怎么定方向，转一圈回来后值都不等于原来的值，也就不符合条件。

所以不能有奇环，也就是说是二分图。

那么没有奇环，且已经存在 i 到 j 的边，则其它 i 到 j 的路径长度必为奇数，也就不可能再有 ai=aja_i=a_j 了。

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
#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 = 998244353;
int n, m;
int d[210][210];
int c[210];
bool bip(int u) {
	for (int i = 1; i <= n; i++) {
		if (i == u || d[u][i] == INF)continue;
		if (c[u] == c[i])return false;
		if (!c[i]) {
			c[i] = 3 - c[u];
			if (!bip(i))return false;
		}
	}
	return true;
}
int main(){
	scanf("%d%d", &n, &m);
	memset(d, 0x3f, sizeof(d));
	for (int i = 1; i <= n; i++)d[i][i] = 0;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		if (w == 0) {
			d[u][v] = d[v][u] = 1;
		}
		else {
			d[u][v] = 1;
			d[v][u] = -1;
		}
	}
	c[1] = 1;
	if (!bip(1)) {
		puts("NO");
		return 0;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)if (d[i][i] < 0) {
		puts("NO");
		return 0;
	}
	for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)ans = max(ans, d[i][j]);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (d[i][j] == ans) {
				puts("YES");
				printf("%d\n", ans);
				for (int k = 1; k <= n; k++) {
					printf("%d%c", d[i][k], " \n"[k == n]);
				}
				return 0;
			}
		}
	}
	return 0;
}