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

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

Easy 【模板】队列

简要题意

要求实现队列支持的操作。

Solution

队列，即先进先出 (FIFO) 表。支持 插入， 弹出。

STL 中的 queue 实现了队列的功能。

Code

void R()
{
	int n;
	cin>>n;
	queue<int> q;
	while (n--)
	{
		string op;
		cin>>op;
		if (op=="push")
		{
			int x;
			cin>>x;
			q.push(x);
		}
		else
		{
			if (q.empty()) cout<<"error\n";
			else
			{
				cout<<q.front()<<'\n';
				if (op=="pop") q.pop();
			}
		}
	}
	return;
}

Medium 【模板】循环队列

简要题意

要求实现循环队列支持的操作。

Solution

其实循环队列是一种在弹出频繁时限制空间消耗为队列长度上界的实现方式，但是 queue 本身就有这方面的优化，我们对其加一个 size 的判断即可。

Code

void R()
{
	int n,Q;
	cin>>n>>Q;
	queue<int> q;
	while (Q--)
	{
		string op;
		cin>>op;
		if (op=="push")
		{
			int x;
			cin>>x;
			if (q.size()==n) cout<<"full\n";
			else q.push(x);
		}
		else
		{
			if (q.empty()) cout<<"empty\n";
			else
			{
				cout<<q.front()<<'\n';
				if (op=="pop") q.pop();
			}
		}
	}
	return;
}

Hard 合并回文子串

简要题意

给定两个字符串 ，对其在不破坏内部相对顺序的前提下组合成的新字符串，求其最长回文子串的最大长度。

Solution

设 表示使用 能否组合成为回文串，有转移：

对 的 取 max 即为答案。

显然上面的 dp 过程也可以采用 BFS 转移。

Code

void R()
{
	string a,b;
	cin>>a>>b;
	int n=a.size(),m=b.size();
	queue<tuple<int,int,int,int>> q;
	vector<vector<vector<vector<int>>>> dp(n+1,vector<vector<vector<int>>>(n+1,vector<vector<int>>(m+1,vector<int>(m+1))));
	for (int i=0;i<=n;i++)
		for (int j=0;j<=m;j++)
		{
			dp[i][i][j][j]=1;
			q.push({i,i,j,j});
			if (i<n)
			{
				dp[i][i+1][j][j]=1;
				q.push({i,i+1,j,j});
			}
			if (j<m)
			{
				dp[i][i][j][j+1]=1;
				q.push({i,i,j,j+1});
			}
		}

	int ans=0;
	while (!q.empty())
	{
		auto [l1,r1,l2,r2]=q.front();
		q.pop();
		ans=max(ans,r1-l1+r2-l2);
		if (l1&&r1+1<=n&&a[l1-1]==a[r1]&&!dp[l1-1][r1+1][l2][r2])
			dp[l1-1][r1+1][l2][r2]=1,q.push({l1-1,r1+1,l2,r2});
		if (l1&&r2+1<=m&&a[l1-1]==b[r2]&&!dp[l1-1][r1][l2][r2+1])
			dp[l1-1][r1][l2][r2+1]=1,q.push({l1-1,r1,l2,r2+1});
		if (l2&&r1+1<=n&&b[l2-1]==a[r1]&&!dp[l1][r1+1][l2-1][r2])
			dp[l1][r1+1][l2-1][r2]=1,q.push({l1,r1+1,l2-1,r2});
		if (l2&&r2+1<=m&&b[l2-1]==b[r2]&&!dp[l1][r1][l2-1][r2+1])
			dp[l1][r1][l2-1][r2+1]=1,q.push({l1,r1,l2-1,r2+1});
	}
	cout<<ans<<'\n';
	return;
}