首页 > 代码库 > 集训 0617

集训 0617

  今天的题目很良心,都切中我们当前急需提高的地方,针对性强。

  第一题是道有趣的贪心题目。

  多组询问用长度为k的祖先儿子链覆盖一棵树的最小使用次数。

  首先,贪心性质很容易看出来,每次选择一个未被覆盖深度最深的叶子节点,往上覆盖K个点,这样构造一定能构造出一种最佳方案。可以用优先队列维护。

  那么我们考虑如何加速这个过程,或者说,如何均摊查询的复杂度。

  使用上面的构造方法,很容易看出来,单次复杂度很容易卡成O(n),而且不同的K基本上复杂度都没有什么变化。

  考虑一下上面的贪心的点个数,设叶子数为L,则入队点的个数不超过O(L+(n-L)/k)

  这个可以根据以上贪心的部分证明。

  那么再考虑本质不同的K,本质相同的K我们可以直接记下来答案,则相当于复杂度为

  ∑(1<=k<=n)O(L+(n-L)/k)。

  这里的L十分讨厌,不优化到L无法实现均摊,尝试优化掉这个L,这个东西可以使用DP求d[i]表示i节点最近的叶节点的距离即可。

  然后我们就发现这玩意均摊完了是nlog2n的。

 

  考试时,一方面状态设置得不好,导致一个问题不好解决,另一方面没有想到去掉L,于是只拿了52.

 

  第二题:

  推DP状态的题目。

  题解里给了4个状态:

  暴力状态。

  f[i][S],S表示排列状态,阶乘级别状态。

  f[i][x][S],S表示2进制状态,幂级状态。

  f[x][y][0/1/2/3],n^2级别状态,多项式级别的状态。

  很有趣,很多考试中都会出现这种类型的题目。

 

  恩,推出了前两个,在考虑第三个时,经验不足,挂了,然后卡常...

  第三题:

  考虑若x>y且x放到了y的前面那么x将一直放在y的后面。

  那么可以将x,y进行考虑贡献,就成了二维数点问题。

  恩,没推导出二位数点,10分辛苦分。

 

  总的来说,考挂的原因主要是1.模型挂了2.状态设置以及性质推导。

 

 

 

 

   

集训 0617