Codeforces Round 618 (Div. 2)

题目

Codeforces Round 618 (Div. 2) - Codeforces

Problem - A

方法一：枚举 模拟

思路

题目要求数组 $a$ 的和不能为 0，且积也不能为 0（即：数组中不能出现元素 $0$）。

所以可以先对数组中所有 0 进行一次 +1 操作，随后如果数组和为 0 则再进行一次 +1 操作即可。

代码

#include <cstdio>

using namespace std;

int t, n;

void solve() {
    scanf("%d", &n);
    int sum = 0, zero_cnt = 0;
    for (int i = 0; i < n; ++i) {
        int x; scanf("%d", &x);
        if (x == 0) ++zero_cnt;
        sum += x;
    }
    int ans = zero_cnt;
    sum += zero_cnt;
    if (sum == 0) ++ans;
    printf("%d\n", ans);
}

int main() {
    scanf("%d", &t);
    while (t--) solve();

    return 0;
}

Problem - B

方法一：排序 中位数

思路

把一个偶数位的序列分成两个奇数位的序列，最小化这两个序列的中位数之差。这个最小值其实就是原偶数位序列的两个中位数之差（$a_{(len/2)+1} - a_{len/2}$）。

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;
int t, n;
int a[N];

void solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n * 2; ++i) scanf("%d", &a[i]);
    sort(a + 1, a + n * 2 + 1);
    printf("%d\n", a[n + 1] - a[n]);
}

int main() {
    scanf("%d", &t);
    while (t--) solve();

    return 0;
}

Problem - C

方法一：位运算

思路

考虑 $f(x,y)$ 的四种情况：

x	y	x|y	(x|y)-y
0	0	0	0
0	1	1	0
1	0	1	1
1	1	1	0

发现当且仅当在 $x$ 的某一位为 $1$，$y$ 的该位为 $0$ 时，该位才对答案有贡献。

展开 $f(f(\dots f(f(a_1, a_2), a_3), \dots), a_n)$ 得到： $(((((((a_1|a_2)-a_2)|a_3)-a_3)|\dots)-\dots)|a_n)-a_n$。

发现 $a_1$ 始终在 $x$ 的位置，所以只有在 $a_1$ 位置的数的位为 $1$ ，$a_2\dots a_n$ 该位为 $0$ 时，该位才对答案有贡献。

由于答案要使得到的数最大（而不是为 $1$ 的数位最多），所以从低位到高位，每一位对答案的贡献是指数递增的，具体来说是： $1_{(2)}:1, 10_{(2)}:2, 100_{(2)}:4, 1000_{(2)}:8, 10000_{(2)}:16, \dots$

具体做法是：

• 首先遍历数组，对于每一个数：
  • 遍历其每一二进制位，如果该位为 $1$，则在哈希表中把该位的计数增加。例如 $1001000_{(2)}$ 在遍历到第 3 位时为 $1000_{(2)}$ 则记录：cnts[0b1000] += 1。
• 再次遍历数组，对于每一个数：
  • 遍历其每一二进制位，如果该位为 $1_{(2)}$，且 $cnts[该位] = 1$，则说明该数若放在首位，该位对答案有贡献。例如： $1001000_{(2)}$ 在遍历到第 6 位时为 $1000000_{(2)}$ 且此时记录 cnts[0b1000000] == 1，则该数该位的贡献为 $1000000_{(2)}=64_{(10)}$。
  • 计算每个数的总贡献的同时，维护一个最大贡献值。
• 把最大贡献值的数放在首位，其他位随便放（按照原序列顺序放）即为答案。

代码

#include <cstdio>
#include <unordered_map>

using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];
unordered_map<int, int> cnts;

int lowbit(int x) {
    return x & -x;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        int x = a[i];
        while (x) {
            int mask = lowbit(x);
            ++cnts[mask];
            x -= mask;
        }
    }
    int mx = 0, mx_idx = 0;
    for (int i = 0; i < n; ++i) {
        int x = a[i];
        int val = 0;
        while (x) {
            int mask = lowbit(x);
            if (cnts[mask] == 1) val += mask;
            x -= mask;
        }
        if (val > mx) {
            mx = val;
            mx_idx = i;
        }
    }
    printf("%d ", a[mx_idx]);
    for (int i = 0; i < n; ++i) {
        if (mx_idx != i) printf("%d ", a[i]);
    }

    return 0;
}

