Contestant. Rank 3650. Rating +66.

A. Contest Result

题意

给定数组 \(a, b\)，输出 \(a_{b_i}\) 的总和。

思路

如题。

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

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

int a[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1;i<=n;i++) cin >> a[i];
    int ans = 0;
    for(int i=0;i<m;i++){
        int p;
        cin >> p;
        ans += a[p];
    }
    cout << ans << '\n';
}

太打卡了吧（（

B. Qual B

题意

给定一个由 \(o, x\) 组成的字符串，将第 \(k + 1\) 个及以后的 \(o\) 替换成 \(x\)，输出字符串。

思路

如题。

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

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

int a[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    int cnt = 0;
    for(int i=0;i<n;i++){
        if(s[i] == 'x') cout << 'x';
        else{
            cnt ++;
            if(cnt > m) cout << 'x';
            else cout << 'o';
        }
    }
}

做的太慢了捏

C. Max MEX

题意

给定一个数组 \(a\)，找出一个长为 \(k\) 的子串 \(X\)，满足 \(MEX\) 值最大。

定义 \(MEX(X)\) 为最大的 \(m\) ，满足下面的条件：

  1. \([0, m)\) 都在 \(X\) 内；

  2. \(m\) 不在 \(X\) 内

思路

我们不妨将数组升序排序，去除所有的重复元素，然后从 \(0\) 开始匹配，若能找到 \(0, 1, \ldots, k\) ，那么输出 \(k + 1\)，否则找到最长的 \(0, 1, \ldots, t\) ，输出 \(t + 1\)。

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

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

int a[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a, a + n);
    a[n] = inf;
    int l = 0;
    for(int i=0;i<=n;i++){
        if(a[i] == l - 1) continue;
        if(a[i] == l) l ++;
        if(l >= m) break;
    }
    cout << l;
}

模拟不明白了（（

D. Marking

题意

对于 \(t\) 个询问，给定三个整数 \(n, d, k\)，输出第 \(k\) 次标记的点。

标记满足下面的规则：

  1. 第一次标记 \(0\) 点；

  2. 重复下述操作 \(n - 1\) 次，其中 \(a\) 为前一次标记的下标：

    1. 令 \(x = (a + d)\mod N\)；
    2. 找到 \(x\) 及以后第一个没标记的下标并标记

思路

首先，很明显地，我们需要找出标记的周期，当完成一次周期后，我们需要移到下一位并继续循环，直至结束。

不难证明，周期是 \(x = \frac{n}{gcd(n, d)}\)，而我们只需要计算经过了多少个周期，然后将最后的答案加上这个值即可。

考虑到数据量不超过长整型，我们直接计算 \((d \times k)\mod n\) 即可，然后按照上述操作加上 \(\frac{k}{x}\) 即可。

时间复杂度：不会分析捏

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    private static long gcd(long a, long b) {
        while(b != 0) {
            long tmp = a;
            a = b;
            b = tmp % b;
        }
        return a;
    }

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        while(t -- > 0){
            long n = console.nextInt(), d = console.nextInt(), k = console.nextInt();
            k --;
            console.println(d * k % n + k / (n / gcd(n, d)));
        }
        console.close();
    }

    //快读模板 此处略去
    //public static class Console implements Closeable {}
}

nnd，没考虑到类似于 \(6, 9\) 的测试数据，寄