http://codeforces.com/contest/1236

C. Labs

 

题意：把 1到 n2n^2 分成n组，组间连边，且只有从大数向小数连有向边，要求最大化两组之间边数的最小值。

直接猜蛇形构造。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
int a[310][310];
int main() {
	scanf("%d", &n);
	int p = 1, ad = 1;
	for (int i = 1; i <= n * n; i++) {
		int t = (i - 1) / n + 1;
		a[p][t] = i;
		if (p == n && (t & 1) || p == 1 && (!(t & 1)))continue;
		if (t & 1)p++;
		else p--;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)printf("%d%s", a[i][j], j == n ? "\n" : " ");
	}
	return 0;
}

D. Alice and the Doll

 

题意：nm网格，从左上角出发，要走遍所有非障碍物的格子，每次只能右转或直走，且每一格内只能右转一次，问是否可以经过非障碍每一格一次。

从起点走只能向右直走到底否则就走不出自己经过的轨迹了，再发现每一点都是这样，只能走到底转弯。

所以固定只能螺旋走位，那就是个大模拟题，判断能走的格子数+障碍数是否为总数。

但是由于复杂度不能nm暴力，所以模拟时要跳着走，直接跳到障碍或者边界去。

维护每一行以及每一列的障碍，再维护外侧的矩形，矩形不断缩小。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
int n, m, K;
ll ans;
vector <int> X[N], Y[N];
int main(){
	scanf("%d%d%d", &n, &m, &K);
	for (int i = 1; i <= K; i++){
		int a, b; scanf("%d%d", &a, &b);
		X[a].push_back(b); Y[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) sort(X[i].begin(), X[i].end());
	for (int i = 1; i <= m; i++) sort(Y[i].begin(), Y[i].end());
	int x = 1, y = 1, k = 1, flag = 0; ans++;
	int xL = 0, xR = n + 1, yL = 0, yR = m + 1;
	while (1){
		int tx = 0, ty = 0;
		if (k == 1){
			tx = x, ty = lower_bound(X[x].begin(), X[x].end(), y) - X[x].begin();
			if (ty == X[x].size()) ty = yR - 1;
			else ty = min(yR - 1, X[x][ty] - 1);
			k = 2; xL = x;
		}
		else if (k == 2){
			tx = lower_bound(Y[y].begin(), Y[y].end(), x) - Y[y].begin(), ty = y;
			if (tx == Y[y].size()) tx = xR - 1;
			else tx = min(xR - 1, Y[y][tx] - 1);
			k = 3; yR = y;
		}
		else if (k == 3){
			tx = x, ty = lower_bound(X[x].begin(), X[x].end(), y) - X[x].begin() - 1;
			if (ty < 0) ty = yL + 1;
			else ty = max(yL + 1, X[x][ty] + 1);
			k = 4; xR = x;
		}
		else if (k == 4){
			tx = lower_bound(Y[y].begin(), Y[y].end(), x) - Y[y].begin() - 1, ty = y;
			if (tx < 0) tx = xL + 1;
			else tx = max(xL + 1, Y[y][tx] + 1);
			k = 1; yL = y;
		}
		if (x == tx && y == ty && flag) break;
		ans += abs(x - tx) + abs(y - ty); x = tx, y = ty;
		flag = 1;
	}
	if (ans == 1ll * n*m - K) printf("Yes\n");
	else printf("No\n");
	return 0;
}