后悔没把 D 写快点。

A. A ↔ BB

给定一个长为 $N$ 的仅包含 ABC 的字符串 $S$。可以做以下两种操作

  • 把 A 替换为 BB
  • 把 BB 替换为 A

求操作后 $S$ 的字典序最小是多少。

分析

我赛时是想到 BA 可以变为 AB，从而降低字典序。

int main() {
	int N;
	string s;
	cin >> N >> s;
	for (int i = 0; i < s.size() - 1; i++) {
		if (s[i] == 'B' && s[i + 1] == 'B') {
			s[i] = 'A';
			s.erase(s.begin() + i + 1);
		}
		if (s[i] == 'B' && s[i + 1] == 'A') {
			swap(s[i], s[i + 1]);
		}
	}
	cout << s;
	return 0;
}

全部代码请看：Atcoder/ARC136/ARC136A.cpp。

现在想来，先进行操作 1 再进行操作 2 足以。

input()
s = input()
print(s.replace('A','BB').replace('BB','A'))

B. Triple Shift

给定两个长为 $N$ 的排列 $A,B$，每一次操作可以选择 $A_{i},A_{i+1},A_{i+2}$ 变成 $A_{i+2}, A_{i}, A_{i+1}$。

是否存在操作方法能够把 $A$ 变成 $B$。

分析

第一想法就是观察到操作操作不改变逆序数的奇偶性，判断奇偶性是否相同即可。

而且若序列中有相同的数，那么其奇偶性可以被任意的指定。

至于具体为什么，我不会证。

int inver(const vector<int> &v) {
	int ans = 0, n = v.size();
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			ans += v[i] > v[j];
		}
	}
	return ans;
}

int main() {
	int N;
	cin >> N;
	vector<int> A(N), B(N);
	for (auto &ai : A)
		cin >> ai;
	for (auto &bi : B)
		cin >> bi;
	int ivA = inver(A), ivB = inver(B);
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	if (A == B) {
		bool same = false;
		for (int i = 0; i < N - 1; i++)
			same = same || A[i] == A[i + 1];
		if (same || (ivA + ivB) % 2 == 0)
			cout << "Yes";
		else
			cout << "No";
	} else {
		cout << "No";
	}
	return 0;
}

全部代码请看：Atcoder/ARC136/ARC136B.cpp。

D. Without Carry

给定一个 $N$ 个数的序列，求使得 $A_i+A_j$ 不发生进位的二元对个数 $(i,j)$，且 $1 \leqslant i < j \leqslant N$。

分析

我赛中写了一个六维 DP，调起来很费劲，赛后才发现写难了。

我的六维 DP 的定义是小于 DP 位的数的个数，就是个六维前缀和。我想办法用 6 维容斥转移，勉强能过。

实际上 6 维前缀和容斥转移需要 $2^6=64$ 个数参与计算，用刷表可以只用 $6$ 次。

const int M = 1E6;

bool check(int x) {
	while (x) {
		if (x % 10 >= 5)
			return false;
		x /= 10;
	}
	return true;
}

int main() {
	int N;
	cin >> N;
	vector<int> a(N), dp(M);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		dp[a[i]]++;
	}

	for (int k = 1; k < M; k *= 10) {
		for (int i = 0; i < M; i += k * 10) {
			for (int j = 0; j < k * 9; j++) {
				dp[i + j + k] += dp[i + j];
			}
		}
	}

	ll ans = 0;
	for (int i = 0; i < N; i++) {
		ans += dp[M - 1 - a[i]] - check(a[i]);
	}
	cout << ans / 2;

	return 0;
}

全部代码请看：Atcoder/ARC136/ARC136D.cpp。