codeforces 1095 (div3) • santisify Site

A. Koshary#

题目描述#

在平面坐标系中两种移动方式向某个轴的正方向走 1 (最多一次)或者 2 步. 问：能否从(0,0)走到(x, y).

解题思路#

因为最多走一次1步,所以可以直接考虑x和y是否同时为奇数就可以判定了.

参考代码#

void solve() {
    int x, y;
    std::cin >> x >> y;
    std::cout << ((x % 2 && y % 2) ? "NO" : "YES") << std::endl;
}

cpp

B. Party Monster#

题目描述#

给出一个括号字符串,是否可以对这个字符串重新排列成一个合法的括号序列.

解题思路#

既然是对字符串重新排列,那么只要有成对的()就可以排列成合法的序列.

参考代码#

void solve() {
    int n;
    std::string s;
    std::cin >> n >> s;
    if (n & 1) {
        std::cout << "NO" << std::endl;
        return;
    }
    int ct1 = 0, ct2 = 0;
    for (int i = 0; i < n; i ++) {
        ct1 += (s[i] == '(');
        ct2 += (s[i] == ')');
    }

    std::cout << (ct1 == ct2 ? "YES" : "NO") << std::endl;
}

cpp

C. Snowfall#

题目描述#

给定一个数组,现在需要对数组进行排序,使得该数组中的子数组的乘积 $\prod_{i=l}^{r}a_{i}(1\le l\le r\le n)$ 能被6整除的子数组数量最少.

解题思路#

被6整除可以分为两种情况:

$a_{i} \% 6 = 0$ ,即 $a_{i}$ 为6的倍数

$(a_{i} * a_{j}) \% 6=0$ ,即 $a_{i}$ 为2的倍数( $a_{j}$ 为3的倍数)或者 $a_{i}$ 为3的倍数( $a_{j}$ 为2的倍数) >首先可以想到数组中能被6整除的数随意放位置,那么就需要考虑能被2和3整除的数如何放了,很明显尽可能让2和3的倍数放在一起.

参考代码#

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i ++) std::cin >> a[i];
    std::vector<int> b, c, d, e;
    for (int i = 0; i < n; i ++) {
        if (a[i] % 6 == 0) b.push_back(a[i]);
        else if (a[i] % 3 == 0) e.push_back(a[i]);
        else if (a[i] % 2 == 0) c.push_back(a[i]);
        else d.push_back(a[i]);
    }

    for (auto i : b) {
        std::cout << i << " ";
    }
    for (auto i : c) {
        std::cout << i << " ";
    }
    for (auto i : d) {
        std::cout << i << " ";
    }
    for (auto i : e) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

cpp

D. Palindromex#

题目描述#

一个长为2n数组(数组中的数 $x \in [0,n-1]$ ,并且每个数出现两次)中的所有回文数组的最大mex mex:数组中不出现的最小非负整数. 回文数组:和回文字符串同理,将数组倒置和原数组一致.

解题思路#

想要mex最大,那一定包含数字0,既然每个数都出现两次，那么我们就可以直接找到两个0的位置，回文字符串要么包含其中一个0，要么包含两个0.

包含一个0,直接向外拓展.

包含两个0,找到两个0的中心点，向外拓展. >最后取这些情况的最大值即可.

参考代码#

void solve() {
    int n, p1 = -1, p2 = -1;
    std::cin >> n;
    std::vector<int> a(n * 2 + 1, 0);
    for (int i = 0; i < 2 * n; i ++) {
        std::cin >> a[i];
        if (a[i] == 0) {
            if (p2 == -1 && p1 != -1) p2 = i;
            if (p1 == -1) p1 = i;
        }
    }

    auto mex = [&](int l, int r) -> int {
        std::vector<bool> vis(2 * n + 1, false);
        for (int i = l; i <= r; i ++) vis[a[i]] = true;
        for (int i = 0; i <= n; i ++)
            if (!vis[i])
                return i;

        return 1;
    };

    auto extend = [&](int x) -> int {
        int l = x / 2, r = (x + 1) / 2;
        while (l >= 0 && r < 2 * n && a[l] == a[r])
            l --, r ++;

        return mex(l + 1, r - 1);
    };

    std::cout << std::max({extend(p1 + p2), extend(p1 * 2), extend(p2 * 2)}) << std::endl;;
}

cpp

E. It All Went Sideways#

题目描述#

给你一个由 nn 列方块组成的序列，第 ii 列初始有 aiai 个方块，竖直堆叠。在重力向右作用后，每块方块会尽量向右滑动，但不能穿过或重叠其他方块，且保持原来的高度。你可以在重力变化前最多执行一次操作：选择某一列将其方块数减少 1（也可不操作）。

定义“移动的方块”为重力变化后列编号发生变化的方块。

问通过最优操作（或不操作），最多能让多少方块移动。

解题思路#

重力向右后，方块保持高度尽量右移，最终第 i 列的高度等于 $(\min_{j\ge i} a_j)$ 。

定义数组 $mi[i] = min(a_{i}, \cdots, a_{n-1})$ ，即后缀最小值。

初始总方块数 S = sum(a)。不移动的方块数 = sc = sum(mi)，因为每列最底部的 mi[i] 个方块不会改变列编号。原有移动数 = S - sc。只能将某一列减少 1，总方块数减 1，同时可能改变后缀最小值。

减少操作的效果等价于：选择一个位置，把该列及其左侧所有列的 mi 值可能降低（取决于是否突破原来的最小值）。

最优操作是找 mi 数组中连续相等的最长段，将该段最左侧那一列减少 1。这样会让该段中每一列的不移动方块都减少 1，新增移动数 = 段长（ma），但总方块数也少了 1，因此净增移动数为 ma - 1。 $ans = (S - sc) + (ma - 1)$ 其中 ma 是后缀最小值数组中最长连续相等段的长度。

参考代码#

#define int long long
void solve() {
    int n, s = 0;
    std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 0; i < n; i ++) {
        std::cin >> a[i];
        s += a[i];
    }
    auto mi = a;
    for (int i = n - 2; i >= 0; i --)
        mi[i] = std::min(mi[i], mi[i + 1]);

    int sc = std::accumulate(mi.begin(), mi.end(), 0ll);
    std::cerr << s - sc << std::endl;

    int ma = -1, cnt = 1;
    for (int i = 1; i < n; i ++) {
        if (mi[i] == mi[i - 1])
            cnt ++;
        else {
            ma = std::max(ma, cnt);
            cnt = 1;
        }
    }
    ma = std::max(ma, cnt);

    std::cout << s - sc + ma - 1 << std::endl;
}

cpp

G.Drowning#

思路及参考代码Hailuo4ever ↗