Codeforces Round 983 (Div.2) 题解

发表于 2024-11-02 更新于 2025-03-28 分类于 Codeforces 阅读次数：本文字数： 4.5k

一想到jiangly的A和C都WA了我就为久违的上分感到不容易了。

A

题意

有\(n\)盏灯，没盏灯都有两个开关，开关可以控制灯的亮灭，如果两个开关都打开或都关上，灯就不会亮。现在不知道哪个开关控制哪盏灯，求最大和最小可能灯亮的个数。

题解

题意有点难懂，但是看样例猜出来开关都开和都关灯都会熄灭的话就好做了。

最少的情况肯定是所有1按照1 1的方式配对，所以1的个数为奇数的话会多出来一个，一定会让一盏灯亮，最小值就是1；为偶数的话最小值就是0。

最大值也是就是1的个数和0的个数的最小值，因为要优先把0和1配对。

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(2 * n);
    int cnt0 = 0, cnt1 = 0;
    for (int i = 0; i < 2 * n; i++) {
        cin >> a[i];
    }
    cnt1 = accumulate(a.begin(), a.end(), 0);
    cnt0 = 2 * n - cnt1;
    int mn = 0;
    int mx = min(cnt0, cnt1);
    if (cnt1 & 1) {
        mn = 1;
    } else {
        mn = 0;
    }
    cout << mn << " " << mx << "\n";
}

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

B

题意

给定一个奇数\(n\)，和一个数\(k\)，将按照顺序排列好的\(1,2,...,n\)划分为\(m\)个部分（\(m\)也是奇数），要求每个部分的大小都是奇数，然后从每个部分取出中位数组合在一起，要求这个新组合的中位数也是\(k\)，输出每个部分的第一个数或-1代表不可能。

题解

构造题，首先对于无解的情况很可能是我们的突破口。既然都是奇数，那么中位数一定是中间的数，所以\(k\)为1或\(n\)的话，一定不能作为中位数。否则我们就可以划分为三个部分，让中间的部分的中位数是\(k\)。如果\(k\)是偶数，那么直接让\(k\)自己作为一个部分，可以划分为\(1,...,k-1;k;k+1,...,n\)，这样三个部分都是奇数大小，满足条件。如果\(k\)是奇数，那就把中间的部分大小设为3，划分为\(1,...,k-2;k-1,k,k+1;k+2,...,n\)，这样三个部分也还是奇数大小，满足条件。

此外，需要特判\(n = 1\)的情况。

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    if (n == 1) {
        cout << 1 << "\n" << 1 << "\n";
        return;
    }
    if (k == n || k == 1) {
        cout << -1 << "\n";
        return;
    }
    cout << 3 << "\n";
    if (k & 1) {
        cout << 1 << " " << k - 1 << " " << k + 2 << "\n";
    } else {
        cout << 1 << " " << k << " " << k + 1 << "\n";
    }
}

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

C

题意

给定一个序列\(a_i\)，对于下标\(i,j\)，可以进行若干次\(a_i = a_j\)的操作，要求最后生成的序列里任取三个数都满足可以构成三角形，求最小操作次数。

题解

构成三角形要求两边之和大于第三边，既然要求任取三个数都满足，所以需要最小的两个数之和都大于最大的数，所以自然需要一次排序。一个想法是从左到右和从右到左各遍历一次，维护一个能够满足的范围，但是这样的问题是：还有可能满足条件的范围在中间，所以这样贪心的思路好像并不可行。不过，我们基本的思路已经出来了：就是维护能够满足条件的范围，不妨把每个左端点能拓展到的位置都尝试一遍。

我们用滑动窗口的思想，维护一个满足条件的区间，要求区间内任取两个数都是可以构成三角形的，我们在双指针移动的过程中更新答案。

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int ans = n - 1;
    for (int i = 0, j = 0; i < n - 1; i++) {
        while (j + 1 < n && a[i] + a[i + 1] > a[j + 1]) {
            j++;
        }
        ans = min(ans, n - (j - i + 1));
    }
    cout << ans << "\n";
}

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

D

题意

交互题。

给定一颗\(n\)个节点的数，编号为\(0,1,...,n-1\)，设每个节点的父亲节点为\(p_i\)，这棵树满足如下性质：

如果去掉0节点，剩余的部分由若干条链组成
对于节点\(x,y\)，如果\(x < y\)，那么必有\(p_x\le p_y\)
节点1有两个相邻的节点（包括节点0）

交互：你可以询问两个节点的路径上是否有0节点，不超过\(2n-6\)次。

输出\(p_1,p_2,...,p_{n-1}\)

题解

我们首先根据树的性质，思考这棵树的大致形状。

根据性质1，我们知道除了根节点，这棵树的每一个节点只有一个儿子节点。

根据性质2，我们容易想到：这棵树节点的排列顺序一定是分层排列，每一层节点从小到大，父亲节点也是从小到大的。否则，会违反性质2。并且，一旦一层中某个节点在下一层没有子节点，那么之后这个节点再也不可能有子节点了。

大概确定树的形状后，我们可以通过类似BFS的方式求出每个节点的父节点。具体为：询问当前节点和上一层的节点，如果回答是1，说明不是父亲，否则说明找到父亲了。

接下来思考性质3的作用：其实就是帮助我们确定有多少条链，我们从2开始的节点\(i\)询问1和\(i\)，直到回答为0，此时的\(i\)就是1的儿子节点，之前的\(i\)都是和1同层的节点。

然后，我们依次询问每一个节点的父亲，如果不是，则说明询问的父亲节点不再可能是任何节点的父亲了，由于这棵树就是每一层按顺序排列的，我们依次询问即可。

关于\(2n-6\)的询问次数的正确性：我们注意到一个性质：从上到下的每一层的节点数量是非递增的。对于一个节点，最坏的情况就是它的父亲是它当前层的第一个节点，这样他就会遍历一整层之后才能确定父亲。不过，一旦发生这种情况后，后面的遍历中链的数量就会减少，除掉这种情况，平均还是1次询问就能确定一个节点。如果一层节点的数量很多，说明在找节点1的儿子时已经确定了不少节点，后续要么很快找到父亲，要么很快退化成链；如果一层节点的数量较少，那么就是链上询问，额外的次数消耗不大。在\(2n-6\)的询问次数下还是可以完成任务的。（具体证明我也不太会）

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    auto query = [&](int x, int y) {
        cout << "? " << x << " " << y << "\n";
        cout.flush();
        int exist;
        cin >> exist;
        return exist;
    };
    vector<int> p(n);
    p[0] = p[1] = 0;
    int a = 2;
    while (query(a, 1)) {
        p[a++] = 0;
    }
    p[a++] = 1;
    int l = 2;
    for (int i = a; i < n; i++) {
        while (query(i, l)) {
            l++;
        }
        p[i] = l++;
    }
    cout << "! ";
    for (int i = 1; i < n; i++) {
        cout << p[i] << " \n"[i == n - 1];
    }
    cout.flush();
}

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