526互联

Educational Codeforces Round 148 (Rated for Div. 2) A~E

发布时间 2023-05-21 17:16:59作者: xhy666

Educational Codeforces Round 148 (Rated for Div. 2) A~E

A. New Palindrome

对于奇回文串不能统计中心的字符，然后判断是否有不同的字符

void work() {  
	string s;
	cin >> s;
	vector<int> ch(26);
	int ok = 0;
	for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
		++ch[s[i] - 'a'];
	}
	rep (i, 0, 25) if (ch[i]) ok++;
	cout << (ok > 1 ? "YES\n": "NO\n");
}

B. Maximum Sum

最小值的个数确定，最大值的个数也确定了。所以只要枚举最小值或者最大值的个数。排序后求出前缀和，时间复杂度\(O(nlogn)\)

void work() {  
	int n, k;
	cin >> n >> k;
	vector<LL> a(n + 1), s(n + 1);
	rep (i, 1, n) cin >> a[i];
	sort(a.begin() + 1, a.end());
	rep (i, 1, n) s[i] = s[i - 1] + a[i];
	LL pre = 0, res = 0;
	for (int i = 0; i <= n; i += 2) {
		if (i != 0) pre += a[i] + a[i - 1];
		if (i / 2 > k) break;
		if (n - i < (k - i / 2)) break;
		res = max(res, s[n] - ((s[n] - s[n - k + i / 2]) + pre));
	}
	cout << res << "\n";
}

C. Contrast Value

对于\(a_{i-1}\le a_i\le a_{i+1}\)或者\(a_{i-1}\ge a_i\ge a_{i+1}\)的\(a_i\)，删掉只会使答案更优。答案等于波峰和波谷的数量

void work() {  
	int n;
	cin >> n;
	vector<int> a(n + 1), b;
	rep (i, 1, n) cin >> a[i];
	b = a;
	sort(b.begin() + 1, b.end());
	if (b[1] == b[n]) {
		cout << 1 << "\n";
		return;
	}
	int res = 2;
	rep (i, 2, n - 1) if ((a[i - 1] <= a[i] && a[i] <= a[i + 1]) || (a[i] <= a[i - 1] && a[i + 1] <= a[i])) {
		a[i] = a[i - 1];
	} else res++;
	cout << res << "\n";
}

D2. Red-Blue Operations (Hard Version)

答案具有单调性，可以二分答案。判断最小值能否大于等于\(x\)，将原数组排序后考虑所有小于\(x\)的(排序后的\(a_1a_2...a_m\))，然后贪心分配\(1,2,...,k\)

贪心策略：

对于一个数\(a_i\)，我们假设最后分配给它的数共有\(t\)个

\[a_i^{\prime}= a_i+p_1-p_2+...+(-1^{1-t\%2})p_t \]

因为\(p_1<p_2<...<p_t\)，所以当\(t\)为奇数时值变大，偶数时变小，显然都要所有小于\(x\)的\(a_i\)都要分配奇数个

那么先考虑所有小于\(x\)的，从小到大为\(a_1a_2...a_m\)

将\(k,k-1,...,k-m+1\)依次分配给\(a_1a_2...a_m\)，得到\(a_1^{\prime}a_2^{\prime}...a_m^{\prime}\)，如果这些数中的最小值还是小于\(x\)，那么肯定没救了，直接返回\(false\)，当然如果\(k<m\)也返回\(false\)

然后剩下还要分配\(1,2,...,k-m\)，我们先考虑用剩下大于等于\(x\)的\(a_{m+1},a_{m+2}...,a_n\)救场

如果\(k<n\)，那么这些数都至少不减，返回\(true\)

如果\(k-m\)为奇数，那么只要剩下至少一个数，就能返回\(true\)（全都加在一个数上），否则返回\(false\)（所有小于\(x\)的\(a_i\)都要分配奇数个）

如果\(k-m\)为偶数，如果剩下至少两个数，让两个数分配奇数个即可，返回\(true\)

剩下的情况，我们发现形如\(+1-2,+3-4\)这样分配能用\(-1\)的代价消去两项，显然代价是最小的，并且这时\(k-m\)为偶数，只要判断\((k-m)/2\)和数组中大于\(x\)的部分的大小即可

时间复杂度\(O(nlogn+logAlogn)\)

void work() {  
	LL n, q, k;
	cin >> n >> q;
	vector<LL> a(n + 1), b(n + 1), mn(n + 1), sa(n + 1), sb(n + 1);
	rep (i, 1, n) cin >> a[i];
	sort(a.begin() + 1, a.end());
	rep (i, 1, n) sa[i] = sa[i - 1] + a[i];
	rep (i, 1, n) b[i] = a[i] - i + 1;
	rep (i, 1, n) sb[i] = sb[i - 1] + b[i];
	mn[1] = b[1];
	rep (i, 2, n) mn[i] = min(mn[i - 1], b[i]);
	
	function<bool(LL)> check = [&](LL x) {
		int cnt = lower_bound(a.begin() + 1, a.end(), x) - a.begin() - 1;
		if (!cnt) {
			if (k % 2 == 0 && n == 1) return a[1] - k / 2 >= x; 
			return true;	
		}
		if (mn[cnt] + k < x) return false;
		if (k <= n) return true;
		if ((k - cnt) % 2) return cnt < n;
		else {
			if (cnt + 2 <= n) return true;
			else {
				LL ext = k * cnt + sb[cnt] + sa[n] - sa[cnt] - n * x;
				return ext >= (k - cnt) / 2;
			}
		}
	};
		
	while (q--) {
		cin >> k;
		LL l = -1e18, r = 1e18;
		while (l < r) {
			LL mid = l + r + 1 >> 1;
			if (check(mid)) l = mid;
			else r = mid - 1;
		} 
		cout << l << " ";
	}
	
}

E. Combinatorics Problem

赛时我在草稿纸上列出了\(k=1,2,3\)对应的\(b\)的前若干项系数，然后惊奇地发现相邻项\(a_i\)的系数差正好等于\(k-1\)的对应系数，也就是做\(k\)次前缀和就好了。时间复杂度\(O(nk)\)...

正解是用组合数推出\(dp\)转移式($\binom{x}{y}=\binom{x - 1}{y - 1} + \binom{x - 1}{y} $)，复杂度也是一样的

void work() {  
	int n, k, x, y, m;
	cin >> n;
	vector<int> a(n + 1), s(n + 1), b(n + 1);
	cin >> a[1] >> x >> y >> m >> k;
	s[1] = a[1];
	rep (i, 2, n) a[i] = (1ll * a[i - 1] * x % m + y) % m, s[i] = (1ll * s[i - 1] + a[i]) % MOD; 
	rep (i, 1, n) b[i] = (1ll * b[i - 1] + s[i]) % MOD;
	int K = k;
	k--;
	while (k--) {
		rep (i, 1, n) b[i] = (1ll * b[i - 1] + b[i]) % MOD;
	}
	LL res = 0;
	rep (i, 1, n - K + 1) res = res ^ (1ll * b[i] * (i + K - 1));
	cout << res << "\n"; 
}