「考试反思」2020-10-28 莫得

技术文章 5个月前 完美者
2,052 0

标签:统计   怎么   部分   方向   ken   span   线段树   模拟   转移   

orz G_keng 给的题!

辣鸡(ljh)

写复杂了,然后全程在写这个题目

其实可以直接排序完了模拟

然后自己套上了原来的一个题的做法

不过不太好写,写出来了还是能行


以下均为考后刷题

模板(ac)

线段树按照 时间 开,存颜色和数量,统计的时候

这样子最后统计的时候就直接在树的前 \(k_i\) 个点算就行

修改对着当前点改就行了

下面是思考的两点

1.怎么修改的时候判重

整个线段树合并做,然后维护最早出现时间

2.修改的时间也要改

跟着上面的做就行了

妙呀!

复兴了线段树合并

争取下次听完沈子舜说题面之后能直接说出来:“时间建树,判判重就没了”

超级树

\(f_{i,j}\)\(i\) 级超级树,\(j\) 条路径互不相交的方案数,这里的路径如果方向不一样也算不同的方案,比如 \(1\to 2 \neq 2\to 1\)

转移分为以下:

\((1)\ f_{i+1,j+k}+=f_{i,j}\times f_{i,k}\) 从左边选择 \(j\) 条,右边选择 \(k\) 条,不进行更新


\((2)\ f_{i+1,j+k-1}+=f_{i,j}\times f_{i,k}\times 2\times j\times k\) 合并路径


\((3)\ f_{i+1,j+k}+=f_{i,j}\times f_{i,k} \times 2\times(j+k)\) 起点或者终点连到根上面

因为想咋走就可以随便从上面走下来或者走上去


\((4)\ f_{i+1,k+j-1}+=f_{i,j}\times f_{i,k}\times (j\times (j-1)+(k-1)\times k)\) 直接在子树里面走


$(5)\ f_{i+1,j+k+1}+=f_{i,j}\times f_{i,k} $ 添加多出来的根节点

这个部分真的很容易漏掉!!

计数注意:增量的添加

初始状态 \(f_{1,0}=f_{1,1}=1,ans=f_{n,1}\)


一些卡常:

减半优化,最值优化

C++11优化,O2优化

「考试反思」2020-10-28 莫得

标签:统计   怎么   部分   方向   ken   span   线段树   模拟   转移   

原文地址:https://www.cnblogs.com/yspm/p/13898606.html

版权声明:完美者 发表于 2020-10-30 12:31:33。
转载请注明:「考试反思」2020-10-28 莫得 | 完美导航

暂无评论

暂无评论...