模拟赛

T1

是不是跑个类似单调栈的东西就行？

T2

考虑转化为计数问题

考虑一个最简单的dp，设 $f_{i,j,k}$ 表示拥有三种线段的数量的情况的答案 红 绿 杂

那么枚举所有合并的可能

当 $i,j=0$ 时，答案是显然的，其实答案最后面都可以转为杂色段的情况的贡献

当绿段与红段合并时，转化为杂色段，贡献为 $\frac{(4ij)}{(2i+k)(2j+k)}f_{i-1,j-1,k+1}$

当红段与杂段合并时，转化为红色段，贡献为 $\frac{(2ik)}{(2i+k)(2j+k)}f_{i,j,k-1}$

当绿段与杂段合并时，转化为绿色段，贡献为 $\frac{(2jk)}{(2i+k)(2j+k)}f_{i,j,k-1}$

当绿绿或者红红合并时，转化为纯色段，贡献为 $\frac{(\frac{i(i-1)}{2})}{(2i+k)(2j+k)}f_{i-1,j,k}+\frac{(\frac{j(j-1)}{2})}{(2i+k)(2j+k)}f_{i,j-1,k}$

![[day1.pdf]]