侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

Codeforces Round 618 (Div. 2)

GabrielxD
2023-10-27 / 0 评论 / 0 点赞 / 362 阅读 / 2,164 字
温馨提示:
本文最后更新于 2023-10-27,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

Codeforces Round 618 (Div. 2) - Codeforces

Problem - A

方法一:枚举 模拟

思路

题目要求数组 aa 的和不能为 0,且积也不能为 0(即:数组中不能出现元素 00)。

所以可以先对数组中所有 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)+1alen/2a_{(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)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

发现当且仅当在 xx 的某一位为 11yy 的该位为 00 时,该位才对答案有贡献。

展开 f(f(f(f(a1,a2),a3),),an)f(f(\dots f(f(a_1, a_2), a_3), \dots), a_n) 得到: (((((((a1a2)a2)a3)a3)))an)an(((((((a_1|a_2)-a_2)|a_3)-a_3)|\dots)-\dots)|a_n)-a_n

发现 a1a_1 始终在 xx 的位置,所以只有在 a1a_1 位置的数的位为 11a2ana_2\dots a_n 该位为 00 时,该位才对答案有贡献。

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

具体做法是:

  • 首先遍历数组,对于每一个数:
    • 遍历其每一二进制位,如果该位为 11,则在哈希表中把该位的计数增加。例如 1001000(2)1001000_{(2)} 在遍历到第 3 位时为 1000(2)1000_{(2)} 则记录:cnts[0b1000] += 1
  • 再次遍历数组,对于每一个数:
    • 遍历其每一二进制位,如果该位为 1(2)1_{(2)}cnts[该位]=1cnts[该位] = 1,则说明该数若放在首位,该位对答案有贡献。例如: 1001000(2)1001000_{(2)} 在遍历到第 6 位时为 1000000(2)1000000_{(2)} 且此时记录 cnts[0b1000000] == 1,则该数该位的贡献为 1000000(2)=64(10)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

方法一:计算几何

思路

TT 是一个有 nn 个点的凸多边形。

TT 平移 nn 次,每一次将一个顶点与原点 (0,0)(0, 0) 重合。

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

故若要使 PPTT 相似, TT 也必须是一个中心对称图形。

判断 TT 是否中心对称即可。

代码

#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

方法一:单调栈

设有一数组 {a1,a2,a3,a4,a5}\{ a_1, a_2, a_3, a_4, a_5 \},其以 a3,a4a_3, a_4 之间为界被分为两段:seg1={a1,a2,a3},seg2={a4,a5}seg_1 = \{ a_1, a_2, a_3 \}, seg_2 = \{ a_4, a_5 \} ,故有:seg1seg_1 和为 sum1sum_1,长度为 len1len_1seg2seg_2 和为 sum2sum_2,长度为 len2len_2

此时,如何判断是否应该合并 seg1seg_1seg2seg_2

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

即判断是否有: sum1+sum2len1+len2sum1len1\frac{sum_1 + sum_2}{len_1 + len_2} \le \frac{sum_1}{len_1},化简一下:

sum1+sum2len1+len2sum1len1(sum1+sum2)len1sum1(len1+len2)sum1len1+sum2len1sum1len1+sum1len2)sum2len1sum1len2sum2len2sum1len1\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}\{sum, len \} 的形式表示一个分段。枚举数组中每个元素:

  • 把当前元素当作一个 {au,1}\{a_u, 1\} 的分段;
  • 将该分段与栈顶分段 {sumt,lent}\{ sum_t, len_t \} 对比:
    • aulentsumt×1a_u \cdot len_t \le sum_t \times 1 (由上面化简不等式 sum2len1sum1len2sum_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;
}
0

评论区