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

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

Easy a的翻转

简要题意

对十进制数 翻转数位得到 ，求 。

Solution

简单模拟即可。

Code

void R()
{
	int a,b=0;
	cin>>a;
	for (int t=a;t;t/=10)
		b=b*10+t%10;
	cout<<a+b<<'\n';
	return;
}

Medium 斐波那契数列

简要题意

求斐波那契数列第 项。

Solution

递推式为 ，直接递推即可。

Code

void R()
{
	int n,lst=0,now=1;
	cin>>n;
	while (n--)
	{
		swap(lst,now);
		now+=lst;
	}
	cout<<lst<<'\n';
	return;
}

Hard 括号区间匹配

简要题意

给一个仅包含 (,),[,] 的字符串，求插入多少个括号能使该括号串合法配对。

Solution

设 表示使子串 合法配对的最小代价，有转移：

即为答案。

Code

void R()
{
	constexpr int inf=1e9;
	string s;
	cin>>s;
	int n=s.size();
	vector<vector<int>> dp(n,vector<int>(n,inf));

	auto match=[&](char a,char b)->bool
	{
		return (a=='('&&b==')')||(a=='['&&b==']');
	};

	auto dfs=[&](auto &self,int l,int r)->int
	{
		if (l>r) return 0;
		if (dp[l][r]!=inf) return dp[l][r];
		if (l==r) return dp[l][r]=1;
		dp[l][r]=min(dp[l][r],self(self,l+1,r-1)+(!match(s[l],s[r]))*2);
		dp[l][r]=min(dp[l][r],self(self,l+1,r)+1);
		dp[l][r]=min(dp[l][r],self(self,l,r-1)+1);
		for (int k=l;k<r;k++)
			dp[l][r]=min(dp[l][r],self(self,l,k)+self(self,k+1,r));
		return dp[l][r];
	};

	cout<<dfs(dfs,0,n-1)<<'\n';
	return;
}