牛客春招刷题训练营 - 2025.3.19 题解

活动地址：牛客春招刷题训练营 - 编程打卡活动

Easy 简单密码

简要题意

给一个含大小写字母及数字的字符串。

将小写字母改为对应九键上的数字，大写字母改为循环右移一位的小写。

Solution

直接模拟修改即可。

注意到前几键都代表三个字母，所以用等差性质简化了一下代码。

Code

void R()
{
	string s;
	cin>>s;
	for (char &c:s)
		if (!isdigit(c))
		{
			if (c>='A'&&c<='Z')
				c=(c-'A'+1)%26+'a';
			else if (c<='r')
				c=(c-'a')/3+2+'0';
			else if (c<'t')
				c='7';
			else if (c<'w')
				c='8';
			else c='9';
		}
	cout<<s;
	return;
}

Medium 蛇形矩阵

简要题意

输出规模为 的满足下面规律的上三角矩阵。

Solution

不难注意到每行都是一个二阶等差数列，第一列是 ，枚举输出即可。

Code

void R()
{
	int n;
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		int t=i*(i-1)/2+1;
		cout<<t<<" \n"[i==n];
		for (int j=i+1;j<=n;j++)
		{
			t+=j;
			cout<<t<<" \n"[j==n];
		}
	}
	return;
}

Hard 火车进站

简要题意

个元素以某个顺序入栈，中间出栈时机不定。

求所有使元素全部出栈的合法出栈序列，要求按字典序输出。

Solution

事实上方案数就是 Catalan Number，但这里不需要用到。

用 0 表示入栈，1 表示出栈。 个 0 与 个 1 的全排列一定覆盖了所有答案。

用 next_permutation() 枚举全排列，模拟判断当前排列是否合法，并将出栈序列存到一个 vector 里，枚举完 sort() 一下就能输出了。

时间复杂度是跟答案规模同阶的，肯定不会超时。

Code

void R()
{
	int n;
	cin>>n;
	vector<int> tmp(2*n),a(n);
	vector<vector<int>> ans;
	for (int &x:a) cin>>x;
	for (int i=n;i<2*n;i++) tmp[i]=1;
	do
	{
		int now=0;
		vector<int> stk,ord;
		for (int x:tmp)
			if (x)
			{
				if (stk.empty()) goto ed;
				else
				{
					ord.push_back(stk.back());
					stk.pop_back();
				}
			}
			else stk.push_back(a[now++]);
		ans.push_back(ord);
		ed:;
	} while (next_permutation(tmp.begin(),tmp.end()));

	sort(ans.begin(),ans.end());
	for (auto &v:ans)
		for (int i=0;i<n;i++)
			cout<<v[i]<<" \n"[i+1==n];
	return;
}