http://codeforces.com/contest/1301

C. Ayoub’s function

 

题意：已知一个n位的01串中有k个1，问最多有几个子串中至少有1个1.

反面考虑有几个串只有0。每一段长度为a的连续的0会有 a⋅(a+1)2\frac{a\cdot(a+1)}{2} 个只有0的串，把所有连续0结果加起来就是总的只有0的串。

相当于最小化 a⋅(a+1)+(n−a)⋅(n−a+1)=2⋅(a2−na)+n2+na\cdot (a+1)+(n-a)\cdot (n-a+1)=2\cdot(a^2-na)+n^2+n，当 a=n2a=\frac{n}{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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int T;
ll n, m;
ll cal(ll x) {
	return (x + 1)*x / 2;
}
int main() {
	cin >> T;
	while (T--) {
		scanf("%lld%lld", &n, &m);
		ll ans = 0;
		ll cnt0 = n - m, cnt1 = m;
		ll blo = cnt0 / (cnt1 + 1), rs = cnt0 % (cnt1 + 1);
		ans = rs*cal(blo + 1) + (cnt1 + 1 - rs)*cal(blo);
		ans = cal(n) - ans;
		printf("%lld\n", ans);
	}
	return 0;
}

 

D. Time to Run

 

题意：nm网格上相邻两格间有两条有向道路，要求走k步，不能重复经过同一条边，输出路径。

每一格入度出度和为0，可知存在欧拉路径，那么所有路径都可以一笔走完，不经过重复边，只要找到一个周期性输出路径的方法。

又是一个蛇形构造

不断地周期性添加操作，直到k减小到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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, char>pic;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n, m, k;
vector<pic>ans;
void add(int t, char c) {
	t = min(t, k);
	k -= t;
	if (t)ans.push_back(pic(t, c));
}
void solve() {
	for (int i = 0; i < n - 1; i++) {
		add(m - 1, 'R'); add(m - 1, 'L'); add(1, 'D');
	}
	for (int i = 0; i < m - 1; i++) {
		add(1, 'R'); add(n - 1, 'U'); add(n - 1, 'D');
	}
	add(m - 1, 'L'); add(n - 1, 'U');
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	if (k > 4 * n*m - 2 * n - 2 * m)puts("NO");
	else {
		puts("YES");
		solve();
		printf("%d\n", (int)ans.size());
		for (pic p : ans)
			printf("%d %c\n", p.first, p.second);
	}
	return 0;
}

 

E. Nanosoft

 

题意：给定矩阵区域内找到类似下图的正方形的最大面积。

二维前缀和

O(n3)O(n^3) 预处理出每个格子作为正方形左上角的最长边长，每个格子作为左上角的正方形是唯一的。可以先二维前缀和找到每个区域里的四种颜色分别的个数，验证能否成为特定长度，特定左上角的正方形能否存在时可以用四种颜色的前缀和验证个数是否满足，再求前缀和以便以后查询。

之后对于每个询问，可以 O(n)O(n) 枚举正方形边长，再验证区域内是否存在特定边长的正方形左上角，注意并不是查询整个区域内的前缀和，而是左上角可能存在的区域的前缀和。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n, m, q;
int g[501][501], r[501][501], y[501][501], b[501][501], f[501][501][501];
char mz[510][510];
int cal(int r1, int c1, int r2, int c2, int a[501][501]) {
	return a[r2][c2] - a[r1 - 1][c2] - a[r2][c1 - 1] + a[r1 - 1][c1 - 1];
}
bool check(int i, int j, int k) {
	int a = k / 2, S = a * a;
	if (i + 2 * a - 1 > n || j + 2 * a - 1 > m)return false;
	if (cal(i, j, i + a - 1, j + a - 1, r) < S)return false;
	if (cal(i, j + a, i + a - 1, j + 2 * a - 1, g) < S)return false;
	if (cal(i + a, j, i + 2 * a - 1, j + a - 1, y) < S)return false;
	if (cal(i + a, j + a, i + 2 * a - 1, j + 2 * a - 1, b) < S)return false;
	return true;
}
int main() {
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf(" %c", &mz[i][j]);
			switch (mz[i][j])
			{
			case 'R':r[i][j] = 1; break;
			case 'G':g[i][j] = 1; break;
			case 'B':b[i][j] = 1; break;
			case 'Y':y[i][j] = 1; break;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			r[i][j] = r[i][j] + r[i - 1][j] + r[i][j - 1] - r[i - 1][j - 1];
			g[i][j] = g[i][j] + g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
			b[i][j] = b[i][j] + b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
			y[i][j] = y[i][j] + y[i - 1][j] + y[i][j - 1] - y[i - 1][j - 1];
		}
	}
	int L = min(n, m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (mz[i][j] != 'R')continue;
			for (int k = 2; k <= L; k += 2) {
				if (check(i, j, k)) { f[k][i][j] = 1; break; }
			}
		}
	}
	for (int k = 2; k <= L; k += 2) {
		for (int i = 1; i + k - 1 <= n; i++) {
			for (int j = 1; j + k - 1 <= m; j++) {
				f[k][i][j] = f[k][i][j] + f[k][i - 1][j] + f[k][i][j - 1] - f[k][i - 1][j - 1];
			}
		}
	}
	while (q--) {
		int r1, c1, r2, c2;
		scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
		int res = 0;
		int k = min(r2 - r1 + 1, c2 - c1 + 1);
		k -= (k & 1);
		for (; k > 0; k -= 2) {
			if (f[k][r2 - k + 1][c2 - k + 1] - f[k][r1 - 1][c2 - k + 1] - f[k][r2 - k + 1][c1 - 1] + f[k][r1 - 1][c1 - 1] > 0) {
				res = k; break;
			}
		}
		printf("%d\n", res*res);
	}
	return 0;
}

 

