首页 > 其他分享 >P5765 [CQOI2005] 珠宝 题解

P5765 [CQOI2005] 珠宝 题解

时间:2023-12-31 20:12:11浏览次数:29  
标签:颜色 题解 P5765 CQOI2005 sum 珠宝

P5765 [CQOI2005] 珠宝 题解

思路

好题,注意到有性质:颜色数最多为 \(\lfloor\log_2 n\rfloor + 1\),有了这个性质之后直接树形 DP 糊上去就过了。

简要的证明:

考虑一个点,显然一种颜色即可。

对于一个颜色为 \(c\) 的点,其儿子至少有 \(c - 1\) 个,且为 \(1\sim c - 1\) 的排列,这样可以感性理解是最劣的,所以对于最大颜色为 \(n\) 的树,其最坏情况下至少需要有 \(f_n\) 个点,有递推式:

\[f_n = \sum_{i = 1}^{n - 1} f_i + 1\\ f_1 = 1 \]

注意到 \(f_n = 2^{n - 1}\)。

证明:

\[施数学归纳法于 递推式 f\\ 对于 f_1 = 1\\ 假设对于 n\le k,有f_n = 2^{n - 1}\\ 则 f_{k + 1} = \sum_{i = 1}^k f_i + 1\\ f_{k + 1} = \sum_{i = 1}^k 2^{i - 1} + 1 = 2^k - 1 + 1 = 2^k\\ 则当 n\le k + 1 时也成立 \]

因此对于一个有 \(n\) 个点的树,其最多拥有 \(\lfloor\log_2 n\rfloor + 1\) 种颜色。

标签:颜色,题解,P5765,CQOI2005,sum,珠宝
From: https://www.cnblogs.com/MoyouSayuki/p/17937932

相关文章

  • P2898 [USACO08JAN] Haybale Guessing G 题解
    题目传送门前置知识二分答案|并查集解法对条件的合法性判断其他题解已经讲得很明白了,这里不再赘述。这里主要讲一下用并查集实现黑白染色问题。以下内容称被覆盖为黑色,不被覆盖为白色。本题因为是单向染色,即从白到黑,故可类似luoguP1840ColortheAxis和D的并查集或......
  • 二叉树面试题解析
    二叉树面试题解析判断相同的树/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(){}*TreeNode(intval){this.val=val;}*TreeNode(intval,TreeNode......
  • 剑指Offer Java题解(前3道题)
    目录1.二维数组中的查找2. 替换空格3. 从尾到头打印链表1.二维数组中的查找题目链接:传送。方法一,暴力枚举。参考代码:packageproblem01;/***@Authorsyrdbt*@Date2019/7/314:05*二维数组中的查找*方法一,暴力枚举*/publicclassSolution{publicboole......
  • 杭州电子科技大学2023新生赛 E 树 题解
    Question杭州电子科技大学2023新生赛E树给定一颗包含\(n\)个节点的带边权的树,定义\(xordist(u,v)\)为节点\(u\)到\(v\)的简单路径上所有边权值的异或和有\(q\)次询问,每次给出lrx求\(\sum_{i=l}^rxordist(i,x)\)的值Solution考试的时候脑子坏了对于一条......
  • 【省选联考2020】树 题解
    省选题解第一发~【省选联考2020】树我和这道题还挺有缘分的。有一次看大佬的省选游记(不知道是哪一年),然后提到有一道是01trie整体加一,当时我就印象深刻,然后在oiwiki上看了一下,心想这整体加一也只能从低位到高位维护01trie啊,又不能查询最大值,有什么卵用(划掉)。这是两周前的事......
  • 题解 [SDOI2016] 游戏
    可以看出来出题人很想出一道把李超和别的什么东西凑起来的题目,于是给了这么一个缝合怪。https://www.luogu.com.cn/problem/P4069符号有点混乱。比如箭头又可以表示路径又可以表示赋值,代入语境应该还是好理解的。看到\(a\timesdis+b\)就应激反应出来是李超了,看到\(s\to......
  • CF1884D Counting Rhyme 题解
    Problem-D-CodeforcesCountingRhyme-洛谷法1:我们之前肯定看过这样一道非常经典的题:求\(a_i\)中有多少对\((i,j)\),满足\(\gcd(a_i,a_j)=1\)\(n\leq10^6\)这题是莫反板子题,但显然可以不用莫反做。先不说这题怎么做,我们发现这道题和CF1884D的不同之处在......
  • [ABC334C] Socks 2 题解
    题目传送门一道贪心题。数量为\(2\)的袜子不用考虑,因为最好的情况就是相同颜色的配一对。我们只需要考虑那\(k\)种只有\(1\)个的袜子,如果\(k\)为偶数,答案为相邻两数之差之和;如果\(k\)为奇数,就枚举删掉一个数,让剩下的数按照\(k\)为偶数的情况做,最后取一个最小值。这......
  • [ABC334E] Christmas Color Grid 1 题解
    题目传送门一道dfs题。先统计出绿连通块数量,然后对于每个红色方块统计涂成绿色方块后会变成多少个连通块。正常涂成绿色后应该会增加一个大小为\(1\)的绿连通块,但若是有不同的绿连通块与其相邻,答案又会减少\(1\)。Code#include<bits/stdc++.h>constlonglongIMX=1......
  • CF1917F Construct Tree 题解
    Description给你一个数组\(l_1,l_2,\dots.l_n\)和一个数字\(d\)。问你是否能够构造一棵树满足以下条件:这棵树有\(n+1\)个点。第\(i\)条边的长度是\(l_i\)。树的直径是\(d\)。只需要判断是否有解即可。\(2\len\le2000,1\led\le2000,1\lel_i\led\)。Solutio......