C/C++教程

AtCoder Beginner Contest 242

本文主要是介绍AtCoder Beginner Contest 242,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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替换为BCB替换为CAC替换为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\)。

题解

这篇关于AtCoder Beginner Contest 242的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!