F. Super Jaber

 

题意：nm的网格上每点有颜色，相同颜色距离为1，相邻点距离为1，多次询问，问从起点到终点的最短距离。

起点会变，所以没法直接bfs，但是发现颜色很少，想到要枚举颜色bfs，预处理出每点到某个颜色的最短距离。

询问时先判断是否需要同颜色传送，如果需要，则枚举颜色的时候一定能够找到某个颜色作为中间值，且起点和终点到这个颜色一定都是走的最短距离，注意答案要再加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
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n, m, k;
vector<pii>col[100];
int d[50][1010][1010], c[1010][1010], vis[100];
int dx[]{ 0,0,-1,1 };
int dy[]{ -1,1,0,0 };
queue<pii>q;
void bfs(int co) {
	memset(vis, 0, sizeof(vis)); vis[co] = 1;
	for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)d[co][i][j] = -1;
	for (pii p : col[co])d[co][p.first][p.second] = 0, q.push(p);
	while (!q.empty()) {
		int x = q.front().first, y = q.front().second; q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && d[co][nx][ny] == -1) {
				d[co][nx][ny] = d[co][x][y] + 1;
				q.push(pii(nx, ny));
			}
		}
		if (vis[c[x][y]])continue;
		vis[c[x][y]] = 1;
		for (pii p : col[c[x][y]]) {
			if (d[co][p.first][p.second] == -1) {
				d[co][p.first][p.second] = d[co][x][y] + 1;
				q.push(p);
			}
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			scanf("%d", &c[i][j]), col[c[i][j]].push_back(pii(i, j));
	}
	for (int i = 1; i <= k; i++)bfs(i);
	int q;
	scanf("%d", &q);
	while (q--) {
		int r1, c1, r2, c2;
		scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
		int ans = abs(r1 - r2) + abs(c1 - c2);
		for (int i = 1; i <= k; i++) {
			ans = min(ans, d[i][r1][c1] + d[i][r2][c2] + 1);
		}
		printf("%d\n", ans);
	}
	return 0;
}