http://codeforces.com/contest/1300

C. Anu Has a Function

 

题意：定义 f(x,y)=(x∣y)−yf(x, y) = (x | y) - y，重排给定数列 [a1,a2,…,an][a_1, a_2, \dots, a_n]，使得 f(f(…f(f(a1,a2),a3),…an−1),an)f(f(\dots f(f(a_1, a_2), a_3), \dots a_{n-1}), a_n) 最大。

这个函数的作用就是从x中扣掉y里有1的位。

所以实际上只有第一个x对结果有影响，确定了第一个之后其它的顺序无所谓。

第一个里如果某一位有1而其它也存在数这一位为1，那么这个1必定被抠掉，仅当只有第一个数在这一位是1，它才会留到最后。所以就要找到最大的能留到最后的位。就是从大到小遍历找到某一位只有一个数在该位为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>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
int T;
int n, a[maxn];
vector<int>p[maxn];
int vis[maxn];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		for (int k = 0; k <= 30; k++) {
			if ((1 << k)&a[i])p[k].push_back(i);
		}
	}
	int k = 30;
	for (; (int)p[k].size() != 1 && k >= 0; k--);
	if (k >= 0)for (int u : p[k])printf("%d ", a[u]), vis[u] = 1;
	for (int i = 1; i <= n; i++)if (!vis[i])printf("%d ", a[i]);
	puts("");
	return 0;
}

 

D. Aerodynamic

 

题意：给定一个凸多边形P，移动P使得原点在这个多边形内，这些多边形构成多边形T。问T和P是否相似。

样例实在太良心了，最后一个样例直接表明了，YES等价于每条边都与它的对边平行。

可以直接做了，当然还可以再转变一下。

每条边都与对边平行等价于每个点和它的对顶点的中点都是同一点。

先证充分性：随便取一组对边，构成平行四边形，平行四边形对角线互相平分，所以中点重合，再取相邻的一组对边，这两个平行四边形一定有一个共用的对角线，则由第二个平行四边形的两个对角线中点重合可以得到三条对角线中点重合。以此类推，所有对角线中点重合。

必要性：问题可以简化为一个四边形两条对角线互相平分，证明是平行四边形，就是初中数学题了，平移一条边，由中位线定理证明平行。

所以直接枚举每对相对顶点，判断中点是否为同一点即可。

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
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
int n;
int x[maxn], y[maxn];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &x[i], &y[i]);
	}
	if (n & 1) { puts("NO"); return 0; }
	double dx = 0.5*(x[1] + x[1 + n / 2]), dy = 0.5*(y[1] + y[1 + n / 2]);
	int k = n / 2;
	for (int i = 2; i <= k; i++) {
		if (0.5*(x[i] + x[i + k]) != dx || 0.5*(y[i] + y[i + k]) != dy) {
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}

 

E. Water Balance

 

题意：给定初始一个数组，可以操作任意次，每次操作选一个区间，把区间里所有数变为区间里数的平均值。要求数组的字典序最小。可以有浮点数。

贪心

每输入一个数就把它当成一个独立的区间，试着与前面的区间合并，如果前面的区间平均值大于后面的，就合并。

证明贪心的正确性：假设读入一个数，且前面的所有数已经达到最优。

假设当前区间均值大于前面区间平均值，与前面整个区间合并肯定不赚，而如果把前面的区间拆掉合并，最前面的数一定变大，更不赚。而由于假设了前面已经最优，所以把当前区间拆掉的情况不存在。

而如果当前区间小于前面区间均值，如果都要合并的话，马上合并与等后面的一起合并是一样的，马上合并并不会导致后面的合并不了，反而等后面的一起合并会导致多合并一些不需要的。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int n;
ll a[maxn];
ll sum[maxn], len[maxn];
int main() {
	cin >> n;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		ll x, y = 1;
		scanf("%lld", &x);
		while (cnt&&sum[cnt] * y >= x * len[cnt]) {
			x += sum[cnt];
			y += len[cnt--];
		}
		sum[++cnt] = x;
		len[cnt] = y;
	}
	for (int i = 1; i <= cnt; i++) {
		for (int j = 1; j <= len[i]; j++)
			printf("%.9lf\n", 1.0*sum[i] / len[i]);
	}
	return 0;
}