Codeforces Round 882 (Div. 2)

A The Man who became a God

给定一个数组 \(\{x_1,x_2,\cdots,x_n\}\) 和一个整数 \(k\)，记 \(f(l,r)=\sum_{i=0}^{i \le r-l} |x_{l+i}-x_{l+i+1}|\)，求将数组划分为 \(k\) 个部分的划分方案，使得对每个部分的 \(f(l,r)\) 之和最小.

​ 将两数相差大的地方尽可能断开，可以得到结果最小。通过将差值排序后从大到小删除 \(k-1\) 个得出。

B Hamon Odyssey

乔纳森正在与迪奥的吸血鬼手下战斗。其中有 \(n\) 个吸血鬼，它们的强度分别为 \(a_1, a_2,\cdots, a_n\)。
将 \((l,r)\) 表示由索引 \(l\) 到 \(r\) 的吸血鬼组成的一组。乔纳森意识到每个这样的组的强度取决于它们的最弱环节，即按位与操作。更具体地说，组 \((l,r)\) 的强度等于 \(f(l,r) =\) \(a_l \ \& \ a_{l+1} \ \& \ a_{l+2} \ \& \cdots \& \ a_r\)。这里，\(\&\) 表示按位与操作。

乔纳森希望能快速击败这些吸血鬼手下，因此他会将吸血鬼分成连续的组，使得每个吸血鬼正好属于一组，并且这些组的强度之和尽量小。在所有可能的分组方式中，他希望找到组数最多的方式。

给定每个吸血鬼的强度，找出在所有可能的分组方式中，拥有最小强度之和的组的最大数量。

​ 首先我们可以知道，一堆数按位与起来只会让结果变得更小。那么我们先将整个序列与起来，记这个值为 \(x\) ，那么如果 \(x \not = 0\) ，那么答案就为 \(1\) 。如果 \(x = 0\) 时，我们要将 \(x\) 分成若干段，使得每一段中的数位与起来的值为 \(0\) ，那么我们把 \(a\) 从前往后扫，记录当前段的按位与的值，当值为 \(0\) ，新开一段记录即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int T, n;
int a[N];

signed main() {
	for (scanf("%d", &T); T; --T) {
		int ans = 0;
		scanf("%d", &n);
		
		for (int i = 1; i <= n; ++i)
			scanf("%d", &a[i]);
		
		int x = a[1];
		
		for (int i = 2; i <= n; ++i)
			x &= a[i];
			
		if (x != 0) {
			puts("1");
			continue;
		}
		
		int pos = -1;
		
		for (int i = 1; i <= n; ++i) {
			if (pos == -1) {
				pos = a[i];
				++ans;
			}
			
			pos &= a[i];
			
			if (pos == 0)
				pos = -1;
		}
		
		if (pos != -1)
			--ans;
			
		printf("%d\n", ans);
	}
	
	return 0;
}

C Vampiric Powers, anyone?

DIO 意识到星尘十字军已经知道了他的位置，并且即将要来挑战他。为了挫败他们的计划，DIO 要召唤一些替身来迎战。起初，他召唤了 $ n $ 个替身，第 $ i $ 个替身的战斗力为 $ a_i $。依靠他的能力，他可以进行任意次以下操作：

• 设当前的替身数量为 $ m $。
• DIO 选择一个序号 $ i \text{ } ( 1 \le i \le m ) $。
• 接着，DIO 召唤一个新的替身，其序号为 $ m + 1 $，战斗力为 $ a_{m + 1} = a_i \oplus a_{i + 1} \oplus \ldots \oplus a_m $。其中，运算符 $ \oplus $ 表示按位异或。
• 现在，替身总数就变成了 $ m + 1 $。

但对于 DIO 来说，不幸的是，星尘十字军通过隐者之紫的占卜能力，已经知道了他在召唤替身迎战的事情，而且他们也知道初始的 $ n $ 个替身的战斗力。现在，请你帮他们算一算 DIO 召唤的替身的最大可能战斗力（指单个替身的战斗力，并非所有替身战斗力之和）。

​ 我们要在数列 \(a\) 中选出一个区间，使得这个区间的数异或起来的值尽可能的大。我们要求出 \(a\) 的前缀异或数组 \(x\) 。接下来我们就把问题转换为在 \(0\sim n\) 中选两个数 \(i,j\) ，使得 \(x_i \oplus x_j\) 的值尽可能大。考虑开一个桶，将 \(x\) 扔进去，我们枚举 \(i\) ，第二重枚举 \(V\) ，其中 \(V\) 的上限为 \(2^8\) 。这个算法复杂度为 \(\Theta(2^8 \times \sum n)\) 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int P = 256;

int T, n;
int a[N], x[N];
int b[1 << 9];

inline void calc(int I) {
	for (int i = 1; i <= n; ++i)
		x[i] = x[i - 1] ^ a[i];
	
	for (int i = 0; i <= n; ++i)	
		b[x[i]] = I;
}

signed main() {
	scanf("%d", &T);
	
	for (int I = 1; I <= T; ++I) {
		int ans = 0;
		scanf("%d", &n);
		
		for (int i = 1; i <= n; ++i)
			scanf("%d", &a[i]);
		
		calc(I);
		
		for (int i = 0; i <= n; ++i) 
			for (int p = 0; p < P; ++p) 
				if (b[p] == I)
					ans = max(ans, x[i] ^ p);
		
		printf("%d\n", ans);
	}
	
	return 0;
}