Problem - D

方法一：计算几何

思路

$T$ 是一个有 $n$ 个点的凸多边形。

把 $T$ 平移 $n$ 次，每一次将一个顶点与原点 $(0, 0)$ 重合。

如上操作得到了图形 $P$，显然，$P$ 是一个关于原点中心对称的图形。

故若要使 $P$ 与 $T$ 相似， $T$ 也必须是一个中心对称图形。

判断 $T$ 是否中心对称即可。

代码

#include <cstdio>

using namespace std;

const int N = 1e5 + 10;
int n;
struct Polygen {
    int x, y;
} p[N];

int main() {
    scanf("%d", &n);
    if (n & 1) {
        puts("NO");
        return 0;
    }
    for (int i = 0; i < n; ++i) scanf("%d%d", &p[i].x, &p[i].y);
    double xx, yy;
    for (int i = 0; i < n / 2; ++i) {
        double cx = (p[i].x + p[i + n / 2].x) / 2.0;
        double cy = (p[i].y + p[i + n / 2].y) / 2.0;
        if (i == 0) xx = cx, yy = cy;
        else if (cx != xx || cy != yy) {
            puts("NO");
            return 0;
        }
    }
    puts("YES");

    return 0;
}

Problem - E

方法一：单调栈

设有一数组 $\{ a_1, a_2, a_3, a_4, a_5 \}$，其以 $a_3, a_4$ 之间为界被分为两段：$seg_1 = \{ a_1, a_2, a_3 \}, seg_2 = \{ a_4, a_5 \}$ ，故有：$seg_1$ 和为 $sum_1$，长度为 $len_1$；$seg_2$ 和为 $sum_2$，长度为 $len_2$。

此时，如何判断是否应该合并 $seg_1$ 与 $seg_2$ ？

为使数组的字典序尽可能小，若合并后的整段平均值 <= $seg_1$ 的平均值则应该合并，否则反之。

即判断是否有： $\frac{sum_1 + sum_2}{len_1 + len_2} \le \frac{sum_1}{len_1}$，化简一下：

$$\begin{aligned} \frac{sum_1 + sum_2}{len_1 + len_2} &\le \frac{sum_1}{len_1} \\ (sum_1 + sum_2)\cdot len_1 &\le sum_1 \cdot (len_1 + len_2) \\ \cancel{sum_1 len_1} + sum_2 len_1 &\le \cancel{sum_1 len_1} + sum_1 len_2) \\ sum_2 len_1 &\le sum_1 len_2 \\ \frac{sum_2}{len_2} &\le \frac{sum_1}{len_1} \\ \end{aligned}$$

如上我们发现，每一段的平均值是单调不递减的，即答案序列一定是单调不递减的，观察测试用例也符合这个规律。

综上：维护一个单调栈，其中每个元素以 $\{sum, len \}$ 的形式表示一个分段。枚举数组中每个元素：

• 把当前元素当作一个 $\{a_u, 1\}$ 的分段；
• 将该分段与栈顶分段 $\{ sum_t, len_t \}$ 对比：
  • 若 $a_u \cdot len_t \le sum_t \times 1$ （由上面化简不等式 $sum_2 len_1 \le sum_1 len_2$ 得来）成立，则弹出栈顶，把其和并在当前段上；
  • 循环该操作直到栈空或上一步不成立。

最后，栈中（从栈顶到栈底）即为倒序的答案分段，反向输出（注意要把分段还原为一段序列）即可。

代码

#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;
int n;
struct Seg {
    LL sum;
    int len;
} stk[N];
int tt;

int main() {
    scanf("%d", &n);
    while (n--) {
        Seg u = {0LL, 1};
        scanf("%lld", &u.sum);
        while (tt && u.sum * stk[tt].len <= stk[tt].sum * u.len) {
            u.sum += stk[tt].sum, u.len += stk[tt].len;
            --tt;
        }
        stk[++tt] = u;
    }
    for (int i = 1; i <= tt; ++i) {
        int len = stk[i].len;
        double avg = 1.0 * stk[i].sum / stk[i].len;
        while (len--) printf("%.9llf\n", avg);
    }

    return 0;
}