Codeforces Round 951 (Div. 2) 题解分享

本文主要是介绍Codeforces Round 951 (Div. 2) 题解分享，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. Guess the Maximum

思路

贪心

毫无疑问的是，Alice会选择所有区间最大值的最小值-1，即 $min\sum - 1$ 。

关键是如何选取。我们注意到区间长度越大，这个区间的最大值是随着它不减的，所以如果Bob要让Alice选的最小的话，选择的区间长度一定是2。

因此我们从左往右遍历一遍区间长度为2的情况即可。

code

inline void solve() {int n; cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];int minv = 1e9;for (int i = 1; i < n; i ++ ) {minv = min(minv, max(a[i], a[i + 1]));}cout << minv - 1 << endl;return;
}

B. XOR Sequences

思路

Q：该怎么做？真的是打暴力么？

A：打暴力肯定是错误的，题目中给了一个神奇的条件， $x != y$ ，假设我们让a和b分别从i和j的位置开始相等，即满足 $a_{I} XOR x = b_{j} XOR y$ ，当我们注意到这个条件的时候，自然而然的就会把x异或过去。

Q：我懂了，然后怎么做，感觉还是找不出来数量。

A：结合样例二，x XOR y = 1000，而答案为8。

Q：其实这样也能猜出来是2的(0的个数次)

A：后面3个零，也就是8。后面如果选的bj后面三位有1，这样往上加1的过程肯定是两个相等的情况一定是小于8的，换句话说，这个一卡着了最大长度。

code

inline void solve() {int a, b; cin >> a >> b;int x = a ^ b;cout << (x & (-x)) << endl;return;
}

C. Earning on Bets

思路

题目大意是让你分配任意的钱，使得任意一处获奖得到的钱能够严格大于你花的钱的总数。

Q：首先猜一个lcm

A：然后用lcm实现刚好合适（）

code

inline void solve() {ll n; cin >> n;vector<ll> a(n + 1);ll g = 1;for (int i = 1; i <= n; i ++ ) {cin >> a[i];g = lcm(g, a[i]);}ll sum = 0;for (int i = 1; i <= n; i ++ ) {sum += g / a[i];}if (sum >= g) cout << -1 << endl;else {for (int i = 1; i <= n; i ++ ) {cout << g / a[i] << ' ';}cout << endl;}return;
}

这篇关于Codeforces Round 951 (Div. 2) 题解分享的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！