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

A. Guess the Maximum

思路

贪心

毫无疑问的是，Alice会选择所有区间最大值的最小值-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：打暴力肯定是错误的，题目中给了一个神奇的条件，，假设我们让a和b分别从i和j的位置开始相等，即满足，当我们注意到这个条件的时候，自然而然的就会把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;
}

D. Fixing a Binary String

思路

模拟 + 贪心

题目是将字符串切两半，然后左边一半翻转接到右边去

只有最右边才可以衔接变成k个连续的，

那么我们贪下切的位置

从右边往左边看，000011100.

我们可以0|00011100

就是要把连续的k个都要放到右边部分，不然的话翻转了也没啥用啊。

而对于最右边的两个0，就是去跟左边翻转后的匹配的，最后检查一次即可。

举样例切的位置的例子。

注意，这只是切的位置，还要检查一遍的。

样例1

111 | 00001

样例2

1 | 110

样例3

1110001 | 00011

样例4

| 00000

样例5

1010 | 01

样例6

0111000 | 1

样例7

110 | 001100110

自己举的例子

| 0011001100110011   p = 2

101110 | 000  p = 3

1 | 11100011  p = 3

就是典型的讨论 + 模拟吧，大意再总结下就是最右边连续的如果小于k的话，那么一定要跟翻转后的左边去匹配的，接着再把所有连续的k个都放到右边，因为如果连续的k个在左边的话，翻转一点用都没有。

code

inline void solve() {
     int n, k; cin >> n >> k;
     string s; cin >> s;    
     s = " " + s;
     int j = n, len = 0;
     while (len < k && s[j] == s[n]) j -= 1, len += 1;
     int ok = j, ji = len;
     if (j == 0) return cout << n << endl, void();
     if (s[j] != s[n]) {
     	while (true) {
     		char cur = s[j];
     		len = 0;
     		while (s[j] == cur) j -= 1, len += 1;
     		if (len == k) ok = j;
     		else if (len > k) {
     			ok = j + len - k;
     			break;
     		}else break;
     		if (j == 0) break;
    	}
     }
     if (ok == 0) {
     	if (ji == k) cout << n << endl;
     	else cout << -1 << endl;
     	return;
     }
     reverse(s.begin() + 1, s.begin() + 1 + ok);
     s = " " + s.substr(1 + ok) + s.substr(1, ok);
     len = 0;
     int cur = s[1] - '0';
     bool flag = true;
     for (int i = 1; i <= n - k; i ++ ) {
     	if (s[i] - '0' != cur) flag = false;
     	len += 1;
     	if (len == k) len = 0, cur ^= 1;
     	if (s[i + k] == s[i]) flag = false;
     }
     if (k == n) {
     	char tt = s[1];
     	for (int i = 1; i <= n; i ++ ) if (s[i] != tt) flag = false;
     }
     if (flag) cout << ok << endl;
     else cout << -1 << endl;
	 return;
}