Codeforces Round #618 (Div. 1) 题解

作者: xht37 分类: 题解 发布时间: 2020-02-10 00:32

点击数:194

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注