P2351 [SDOi2012]吊灯

https://www.luogu.org/problemnew/show/P2351

题意：
　　一棵树，能否全部分成大小为x的联通块。

分析：
　　显然x是n的约数。然后对于一个约数x，判断能否分成 $ \frac{n}{x} $ 个大小为x的联通块。

　　结论：如果x可以，那么一定存在$ \frac{n}{x} $个节点的子树大小是x的倍数。

　　证明：上面的结论说明的也就是每个大小是x的倍数的点，对答案的贡献是1（每个点都可以分出一个大小为x的块），加起来就是$ \frac{n}{x} $。

　　现在就要考虑一个点u的siz是kx，然后它的子树里如果没有其他点的siz的是x的倍数的话，它的贡献是1，它可以从根节点开始，分出一个包含根节点，一共x个点的联通块。

　　然后考虑u的子树里还有一个点v的siz是x的倍数，那么如果它们还能分成两个大小为x的块的话，那么每个这样的点的贡献还是1。首先从在v的子树里一定可以从根开始分出一个大小为x的块（u在其中），然后u的子树里需要找一个大小为x的块，且不使用v中的点。假设去掉v中的点还剩siz[u]-siz[v]个，这也是x的倍数，所以u的子树里，从根开始，不占用v的点，还可以分出一个大小为x的块。说明u的子树可以贡献2，uv各自贡献1。

　　如果u的子树还有这样的点，那么把v删掉，还是两个点的情况，所以还是合法的。

　　到此发现每个大小为x的倍数的点，会对答案贡献1。$ \frac{n}{x} $$个，就会有$ \frac{n}{x} $个大小为x的联通块，如果小于则不行。

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 #include<set>

 #include<vector>

 #include<queue>

 #include<map>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 int fa[N], cnt[N], siz[N], n;

 vector<int> v;

 bool check(int x) {

     int res = ;

     for (int i=x; i<=n; i+=x) res += cnt[i];

     return res >= n / x;

 }

 int main() {

     n = read();

     for (int lim=sqrt(n),i=; i<=lim; ++i) {

         if (n % i == ) {

             v.push_back(i);

             if (n / i != i) v.push_back(n / i);

         }

     }

     sort(v.begin(), v.end());

     for (int i=; i<=n; ++i)

         fa[i] = read();

     for (int T=; T<=; ++T) {

         printf("Case #%d:\n",T);

         for (int i=; i<=n; ++i) cnt[i] = , siz[i] = ;

         for (int i=n; i>=; --i) siz[fa[i]] += siz[i], cnt[siz[i]] ++;

         for (int i=; i<v.size(); ++i)

             if (check(v[i])) printf("%d\n",v[i]);

         if (T != ) for (int i=; i<=n; ++i)

             fa[i] = (fa[i] + ) % (i - ) + ;

     }

     return ;

 }

巴特西

P2351 [SDOi2012]吊灯

P2351 [SDOi2012]吊灯

最新文章

热门文章