#P7422. Low Complexity Tree

    ID: 7436 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>难度分类提高动态规划树形 DP字符串Trie数论向下取整与向上取整CF2200

Low Complexity Tree

Low Complexity Tree

题目描述

机房中有一棵高度为hh 的满二叉树(包含2h2^{h}个叶结点),传说是某 i 姓同学被吊打过的地方。在这棵树上,我们将所有叶子结点从左往右依次编号为1,...,2h1,...,2^{h}。其中有mm个叶子结点称为关键结点,它们的编号依次为t1,...,tmt_{1},...,t_{m}。这棵树上的每个非叶结点上有一个开关,开关有左右两种状态。接下来执行如下的投球过程:一个球从根结点出发,每次走到当前结点开关指向的那个儿子处,直到走到叶结点,此时该球将会计入该叶结点的球数中,然后,这个球经过的所有结点的开关状态将取反(左变右,右变左)。你可以设置每个开关最初的位置,然后连续投下nn 个球,你需要使得最终所有关键结点的球数之和最大, 只需要输出这个最大值。

输入格式

第一行:三个整数h,m,nh,m,n,分别表示二叉树的深度,关键结点的数量以及投球数。 第二行:mm个整数t1...mt_{1...m},表示关键结点的编号。

输出格式

输出一行一个整数,表示所有关键结点的球数之和的最大值。

样例1输入

2 3 3
1 2 3

样例1输出

3

样例 1 解释

如图,按最左图安排初始时非叶结点的开关方向(红实线为开关方向),前三个球分别落到1,3,21,3,2 这三个点。

原题示意图

数据范围

采用捆绑测试。所有数据满足 1≤h≤601\le h\le60,1≤m≤min⁡(2h,105)1\le m\le\min(2^h,10^5),1≤n≤10181\le n\le10^{18},1≤ti≤2h1\le t_i\le2^h,且所有 tit_i 两两不同。

子任务 分值 特殊限制
1 10 h≤4,n≤100h\le4,n\le100
2 20 h≤10,n≤105h\le10,n\le10^5
3 10 h≤20h\le20
4 h≤60,m=1h\le60,m=1
5 20 h≤60,m≤20h\le60,m\le20
6 30 h≤60h\le60