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

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

Easy 不要三句号的歪

简要题意

给定形如 的字符串，其中 均为正整数，求被省略的数的个数。

Solution

确定三个逗号的位置，分隔字符串求出 ，两者相减再减一就是答案。

Code

void R()
{
	i64 b,c;
	string s;
	vector<int> p;
	cin>>s;
	for (int i=0;i<s.size();i++)
		if (s[i]==',')
			p.push_back(i);
	b=stoll(s.substr(p[0]+1,p[1]-p[0]-1));
	c=stoll(s.substr(p[2]+1,s.size()-p[2]+1));
	cout<<c-b-1;
	return;
}

Medium 尼科彻斯定理

简要题意

把 拆成连续 个奇数和。

Solution

找规律题，容易发现 ，直接输出即可。

Code

void R()
{
	int n;
	cin>>n;

	auto S=[&](int n)->int
	{
		return n*(n+1)/2;
	};

	for (int i=S(n-1);i<S(n);i++)
		cout<<2*i+1<<"+\n"[i+1==S(n)];
	return;
}

Hard 隐匿社交网络

简要题意

给定 个数，若两个数的 bitwise AND 不为 就将它们分进同一组，求最大组内数的个数。

Solution

用并查集维护元素与组的关系，额外开 个不占 siz 的节点代表二进制位，答案就是最大集的 siz。

Code

struct DSU
{
	int n=0;
	vector<int> fa,siz;

	DSU(int n) { init(n); }

	void init(int n)
	{
		fa.resize(n);
		iota(fa.begin(),fa.end(),0);
		siz.assign(n,1);
	}

	int get(int x) { return fa[x]==x?x:fa[x]=get(fa[x]); }

	void merge(int x,int y)
	{
		x=get(x),y=get(y);
		if (x==y) return;
		if (siz[x]<siz[y]) swap(x,y);
		fa[y]=x,siz[x]+=siz[y];
	}
};

void R()
{
	int n,ans=0;
	cin>>n;
	DSU dsu(n+60);
	for (int i=0;i<60;i++)
		dsu.siz[n+i]=0;
	for (int i=0;i<n;i++)
	{
		i64 x;
		cin>>x;
		for (int j=0;j<60;j++)
			if (x>>j&1)
				dsu.merge(i,n+j);
	}
	for (int i=0;i<60;i++)
		ans=max(ans,dsu.siz[dsu.get(i)]);
	cout<<ans<<'\n';
	return;
}