342

A - Yay!

字符串中有一个字符和别人，找出他

void solve() {
    string s;cin >> s;char ch = s[0], chh = s[1];
    if (count(s.begin(), s.end(), s[0]) == 1) {
        cout << "1\n";return;
    }
    for (int i = 1;i < s.size();i++) {
        if (s[i] != s[0]) {
            cout << i + 1 << '\n';return;
        }
    }
}

B - Which is ahead?

有 $N$ 个人站成一排。站在最前面第 $i$ 个位置的是第 $P_{i}$ 个人。

处理 $Q$ 个查询。第 $i$ 个查询如下：

给你整数 $A_{i}$ 和 $B_{i}$ 。在人 $A_{i}$ 和人 $B_{i}$ 之间，打印站在最前面的人的编号。

void solve() {
    int n;cin >> n;vector<int> a(n + 1);
    unordered_map<int, int> m;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        m[a[i]] = i;
    }
    int q;cin >> q;
    while (q--) {
        int l, r;cin >> l >> r;
        if (m[l] < m[r]) {
            cout << l << '\n';
        } else {
            cout << r << '\n';
        }
    }
}

C - Many Replacement

给出字符串和 $q$ 组查询，每次查询将字符串中所有等于 $c$ 的改为 $d$ ，输出最终字符串。

Solution

树状数组/思维

只要知道每个字母最终会变成什么字符就可以。

void solve() {
    int n;cin >> n;string s;cin >> s;
    int q;cin >> q;
    string a = "abcdefghijklmnopqrstuvwxyz";
    while (q--) {
        char c, d;cin >> c >> d;
        for (int i = 0;i < a.size();i++) {
            if (a[i] == c)a[i] = d;
        }
    }
    for (int i = 0;i < n;i++) {
        s[i] = a[s[i] - 'a'];
    }
    cout << s << '\n';
}

D - Square Pair

给定数组 $a$ ，选择两个下标 $i, j (i \neq j)$ 问 $a_{i} \times a_{j}$ 是平方数的个数。

Solution

如果 $A_{i}, A_{j}$ 中有一个为 $0$ ，显然满足条件。

对于整数 $x$ ，设其能整除的最大平方数为 $d_{x}$ 。那么 $A_{i} A_{j}$ 为平方数的充分必要条件是 $\frac{A_{x}}{d_{x}} \frac{A_{y}}{d_{y}}$ 为平方数。而且，这又等价于 $\frac{A_{x}}{d_{x}} = \frac{A_{y}}{d_{y}}$ 。

#define int long long
void solve() {
    int n;cin >> n;vector<int> a(n);for (auto& i : a)cin >> i;
    sort(a.begin(), a.end());
    int ans = 0, p = 0;
    for (int i = 0;i < n;i++) {
        if (!a[i])ans += n - i - 1, p = i + 1;
    }
    vector<int> l(n, 1), num(2e5 + 1);
    for (int i = p;i < n;i++) {
        int k = 1;
        while (k * k <= a[i]) {
            k++;
            if (a[i] % (k * k) == 0)l[i] = (k * k);
        }
        a[i] /= l[i];
        num[a[i]]++;
    }
    for (int i = 1;i <= 2e5;i++) {
        ans += (num[i] - 1) * num[i] / 2;
    }
    cout << ans << '\n';
}

E - Last Train

(待更 $\dots$ )

反向建图

概率DP

线段树/multiset