CF构造题1600-1800（2）

H. Hot Black Hot White(COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred))

题意

有 \(n\) 个石头，每个石头有一个值 \(a_i\)，现在需要给这 \(n\) 个石头染色，要求 \(\frac{n}{2}\) 为白色，\(\frac{n}{2}\) 为黑色( \(n\) 为偶数)，并且任何两个颜色不相同的石头 \(i\)，\(j\) 满足：

\[concat(a_i,a_j) \times concat(a_j,a_i) + a_i \times a_j \not\equiv Z \bmod 3
\]

求 \(Z\) 与染色方法。

\(concat(x, y)\) 表示 \(y\) 的十进制连接在 \(x\) 的十进制右边，例如：\(concat(10,24) = 1024\)

思路

令 \(len(x)\) 表示 \(x\) 的十进制表示法中的位数，所以 \(concat(x, y) = x \times10^{len(y)} + y\)

我们可以发现 \(10\) 的任何次幂模 \(3\) 是等于 1 的，所以 \(concat(x, y) \bmod 3= ((x \bmod 3)\times 1 + (y \bmod 3)) \bmod 3\)

有了上面的发现，我们可以轻松的化简题中的公式：

\[\begin{aligned}
(concat(a_i, a_j) \times concat(a_j, a_i) + a_i \times a_j) \bmod 3
&= (((a_i + a_j) \times (a_j + a_i)) \bmod 3 + a_i \times a_j\mod 3) \bmod 3 \\
&= ((a_i^2 + a_j^2 + 2a_ia_j) \bmod 3 + a_i \times a_j\mod 3) \bmod 3\\
&= ((a_i^2 + a_j^2) \bmod 3 + 3a_ia_j \bmod 3) \bmod 3\\
&= (a_i^2+a_j^2) \bmod 3
\end{aligned}
\]

也就是说我们要满足 \(a_i^2 + a_j^2 \not\equiv Z \bmod 3\) 这样的条件。

对于这个新的公式，我们同样有新的发现：

\[a_i^2 \bmod 3 = (a_i \bmod 3)^2 \bmod 3
\]

\(a_i \bmod 3\) 的值只能是 \(0，1， 2\)，\(a_i^2 \bmod 3\) 的值只能是 \(0, 1\)。

我们可以贪心的让值相同的 \(\frac{n}{2}\) 个数为白色(一定可以找到这么多数，因为数组现在只有两个值)，为黑色的数可能有两个值\(0,1\)或者可能有一个值。

这是我们发现 \(a_i^2 + a_j^2 \bmod 3\) 的值最多只能是两个不同的数，而 \(Z \bmod 3\) 有三个不同的数，一定存在一个 \(Z\)。

实现

void solve_problem() {

    int n;

    std::cin >> n;

    std::vector<int> a0, a1;

    for (int i = 0; i < n; i++) {

        int a;

        std::cin >> a;

        a = a % 3;

        a = a * a % 3;

        if (a == 0) a0.push_back(i);

        else a1.push_back(i);

    }

    int Z = -1;

    std::string ans(n,'0');

    if (a0.size() > n/2) {

        Z = 2;

        for (int i = 1; i <= n/2; i++) {

            ans[a0[i]] = '1';

        }

    } else {

        Z = 0;

        for (int i = 1, j = (int)a1.size() - 1; i <= n/2; i++, j--) {

            ans[a1[j]] = '1';

        }

    }

    std::cout << Z << "\n" << ans << "\n";

}

