AtCoder Beginner Contest 342

pystraf

已于 2024-04-21 19:54:35 修改

阅读量865

点赞数 22

分类专栏： AtCoder 文章标签：算法 c++ 数据结构

于 2024-03-31 18:23:22 首次发布

本文链接：https://blog.csdn.net/sblsf/article/details/137204809

版权

AtCoder 专栏收录该内容

16 篇文章

订阅专栏

文章介绍了四个编程题目，涉及字符串字符计数、查询特定字符位置、替换字符操作及计算满足特定条件的整数对。通过桶排序、映射表和完全平方数性质解决问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

A - Yay!

大意

给定字符串 $S$ ，其中有且仅有一个字符与其他不同，输出这个字符的下标（从1开始）。

思路

桶排序统计次数即可。

代码

#include<iostream>
#include<vector>
using namespace std;
int main(){
    string s;
    cin >> s;
    vector<int> a(26, 0);
    for(int i = 0; i < s.size(); i++) a[s[i] - 'a']++;
    for(int i = 0; i < s.size(); i++){
        if(a[s[i] - 'a'] == 1){
            cout << i + 1 << endl;
            break;
        }
    }
    return 0;
}

B - Which is ahead?

大意

有 $n$ 个人排成一列，从前往后第 $i$ 个位置的人是编号为 $P_i$ 的人。下标从1开始。

请处理 $q$ 个查询，每个查询如下：

给定两个整数 $a$ 和 $b$ 。在编号为 $a$ 的人和编号为 $b$ 的人中，输出站在更前面的那个人的编号。

思路

记录一下每个人的下标，然后对于每个询问比较下标大小即可。

代码

#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    int n, q;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> q;
        a[q - 1] = i;
    }
    cin >> q;
    while(q--){
        int x, y;
        cin >> x >> y;
        if(a[x - 1] < a[y - 1]) cout << x << endl;
        else cout << y << endl;
    }
    return 0;
}

C - Many Replacement

大意

给定一个长度为 $n$ 的字符串，进行 $m$ 次操作。

每次操作，将所有的字符 $a$ 替换成字符 $b$ 。

输出最后的字符串。

思路

朴素做法的复杂度是 $O(nm)$ ，会超时。

我们可以建立一个映射表，每次只需要修改映射表，最后才进行替换。

代码

#include<iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    int n, q;
    string s;
    cin >> n >> s;
    cin >> q;
    string from, to;
    from = to = "abcdefghijklmnopqrstuvwxyz";
    while(q--){
        char c, d;
        cin >> c >> d;
        for(int i = 0; i < 26; i++)
        if(to[i] == c) to[i] = d;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 26; j++)
            if(s[i] == from[j]) cout<<to[j];
    }
    return 0;
}

D - Square Pair

大意

一个长度为 $N$ 的自然数序列 $A$ 。求满足以下两个条件的整数对 $(i,j)$ 的个数：

$1\le i,j \le n$
$A_i\times A_j$ 是一个完全平方数。(0也是完全平方数）

思路

考虑两个自然数 $a,b$ ，如果 $a\times b$ 是完全平方数，只有两种情况：

$a=0$ 或 $b = 0$ ，此时 $a\times b = 0$ 。
$a\times b$ 是完全平方数且不为0。

并且易得 $x^2\times y^2=(x\times y)^2$ 。

所以一个完全平方数因子对 $a\times b$ 是不是完全平方数没有影响。我们可以把 $a$ 和 $b$ 分别除掉所有完全平方数因子，得到 $a'$ 和 $b'$ 。由于它们没有完全平方数因子（除了1），所以只有 $a'=b'$ 时， $a'\times b'$ 才是完全平方数。

因此，我们把所有 $A_i$ 除去所有完全平方数因子，然后遍历 $A_i$ 。

每个 $A_i$ 只有两种情况：

$A_i\ne 0$ ，那么它与前面和 $A_i$ 相同的数以及0可以组成一个平方数对。
$A_i=0$ ，那么它与前面所有数都可以组成一个平方数对。

开个map，一边统计次数，一边计算答案即可。

代码

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;
#define int long long

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n;
    cin >> n;
    vector<int> a(n + 1, 0);

    auto divide = [&](int x){
        for(int i = 2; i <= x / i; i++)
            while(x % (i * i) == 0) x /= (i * i);
        return x;
    };

    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] = divide(a[i]);
    }

    int ans = 0;
    unordered_map<int, int> times;
    for(int i = 1; i <= n; i++){
        if(a[i]) ans += times[a[i]] + times[0];
        else ans += i - 1;
        times[a[i]]++;
    }
    cout << ans << endl;
    return 0;
}