A. Stone Game

题解

从一侧取：两种情况

从两侧取：一种情况

取三种情况的最小值。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        int p1 = min_element(a.begin(), a.end()) - a.begin();
        int p2 = max_element(a.begin(), a.end()) - a.begin();
        cout << min({max(p1, p2) + 1,  n - min(p1, p2), (min(p1, p2) + 1) + (n - max(p1, p2))}) << "
";
    }
    return 0;
}

B. Friends and Candies

题解

如果总和不能平分则无解，否则将多于平均的数重新分配。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());
        int sum = accumulate(a.begin(), a.end(), 0);
        if (sum % n != 0) {
            cout << -1 << "
";
        } else {
            cout << n - (upper_bound(a.begin(), a.end(), sum / n) - a.begin()) << "
";
        }
    }
    return 0;
}

C. Number of Pairs

题解

二分所能加的数的左右边界。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, l, r;
        cin >> n >> l >> r;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            auto it1 = lower_bound(a.begin() + i + 1, a.end(), l - a[i]);
            auto it2 = upper_bound(a.begin() + i + 1, a.end(), r - a[i]);
            ans += it2 - it1;           
        }
        cout << ans << "
";
    }
    return 0;
}

D. Another Problem About Dividing Numbers

题解

最少操作次数：将 (a,b) 向 (gcd(a, b)) 转化，

当 (gcd(a, b) = a) 且 (gcd(a, b) = b) 时，最少操作 (0) 次
当 (gcd(a, b) = a) 或 (gcd(a, b) = b) 时，最少操作 (1) 次
当 (gcd(a, b) e a) 且 (gcd(a, b) e b) 时，最少操作 (2) 次

最多操作次数：将 (a, b) 向 (1) 转化，为两者所有质因子的幂次之和。

如果 (k) 位于两者之间则有解。

因为最少操作次数为 (2) 次，所以特判 (k = 1) 的情况，然后判断 (k) 是否小于最多操作次数即可。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    constexpr int N = 1e5;
    vector<int> isPrime(N, true);
    for (int i = 2; i < N; i++) {
        for (int j = i + i; j < N; j += i) {
            isPrime[j] = false;
        }
    }
    vector<int> Primes;
    for (int i = 2; i < N; i++) {
        if (isPrime[i]) {
            Primes.push_back(i);
        }
    }
    int t;
    cin >> t;
    while (t--) {
        int a, b, k;
        cin >> a >> b >> k;
        if (k == 1) {
            if (a == b) {
                cout << "NO" << "
";
            } else if (a % b == 0 or b % a == 0) {
                cout << "YES" << "
";
            } else {
                cout << "NO" << "
";
            }
            continue;
        }
        auto Count_Expo = [&](int n) {
            int res = 0;
            for (auto i : Primes) {
                while (n % i == 0) {
                    ++res;
                    n /= i;
                }
            }
            if (n != 1) {
                ++res;
            }
            return res;
        };
        cout << (k <= Count_Expo(a) + Count_Expo(b) ? "YES" : "NO") << "
";
    }
    return 0;
}

E. Funny Substrings

题解

因为 (haha) 长为 (4) ，所以保存一个字符串首尾的 (3) 个字符及 (haha) 的个数。

代码

#include <bits/stdc++.h>
using namespace std;
struct P{
    string front;
    string back;
    long long cnt_haha = 0;
};
P cal(const string& s) {
    P res;
    res.front = s.substr(0, 3);
    res.back = s.substr(max(0, (int)s.size() - 3));
    for (int i = 0; i < (int)s.size(); i++) {
        if (s.substr(i, 4) == "haha") {
            ++res.cnt_haha;
        }
    }
    return res;
}
P merge(const P& a, const P& b) {
    P res;
    res.front = (a.front + b.front).substr(0, 3);
    res.back = (a.back + b.back).substr(max(0, (int)a.back.size() + (int)b.back.size() - 3));
    res.cnt_haha = a.cnt_haha + b.cnt_haha + cal(a.back + b.front).cnt_haha;
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        map<string, P> mp;
        for (int i = 0; i < n; i++) {
            string name, op;
            cin >> name >> op;
            if (op == ":=") {
                string str;
                cin >> str;
                mp[name] = cal(str);
            } else if (op == "=") {
                string a, b;
                char ch;
                cin >> a >> ch >> b;
                mp[name] = merge(mp[a], mp[b]); 
            }
            if (i == n - 1) {
                cout << mp[name].cnt_haha << "
";
            }
        }
    }
    return 0;
}

F. Interesting Function

题解

依次计算每一位对前一位产生了多少进位。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int l, r;
        cin >> l >> r;
        string s1 = to_string(l), s2 = to_string(r);
        s1 = string(s2.size() - s1.size(), '0') + s1;
        int ans = 0, carry = r - l;
        for (int i = s1.size() - 1; i >= 0; i--) {
            ans += carry;
            carry = (carry + s1[i] - '0') / 10;
        }
        cout << ans << "
";
    }
    return 0;
}

G. Gift Set

题解

因为总次数具有单调性，所以考虑对其二分。

若某次所二分的总次数值为 (n) ，假设进行了操作一 (k) 次，那么有：

(a imes k + b imes (n - k) le x)
(b imes k + a imes (n - k) le y)

不妨令 (a gt b) ，化简得：

(k le frac{x - b imes n}{a - b})
(k ge frac{y - a imes n}{b - a} = frac{a imes n - y}{a - b})

同时，有：

(k ge 0)
(k le n)

若上述四个不等式在数轴上有交集，则 (k) 存在，表示当前二分值 (n) 可行。

Tips

若分子 (a) 可能为正负整数，分母 (b) 为正整数，则有：

取上整： (lfloor frac{a + b - 1}{b} floor)
取下整： (lfloor frac{a + b}{b} floor - 1)

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        if (a == b) {
            cout << min(x, y) / a << "
";
            continue;
        }
        if (a < b) {
            swap(a, b);
        }
        int l = 0, r = (x + y) / (a + b);
        while (l < r) {
            int n = (l + r + 1) / 2;
            int L = max(0, (a * n - y + a - b - 1) / (a - b));
            int R = min(n, (x - b * n + a - b) / (a - b) - 1);
            if (L <= R) {
                l = n;
            } else {
                r = n - 1;
            }
        }
        cout << l << "
";
    }
    return 0;
}