Codeforces Round 945 (Div. 2)

题目链接

Codeforces Round 945 (Div. 2)

Problem A: Chess For Three

• 时间限制：1秒
• 内存限制：256 MB

题目描述

　　三个人，两两可以进行游戏，游戏可以进行任意多局（可以是0）。每一局游戏结束时，胜方得2分，败方不得分，若平局，则各得1分。现在给定三人的最终得分 $p_1, p_2, p_3$ ，保证 $p_1 \le p_2 \le p_3$ ，问：最多可能平局了多少次？输出这个最大可能值。如果这个得分情况不可能存在，则输出-1。

• 输入描述
  　　第一行，一个正整数 $t (1\le t \le 500)$，表示接下来有 $t$ 组数据。
  　　接下来 $t$ 行，每行三个非负整数 $p_1, p_2, p_3 (0\le p_1 \le p_2 \le p_3 \le 30)$，表示三人的最终得分。

• 输出描述
  　　对于每组数据，输出一个可能的最大平局数，如果该组得分不合法，输出-1。

测试样例

• 输入

  7
  0 0 0
  0 1 1
  1 1 1
  1 1 2
  3 3 3
  3 4 5
  1 1 10

• 输出

  0
  1
  -1
  2
  -1
  6
  2

解题思路

　　假设三人的得分都是偶数，那么分数一定是合法的。如果三人中两人是奇数，一人是偶数，那么也是合法的，因为两个奇数得分的玩家可以平局一次，剩下的分数就都是偶数了。其他奇偶情况都不合法，直接输出-1即可。在数据合法的情况下，直接贪心。如果满足 $p_1 + p_2 \ge p_3$ ，那么全部都可以是平局，最终答案就是 $\frac{p_1+p_2+p_3}{2}$ 。如果不满足，答案就是 $p_1+p_2$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int p1 = 0, p2 = 0, p3 = 0;
    cin >> p1 >> p2 >> p3;
    // 奇数个数是奇数
    if ((p1 & 1) ^ (p2 & 1) ^ (p3 & 1))
    {
        cout << -1 << endl;
        return;
    }
    if (p1 + p2 >= p3)
    {
        cout << (p1 + p2 + p3) / 2 << endl;
    }
    else
    {
        cout << p1 + p2 << endl;
    }
}
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

Problem B: Cat, Fox and the Lonely Array

• 时间限制：2秒
• 内存限制：256 MB

题目描述

　　定义一个数组 $A$ 的孤独值 $k$ 为满足某个条件的最小可能取值。条件：数组中任意连续 $k$ 个相邻元素的按位或(bitwise OR)结果相同。更数学化的表达为：
$$
\forall{i}\forall{j}(i,j \in [1,n-k+1] \cap \mathbb{Z}) \rightarrow a_i|a_{i+1}|…|a_{i+k-1} = a_j|a_{j+1}|…|a_{j+k-1}$$ 其中 $\mathbb{Z}$ 为整数域。
　　显然，当 $k=n$ 时满足条件，因为当 $k=n$ 时，连续 $k$ 个相邻元素只有一种选取情况，即整个数组，故而只有一种计算结果。现在给定一个数组，请问它的孤独值是多少？

• 输入描述
  　　第一行，一个正整数 $t (1\le t\le 10^4)$，表示接下来有 $t$ 组数据。
  　　每组数据包含两行，第一行，一个正整数 $n (1\le n\le 10^5)$，表示数组长度。
  　　每组数据第二行， $n$ 个非负整数 $a_1,a_2,…,a_n(0\le a_i\le 2^{20})$，表示给定的数组。
  　　数据保证所有组数的 $n$ 总和不超过 $10^5$。
• 输出描述
  　　每一组数据输出一行，包含一个正整数，表示该组数据得到的孤独值。

测试用例

• 输入

  7
  1
  0
  3
  2 2 2
  3
  1 0 2
  5
  3 0 1 4 2
  5
  2 0 4 0 2
  7
  0 0 0 0 1 2 4
  8
  0 1 3 2 2 1 0 3

• 输出

  1
  1
  3
  4
  4
  7
  3

解题思路

　　当一个取值 $k$ 符合条件时，比 $k$ 更大的数值也一定符合条件，因此最外层可以用二分法来调整 $k$ 的取值。内部判断该取值是否符合条件时，可以用滑动窗口思想来处理，滑动窗口就是双指针的一种特殊情况，双指针的两个指针距离固定。我们可以先统计前 $k$ 个元素的二进制表示下各个位上有值的次数，比如 $1, 3, 4$ ，就是 $2^0$ 出现 $2$ 次， $2^1, 2^2$ 各出现 $1$ 次。在我们将窗口依次往后移动的时候，如果存在某个位的次数统计从 $0$ 变为 $1$ ，或者减少为 $0$ ，那么意味着当前窗口的按位或结果和最初的结果不一致，这个 $k$ 的取值就不符合条件。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int arr[100005];

