暑假集训 Nowcoder 多校 Round 2

比赛链接

---

E 「Square」

枚举 \(k\) ，然后二分查找即可。

时间复杂度：\(O(logn)\)

空间复杂度：\(O(1)\)

#include <iostream>

using i64 = long long;

i64 pow10[19];

void init() {
    pow10[0] = 1;
    for (int i = 1; i < 19; i++) pow10[i] = 10ll * pow10[i - 1];
}

void solve() {
    i64 x;
    std::cin >> x;
    for (int k = 0; k < 19; k++) {
        i64 left = 0, right = 1000000000ll;
        while (left <= right) {
            i64 mid = (left + right) / 2;
            i64 prefix = mid * mid / pow10[k];
            if (prefix < x) {
                left = mid + 1;
            }
            else if (prefix > x) {
                right = mid - 1;
            }
            else {
                std::cout << mid << '\n';
                return;
            }
        }
    }

    std::cout << -1 << '\n';
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    init();
    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

F 「Link with Chess Game」

这是一道典型的二分图博弈问题，对于三元组 \((r, b, g)\) ，我们可以看成边长为 \(n\) 的立方体的坐标，对于 \(n\) 为偶数的情况，任意一个初始状态都是最大匹配的必要点，若 \(n\) 为奇数，则只要 \(r_0 + b_0 + g_0\) 为偶数，则该初始状态为最大匹配点必要点。

综上所示，\(n\) 为偶数或者 \(r_0 + b_0 + g_0\) 为偶数时，先手必胜。

时间复杂度：\(O(1)\)

空间复杂度：\(O(1)\)

#include <iostream>

void solve() {
    int n, r, b, g;
    std::cin >> n >> r >> b >> g;
    if (n % 2 == 0 || (r + b + g) % 2 == 0) {
        std::cout << "Alice\n";
    }
    else {
        std::cout << "Bob\n";
    }
}

int main() {
    int numTest;
    std::cin >> numTest;
    while (numTest--) solve();

    return 0;
}

G 「Link with Centrally Symmetric Strings」

这题需要一些前置知识：Manacher 算法