专栏文章

P11455 [USACO24DEC] Cowdepenence G

IIamZZ
P11455题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miqnl09e
此快照首次捕获于
2025/12/04 07:43
3 个月前
此快照最后确认于
2025/12/04 07:43
3 个月前
查看原文
G 组练习总结#14
Platinum 组开题，三道 Benq，两眼一黑，不省人事。
那就来研究 Gold 组吧。

题目大意

FJ 的奶牛们正在交朋友，她们希望组成一个个小组促进感情。
具体来说，FJ 拥有 N(N≤105)N(N\le 10^5) 个奶棚，i(i≤N)i(i\le N) 号奶棚里有一只品种为 ai(ai≤N)a_i(a_i\le N) 的奶牛，两个奶棚的距离为编号相减。
奶牛很高傲，只愿意和自己品种相同的奶牛做朋友，同时，为了方便交流，朋友之间的距离不能太远（可能取决于奶牛的嗓门大小吧）。
为了方便管理，FJ 规定奶牛们应组成尽可能少的小组。
现在，他想知道，对于每一个最大交流距离 x(1≤x≤N)x(1\le x\le N)，最少需要分多少个小组？

解题思路

我们首先可以想一些题目的性质，一个小组必定在一段长度小于交流距离的区间里，否则不优。
其次，当我们确定了左端点时，右端点肯定是尽可能大，尽量涵盖更多奶牛。
如果一头奶牛已经超出了左端点的交流范围，新开一组。

暴力

有了这上面的性质，我们可以写出最基础的暴力了，枚举交流距离，扫一遍所有奶牛，超出范围就新开一组，时间复杂度 Θ(N2)\Theta(N^2)。
这道题目的另外两个部分分很有引导性，解决它们对得出正解有很大帮助。

Subtask 1：品种数量不超过 10

既然，品种数量这么少，我们可以考虑对每一个品种单独处理。
思考一下，如果当前的交流距离为 xx，这个品种的奶牛分组数量不可能大于 ⌈Nx⌉\lceil\frac{N}{x}\rceil 个，因为塞不下更多长度为 xx 的区间了。
我们找到第一个左端点编号 pospos，然后在 pos+xpos+x 之后找到下一个最近的，设为第二个左端点，同时组数加一。
因为分组数量有上限，这种跳跃的操作不会超过 ⌈Nx⌉\lceil\frac{N}{x}\rceil 次。
根据调和级数 ∑x=1NNx≈Nln⁡N\sum_{x=1}^N\frac{N}{x}\approx N\ln N，外加一个 1010 （取决于品种数）的常数，复杂度 Θ(Nln⁡N)\Theta(N\ln N)。
跳跃操作可以通过记录数组 ee 完成，eie_i 表示 ii 之后最近的这种品种奶牛的编号。

Subtask 2：每个品种的奶牛数量不超过 10

仔细思考，奶牛数量上的限制，同时也限制了什么？
是的，因为每一个小组至少得有一头奶牛吧，小组的数量同时也被限制了。
那我们就可以依据小组的数量来处理答案。
假设我们要求某个品种的奶牛分为 vv 组。我们找到满足奶牛被分成了 vv 组的最大的交流距离，记这个距离为 gvg_v（用二分）。
我们发现，随着 vv 的不断增大，gvg_v 是不断减小的（理解为越分越细），而在 [gv+1+1,gv][g_{v+1}+1,g_v] 之间的距离都能用 vv 组分配。
我们用一个前缀和，是不是就可以解决每个距离的答案了？时间复杂度 Θ(Nlog⁡2N)\Theta(N\log_2N)，带一个 1010 （取决于每组数量）的常数。
解决了两个部分分，有没有发现，问题是不是已经解决了？
如果将每个品种奶牛数量分开处理，≤N\le\sqrt N 的用 Subtask 2 方法，反之用 Subtask 1 方法。
我们发现，因为每个品种数量 ≤N\le\sqrt N，每种奶牛的数量得到了限制，而我们只需要 Θ(NNlog⁡2N)\Theta(N\sqrt N \log_2N) 的复杂度来处理第一部分。
而对于 >N>\sqrt N 的品种，这些品种的个数不会超过 N\sqrt N，我们也可以在 Θ(NNln⁡N)\Theta(N\sqrt N\ln N) 的复杂度内处理第二部分。
综上，我们可以在 Θ(NNlog⁡2N)\Theta(N\sqrt N\log_2 N) 的时间复杂度内处理这个问题。
完结撒花(●'◡'●)！

参考代码

C
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,Z=300;
int n,a[N],c[N],e[N],t,o[Z],k,m[N],pos,s,ed[N],to[N],ct[N],sp[N];
int find(int v,int id)//找到最大交流距离g[v]
{
	int l=0,r=sp[v-1],d,x,i,ls,g,ans;//递减的答案，缩小二分范围
    //l可以为0，有些品种的分组有上限，挨太近了
	while(l<=r)
	{
		d=l+r>>1;
		x=to[id],ls=-1e9,g=0;
		for(i=1;i<=c[id];++i)//好比暴力部分，超了范围就开新组
		{
			if(x-ls>d)
			  ++g,ls=x;//更新左端点
			x=ed[x];//同种的下一只奶牛
		}
		if(g>=v)
		  ans=d,l=d+1;
		else
		  r=d-1;
	}
	return ans;
}
void init(int id)//初始化e数组
{
	int i;
	t=n+1;
	for(i=n;i;--i)
	{
		e[i]=t;
		if(a[i]==o[id])
		  t=i;
	}
	return ;
}
int main()
{
	int i,j;
	scanf("%d",&n),sp[0]=n;
	for(i=1;i<=n;++i)
	  scanf("%d",a+i),++c[a[i]];//统计每种奶牛数量
	for(i=1;i<=n;++i)
	{
		if(c[i]>Z)//分类
		  ++k,o[k]=i;
		to[i]=n+1;
	}
	for(j=1;j<=k;++j)
	{
		init(j);//初始化
		for(i=1;i<=n;++i)
		{
			pos=t,s=0;
			while(pos<=n)
			{
				++s;//开新组
				if(pos+i+1>n)
				  break;
				pos=e[pos+i];//i个i个跳跃
			}
			m[i]=m[i]+s;//统计第一部分答案
		}
	}
	for(i=n;i;--i)
	  ed[i]=to[a[i]],to[a[i]]=i;//找到同种的下一只奶牛
	for(i=1;i<=n;++i)
	{
		if(c[i]>Z)
		  continue;
		for(j=1;j<=c[i];++j)
		  ++ct[sp[j]=find(j,i)];//前缀和统计第二部分答案
	}
	s=0;
	for(i=n;i;--i)
	   s=s+ct[i],m[i]=m[i]+s;//前缀和转答案
	for(i=1;i<=n;++i)
	  printf("%d\n",m[i]);
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...