Codeforces Round #789 (Div. 2)

比赛链接：

https://codeforces.com/contest/1678

B. Tokitsukaze and Good 01-String

题目大意：

长为 \(n\) 的 01 字符串，连续的 0 或 1 分成一段，若每一段都是偶数，则定义该字符串是 \(good\) 的，每一次操作可以让某个位置上的 0 变 1，或者 1 变 0，问最少多少步可以让字符串变成 \(good\) 的，同时输出用最小操作步骤使分的段数最小。

思路：

将整个字符串拆成长度为 2 的若干段字符串，每段两个字符不同，则改变其中一个，操作次数 + 1。
而最小分段的方法，就是让改变后的字符串尽可能与前面一致。

代码：

#include 
using namespace std;
int T, n;
string s;
void solve(){
	cin >> n >> s;
	int ans = 0, k = 0, p = -1;
	for (int i = 0; i < n; i += 2 ){
		if (s[i] != s[i + 1]) ans ++ ;
		else{
			if (p != s[i]) k ++ ;
			p = s[i];
		}
	}
	cout << ans << " " << max(k, 1) << "\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> T;
	while (T -- )
		solve();
	return 0;
}

C. Tokitsukaze and Strange Inequality

题目大意：

给定一个序列，找出 \([a, b, c, d](1 <= a < b < c < d <= n)\)，满足 \(p_a < p_c and p_b > p_d\) 的数量。

思路：

固定 \(b\) 和 \(c\)。
每次只需找到 \([1, b - 1]\) 中小于 \(p_c\) 的值的数量以及 \([c + 1, n]\) 中小于 \(p_b\) 的数量，相乘之后累加就是答案。
预处理一个前缀和数组 \(s[i][j]\)，表示前 \(i\) 个中小于等于 \(j\) 的数量有多少个。

代码：

#include 
using namespace std;
const int N = 5010;
int T, n, p[N], s[N][N];
void solve(){
	cin >> n;
	for (int i = 1; i <= n; i ++ )
		cin >> p[i];
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= n; j ++ )
			s[i][j] = 0;
	for (int i = 1; i <= n; i ++ ){
		for (int j = 1; j <= n; j ++ )
			s[i][j] += s[i - 1][j];
		for (int j = p[i]; j <= n; j ++ )
			s[i][j] ++ ;
	}
	long long ans = 0;
	for (int b = 1; b <= n; b ++ )
		for (int c = b + 1; c <= n; c ++ )
			ans += s[b - 1][p[c] - 1] * (s[n][p[b]] - s[c][p[b]]);
	cout << ans << "\n";
}
int main(){
	cin >> T;
	while (T -- )
		solve();
	return 0;
}

D. Tokitsukaze and Meeting

题目大意：

\(n * m\) 个学生依次进入 \(n * m\) 大小的教室，每个学生标号是 0 或 1，新的同学进来后坐在 (1, 1)，原来坐在 (1, 1) 的坐到 (1, 2) 去，第 (1, m) 的同学做到第 (2, 1) 去，以此类推。
问每位学生入座后，有多少行和多少列有至少一个标号为 1 的学生。

思路：

首先考虑列，当新进入一个学生后，可以发现，每列是整体向右移动一位的，所以当某一列上有 1 之后，后面就一直有 1，通过取模将列划分为成 \(m\) 份，通过一个数组记录下来每列有没有 1 即可，当某列新进来一个 1，答案 + 1。
考虑行，第 \(i\) 的状态可以从第 \(i - m\) 转移过来，不断转移下去，可以发现余数相同的位置的状态其实是一样的。
新加入的一个数，如果前面有个 1 也在第 1 行，那么它的答案要 + 1，通过不断更新最近的 1 的位置，来求列的值。
第 \(i\) 位的结果就是列的结果和行的结果之和。

代码：