bool check(int k)
{
    int bit_count[25] = {0};
    for (int i = 1; i <= k; ++i)
    {
        for (int j = 0; j <= 20; ++j)
        {
            if (arr[i] & (1 << j))
            {
                bit_count[j]++;
            }
        }
    }
    int l = 1, r = k;
    while (r < n)
    {
        for (int j = 0; j <= 20; ++j)
        {
            int tmp = bit_count[j];
            if (arr[l] & (1 << j))
            {
                bit_count[j]--;
            }
            if (arr[r + 1] & (1 << j))
            {
                bit_count[j]++;
            }
            if ((tmp == 0) != (bit_count[j] == 0))
            {
                return false;
            }
        }
        l++, r++;
    }
    return true;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
    }
    int l = 1, r = n;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << r << endl;
}
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

Problem C: Cat, Fox and Double Maximum

• 时间限制：2秒
• 内存限制：256MB

题目描述

　　给定一个长度为偶数的排列 $P$ ，请构造一个长度和 $P$ 一致的排列 $P_2$ 使得二者每个位置上对应元素相加后得到的数组 $A$ 的局部最大元素的个数最多，如果有多种构造方案，请给出任意一种。
　　排列 ：如果排列长度是 $n$ ，那么其中 $1 \sim n$ 每个值都出现且仅出现一次。
　　局部最大元素 ：数组中严格大于相邻的左右两个元素值的元素，数组首部和尾部不作为局部最大元素。

• 输入描述
  　　第一行，一个正整数 $t(1\le t\le 10^4)$ ，表示接下来有 $t$ 组数据。
  　　每组数据的第一行，一个正整数 $n(4\le n\le 10^5,且 n 是偶数)$，表示该组数据给定的排列长度。
  　　每组数据的第二行，一个长度为 $n$ 的排列 $p_1, p_2, … , p_n$。
  　　数据保证所有组的 $n$ 总和不超过 $10^5$ 。

• 输出描述
  　　对于每组数据，输出一个长度和给定排列 $P$ 一致的排列 $P_2$ ，使得 $P$ 与 $P_2$ 对应位置元素相加后得到的数组具有最多的局部最大元素个数。

测试用例

• 输入

  4
  4
  1 2 3 4
  4
  4 3 1 2
  6
  6 5 1 4 2 3
  8
  1 2 4 5 7 6 8 3

• 输出

  2 4 1 3
  3 1 4 2
  2 5 1 4 3 6
  5 4 8 2 7 1 6 3

解题思路

　　给定的排列长度 $n$ 是偶数，而首尾又不能算作局部最大元素，那么在最好的情况下，最终能得到的局部最大元素个数为 $\frac{n}{2} - 1$。给出的是排列，要构造的也是排列，最为均衡的情况就是我们可以让最终的每个元素值都等于 $n+1$ ，只不过这样是没有局部最大值的。所以要考虑一下能否将所有奇数位置的元素或者所有偶数位置的元素都再大一点，比如将所有偶数位置都凑成 $n+2$ ，奇数位置则小一点。不过有个元素比较特殊，那就是 $1$ ，因为最多能让它凑成 $n + 1$ 。因此，如果 $1$ 在偶数位，我们就凑奇数位，反之凑偶数位。这样就必然能够让 $\frac{n}{2}$ 个间隔开来的元素凑成 $n+2$ ，至于另外的 $\frac{n}{2}$ 个元素，它们总体上肯定是比之前均衡分配时要小上 $\frac{n}{2}$ ，但是如果将剩余的元素胡乱分配，也是有可能又不小心凑出个 $n + 2$ ，导致整个数组少那么一两个局部最大值。所以不能胡乱分配，应该让数值越小的元素分配越大的值。

解题代码

