欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ3004: 吊灯(结论 毒瘤)

程序员文章站 2022-05-25 15:42:43
题意 $n$个节点的树,判断能否划分成$\frac{n}{k}$个大小为$k$的联通块 Sol 首先$k$必须是$n$的倍数。 然后刚开始我就非常傻的以为输出所有约数就行了。。 但是图是这样,$k = 2$的话肯定是不行的。 结论:若$k$是可行的,则至少有$\frac{n}{k}$个节点的大小为$ ......

题意

$n$个节点的树,判断能否划分成$\frac{n}{k}$个大小为$k$的联通块

sol

首先$k$必须是$n$的倍数。

然后刚开始我就非常傻的以为输出所有约数就行了。。

但是图是这样,$k = 2$的话肯定是不行的。

 BZOJ3004: 吊灯(结论 毒瘤)

 

结论:若$k$是可行的,则至少有$\frac{n}{k}$个节点的大小为$k$的倍数

证明:直接归纳吧。

$k = n$的时候显然

$k = n / 2$的时候,我们要把树划分成互不相交的两块,这两块一定是完全独立的,且分别有自己的根节点。

剩下的继续归纳即可,注意这里我们为什么要是“至少”,因为整棵树是联通起来的,我们在判断$k$的时候,大小为$2k$的也会被统计入答案

 

然后这题卡dfs,不愧是sdoi。。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 2 * 1e6;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n;
vector<int> ap;
int fa[maxn], tim[maxn];
void rebuild() {
    memset(tim, 0, sizeof(tim));
   // for(int i = 1; i <= n; i++) v[i].clear();
    for(int i = 2; i <= n; i++) fa[i] = (fa[i] + 19940105) % (i - 1) + 1;
}
int siz[maxn];
/*void dfs(int x, int fa) { mdzz卡dfs,不愧是sdoi啊。。 
    siz[x] = 1;
    for(int i = 0; i < v[x].size(); i++) {
        int to = v[x][i];
        if(to == fa) continue;
        dfs(to, x);
        siz[x] += siz[to];
    }
}*/
void solve(int id) {
    printf("case #%d:\n", id);
    for(int i = 1; i <= n; i++) siz[i] = 1;
    for(int i = n; i >= 1; i--) siz[fa[i]] += siz[i];
    for(int i = 1; i <= n; i++) tim[siz[i]]++;
    for(int i = 0; i < ap.size(); i++) {
        int num = ap[i], cnt = 0;
        for(int j = num; j <= n; j += num)
            cnt += tim[j];
        if(cnt >= n / num) {
            printf("%d\n", num);
        }
    }
}
int main() {
    n = read();
    for(int i = 1; i <= n; i++) 
        if(n % i == 0) 
            ap.push_back(i);
    for(int i = 2; i <= n; i++) 
        fa[i] = read();
    solve(1);
    for(int i = 2; i <= 10; i++) {
        rebuild();
        solve(i);
    }
    return 0;
}