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

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

Easy 求int型正整数在内存中存储时1的个数

简要题意

求一个整数在二进制表示下 的个数。

Solution

事实上 C++ 的内置函数 __builtin_popcount() 函数实现了这个功能，效率优于模拟。

Code

void R()
{
	int n;
	cin>>n;
	cout<<__builtin_popcount(n);
	return;
}

Medium 整数与IP地址间的转换

简要题意

给一个 IP 地址，将其转为长整数；

给一个长整数，将其转为 IP 地址。

Solution

问题等价于 进制与 进制的互转，简单模拟即可。

stoi(),to_string() 分别能实现字符串转数字，数字转字符串。

Code

void R()
{
	i64 ans1=0,x;
	string s,ans2;
	cin>>s>>x;

	int lst=0;
	for (int i=0;i<=s.size();i++)
		if (s[i]=='.'||i==s.size())
		{
			ans1<<=8;
			ans1+=stoi(s.substr(lst,i-lst));
			lst=i+1;
		}

	for (int i=3;i>=0;i--)
	{
		ans2+=to_string(x>>i*8);
		if (i) ans2+='.';
		x%=1<<i*8;
	}

	cout<<ans1<<'\n'<<ans2;
	return;
}

Hard 字符串通配符

简要题意

有两种通配符：* 和 ?，前者能配任意一个字符串（包括空串），后者能配任意数字/字母。

给定一个含通配符的串 和一个不含通配符的串 ，问两者能否匹配。

Solution

因为不区分大小写，先把所有字母统一处理成小写/大写。

因为匹配的过程是无后效的，所以不难想到动态规划：

设 表示 的前缀 可以匹配到 的前缀 。

外层枚举 ，考虑 可以转移到哪：

• 是 *，我们让它再配一位，转移到 ；

• 与 匹配，转移到 ；

特别地，因为 * 可以不配，所以还有转移：

• 为 * 时， 可以转移到 。

事实上 对转移的影响不大，可以滚动数组，但是要注意代码细节。

Code

void R()
{
	string s,t;
	cin>>s>>t;
	for (char &c:s)
		if (c>='A'&&c<='Z')
			c+=32;
	for (char &c:t)
		if (c>='A'&&c<='Z')
			c+=32;
	s='A'+s;

	int n=s.size(),m=t.size();
	vector<int> dp(n);
	dp[0]=1;
	for (int i=0;i+1<n;i++)
		if (dp[i]&&s[i+1]=='*')
			dp[i+1]=1;

	for (char c:t)
	{
		vector<int> ndp(n);
		for (int i=0;i<n;i++)
		{
			if (dp[i])
			{
				if (s[i]=='*') ndp[i]=1;
				if (i+1<n&&(s[i+1]=='*'||(s[i+1]=='?'&&(isdigit(c)||(c>='a'&&c<='z')))||s[i+1]==c))
					ndp[i+1]=1;
			}
			if (i+1<n&&ndp[i]&&s[i+1]=='*')
				ndp[i+1]=1;
		}
		swap(dp,ndp);
	}

	if (dp[n-1]) cout<<"true\n";
	else cout<<"false\n";
	return;
}