Codeforces Round #823 (Div. 2) A-D

• 2022 年 10 月 4 日
• 筆記
• CF

比赛链接

A

题解

知识点：贪心。

对于一个轨道，要么一次性清理，要么一个一个清理。显然，如果行星个数大于直接清理的花费，那么选择直接清理，否则一个一个清理。即 \(\sum \min (c,cnt[i])\)，其中 \(cnt[i]\) 表示轨道 \(i\) 的行星个数。

时间复杂度 \(O(n)\)

空间复杂度 \(O(1)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int cnt[107];

bool solve() {
    int n, c;
    cin >> n >> c;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    int ans = 0;
    for (int i = 1;i <= 100;i++) ans += min(c, cnt[i]);
    cout << ans << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

B

题解

方法一

知识点：三分。

按位置从小到大排列，显然约会花费是一个关于 \(x_0\) 的单谷函数，因此可以三分位置。

由于位置最大有 \(10^8\) ，但点的个数只有 \(10^5\) ，考虑先用 map 存储有序对 \((x,t)\) ，其中 \(t\) 是位置 \(x\) 的人最大打扮时间，因为比这个时间少的一定不影响结果。遍历结束以后把 map 内容移到 vector 中用 pair 存储用以三分，check 函数则只要遍历一遍 vector 即可。

时间复杂度 \(O(n \log \max(eps))\)

空间复杂度 \(O(n)\)

方法二

知识点：贪心。

把 \(t\) 等效进位置，如果 \(x_i\) 在 \(x_0\) 左侧，则等效位置是 \(xi – t\) ;如果 \(x_i\) 在 \(x_0\) 右侧，则等效位置是 \(x_i + t\) 。

所有点的左侧等效位置最左的位置，就是等效区间左端点；所有点的右侧等效位置最右的位置就是等效区间的右端点。

如果等效区间的左右端点来自于不同两点的等效点，那么等效区间的中点一定在这两点之间，否则原来的点必有一个能覆盖另一个点，等效区间的左右端点就属于同一个点的等效点。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

代码

方法一

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int x[100007];
map<int, int> mp;
vector<pair<int, int>> v;

double check(double mid) {
    double mx = 0;
    for (auto [i, j] : v) {
        mx = max(mx, abs(i - mid) + j);
    }
    return mx;
}

bool solve() {
    mp.clear();
    v.clear();
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> x[i];
        mp[x[i]] = 0;
    }
    for (int i = 1;i <= n;i++) {
        int T;
        cin >> T;
        mp[x[i]] = max(mp[x[i]], T);
    }
    for (auto [i, j] : mp) {
        v.push_back({ i,j });
    }

    double l = 0, r = v.back().first;
    while (abs(r - l) >= 1e-7) {
        double mid1 = l + (r - l) / 3;
        double mid2 = r - (r - l) / 3;
        if (check(mid1) <= check(mid2)) r = mid2;
        else l = mid1;
    }
    cout << fixed << setprecision(10) << l << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

方法二

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int x[100007], T[100007];

bool solve() {
    int n;
    cin >> n;
    int l = 1e9, r = 0;
    for (int i = 1;i <= n;i++) cin >> x[i];
    for (int i = 1;i <= n;i++) cin >> T[i];
    for (int i = 1;i <= n;i++) {
        l = min(x[i] - T[i], l);///最左侧等效点
        r = max(x[i] + T[i], r);///最右侧等效点
    }
    cout << fixed << setprecision(8) << (l + r) / 2.0 << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

C

题解

知识点：贪心。

因为要字典序最小，那么一个数字他后面没有更小的数字则可以保留，其他都应该删除，所以从右往左找一个合法的保留序列，其他的数字加一，并且都是位置随意的，于是可以插入到保留下来的序列，并使插入后的序列是从小到大字典序最小的排列。因此直接把保留序列外的数字加一以后，对整个序列排序即可。

也可以直接桶排序。

时间复杂度 \(O(n \log n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;


bool solve() {
    string s;
    cin >> s;
    int mi = 10;
    for (int i = s.size() - 1;i >= 0;i--) {
        if (s[i] - '0' <= mi) mi = s[i] - '0';
        else s[i] = min(s[i] + 1, '9' + 0);
    }
    sort(s.begin(), s.end());
    cout << s << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

D

题解

知识点：构造。

注意到操作不会改变无序对 \((a_i, b_{ n – i + 1 })\) 数量以及种类。

引理：\(a = b\) ，当且仅当无序对是回文的。

充分性：

当 \(a = b\) 时，如果 \(i\) 处存在一组无序对 \((x, y)\) ，则必然会在 \(n-i+1\) 产生相同一组无序对 \((y, x)\) ，除非当 \(n\) 为奇数时，可以在中间产生一个元素相同的无序对 \((x,x)\) ，因此 \(a = b\) 时，无序对必然成回文状。

必要性：

当无序对是回文的，则第 \(i\) 组无序对 \((x,y)\) 可以对应第 \(n-i+1\) 组无序对 \((y,x)\) ，即 \(a_i = b_i\) ,所以 \(a = b\) 。

充要条件：YES 当且仅当无序对 \((a_i, b_{ n – i + 1 })\) 中元素不同的无序对有偶数个，元素相同的无序对仅在 \(n\) 为奇数时至多 \(1\) 种有奇数个。

充分性：

根据引理，显然满足右边条件。

必要性：

显然没有任何限制时，给出的无序对条件能排列成回文的，现在尝试证明其必然可构造无序对回文。

注意到操作 \(k = i\) 可以使得 \(a[1 \cdots k]\) 和 \(b[k\cdots n]\) 交换位置，即 \((a[k], b[n – k + 1])\) 这一组无序对被置换到了 \(1\) 号位置，同时 \((a[1],b[n])\) 这一组无序对被置换到了 \(i\) 号位置，但这不会改变 \(a[k+1 \cdots n]\) 和 \(b[1\cdots k-1]\) 的顺序，即第 \(k+1\) 到 \(n\) 组无序对及其实际元素顺序没有改变。因此，如果我们想要将无序对通过操作变成一个我们想要的顺序，可以从右往左构造。

假设 \(i+1\) 到 \(n\) 的无序对都安排好了，现在 \(i\) 号位置想要 \(j (j\leq i)\) 号位置的无序对时，可以先 \(k=j\) ，将 \(j\) 号替换到 \(1\) 号，然后 \(k=i\) ，将 \(1\) 号替换 \(i\) 号，过程中 \(i+1 \cdots n\) 的无序对不会改变，包括实际元素顺序。

上述操作最后结果是无序对 \(j\) 替换到 \(i\) ，且 \(j\) 号无序对元素的实际顺序不会改变。但如果我们希望实际元素的顺序也发生改变，我们可以加一个步骤 \(k = 1\) 在中间，即通过 \(k = j, k = 1, k = i\) 替换 \(i\) 号后的 \(j\) 号元素实际顺序与原来是相反的，这也是为什么我们只需要知道无序对顺序即可，因为元素实际顺序是可以随时改变的。

通过上述操作我们可以实现无序对的任意排列，以及无序对实际元素的顺序。因此无序对满足回文条件时，必然可以构造出无序对回文。于是根据引理，得到 \(a = b\) 。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

string a, b;
int cnt[26][26];

bool solve() {
    memset(cnt, 0, sizeof(cnt));
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    for (int i = 0;i < n;i++) {
        int x = a[i] - 'a', y = b[n - 1 - i] - 'a';
        if (x > y) swap(x, y);
        cnt[x][y]++;
    }

    bool ok = true;
    int esum = 0;
    for (int i = 0;i < 26;i++) {
        for (int j = i;j < 26;j++) {
            if (i == j) esum += cnt[i][j] & 1;
            else ok &= !(cnt[i][j] & 1);
        }
    }

    if (ok && esum <= (n & 1)) cout << "YES" << '\n';
    else cout << "NO" << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}