AtCoder Beginner Contest 242

A T-shirt

题意

排名在 \(A\) 及以上的参赛选手，一定能获得一件 T 恤，排名在 \([A+1,B]\) 的选手，其中的 \(C ( 1 \leq C \leq B-A)\) 个参赛选手等概率获得一件 T 恤，求排名为 \(x\) 的参赛选手，能获得 T 恤的概率。

数据满足：\(1 \leq A,B,C,x \leq 1000\)。

题解

• 判断 \(x \leq A\)，则必然获得一件T恤，输出 \(1\)。
• 判断 \(A + 1 \leq x \leq B\)，由于其中的 \(C\) 个人等概率获得T恤，因此其中一个人获得T恤的概率为\(\frac{C}{B-A}\)。
• 判断\(x \geq B+1\)，则不可能获得一件T恤，输出\(0\)。

时间复杂度\(O(1)\)。

C++代码实现

# include <bits/stdc++.h>
using namespace std;
int main() {
	int a,b,c,x; cin>>a>>b>>c>>x;
	if (x<=a) puts("1");
	else if (x>=a+1&&x<=b){
		double ans = c/(double)(b-a);
		printf("%.10lf\n",ans);
	}else puts("0");
	return 0;
}

B Minimize Ordering

题意

长度为 \(n\) 的字符串 \(s\)，求出重排所有字符后，能获得字典序最小的字符串\(s'\)。

数据满足：\(1 \leq n \leq 2\times 10^5\)。

题解

把字符串看做字符数组，重排字符让字典序最小，等价于将这个字符数组排序。

时间复杂度\(O(n \log_2 n)\)。

C++代码实现

# include <bits/stdc++.h>
using namespace std;
int main() {
	string s; cin>>s;
	sort(s.begin(),s.end());
	cout<<s<<endl;
	return 0;
}

C 1111gal password

题意

求出 \(n\) 位十进制数的个数，满足每个数位上的数字在\([1,9]\)，且相邻数位相差的绝对值不超过\(1\)，答案对 \(998244353\) 取模。
数据满足：\(2 \leq n \leq 10^6\)。

题解

考虑数位DP，由于不存在前导零，这个问题就变的更加简单了。

设 \(f[i][j]\) 表示考虑到前 \(i\) 个数位，第 \(i\) 个数位上填写的数字为 \(j\) 的数的个数。

• 转移方程：\(f[i][j] = f[i-1][k])\) 其中 \(\max(1,j-1)\leq k \leq \min(n,j+1)\)。

时间复杂度\(O(kn)\)，这里\(k = 9\)。

C++代码实现

# include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int mo = 998244353;
int f[N][10];
int main() {
	int n; cin>>n;
	for (int i=1;i<=9;i++) f[1][i]=1;
	for (int i=2;i<=n;i++)
		for (int j=1;j<=9;j++)
			for (int k=j-1;k<=j+1;k++) {
				if (k<1||k>9) continue;
				(f[i][j]+=f[i-1][k])%=mo;
			}
	int ans = 0;
	for (int i=1;i<=9;i++) (ans+=f[n][i])%=mo;
	cout<<ans<<endl;		
	return 0;
}

D ABC Transform

题意

给出一个只包含ABC三种字符的字符串\(s\) (下标从 \(1\) 开始)，做 \(k\) 次如下变换，记作\(s^{(k)}\)。

• 对于\(k = 0\)，变换后结果为 \(s\) 本身。
• 对于\(k \geq 1\)，变换后结果为字符串 \(s^{(k-1)}\) 中A替换为BC，B替换为CA，C替换为AB后新生成字符串的值。

有 \(Q\) 组询问，每组询问用 \(t_i \ k_i\) 表示，求出 \(s^{(t_i)}[k_i]\) 的值。
数据满足：\(2 \leq |s|,Q \leq 10^5,0 \leq t_i \leq 10^{18} ,1 \leq k_i \leq \min(10^{18},|s^{(t_i)}|)\)。

题解

首先发现的一个性质是：每多进行 \(1\) 次操作，字符串的长度会加倍。

因此，如果我们依次写出进行 \(1...t\) 次变换的所有所有变化的话，可以发现，这些变化形成了 \(n\) 棵以原字符串的 \(n\) 个位置为根节点，深度为 \(t\) 的完全二叉树（根节点深度为 \(0\)。

每个根节点都对应一段最后生成字符串中的一个长度为 \(2^t\) 的连续区间（叶节点），因此给出一个 \(k\) 我们可以在\(O(\log_2 n)\)的时间复杂度内，定位编号为 \(k\) 的这个叶节点是哪个根节点派生的。

这样，问题就转化到一棵完全二叉树上了。

如果把一棵完全二叉树每层的节点从左往右从 \(1\) 开始依次编号，那么如果一个非根节点的编号为 \(x\):

• \(x\) 为奇数，那么该节点是从上层节点的左儿子。
• \(x\) 为偶数，那么该节点是从上层节点的右儿子。
• \(x\) 的父节点编号为 \(\lfloor \frac{x-1}{2} \rfloor + 1\)。

考虑从编号为 \(k\) 的这个叶子节点往上去寻找从根节点的唯一路径，这条路径就可以推出当前叶子节点的答案。
模拟上述过程，可以发现，\(k\)的规模每次减少一半，\(\log_2 k\)次计算后，必然为\(1\)。
这意味着，由于 \(k\) 的规模的限制，在开始的很长一段时间内，都是往左子树走的。

然后我们发现，往左子树连续走 \(3\) 次是没有意义的，因为会重新回到根节点的值，这样每次计算的规模就被我们简化到 \(3 + \log_2 k\) 次了，这样直接模拟就可以了。

时间复杂度为\(O(|s| + Q\log_2 k)\)。

C++代码实现

# include <bits/stdc++.h>
# define int long long
using namespace std;
inline char getleft(char x) {
	return (x-'A'+1)%3+'A';
}
inline char getright(char x) {
	return (x-'A'+2)%3+'A';
}
signed main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	string s; cin>>s;
	int q; cin>>q;
	while (q--) {
		int t,k; cin>>t>>k;
		int id;
		if (t>=60) id=0;
		else {
			int left=1,right=(1ll<<t),x=0;
			while (true) {
				if (k>=left && k<=right) {
					id=x; k=k-left+1; break;
				}
				x++; left+=(1ll<<t); right+=(1ll<<t);
			}
		}
		int tm = 0;
		char now = s[id];
		for (int i=1;i<=t;i++) {
			if (k == 1) { tm = t-i+1; break;}
			if (k&1) now=getleft(now);
			else now = getright(now);
			k=(k-1)/2+1;
		}
		tm%=3;
		for (int i=1;i<=tm;i++) now=getleft(now);
		cout<<now<<'\n';
	}
	return 0;
}

E (∀x∀)

题意

\(T\) 组数据，每组数据给出一个字符串\(s\)，求出字典序比 \(s\) 小且长度为 \(|s|\) 的回文串个数，答案对 \(998244353\) 取模。
数据满足：\(1 \leq T \leq 250000,1 \leq \sum |s| \leq 10^6\)。

题解