A. T-shirt

前 $A$ 名一定获得衣服，在 $[A+1, B]$ 之间的人将随机挑 $C$ 个人获得衣服。

若已知他排名于 $X$，求其获得衣服的概率。

分析

int main() {
	int A, B, C, X;
	cin >> A >> B >> C >> X;
	double ans = 0;
	if (X <= A) {
		ans = 1;
	} else if (X <= B && A != B) {
		ans = 1.0 * C / (B - A);
	}
	printf("%.12lf", ans);
	return 0;
}

全部代码请看：Atcoder/ABC242/ABC242A.cpp。

B. Minimize Ordering

给定一个字符串 $S$，请找到 $S$ 的重排 $S’$，并且使其字典序尽可能小。

分析

int main() {
	string s;
	cin >> s;
	std::sort(s.begin(), s.end());
	cout << s;
	return 0;
}

全部代码请看：Atcoder/ABC242/ABC242B.cpp。

C. 1111gal password

相邻数字差为 $1$ 且有 $N$ 位的数字有多少个。

分析

const int P = 998244353;

int main() {
	int n;
	cin >> n;
	vector<int> v1(10, 1), v2(10);
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < 9; j++) {
			v2[j] = ((v1[j - 1] + v1[j]) % P + v1[j + 1]) % P;
		}
		v2[0] = v1[1], v2[9] = v1[8];
		v1 = v2;
	}
	int sum = 0;
	for (int i = 0; i < 9; i++) {
		sum = (sum + v1[i]) % P;
	}
	cout << sum;
	return 0;
}

全部代码请看：Atcoder/ABC242/ABC242C.cpp。

D. ABC Transform

给定包含 ABC 的字符串 $S$，可以对字符串做如下变换：

  • A->BC，B->CA，C->AB。

多次询问，回答经过 $t_i$ 次变换后第 $k_i$ 个字符。

分析

注意到一个字符经过变换后会变成两个字符，是类似二叉树的东西。

因此我们可以沿着树向上走，而且每向上走一层，长度就少一半，故很快就到 $0$。

似乎有更快的位运算做法，有空再回来看看吧。

int main() {
	string s;
	int Q;
	cin >> s >> Q;
	std::function<ll(ll, ll)> get = [&](ll pos, ll t) -> ll {
		if (t == 0) {
			return s[pos] - 'A';
		} else if (pos == 0) {
			return (s[0] - 'A' + t) % 3;
		} else if (pos % 2 == 0) {
			return get(pos / 2, t - 1) + 1;
		} else {
			return get(pos / 2, t - 1) + 2;
		}
	};
	while (Q--) {
		ll ti, ki;
		cin >> ti >> ki;
		cout << char(get(ki - 1, ti) % 3 + 'A') << "\n";
	}
	return 0;
}

全部代码请看：Atcoder/ABC242/ABC242D.cpp。

E. (∀x∀)

给定一个长为 $N$ 的字符串 $S$，计算满足下列条件的字符串数量：

  • $X$ 是一个长为 $N$ 的回文串。
  • 在字典序下有 $X \leqslant S$。

分析

类似于数位 DP，考虑第 $i$ 位如果满足 $X_i < S_i$，那么中间几位可以随便放。

最后，如果存在的话，注意特判中间一位，和其他特殊情况。

const int N = 1E6, P = 998244353;

int main() {
	vector<int> pw(N);
	pw[0] = 1;
	for (int i = 1; i < N; i++) {
		pw[i] = 1ll * pw[i - 1] * 26 % P;
	}
	int T;
	cin >> T;
	while (T--) {
		int n;
		string s;
		cin >> n >> s;
		ll sum = 0;
		int mid = n / 2;
		for (int i = 0; i < mid; i++) {
			sum += 1ll * pw[n - mid - i - 1] * (s[i] - 'A') % P;
		}
		if (n % 2 == 1) {
			sum += s[mid] - 'A';
		}
		string s2(s.begin() + (n - mid), s.end());
		string s3(s.begin(), s.begin() + mid);
		std::reverse(s3.begin(), s3.end());
		if (s3 <= s2)
			sum++;
		cout << sum % P << "\n";
	}
	return 0;
}

全部代码请看：Atcoder/ABC242/ABC242E.cpp。