#include 
using namespace std;
#define LL long long
LL T, n, m;
string s;
void solve(){
	cin >> n >> m >> s;
	vector  ans(n * m), r(m), c(m);
	LL cnt = 0, p = - m - 1;
	for (int i = 0; i < n * m; i ++ ){
		if (s[i] == '1'){
			p = i;
			if (c[i % m] == 0){
				c[i % m] = 1;
				cnt ++ ;
			}
		}
		if (i - p < m) r[i % m] ++ ;
		ans[i] = r[i % m] + cnt;
	}
	for (int i = 0; i < n * m; i ++ )
		cout << ans[i] << " \n"[i == n * m - 1];
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> T;
	while (T -- )
		solve();
	return 0;
}

E. Tokitsukaze and Two Colorful Tapes

题目大意：

有 \(n\) 种不同的颜色，出现在两条彩带上，每种颜色在每条彩带上出现且只出现一次，告诉你数组 \(a\) 和 \(b\)，表示两条彩带上各个位置的颜色。现在给每种颜色赋一个值 \(x(1 <= x <= n)\)，每个值只能用一次。
这样子操作后可以得到数组 \(aa\) 和 \(bb\)，求出 \(\sum_{i = 1}^{n} \lvert aa_i - bb_i \rvert\) 的最大值。

思路：

首先，颜色之间的关系构成了一个环。
对于一个环，最后价值最大的赋值方式就是一个取最小值一个取最大值，依次赋值。
但在环的长度为奇数的情况下，最后一个值不管是什么，对答案的贡献都是一样的，所以赋一个中位数，因为剩下的大和小的数要留给后面的环使用。
可以直接模拟求解，对奇数的情况特判一下。

#include 
using namespace std;
int n, T;
void solve(){
	cin >> n;
	vector  a(n), b(n), p(n + 1), v(n + 1);
	for (int i = 0; i < n; i ++ )
		cin >> a[i];
	for (int i = 0; i < n; i ++ ){
		cin >> b[i];
		p[b[i]] = a[i];
	}
	int d = 1, u = n;
	long long ans = 0;
	for (int i = 0; i < n; i ++ ){
		if (v[b[i]]) continue;
		int t = p[b[i]], len = 1;
		while (t != b[i]){
			v[t] = 1;
			t = p[t];
			len ++ ;
		}
		if (len == 1) continue;
		vector  num;
		for (int i = 0; i < len - len % 2; i ++ ){
			if (i & 1) num.push_back(u -- );
			else num.push_back(d ++ );
			if (i > 0) ans += abs(num[i] - num[i - 1]);
		}
		ans += abs(num.back() - num[0]);
	}
	cout << ans << "\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> T;
	while (T -- )
		solve();
	return 0;
}

可以发现，其实每个环对答案的贡献就是最大值减去最小值 * 2，且其中只有 \(\lfloor \frac{len}{2} \rfloor\) 个数对答案产生了影响。（\(len\) 表示环的长度）
设 p 为 \(\sum_{i = 1}^{k} \lfloor \frac{len}{2} \rfloor\)，所有环的长度除 2 向下取整的总和。
答案就是 \(2 * p * (n - p)\)。（\(n\) 为颜色的数量）
举个例子：
样例一的第一个环的长度是 4，每个点可以依次赋值为 1, 6, 2, 5。
答案为 \((6 - 1) + (6 - 2) + (5 - 2) + (5 - 1)\)，环长度的一半为 2。
该环对答案的贡献为最大的两个值减去最小的两个值的两倍。

#include 
using namespace std;
#define LL long long
LL n, T;
void solve(){
	cin >> n;
	vector  a(n), p(n + 1), v(n + 1);
	for (int i = 0; i < n; i ++ )
		cin >> a[i];
	for (int i = 0; i < n; i ++ )
		cin >> p[a[i]];
	LL ans = 0;
	for (int i = 0; i < n; i ++ ){
		if (v[a[i]]) continue;
		int t = p[a[i]], len = 1;
		while (t != a[i]){
			v[t] = 1;
			t = p[t];
			len ++ ;
		}
		ans += len / 2;
	}
	cout << 2 * ans * (n - ans) << "\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> T;
	while (T -- )
		solve();
	return 0;
}