http://codeforces.com/contest/1269

B. Modulo Equality

 

题意：给定 a,ba,b 两个数组，求最小的 XX ，使得 (a[i]+X)mod  m(a[i]+X)\mod m 与 bb 的某个排列一一对应。

没法暴力枚举 XX，所以考虑枚举减小枚举的范围，枚举 bb 中的数，作为与 a[1]a[1] 对应的 b[1]b[1]，可以得到唯一的 XX，再验证 XX 是否满足其它 a[i],b[j]a[i],b[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
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m;
vector<int> a, b;
int main(){
	scanf("%d%d", &n, &m);
	a.resize(n), b.resize(n);
	for (int i = 0; i < n; i++)scanf("%d", &a[i]);
	for (int i = 0; i < n; i++)scanf("%d", &b[i]);
	sort(b.begin(), b.end());
	int ans = INF;
	for (int i = 0; i < n; ++i){
		int x;
		if (b[0] >= a[i])x = b[0] - a[i];
		else x = m + b[0] - a[i];
		vector<int> c(a);
		for (int j = 0; j < n; ++j) c[j] = (c[j] + x) % m;
		sort(c.begin(), c.end());
		if (c == b)ans = min(ans, x);
	}
	printf("%d\n", ans);
	return 0;
}

 

D. Domino for Young

 

题意：有类似以下图形，保证从左向右格子数递减，向其中放1x2的矩形，问最多放几个。

构造

神奇的题目。

向上面这样涂色后每个矩形必定占1个蓝，1个白，而可以证明（或者猜）一定是可以尽量放满的，也就是说矩形数量等于蓝格，白格中的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pii;
const int INF = 0x3f3f3f3f;
const int N = 3e5 + 10;
int n;
ll a[N], c[2];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
	for (int i = 1; i <= n; i++) {
		c[0] += a[i] / 2, c[1] += a[i] / 2;
		c[i % 2] += a[i] % 2;
	}
	cout << min(c[0], c[1]) << endl;
	return 0;
}

 

E. K Integers

 

字节跳动网络赛同名题的改装版。。

题意：给定一个 nn 的排列，每次操作交换两个相邻数，定义 f(k)f(k) 为存在 11 到 kk 的连续段的最小操作数，求 f(1)f(1) 到 f(n)f(n)。

树状数组，二分

首先把所有 11 到 kk 聚集到一起，然后就是求逆序对数。

逆序对数用树状数组求。

要聚集肯定是把中间所有大于 kk 的数往数少的那边移出去，也相当于把所有 11 到 kk 的数往最中间聚集，最中间就是左边 11 到 kk 的数的个数为 k/2k/2 的位置，可以在树状数组上二分找到。

找到 midmid 之后，设原位置为 p[i]p[i]，最终位置为 t[i]t[i]，则左边的数的总操作数为 ∑i<midt[i]−p[i]\sum_{i < mid} t[i]-p[i]，右边的操作数为 ∑i>midp[i]−t[i]\sum_{i > mid}p[i]-t[i]，t[i]t[i] 是 midmid 周围的总数为 kk 的等差数列，知道 midmid 后可以直接求。pp 可以再维护一个树状数组，在每个 p[i]p[i] 的位置上加 p[i]p[i]，这样求和就是 ∑p[i]\sum p[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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pii;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int n, a[N], p[N];
ll s1[N], s2[N];
int lowbit(int x) {
	return x & -x;
}
void add(ll* sum, int x, int b) {
	for (int i = x; i <= n; i += lowbit(i)) {
		sum[i] += b;
	}
}
ll query(ll* sum, int r) {
	ll ans = 0;
	for (int i = r; i > 0; i -= lowbit(i)) {
		ans += sum[i];
	}
	return ans;
}
ll ans;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		p[a[i]] = i;
	}
	for (int i = 1; i <= n; i++) {
		add(s1, p[i], 1);
		add(s2, p[i], p[i]);
		ans += 1ll*i - query(s1, p[i]);
		int L = 1, R = n;
		while (L < R) {
			int mid = L + R + 1 >> 1;
			if (query(s1, mid - 1) * 2 <= i)L = mid;
			else R = mid - 1;
		}
		ll aa = 1ll * i / 2, bb = 1ll * i - 1ll * i / 2 - 1ll;
		ll sum = (2 * L - aa - 1)*aa / 2 - query(s2, L - 1);
		sum += query(s2, n) - query(s2, L) - (2 * L + bb + 1)*bb / 2;
		printf("%lld%s", ans + sum, i == n ? "\n" : " ");
	}
	return 0;
}