http://codeforces.com/contest/1393

C. Pinkie Pie Eats Patty-cakes

 

题意：给定一个数组，要求重排，使得相同数字间隔尽量远，问最远能间隔的距离。

贪心+（二分）

把所有数字按照出现次数排序，出现次数最大的先安排。

出现次数最大的数字把整个数组分成几块，其它数字都可以放在里面，且一定可以构造出使得其他数字间隔都不小于出现次数最大的数字的间隔的方案数。

所以可以二分答案，贪心构造。

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
#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 c[N], n, d[N];
bool ck(int x) {
	for (int i = 1; i <= n && c[i]; i++) {
		ll len = 1 + 1ll*(c[i] - 1)*(x + 1);
		if (i + len - 1 > n)return false;
	}
	return true;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)c[i] = 0;
		for (int i = 1; i <= n; i++) {
			int x;
			scanf("%d", &x);
			c[x]++;
		}
		sort(c + 1, c + n + 1, greater<int>());
		int L = 0, R = n;
		while (L < R) {
			int mid = (L + R + 1) / 2;
			if (ck(mid))L = mid;
			else R = mid - 1;
		}
		printf("%d\n", L);
	}
	return 0;
}

 

或者直接推出结果。

假设出现次数最大的数字出现了 k 次，且有 x 个数字都是出现次数最大的数字。则还有 n−xkn-xk 个数字要塞到间隔里。出现次数最大的数字把整个数组分成了 k−1k-1 块，则最大间隔是 n−xkk−1\frac{n-xk}{k-1}，又由于有 x 个数字都是出现次数最大的数字，这些数字都绑在一起，使得间隔增大了 x−1x-1，所以最终结果就是 n−xkk−1+x−1\frac{n-xk}{k-1}+x-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
#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], c[N], mx;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		fill(c, c + n + 1, 0);
		mx = 0;
		for (int i = 1; i <= n; i++)scanf("%d", &a[i]), c[a[i]]++, mx = max(mx, c[a[i]]);
		int x = 0;
		for (int i = 1; i <= n; i++)if (c[i] == mx)x++;
		printf("%lld\n", (n - 1ll*x * mx) / (mx - 1) + x - 1);
	}
	return 0;
}

 

D. Rarity and New Dress

 

题意：给定一个nm的字符矩阵，问满足内部所有字符都相同的斜正方形的个数。

dp

直接求斜正方形不好求，但是可以把斜正方形看成一个上三角和一个下三角拼起来，而以某一点为正中心的斜正方形的个数就是以该点为底边正中心的上三角和下三角大小的最小值。

up[i][j]up[i][j] 表示以 s[i][j]s[i][j] 为底边正中心的最大的上三角的大小。

down[i][j]down[i][j] 表示以 s[i][j]s[i][j] 为底边正中心的最大的下三角的大小。

len[i][j]len[i][j] 表示以 s[i][j]s[i][j] 为正中心的底边的最大长度的一半。这也就限制了上三角和下三角的最大大小不能超过 len[i][j]len[i][j]。

从 s[i−1][j]s[i-1][j] 转移得到，如果 s[i][j]==s[i−1][j]s[i][j]==s[i-1][j]，则可以由 s[i−1][j]s[i-1][j] 的上三角和 s[i][j]s[i][j] 的底边拼接得到 s[i][j]s[i][j] 的上三角。up[i][j]=min⁡(up[i−1][j]+1,len[i][j])up[i][j]=\min(up[i-1][j]+1,len[i][j])；否则 up[i][j]=1up[i][j]=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
#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;
char s[2020][2020];
int up[2020][2020], down[2020][2020], l[2020][2020], r[2020][2020], len[2020][2020];
ll ans;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)scanf("%s", s[i] + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (s[i][j] == s[i][j - 1])l[i][j] = l[i][j - 1] + 1;
			else l[i][j] = 1;
		}
		for (int j = m; j >= 1; j--) {
			if (s[i][j] == s[i][j + 1])r[i][j] = r[i][j + 1] + 1;
			else r[i][j] = 1;
		}
		for (int j = 1; j <= m; j++)len[i][j] = min(l[i][j], r[i][j]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (s[i][j] == s[i - 1][j]) {
				up[i][j] = min(len[i][j], up[i - 1][j] + 1);
			}
			else up[i][j] = 1;
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = 1; j <= m; j++) {
			if (s[i][j] == s[i + 1][j]) {
				down[i][j] = min(len[i][j], down[i + 1][j] + 1);
			}
			else down[i][j] = 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ans += min(up[i][j], down[i][j]);
		}
	}
	printf("%lld\n", ans);
	return 0;
}