现在的位置: 首页 > 算法 > 正文

【bzoj 3004】: 吊灯

2017年04月21日 算法 ⁄ 共 1840字 ⁄ 字号 评论关闭

http://www.lydsy.com/JudgeOnline/problem.php?id=3004


合法的方案一定是n的一个约数。首先穷举n的约数m。对于一个结点,假设可以统计出所有子树中未分组的结点个数,设未分组的结点个数加上它自身的值为k,那么:

1、 若k>m,那么这个方案一定不可行;

2、 若k=m,那么这个结点一定是与这些未分组的点分在一起;

3、 若k<m,则不进行操作;

设size[u]是包括u的所有子树的结点个数,那么我们可以推出, m是一个可行方案的充要条件是size[u] % m == 0的结点数量为 n/m。

首先,显然不可能存在一个m是合法方案,并且size[u]%m==0的结点数量大于n/m,因此只可能是小于等于n/m,下面证明不可能小于n/m。

假设存在小于n/m个结点,这每一个结点都对应了一个划分好的连通块,那么必然有一个连通块的结点数大于m,否则就不满足总结点数为n,与条件矛盾。

因此,m是一个可行方案的充要条件是size[u]%m==0的结点数量为 n/m。

整个算法的复杂度的上限为O(NloglogN)。

如果换种方式枚举约数,算法的时间复杂度还可以再优化一点,懒得写了,还要sort

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=(l),___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=(r),___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int read()
{int r=0,k=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;}
/////////////////////////////////////////////////
int n;
int fa[1200010];
int sz[1200010];
int c[1200010];
/////////////////////////////////////////////////
inline bool check(int k)
{
	int cnt=0;
    for(int i=k;i<=n;i+=k) cnt+=c[i];
    return cnt>=n/k;
}
/////////////////////////////////////////////////
void input()
{
    
}
void solve()
{
	n=read();
	rep(i,2,n) fa[i]=read();
	rep(T,1,10)
	{
		MS(c,0); MS(sz,0);
		per(i,n,1)
		{
			sz[i]++;
			sz[fa[i]]+=sz[i];
			c[sz[i]]++;
		}
		printf("Case #%d:\n",T);
		rep(i,1,n) if(n%i==0)
		{
			if(check(i)) printf("%d\n",i);
		}
		rep(i,2,n)
		{
			fa[i]+=19940105;
			fa[i]=fa[i]%(i-1)+1;
		}
	}
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    input(),solve();
    return 0;
}

抱歉!评论已关闭.