Codeforces Round 951 (Div. 2)

A. Guess the Maximum
题意：给定一个数组，求一个k值，k满足对于任意的这个数组的区间的最大值max，k < max。求满足条件的最大k。

思路：只考虑长度为2的区间即可。参与到比较中的数值一定是两个数中的大数，从所有大数中选出最小的一个即可。

总结：赛时很快就A掉了，但是思考的不够细节，思维太飘了。

void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (auto& x : a){
        cin >> x;
    }

    int ans = (int)2e9;
    for (int i = 0; i < n - 1; ++i){
        ans = min(ans, max(a[i], a[i + 1]));
    }

    cout << ans - 1 << '\n';
}

B. XOR Sequences
题意：给定两个整数x和y，以及两个无穷数组。数组中的数是1~inf ^ x(y),求这两个数组的最长公共子串长度。

思路：答案就是x ^ y的lowbit值，官方题解说的已经很好了。

总结：求最长公共长度，那么一定存在公共子串的起始 x ^ a = y ^ b.此时a和b每次 + 1,分析这个 + 1的过程：如果a和b都加1，假设最后一位都是0或者1，那么x ^ a ^ 1 = y ^ b ^ 1,因为a和b都同时更改了相同位的一个bit。如果最低位不同，那么+1更改了不同位的bit，而基于x ^ a = y ^ b的前提，更改后的a和b再与x和y运算肯定不满足相等的条件了。 所以根据这个逻辑可以推出来，我们要找的最大长度，就是a和b加了一个数c以后，a和b改变了相同的bit位，也就是(a + c) = a ^ c, (b + c) = b ^ c,且(a + c) ^ (b + c) = a ^ b。
赛时找规律过的，但是始终不明白为什么，这样分析的话，就说的通了，要先把x和y相等的初始条件列出来，再去考虑增加1或者增加2的时候会有什么样的数学逻辑，有什么样的情况，再去拓展到增加任意数的情况。

void solve() {
	int x, y;
	cin >> x >> y;

	int t = x ^ y;
	cout << (t & -t) << '\n';
}

C. Earning on Bets
题意：给定n个数，n <= 50,a[i] <= 20。构造n个数，使得对于每个i，a[i] * x[i] > sum(x[1 : n])

思路：求出n个数的lcm，然后考虑这个数是否能构造出来，如果不行，则无解。

总结：赛时使用的二分，虽然AC了，但是感觉逻辑上不严谨，这里分析一下另一种直觉做法。给定一个数y，让所有的x[i] * a[i]都> y，那么可以求出每个x[i]。很明显，如果x[i]是一个浮点数，那么需要向上取整，这会造成最后构造出来的数组总和变的更大。所以有一个最优的数学逻辑，就是所有构造出来的x[i]，都是被y / a[i]得到并且y % a[i] == 0。这样可以保证构造出来的sum是最小的，如果这个sum >= y，那么对于其他的任意y，肯定无解，因为其他的任意y在求系数的时候，还需要向上取余，构造出来的数组和只会更大，不会更小。
看了官方题解，这里有一个想不到的逻辑：就是sigma(s / ki) < s => sigma(1 / k) < 1，一个比较新的思考方式。

void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    int lcm_value = 1;
    for (auto& x : a){
        cin >> x;
        lcm_value = lcm(lcm_value, x);
    }

    vector<int> b;
    for (const auto& x : a){
        b.push_back(lcm_value / x);
    }

    if (accumulate(b.begin(), b.end(), 0) >= lcm_value){
        cout << "-1\n";
    }
    else{
        for (int i = 0; i < n; ++i){
            cout << b[i] << " \n"[i == n - 1];
        }
    }
}

D. Fixing a Binary String

先放个TLE代码，再分析正解。

void solve() {
	int n, k;
	cin >> n >> k;

	string s;
	cin >> s;

	{
		int s0 = count(s.begin(), s.end(), '0');
		if (s0 == n || s0 == 0){
			cout << (k == n ? "1\n" : "-1\n");
			return;
		}
		if (s0 % k != 0){
			cout << "-1\n";
			return;
		}
	}

	s = ' ' + s;

	vector<array<int, 2>> cnt(n + 1, {0, 0});
	for (int i = 1; i <= n; ++i) {
		cnt[i][0] = (cnt[i - 1][0] + (s[i] == '0'));
		cnt[i][1] = (cnt[i - 1][1] + (s[i] == '1'));
	}

	for (int i = k + 1; i <= n; ++i) {
		int cur0 = cnt[i][0] - cnt[i - k][0];
		int cur1 = cnt[i][1] - cnt[i - k][1];
		if (!cur0 || !cur1) {
			int tag = 1;
			bool ok = true;
			for (int j = i, t = 1; t <= (n / k) - 1; j += tag * k, t++) {
				int cnt0 = abs(cnt[min(n, j + tag * k)][0] - cnt[j][0]);
				int cnt1 = abs(cnt[min(j + tag * k, n)][1] - cnt[j][1]);
				if (j + k > n) {
					int p = (k - (n - j));
					cnt0 += cnt[i - k][0] - cnt[i - k - p][0];
					cnt1 += cnt[i - k][1] - cnt[i - k - p][1];
					tag = -1;
					j = i - p;
				}
				if (cnt0 != cur1 && cnt1 != cur0) {
					ok = false;
					break;
				}
				swap(cur1, cur0);
			}
			if (ok) {
				cout << i - k << '\n';
				return;
			}
		}
	}
	cout << "-1\n";
}

题意：给定一个01字符串和一种操作，问一次操作后能否使字符串变成k-proper字符串。每次操作是选一个下标，先reverse 该下标前缀串，再首尾交换该串。

思路：先剪枝，可知如果0或1出现次数不是k的整数倍，肯定无解。
先吃饭，晚点整理。

第一种思路：
直接遍历所有块，找到第一个不合法的块，然后判定操作后是否合法。

void solve() {
	int n, k;
	cin >> n >> k;

	string s;
	cin >> s;

	auto check = [&](string & s){
		int cnt = 0;
		for (int i = 0, cur = 0; i < n; ++i){
			if (s[i] == s[cur]){
				cnt ++;
				continue;
			}
			if (cnt < k){
				return i;
			}
			else if (cnt > k){
				return i - k;
			}
			else{
				cur = i;
				cnt = 1;
			}
		}
		return cnt > k ? n - k : n;
	};

	int p = check(s);
	if (p == n){
		cout << n << '\n';
		return;
	}

	reverse(s.begin(), s.begin() + p);
	rotate(s.begin(), s.begin() + p, s.end());

	int t = check(s);

	cout << (t == n ? p : -1) << '\n';
}

第二种思路待整理。