#include <bits/stdc++.h>
using namespace std;
int p[100005];
int p2[100005];
bool used[100005]; // 该值是否已被分配？
// 该数据的 Right[index] 用于存储不小于 index 的最小的一个未被分配的值
int Right[100005];
void solve()
{
    int n;
    bool one_in_odd = false;
    cin >> n;
    // init
    for (int i = 1; i <= n; ++i)
    {
        p[i] = p2[i] = 0;
        used[i] = false;
        Right[i] = i;
    }
    // init end
    for (int i = 1; i <= n; ++i)
    {
        cin >> p[i];
        if (p[i] != 1)
        {
            continue;
        }
        one_in_odd = i % 2;
    }
    for (int i = 1 + (one_in_odd ? 1 : 0); i <= n; i += 2)
    {
        p2[i] = n + 2 - p[i];
        used[p2[i]] = true;
    }
    for (int i = n; i >= 1; --i)
    {
        if (used[i])
        {
            Right[i] = Right[i + 1];
        }
        else
        {
            Right[i] = i;
        }
    }
    priority_queue<pair<int, int>> wait_index;
    for (int i = 1 + (one_in_odd ? 0 : 1); i <= n; i += 2)
    {
        wait_index.push(make_pair(p[i], i));
    }
    int value_unused = Right[1];
    while (!wait_index.empty())
    {
        auto node = wait_index.top();
        wait_index.pop();
        p2[node.second] = value_unused;
        value_unused = Right[value_unused + 1];
    }
    for (int i = 1; i <= n; ++i)
    {
        cout << p2[i] << " ";
    }
    cout << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Problem D: Cat, Fox and Maximum Array Split

• 时间限制：3秒
• 内存限制：256MB

题目描述

　　本题为交互题，输入数据不会一次性全部给出，而是通过用户程序的输出与测试程序进行交互，记得在输出内容后及时刷新输出缓冲区。
　　假设有一个数组 $A = [a_1, a_2, … , a_n]$ ，我们定义 $f(l,r) = (r - l + 1) * \max\limits_{i=l}^{r}{a_i}$，其中 $l \le r$ 。也就是位于数组位置 $[l, r]$ 中的最大值与位于该范围内的元素个数的积。
　　现在，A和你要玩一个小游戏。A拥有一个长度为 $n$ 的数组 $[a_1, a_2, …, a_n]$ 。 B 不知道数组的具体数值， A 只给出了两个正整数 $n, k$ 。其中， $n$ 代表数组的长度，$k$ 代表你需要将数组 $A_n$ 划分为 $k$ 段，使得每一段的 $f(l,r)$ 值都相等，即：
$$
f(1, r_1) = f(r_1 + 1, r_2) = … = f(r_{k-1} + 1, n) = m
$$　　同时，你还需要让这个 $m$ 尽可能大。当然，你不需要给出具体的划分方案，只需要给出这个 $m$ 的值。
　　你可以向 A 进行最多 $2n$ 次询问，每次询问时可以给出两个正整数 “x y” 询问数组中以 $x$ 为左界， 满足 $f(x, r) = y$ 的最小 $r$ 。如果存在这样一个最小 $r$ 使得 $f(x, r) = y$ ，那么 A 会给出 $r$ 的值，否则给出 $n + 1$ 。
　　如果你找到了最终答案 $m$ ，请给出该答案，若不存在合法的划分方式，请给出 $-1$ 。

输入/输出描述

　　第一行，包含一个正整数 $t (1\le t \le 10^3)$ ，表示接下来有 $t$ 组测试数据。
　　每组数据第一行，给出两个正整数 $n, k (1\le k\le n\le 10^4)$ ，表示数组的长度与划分的目标段数。
　　如果你要进行询问，请输出 “? x y” ，其中 $x$ 代表询问的左界， $y$ 代表目标 $f$ 值。若存在一个最小的 $r$ 使得 $f(x, r) = y$ ，则会在输入缓冲区给出这个值。若不存在，则在输入缓冲区给出 $n + 1$ 的值。
　　如果你要确定答案，请输出 “! m” ，其中 $m$ 代表你在该组数据中提交的答案。
　　请注意，在确定答案后，如果答案正确，则会在输入缓冲区给出 “1” ，否则给出 “-1” 。即使你能够保证你的答案一定正确，也请一定要从输入缓冲区中读取这个反馈数据，以免在接收下一组数据时造成影响。如果你答案错误，或者提问超出了次数，都会得到 “-1” ，此时请主动结束程序从而节约时间（因为程序最终一定会给出Wrong Answer）。
　　数据保证，并未向用户给出的数组 $A_n$ 所有元素值皆为 $[1, n] 范围内的正整数$ 。同时，所有组的 $n$ 总和不超过 $10^4$ 。

测试用例

　　有 3 组测试数据，数组分别为 $[1]\quad [1, 2] \quad [1, 3, 6, 1, 2, 1]$。输入输出如下：

input :3
input :1 1
output:! 1
input :1
input :2 2
output:? 1 1
input :1
output:? 2 1
input :3
output:! -1
input :1
input :6 3
output:? 1 9
input :7
output:? 1 6
input :2
output:? 3 6
input :3
output:? 4 6
input :6
output:! 6
input :1

解题思路（官方）

　　根据题目的性质，我们可以推出以下结论：
　　① 数组的最大值 $M$ 我们可以通过至多 $n$ 次询问得到。
　　② 若存在合法答案 $m$ ，则 $m$ 必能被 $M$ 整除。
　　③ 若存在合法答案 $m$ ，则 $m$ 一定在 $M, 2M, … , nM$ 之间。
　　④ 数组合法地分为 $k$ 段后，每段的宽度一定都不小于 $\frac{m}{M}$ 。
　　⑤ 于是有 $k * \frac{m}{M} \le n \Rightarrow m \le \frac{nM}{k}$ ，由于 $m$ 必然能被 $M$ 整除且为整数，因此该式子可以转换为 $m \le \lfloor \frac{n}{k} \rfloor * M$。
　　其中，① 可以通过以下方法实现：由于数组中的元素都在 $[1, n]$ 的范围内，因此我们可以用 $n$ 次询问机会来依次枚举最大值 $M$ 。假设最大值为 $M$ 时，则必有 $f(1, n) = nM$，因此可以依次询问”? 1 n*i”，当返回的结果为 $n$ 时，代表当前的 $i$ 为最大值。
　　当数组的最大值为 $M$ 时，那么它至少在数组出现一次。假设存在合法划分答案，则它必然会被划分到某个子段中，于是该子段的 $f(l,r) = M * (r - l + 1)$ = m ，因此 $m$ 必然能被 $M$ 整除，因此 ② 成立。
　　由于数组长度为 $n$ ，$f(l, r)$ 的最大值为 $f(1, n) = nM$ ，而 $m$ 又能被 $M$ 整除，因此 $m$ 一定是 $M$ 的整数倍，且不超过 $nM$ ，因此 ③ 成立。
　　当划分后的某个子段中包含了最大值 $M$ 时，则该子段的宽度一定是最小的，或者说，不存在其他的比它宽度还小的子段。而该子段的宽度为 $\frac{m}{M}$ ，因此所有子段的宽度都不小于该值，④ 成立。
　　由于每个子段的宽度都不小于 $\frac{m}{M}$ ，且所有子段宽度之和为 $n$ ，于是有 $k * \frac{m}{M} \le n$，⑤ 成立。
　　由于 $m \le \lfloor \frac{n}{k} \rfloor * M$，我们可以从该值依次往下递减 $M$ 来枚举 $m$ 的取值，对于每个取值，至多只需要 $k$ 次询问就能得知该取值是否合法。我们最初通过 “? 1 m”得到 $r_1$ ，再通过 “? $r_1$ m” 得到 $r_2$ ，以此类推，若在 $k$ 次询问之后，成功得到了 $n$ ，则代表当前的 $m$ 是合法答案。若当前的 $m$ 不是合法答案，则会在中途的某次询问中，得到 $n+1$ ，结束询问即可，$m$ 的所有可能取值都验证完毕之后，消耗的询问次数一定不会超过 $k * \lfloor \frac{n}{k} \rfloor$ 次。再加上为获取数组最大值所用掉的 $n$ 次，总共也不会超过 $2n$ 次。

官方原文如下：
Let’s denote maximum value in array a as $mx$. Since the element with maximum value will belong to some segment，then if m exists, m will be divisible by $mx$. Obviously, $m$ can’t be greater than $n ⋅ mx$, so now the candidates for value of $m$ are $mx, 2 ⋅ mx, 3 ⋅ mx, … , n ⋅ mx$.

To find the value of mx we can query “? 1 n⋅i” for each $1\le i \le n$ and $mx$ will be equal to such $i$, querying which will give $n$ as the answer.

We can check each of $n$ possible values in $k$ queries, but that wouldn’t fit in query limit.

Actually, since the length of each segment in partition will be greater than or equal to $\frac{m}{mx}$, and there are exactly $k$ segments, we can get a simple inequality $k ⋅ \frac{m}{mx} \le n$ (since sum of lengths of segments is exactly $n$),which means $m$ can not be greater than $mx ⋅ ⌊n/k⌋$, so it is enough to check first $⌊n/k⌋$ candidates for $m$ in $k$ queries each. Total number of queries used would be $n+k⋅⌊n/k⌋$ which doesn’t exceed $2n$.

解题代码

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
using namespace std;

void solve()
{
    int n, k;
    cin >> n >> k;
    int max_value = 0;
    for (int i = 1; i <= n; ++i)
    {
        cout << "? 1 " << i * n << '\n';
        cout.flush();
        int r;
        cin >> r;
        if (r == n)
        {
            max_value = i;
            break;
        }
    }
    int right = n / k * max_value;
    int response;
    for (int current = right; current; current -= max_value)
    {
        bool legal = true;
        int index = 0;
        for (int i = 1; i <= k; ++i)
        {
            if (index >= n)
            {
                legal = false;
                break;
            }
            cout << "? " << index + 1 << " " << current << '\n';
            cout.flush();
            cin >> index;
        }
        if (!legal || index != n)
        {
            continue;
        }
        cout << "! " << current << '\n';
        cout.flush();
        cin >> response;
        return;
    }
    cout << "! -1" << '\n';
    cout.flush();
    cin >> response;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}