D Professor Higashikata

给出一个长度为 \(n\) 的字符串 \(s\)，字符串仅由 0 或 1 构成。

给出 \(m\) 个区间 \([l_i,r_i]\) (\(1\le i\le m\),\(1\le l_i\le r_i\le n\))，你需要将字符串 \(s\) 的子段 \([l_i,r_i]\) 依次拼接，得到新的字符串 \(t\)。

你可以对字符串 \(s\) 进行操作，每次操作可以交换任意两个字符的位置，注意操作不是实际改变，不会影响后续的询问。定义对于字符串 \(s\)，\(f(s)\) 表示最小的操作次数，使得拼接得到的新字符串 \(t\) 的字典序最大。

然后有 \(q\) 次询问，每次询问给出一个位置 \(x_i\)，表示将原字符串 \(s\) 的 \(x_i\) 位置取反，注意是实际改变，会影响后续的询问。相应的，\(t\) 字符串也会发生改变。你需要求出每次询问后，\(f(s)\) 的值。

首先我们考虑，优先把原字符串 \(s\) 中哪些位置变 1 会使得拼接后字符串 \(t\) 的字典序尽可能大。我们把每个位置的这一信息称为“优先级”。根据题目意思可以得出，将 \(m\) 个区间依次拼接，一个位置第一次出现越靠前，它的优先级越高。

然后考虑如何求出每个位置的优先级。这里讲一种区间覆盖的方法。从最后一个区间开始做区间覆盖。对于第 \(m-i+1(1\le i\leq m)\) 个区间，我们将这个区间的值覆盖为 \(i\)。所有区间覆盖完成后，对全部位置进行排序：第一关键字为覆盖上去的值，从大到小（最后被覆盖的说明区间靠前，优先级高）；第二关键字为原先的位置，从小到大（同一区间内位置靠前的优先）。这样我们就得出了每个位置的优先级。

再考虑求出优先级后如何计算每次询问的答案。我们假设当前原字符串 有用的 1 的个数为 \(cnt\)，那么要使得拼接得到的字符串 \(t\) 的字典序最大，应该让原字符串中优先级前 \(cnt\) 个位置全部变成 1。设原字符串中优先级前 \(cnt\) 个位置当前有 \(tot\) 个 1。那么答案显而易见，就是 \(cnt-tot\)。

注意上一段的粗体字：什么是有用的 1？考虑一种情况，那就是原字符串 \(s\) 中，有一些位置根本没有出现在拼接后字符串 \(t\) 中。这些位置上是 0 或 1 是无所谓的。所以如果计算全部 1 的个数作为 \(cnt\)，就可能导致一些无关的位置被变成 1，从而使答案偏大。所以 \(cnt\) 应该是 min⁡(总共 1 的个数,在 t 串中出现过的位置数)min(总共 1 的个数,在 t 串中出现过的位置数)。

具体实现中，区间覆盖和维护 1 的个数我选用的都是树状数组，所以看着比较长，其实是不难写的。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 7;

int T;

char S[N];

bool s[N], vis[N];

int p[N], fa[N];

int cnt, c[N];

inline int find(int x) {
	if (fa[x] == x)
		return x;
	
	return fa[x] = find(fa[x]);
}

inline int lowbit(int x) {
	return x & -(x);
}

inline void add(int u, int x) {
	if (!u)
		return ;
		
	for (; u <= cnt; ) {
		c[u] += x;
		u += lowbit(u);
	}
}

inline int query(int x) {
	int ans = 0;
	
	for (; x; ) {
		ans += c[x];
		x -= lowbit(x);
	}
	
	return ans;
}

int n, m, q;
int X;

inline void clear() {
	for (int i = 1; i <= n; ++i) {	
		s[i] = S[i] - '0';
		fa[i] = i;
	}
}


inline void init() {
	for (int i = 1, l, r; i <= m; ++i) {
		scanf("%d%d", &l, &r);
		
		for (int j = l; j <= r; j = find(j) + 1)
			if (!vis[j]) {
				vis[j] = true;
				p[j] = ++cnt;
				fa[j - 1] = j;
			}
	}
	
	for (int i = 1; i <= n; ++i)	
		if (s[i]) {
			++X;
			add(p[i], 1);
		}
}

signed main() {
	scanf("%d%d%d%s", &n, &m, &q, S + 1);
	clear();
	
	init();
		
	for (int x; q; --q) {
		scanf("%d", &x);
		
		s[x] ? (--X, s[x] = false, add(p[x], -1)) : (++X, s[x] = true, add(p[x], 1));
		
		printf("%d\n", min(X, cnt) - query(min(X, cnt)));
	}
	
	return 0;
}

E Triangle Platinum?

​ 很显然这是交互题，我不会做。

F The Boss's Identity

给定一个无穷长的整数数列的前 \(n\) 项 \(a_1,a_2 \dots a_n\)，且对于任意 \(i > n\)，\(a_i=a_{i-n}|a_{i-n+1}\).
你需要处理 \(q\) 次询问。每次询问给定一个整数 \(x\)，请找出最小的 \(i\) 满足 \(a_i>x\)。如果不存在这样的 \(i\)，输出 −1 。

​ 很不错，连题解都看不懂。