Blog - Floating Ocean
0%

AtCoder - ABC 290

发表于 更新于
本文字数： 2.3k 阅读时长 ≈ 4 分钟
阅读次数： Valine：

Contestant. Rank 3650. Rating +66.

A. Contest Result

题意

给定数组 ，输出 的总和。

思路

如题。

时间复杂度：

对应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';
}
cpp

太打卡了吧（（

B. Qual B

题意

给定一个由 组成的字符串，将第 个及以后的 替换成 ，输出字符串。

思路

如题。

时间复杂度：

对应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';
        }
    }
}
cpp

做的太慢了捏

C. Max MEX

题意

给定一个数组 ，找出一个长为 的子串 ，满足 值最大。

定义 为最大的 ，满足下面的条件：

  1. 都在 内；

  2. 不在 内

思路

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

时间复杂度：

对应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;
}
cpp

模拟不明白了（（

D. Marking

题意

对于 个询问，给定三个整数 ，输出第 次标记的点。

标记满足下面的规则：

  1. 第一次标记 点；

  2. 重复下述操作 次，其中 为前一次标记的下标：

    i. 令 ；

    ii. 找到 及以后第一个没标记的下标并标记

思路

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

不难证明，周期是 ，而我们只需要计算经过了多少个周期，然后将最后的答案加上这个值即可。

考虑到数据量不超过长整型，我们直接计算 即可，然后按照上述操作加上 即可。

时间复杂度：不会分析捏

对应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 {}

}
java

nnd，没考虑到类似于 的测试数据，寄