F. Equate Multisets(Codeforces Round #805 (Div. 3))

题意

有两个集合 \(a\)，\(b\) (集合中的数可以重复)，每次操作可以选择集合 \(b\) 的任何一个元素 \(x\) 进行以下两种操作的一种：

\(x = x \times 2\)
\(x = \lfloor\frac{x}{2}\rfloor\)

求经过确定次数的操作后，两集合是否能相等(回答 YES或 NO)。

思路

首先可以发现如果 \(a\) 数组中的数是由 \(b\) 数组中的数最后通过 \(\times 2\) 转变来的，那么 \(a\) 数组中的这个数是偶数。

怎么运用这个发现呢？

我们可以考虑两个数组的最大值：

如果最大值是 \(a\) 数组的，那么他一定是最后通过 \(\times2\) 操作转变来的，并且它一定要是偶数
如果最大值是 \(b\) 数组的，那么这个数要转变为 \(a\) 数组中的数一定要进行 \(\lfloor\frac{x}{2}\rfloor\) 操作，因为 \(\times2\) 只会让它更大
如果两个数组的最大值相等，那么很可能不进行任何操作。

我们可以维护两个优先队列来取最大值：

如果最大值是 \(a\) 数组的，我们把它进行 \(\lfloor\frac{x}{2}\rfloor\) 在放进队列中，如果它是奇数，显然，这组数据是不能相等的。
如果最大值是 \(b\) 数组的，我们同样把它进行 \(\lfloor\frac{x}{2}\rfloor\) 在放进队列中，只不过不用考虑奇偶了。
如果两个数组的最大值相等，就把这两数 pop 掉。

最坏的情况我们可以对一个数进行 \(30\) 次 \(\lfloor\frac{x}{2}\rfloor\) 操作，\(2n\) 个数就是 \(60n\) 次 \(\lfloor\frac{x}{2}\rfloor\) 操作，但实际上远远达不到这么多。

实现

void solve_problem() {

    std::priority_queue<int, std::vector<int>, std::less<int>> qa, qb;

    int n;

    std::cin >> n;

    for (int i = 1; i <= n; i++) {

        int a;

        std::cin >> a;

        qa.push(a);

    }

    for (int i = 1; i <= n; i++) {

        int a;

        std::cin >> a;

        qb.push(a);

    }

    while (!qa.empty() && !qb.empty()) {

        int a = qa.top(); qa.pop();

        int b = qb.top(); qb.pop();

        if (a != b) {

            if (a > b) {

                if (a & 1) {

                    std::cout << "NO\n";

                    return;

                } else {

                    a /= 2;

                }

            } else {

                b /= 2;

            }

            qa.push(a);

            qb.push(b);

        }

    }

    std::cout << "YES\n";

}

D. Cyclic Rotation(Codeforces Global Round 20)

题意

有数组 \(a\)，\(b\)，每次可以对数组 \(a\) 进行操作，选择两个下标 \(l\) 和 \(r\) 并且 \(a_l = a_r\)，使得 \(a[l\cdots r] = [a_{l+1}，a_{l+2}，\cdots a_r，a_l]\)，求经过确定次操作后是否可以使两个数组相等(回答 YES或 NO)。

思路

首先可以发现进行过操作之后，选定的这个区间最后两个数是相等的，我们可以考虑反向操作，对数组进行还原。

我们从后向前进行双指针遍历，一个维护数组 \(a\) 的下标 \(i\)，一个维护数组 \(b\) 的下标 \(j\)。

当 \(a_i = b_j\) 时，直接 \(i-1\)， \(j-1\) 即可
当 \(a_i \neq b_j\) 并且 \(b_j = b_{j+1}\) 时，我们可以把 \(b_j\) 存起来，因为它可以放到前面的任意位置，接着进行 \(j-1\)
当 \(a_i \neq b_j\) 并且 \(b_j \neq b_{j+1}\) 时，把 \(a_i\) 与存起来的数进行比较，如果可以找到与 \(a_i\) 相同的，那么他们两个就是匹配的，把这个数在存起来的数中拿出，然后进行 \(i-1\) ；如果没有找到，那这两个数组是不可能通过操作来相等的。

我们可以用 std::map 来存数。

实现

void solve_problem() {

    int n;

    std::cin >> n;

    std::vector<int> a(n), b(n);

    for (auto &x : a) std::cin >> x;

    for (auto &x : b) std::cin >> x;

    if (b.back() != a.back()) {

        std::cout << "NO\n";

        return;

    }

    std::map<int, int> cnt;

    for (int i = n - 2, j = n - 2; i >= 0;) {

        if (j < 0 || a[i] != b[j]) {

            if (j >= 0) {

                if (b[j] == b[j + 1]) {

                    cnt[b[j]]++;

                    j--;

                    continue;

                }

            }

            if (cnt[a[i]] != 0) {

                cnt[a[i]]--;

                i--;

            } else {

                std::cout << "NO\n";

                return;

            }

        } else {

            i--;

            j--;

        }

    }

    std::cout << "YES\n";

}

巴特西

CF构造题1600-1800（2）

H. Hot Black Hot White(COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred))

题意

思路

实现

F. Equate Multisets(Codeforces Round #805 (Div. 3))

题意

思路

实现

D. Cyclic Rotation(Codeforces Global Round 20)

题意

思路

实现

最新文章

热门文章