luogu P5342 [TJOI2019]甲苯先生的线段树

刺骨的言语ヽ痛彻心扉 2021-12-13 04:38 161阅读 0赞

[传送门][Link 1]

> 你个好好的省选怎么可以出CF原题啊,你们这个题害人不浅啊,这样子出题像极了cxk,说到cxk,我又想起了他是NBA形象大使,跟我是西游文化大使一样一样的,今年下半年...

别说了,jinsaisannian

因为线段树树高是\\(logn\\)层的,所以第一问可以直接暴力做,后面记这个权值为\\(n\\).第二问的话,暴力是枚举路径最上面那个点以及下面的两个端点,不过可以改为枚举两边向下延伸的长度,记为\\(l,r\\),然后\\((x,l,r)\\)权值下界为\\(x+2x+4x...+2lx+2(x+1)+4(x+1)...+2r(x+1)=(2^\{l+1\}+2^\{r+1\}-3)x+2^r-1\\)  
也就是两条链全往左延伸;对于\\((x-1,l,r)\\),他权值上界情况下,每个点的权值都是小于\\((x,l,r)\\)的权值下界情况的对应的点权值,所以对于一对\\((l,r)\\),\\(x\\)的权值范围是无交的,那么对于一个\\(n\\)和\\((l,r)\\),只有一个\\(x\\)有贡献,也就是\\(\\lfloor\\frac\{n-2^r+1\}\{2^\{l+1\}+2^\{r+1\}-3\}\\rfloor\\).于是可以把\\(n\\)减去权值下界\\((2^\{l+1\}+2^\{r+1\}-3)x+2^r-1\\),那么只要考虑两条链形态对答案的影响了.以长度为\\(l\\)的链(左链)为例,可以发现有\\(l-1\\)个地方可以选择走左边或者右边,如果在从上到下第一个地方选择走右边,最后会多出来\\(2^\{l-1\}-1\\)的权值,在第二个地方选择走右边会多出来\\(2^\{l-2\}-1\\)的权值...\\(r\\)类似.现在问题变成枚举\\((l,r)\\),然后\\(n\\)减去下界,有两个长度分别为\\(l-1,r-1\\)的\\(01\\)串,在某个串第\\(i\\)位选\\(1\\)权值加上\\(2^i-1\\),问多少个确定每个位置\\(0/1\\)的方案,使得权值为\\(n\\).这个可以数位dp解决但是我不会qwq,还可以记忆化搜索,复杂度为\\(O(d^4)-O(d^5)\\) 复杂度也不会证qwq

[谢罪代码][Link 2]

转载于:https://www.cnblogs.com/smyjr/p/10841521.html

[Link 1]: https://www.luogu.org/problemnew/show/P5342
[Link 2]: https://loj.ac/submission/441276