http://codeforces.com/contest/1408

D. Searchlights

 

题意：二维平面上给定 n 个机器人，m 个监控，1≤n,m≤20001 \leq n, m \leq 2000，每个监控可以覆盖 (1,1)(1,1) 到 (ci,di)(c_i,d_i) 这个矩形范围。每次操作可以把所有机器人向上平移或向右平移，问最少操作次数使得所有机器人都不在监控范围内。

枚举

枚举向右平移多少次，计算需要向上平移的次数。

需要向上平移的次数等于所有机器人所在坐标的 y坐标 与所在 x坐标对应的y的上边界 的差值。

枚举每个机器人和每个监控，记录向右移动 i 距离时，需要向上移动的距离的最大值。

随着往右平移，需要向上平移的次数递减，即向右移动越多，向上移动越少（或相同）。

这是一个类似阶跃函数的形式，先处理出阶跃的点，再画出平台。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 4e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
#define ull unsigned ll
const double eps = 1e-7;
#define debug(x) cout<<#x<<":\t"<<x<<endl;
int n, m;
int a[N], b[N], c[N], d[N], mx[N];
int ans = INF;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)scanf("%d%d", &a[i], &b[i]);
	for (int i = 1; i <= m; i++)scanf("%d%d", &c[i], &d[i]);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (c[j] >= a[i]) {
				mx[c[j] - a[i]] = max(mx[c[j] - a[i]], d[j] - b[i] + 1);
			}
		}
	}
	for (int i = 1000001; i >= 0; i--)mx[i] = max(mx[i], mx[i + 1]);
	for (int i = 0; i <= 1000001; i++) {
		ans = min(ans, i + mx[i]);
	}
	printf("%d\n", ans);
	return 0;
}

 

F. Two Different

 

题意：给定一个数列，1≤n≤15 0001 \leq n \leq 15\,000，初始时 a[i]=ia[i]=i，每次操作选择 a[i],a[j]a[i],a[j]，都变为 f(a[i],a[j])f(a[i],a[j])，ff 为数对到数的映射，且不同的数对映射到不同的数。要求操作不超过 5⋅1055\cdot10^5 次，使得数列中只有不超过2个不同的数。

分治+构造

复杂度是 O(nlog⁡n)O(n\log n) ，所以考虑分治。

假设左边有一些相同的数，右边也有一些相同的数，现在要把这些数变成都相同。例如11122，左边第一个 1 和右边第一个 2 配对，左边第二个 1 和右边第二个 2 配对。现在变成 (1,2) (1,2) 1 (1,2) (1,2) ，左边第三个 1 就没法配对了。

因而如果左右两边的个数不同，则无法使得所有数相同。

所以必须要使得长度为 2 的幂次。

取 lenlen 为小于 n 的最大的 2 的幂次。则先对左边用上面的方法操作，再对右边用上面的方法操作，可能中间会有重叠的部分，但是没有影响。

T(n)=2T(n/2)+O(n)T(n)=2T(n/2)+O(n)，主定理得到 T(n)=O(nlog⁡n)T(n)=O(n\log 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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 4e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
#define ull unsigned ll
const double eps = 1e-7;
#define debug(x) cout<<#x<<":\t"<<x<<endl;
int n;
int len = 1;
typedef pair<int, int>pii;
vector<pii>vc;
void dfs(int l, int r) {
	if (l == r)return;
	int mid = (l + r) / 2, le = r - l + 1;
	dfs(l, mid);
	dfs(mid + 1, r);
	for (int i = l; i <= mid; i++) {
		vc.push_back({ i,i + le / 2 });
	}
}
int main() {
	scanf("%d", &n);
	if (n <= 2) { puts("0"); return 0; }
	while (len < n)len <<= 1;
	len >>= 1;
	dfs(1, len);
	dfs(n - len + 1, n);
	printf("%d\n", (int)vc.size());
	for (pii p : vc)printf("%d %d\n", p.first, p.second);
	return 0;
}