AtCoder Beginner Contest 290

2023-02-20 17:12 由 ~Lanly~ 发表于 #其他

A - Contest Result (abc290 a)

题目大意

给定\(n\)道题的分数。

现在小 \(A\)过了一些题，问他的分数是多少。

解题思路

模拟即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> s(n);
    for(auto &i : s)
        cin >> i;
    int ans = 0;
    while(m--){
        int x;
        cin >> x;
        ans += s[x - 1];
    }
    cout << ans << '\n';

    return 0;
}

B - Qual B (abc290 b)

题目大意

一场比赛，按照排名依次给出每个人参加决赛的意愿（o x）。

最终只能晋级\(k\)个人。取意愿参加决赛的前 \(k\)人晋级。

问实际上每个人晋级决赛的情况。

解题思路

前\(k\)个 o的保留，后面全部置为 x即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, k;
    string s;
    cin >> n >> k >> s;
    for(auto &i : s){
        if (i == 'o' && k){
            -- k;
        }else if (i == 'o' && !k){
            i = 'x';
        }
    }
    cout << s << '\n';

    return 0;
}

C - Max MEX (abc290 c)

题目大意

给定一个\(n\)个数的数组，要求选\(k\)个数出来，使得其\(mex\)最大。

一个数组的\(mex\)值就是最小的，未出现在该数组的非负整数。

解题思路

为了让\(mex\)最大，很显然我们依次取 \(0,1,2,...\)，且仅取一个，直到取了\(k\)个。

如果中途发现有个数取不到则答案就是该数，否则就是 \(k\)。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> s(n);
    for(auto &i : s)
        cin >> i;
    sort(s.begin(), s.end());
    int ans = 0;
    for(auto &i : s){
        if (k <= 0)
            break;
        if (ans > i)
            continue;
        else if (ans == i){
            ++ ans;
            -- k;
        }
        else if (ans < i)
            break;
    }
    cout << ans << '\n';

    return 0;
}

D - Marking (abc290 d)

题目大意

\(n\)个箱子。从 \(0\)开始涂色。每涂一个箱子\(i\)后，下一个涂的箱子编号是 \(i+D\) 。如果该箱子已经被涂色了，则涂编号为\(i+D+1\)的箱子，如果还被涂过则再 \(+1\)，直到没涂过为止。

问第 \(k\)次涂的箱子编号。

解题思路

如果不考虑已经涂色的情况，即就算已经涂了，这次还继续涂，那第\(k\)次涂的箱子编号就是 \(kD \% n\)。

由数论知识可知，当\(D\)和 \(n\)互质时，当 \(k\)取遍 \([0,n - 1]\)时， \(kD \% n\)也恰好的取遍了 \([0, n - 1]\)，因此此时答案就是 \(kD \% n\)

而不互质时，设其\(D,n\)的\(gcd\)为\(a\)，则\(kD \% n\)取到的数都是 \(a\)的倍数。

事实上，设\(D^\prime = \frac{D}{a}, n^\prime = \frac{n}{a}\)，此时\(D^\prime, n^\prime\)互质，则第\(k\)取取到的数就是 \(kD^\prime\)，而在模\(n\)的视角里就是 \(kD^\prime \times a\)。因为循环节大小只有 \(n^\prime\)，因此当\(k > n^\prime\)时，由题意的偏移操作，下一个的循环节就是原来的循环节整体加 \(1\)。

因此最终的答案就是 \(kD^\prime \times a + \frac{k}{n^\prime}\)

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int k, d, n;
        cin >> n >> d >> k;
        -- k;
        int gcd = __gcd(d, n);
        d /= gcd;
        n /= gcd;
        int target = 1ll * k * d % n;
        target = target * gcd + (k / n);
        cout << target << '\n';
    }


    return 0;
}

E - Make it Palindrome (abc290 e)

题目大意

定义一个数组变成回文数组的代价，是其最小进行的操作数。每次操作可以将任意一个数更改为任意一个值。

给定一个\(n\)个数的数组，问其所有连续子数组的代价和。

解题思路

给定一个数组，考虑其变成回文数的代价。很显然我们只要遍历左半边的每个数，看其与对应的数是否相同，不相同则需要一个操作让它们变成相同。

从中我们可以发现，代价贡献来自于每一对数是否相同，以及包含这对数的子数组个数，因此我们的视角从考虑每个子数组转成考虑每对数。

假设当前考虑的是第\(i\)个数\(a_i\)，依次考虑其右边的每一个数，很显然我们只考虑与\(a_i\)不同的那些数，相同的话对答案是没贡献的。

假设\(a_j \neq a_i(j > i)\)，那么这对数\((a_i, a_j)\)会产生一个操作的贡献，但还得考虑有多少个子数组，回文包括 \((a_i,a_j)\) 。

最短的子数组当然是\(a[i,...,j]\)，再大一点就是 \(a[i-1,...,j+1]\) 。因此子数组个数为 \(\min(i, n - j + 1)\)（下标从 \(1\)开始）

如果单纯只有不同数的个数，可以直接预处理，但这里还带了个系数\(\min(i, n - j + 1)\)，且与 \(i\)有关，不好直接预处理。

因此我们得把 \(\min\)去掉，那就是将 \(i\)右边的数分成了两类，一类是 \(a_j \neq a_i\)，且 \(\min(i, n - j + 1) = i\)即 \(j < n - i + 1\)，另一类是 \(a_j \neq a_i\)且 \(\min(i, n - j + 1) = n - j + 1\)即 \(j \geq n - i + 1\)。

对于 \(i < j < n - i + 1\)的那些 \(a_j \neq a_i\)，这些对 \((a_i, a_j)\)对答案的贡献都是 \(i\)。因此我们只要维护这个区间里非 \(a_i\)的个数 \(cnt\)，这部份的贡献就是 \(cnt \times i\)
对于 \(j > n - i + 1\)的那些 \(a_j \neq a_i\)，这些对 \((a_i, a_j)\)对答案的贡献都是 \(n - j + 1\)。因此我们只要维护这个区间里非 \(a_i\)的 \(a_j \times (n - j + 1)\)的和，这部份的贡献就是该和。

维护区间非\(a_i\)的个数以及\(a_j \times (n - j + 1)\) 的和，可以维护所有数的个数与和，再减去\(a_i\)的贡献，即是非 \(a_i\)的个数与和。

当我们迭代求解每个\(a_i\)时，这两个区间信息可以迭代 \(O(1)\)更新，因此总的时间复杂度为 \(O(n)\)

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    LL ans = 0;
    vector<LL> sum(n), cnt(n);
    LL suf = 0, tot = n;
    for(auto &i : a){
        cin >> i;
        -- i;
        cnt[i] ++;
    }
    for(int i = 0; i < n / 2; ++ i){
        tot -= 2;
        cnt[a[i]] --;
        cnt[a[n - i - 1]] --;

        sum[a[n - i - 1]] += i + 1;
        suf += i + 1;

        ans += 1ll * (i + 1) * (tot - cnt[a[i]]) + suf - sum[a[i]];
    }
    if (n & 1)
        ans += suf - sum[a[n / 2]];
    for(int i = (n + 1) / 2; i < n; ++ i){
        sum[a[i]] -= n - i;
        suf -= n - i;

        ans += suf - sum[a[i]];
    }
    cout << ans << '\n';

    return 0;
}