D9
模拟赛.我太菜了.上来直接判定不可做了.
其实感觉T1才是那个跳跃性最强的,拿着随机性质找暴力当正解了属于是.T2反倒比较自然,其实就是数位dp,被唬住了没敢细推而已.T3暴力还是很可拿的,转换根的地方有点技巧性,不过也没有那么邪门.总体而言是套吓人但不算难度特别大的题.
然后就是开题问题,不要恩做t1,也不要随便判不可做.当然不可做的思路一定要剪枝掉,在上面硬钻就浪费时间了.
T1
暴力:有个显然的枚举端点查询链的思路,暴力 \(O(n^3)\) ,考虑简单优化一下,维护与查询链中位数的最好方法只有值域线段树,因此用主席树,优化到 \(O(n^2logV)\) 期望25分.
考虑当前的矛盾点是什么,这种做法相当于要做 \(q=n^2\) 次链查询也就是说传统的数据结构维护是不可行的.这时对于计数问题的一个重要思想就是把贡献用某种方式合并,从而简化计算.但是这种中位数的问题显然不具有连续性,同时值域线段树也没法按分类合并.因此,直接把多条路径同时统计不怎么可行.
所以考虑从直接放弃前面的思路,从整体考虑问题.很容易想到枚举由哪条边作为中位数.又显然这样做可以把边排序,然后在前面的按1,后面按-1,找所有带该条边的权值为1的路径.
然后又回到了找路径的问题,虽然维护值变成和了,还是不可维护.
正解:这时候就要找题目的意图了:随机树,小数据范围.因此可以打 \(\Sigma sz\) 和 \( \Sigma dep\) 的主意了,因此,完全可以dp了,然后在更新过程中,直接向上跳父亲,通过树高的大小,可以认为可过了.
到这里就是暴力dp的内容了.
启发 首先,不可做的思路一定要坚决剪掉,不然严重浪费时间,这种判断力也是能力的一部分.
对于题目给的每一个条件都要会利用,但是不要钻到里面,例如一个劲想办法用\(\Sigma sz\) 想要优化主席树做法.尽量让自己思路顺一点,同时要有一个推进的生成思路,不能停滞在一个点,而是尽可能向前,并拆解成子问题.
T2
暴力:硬算.
正解:考虑这种与二进制高度相关的计数问题,要么推式子,要么考虑数位dp,这是THUSC D1T1 的一个教训,不要被大数据范围吓到.一旦变成二进制数位dp了,直接对数据范围带 \(log\),看起来不可解的问题就可解了.当然不要教条.数位dp能够解决对数字本身的限制问题的计数.而本题的关键矛盾就是大计数与数字统计问题计算困难的矛盾,因此应该考虑到数位dp.
这个题仔细想想有两步大计算,推式子发现没有什么约化的意义,那就考虑数位dp.
首先分两步数位dp肯定是不行的,也是没有优化意义的,因此考虑同时统计.那么要填数的变成 \(a,b,x\) 不过 \(a,b,x\) 之间有很强的约束关系,因此考虑同时对三者填数.考量情况数与条件限制的矛盾,可以发现,需要维护的仅仅是对三个量的限制是否满足.因此可以有一个从低位向高位填数的递推dp方案,考虑填到第 \(i\) 位,分别维护方案数和答案.方案数可以直接更新,然后答案在方案基础上就很可算.
启示 一方面,对于看起来不容易的问题不要改变找基本或关键矛盾的原则,并作出正确的判断,也不要被一时认为此题非常困难的一种感性认知蒙蔽.找到数位dp后,这道题就变得很可做了.
标签：D10,暴力,D12,二中,维护,考虑,思路,dp,数位 From： https://www.cnblogs.com/youlv/p/18262775