P2351 [SDOi2012]吊灯

    • 97通过
    • 215提交
  • 题目提供者 TMXi
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 各省省选 2012 山东 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    山东省省队选拔赛第二试(第一天)

    题目描述

    Alice家里有一盏很大的吊灯。所谓吊灯,就是由很多个灯泡组成。只有一个灯泡是挂在天花板上的,剩下的灯泡都是挂在其他的灯泡上的。也就是说,整个吊灯实际上类似于[b]一棵树[/b]。其中编号为 1 的灯泡是挂在天花板上的,剩下的灯泡都是挂在编号小于自己的灯泡上的。

    现在,Alice想要办一场派对,她想改造一下这盏吊灯,将灯泡换成不同的颜色。她希望相同颜色的灯泡都是相连的,并且每一种颜色的灯泡个数都是相同的。

    Alice希望你能告诉她,总共有哪些方案呢?

    Alice是一个贪心的孩子,如果她发现方案不够多,或者太多了,就会很不高兴,于是她会尝试调整。对于编号为[b]x(x≠1)[/b]的灯泡,如果原来是挂在编号为[b]f[x][/b]的灯泡上,那么Alice会把第x个灯泡挂到[b]第 ( f[x] + 19940105 ) mod (x-1) + 1 个[/b]灯泡上。

    由于九在古汉语中表示极大的数,于是,[b][color=#FF0000]Alice决定只调整9次[/color][/b]。对于原始状态和每一次调整过的状态,Alice希望你依次告诉她每种状态下有哪些方案。

    输入输出格式

    输入格式:

    第一行一个整数n,表示灯泡的数量。

    接下来一行,有n-1个整数Ui,第i个数字表示第i+1个灯泡挂在了Ui个的下面。保证编号为1的灯泡是挂在天花板上的。数字之间用逗号(西文标点)" , "隔开且最后一个数字后面没有逗号。

    输出格式:

    对于10种状态下的方案,需要按照顺序依次输出。

    对于每一种状态,需要先输出单独的一行,表示状态编号,如样例所示。

    之后若干行,每行1个整数,表示划分方案中每种颜色的灯泡个数。

    [b]按升序输出。[/b]

    输入输出样例

    输入样例#1: 复制
    6
    1,2,3,4,5
    输出样例#1: 复制
    Case #1:
    1
    2
    3
    6
    Case #2:
    1
    2
    6
    Case #3:
    1
    3
    6
    Case #4:
    1
    3
    6
    Case #5:
    1
    3
    6
    Case #6:
    1
    2
    6
    Case #7:
    1
    2
    3
    6
    Case #8:
    1
    6
    Case #9:
    1
    2
    6
    Case #10:
    1
    3
    6

    说明

    对于20%的数据,n<=3*10^3。

    对于40%的数据,n<=5*10^4。

    对于50%的数据,n<=1*10^5。

    对于60%的数据,n<=3*10^5。

    对于70%的数据,n<=7*10^5。

    对于100%的数据,n<=1.2*10^6。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。