A - Yay!

大意

给定字符串，其中有且仅有一个字符与其他不同，输出这个字符的下标（从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?

大意

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

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

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

思路

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

代码

#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

大意

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

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

输出最后的字符串。

思路

朴素做法的复杂度是，会超时。

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

代码

#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

大意

一个长度为的自然数序列。求满足以下两个条件的整数对的个数：

• 

• 是一个完全平方数。(0也是完全平方数）

思路

考虑两个自然数，如果是完全平方数，只有两种情况：

• 或，此时。
• 是完全平方数且不为0。

并且易得。

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

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

每个只有两种情况：

• ，那么它与前面和相同的数以及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;
}