http://codeforces.com/contest/1416

B. Make Them Equal

 

题意：给定一个数列，每次选择 i，j，x，使得 ai:=ai−x⋅i,aj:=aj+x⋅ia_i := a_i - x \cdot i,a_j := a_j + x \cdot i。每次操作后必须非负。问不超过 3n 次操作后所有数相等。

贪心

先把所有数都尽量变小，把第一个数尽量变大。再重新分配。

变小时可能需要先从第一个数中拿一些，再给出去。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int T;
int n;
ll a[N];
ll sum;
struct X
{
	int i, j; ll x;
};
vector<X>vc;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		sum = 0;
		for (int i = 1; i <= n; i++)scanf("%lld", &a[i]), sum += a[i];
		if (sum%n != 0) { puts("-1"); continue; }
		sum /= n;
		vc.clear();
		bool flg = 1;
		for (int i = 2; i <= n; i++) {
			ll t = (i - a[i] % i) % i;
			if (a[1] >= t) {
				a[1] -= t;
				a[i] += t;
				vc.push_back(X{ 1,i,t });
			}
			t = a[i] / i;
			a[i] -= t * i;
			a[1] += t * i;
			vc.push_back(X{ i,1,t });
		}
		for (int i = 2; i <= n && flg; i++) {
			if (a[i] > sum) { flg = 0; break; }
			ll t = sum - a[i];
			a[i] += t;
			a[1] -= t;
			vc.push_back(X{ 1,i,t });
		}
		if (!flg) { puts("-1"); continue; }
		if (a[1] != sum) { while (1); }
		printf("%d\n", (int)vc.size());
		for (X u : vc)printf("%d %d %lld\n", u.i, u.j, u.x);
	}
	return 0;
}

 

C. XOR Inverse

 

题意：给定一个数列，求 x，数列中每个每个数异或x，成为新的数列，要新数列的逆序对最少，求满足条件的最小 x。

dfs

对于最高位，为 1 的数和为 0 的数已经可以确定一部分逆序对了，先把能确定的算出来，再dfs进入下一位继续求。

由于是2进制，所以最高位时求的答案和剩下位求的答案不会冲突，所以直接判断x该位为0还是为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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int n;
int a[N];
vector<int>vc;
int m;
ll ans, x, co[100][2];
void dfs(int dep, vector<int>& vc) {
	if (dep < 0 || vc.empty()) {
		return;
	}
	vector<int>t[2];
	ll cnt0 = 0, cnt1 = 0;
	for (int u : vc) {
		if ((u >> dep & 1) == 0)cnt0 += (int)t[1].size();
		else cnt1 += (int)t[0].size();
		t[u >> dep & 1].push_back(u);
	}
	co[dep][0] += cnt0;
	co[dep][1] += cnt1;
	dfs(dep - 1, t[0]);
	dfs(dep - 1, t[1]);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		vc.push_back(a[i]);
		int x = a[i], c = 0;
		while (x) {
			c++;
			x >>= 1;
		}
		m = max(m, c);
	}
	dfs(m - 1, vc);
	for (int i = m - 1; i >= 0; i--) {
		if (co[i][0] > co[i][1])x |= (1ll << i);
		ans += min(co[i][0], co[i][1]);
	}
	printf("%lld %lld\n", ans, x); 
	return 0;
}