hihoCoder挑战赛22题解

3
1

T1:

把a1和a2设出来,通过矩阵快速幂用a1和a2来表示ax和ay。这样就得到了关于a1和a2的二元一次方程。暴力解出来,带回去,矩阵快速幂求解az。

T2:

我们首先考虑一下如何最大化a的和,我们先按照b最小,a最大排序,然后将最前面的p-k个“炮灰”去掉,根据贪心策略,其余所有元素再按照a最大,b最大排序,选出前k个做上标记,就选这k个啦!然后加上原来踢出去的“炮灰”一起按照b最小a最大的排序找出最前面做上标记的元素,向前去连续的p-k个,这p-k个元素b的和做标记的k个元素的a的和就是最优选择,贪心的正确性很好证明,开始取出p-k个元素保证其合法性,然后标记k个保证a的和最大,在此基础上所有元素排序以合法的贪心策略取k个元素使b的和最大。

T3:

用dfs维护这棵数,查询的时候查询u到跟的前缀积以及v的,在乘上到LCA的逆元。修改的时候在dfs的树状数组内修改。 因为数据较大,卡了树剖和LCT。

T4:

首先可以推一波性质,发现在任何局面下,兔子们最多有三种跳法,即中间的向两边跳和两侧较靠内的向内跳。 可以发现除了在左右相等的情况下,其他局面三种跳法都可以完成,且如果把第三种特殊的跳法,这样我们就可以发现跳跃路线构成了一个二叉树,且一开始位于根节点。 于是问题转化为n个节点,最大深度为k的二叉树有多少种,左右子树有区别。 这个问题可以DP。 F[i][j]表示i个节点,最大深度不超过k的树有多少种。 F[i][j]=\sum_{k=1}^{i-1}F[k][j-1]*F[i-k-1][j-1] 这个式子是n^3,不能通过 可以发现j具有明显的阶段性,在此基础上i满足卷积的性质 可以使用NTT优化。

一开始T1数据错了,不好意思QAQ

  • T2 : 什么叫b最小,a最大排序?会不会炮灰里有一个a特别大的人使得小y没选?

  • T3是什么数据量,后来在题库里提交,lca查询用的RMQ,dfs序的点权数组用的树状数组维护,都还TLE,后来copy一份别人的所谓ac代码还是TLE。

  • 添加评论
  • reply

3 answer(s)

1

下次能不能写个给小白看的题解,这个说的也太粗略了,看了和没看一样

0

听说T3卡了LCT啊=-=

  • 被水过去了?QAQ 惨啊

  • 不知道=-=反正我写了个lct就过了的说=-=

  • 添加评论
  • reply
1

被虐得体无完肤

write answer 切换为英文 切换为中文


转发分享