比赛链接
E 「Square」
枚举 \(k\) ,然后二分查找即可。
时间复杂度:\(O(logn)\)
空间复杂度:\(O(1)\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| #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)\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| #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 算法