专栏首页数据结构与算法BZOJ3004: 吊灯(结论 毒瘤)

BZOJ3004: 吊灯(结论 毒瘤)

题意

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

Sol

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

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

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

结论:若$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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1250 Fibonacci数列

    时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 定义:f0=...

    attack
  • 洛谷P5108 仰望半月的夜空(后缀数组)

    warning:下面这个做法只有95分,本地拍了1w+组都没找到错误我表示十分无能为力

    attack
  • 1001 舒适的路线 2006年

    1001 舒适的路线 2006年 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Descrip...

    attack
  • 「2017 Multi-University Training Contest 1」2017多校训练1

    饶文津
  • 1464: [蓝桥杯2019初赛]数的分解

    把2019分解成3个各不相同的正整数之和,并且要求每个正整数都不包含数字2和4,一共有多少种不同的分解方法?注意交换3个整数的顺序被视为同一种方法,例如1000...

    可爱见见
  • 搜索(4)

    mathor
  • 剑指Offer-构建乘积数组

    package Array; import sun.security.util.Length; /** * 构建乘积数组 * 给定一个数组A[0,1,....

    武培轩
  • 初级程序员面试不靠谱指南(三)

    二、指针的好基友的& 1.&的意义。说&是指针的好基友其实不恰当,因为&这个符号在C/C++不止有一种含义,但是因为其经常会和指针一起出现在被问的问题列表上,所...

    一心一怿
  • 1001 舒适的路线 2006年

    1001 舒适的路线 2006年 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Descrip...

    attack
  • 数码管问题(c++实现)

        描述:液晶数码管用七笔阿拉数字表示的十个数字,把横和竖的一 个短划都称为一笔,即7有3笔,8有7笔等。对于十个数字一种排列,要做到  两相邻数字都可以由...

    用户2038589

扫码关注云+社区

领取腾讯云代金券