Codeforces Round #618 (Div. 1) 题解

Codeforces Round #618 (Div. 1)

Anu Has a Function

从高到低位贪心。

const int N = 1e5 + 7;
int n, a[N];
vi e[31];

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i]);
	for (int i = 30; ~i; i--)
		for (int j = 1; j <= n; j++)
			if ((a[j] >> i) & 1) e[i].pb(j);
	for (int i = 30; ~i; i--)
		if (e[i].size() == 1u) {
			int x = e[i][0];
			print(a[x], ' ');
			for (int j = 1; j <= n; j++)
				if (j != x) print(a[j], ' ');
			return 0;
		}
	for (int i = 1; i <= n; i++) print(a[i], ' ');
	return 0;
}

Aerodynamic

判断是否为中心对称图形即可。

const int N = 1e5 + 7;
int n, x[N], y[N];

int main() {
	rd(n);
	if (n & 1) return prints("NO"), 0;
	for (int i = 1; i <= n; i++) rd(x[i]), rd(y[i]);
	int X = x[1] + x[n/2+1], Y = y[1] + y[n/2+1];
	for (int i = 1; i <= n / 2; i++) {
		int j = i + n / 2;
		if (x[i] + x[j] != X || y[i] + y[j] != Y) return prints("NO"), 0;
	}
	prints("YES");
	return 0;
}

Water Balance

分成若干个极大的不升段，那么显然每一段内是肯定要合并的。

从后往前贪心，若合并后更优则合并，否则不合并。

const int N = 1e6 + 7;
int n, a[N], v[N], r[N], l[N];
ll s[N];

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i]), v[i] = a[i] > a[i-1];
	a[n+1] = 1e9, v[n+1] = 1;
	for (int i = n, j = n + 1; i; i--) r[i] = j, j = v[i] ? i : j;
	l[n+1] = 1, s[n+1] = 1e9;
	for (int i = n; i; i--)
		if (v[i]) {
			l[i] = r[i] - i;
			for (int j = i; j < r[i]; j++) s[i] += a[j];
			while (s[i] * l[r[i]] > s[r[i]] * l[i])
				s[i] += s[r[i]], l[i] += l[r[i]], r[i] = r[r[i]];
		}
	for (int i = 1; i <= n; i += l[i])
		for (int j = 1; j <= l[i]; j++)
			printf("%.10Lf\n", 1.0L * s[i] / l[i]);
	return 0;
}

Around the World

注意到大小为 $5$ 的线性基只有 $374$ 个就可以了。

So Mean

题目太神仙了，先咕咕咕着。