526互联

20230704巴蜀暑期集训测试总结

发布时间 2023-07-04 22:24:06作者: 牛肉爱吃dks

T1

考场打的暴力，没有反应过来可以用树剖。签到题啊！

树剖+线段树+\(bitset\) 维护链上颜色集合。利用 Hall 定理求答案。

T2

暴力 \(+1\)。知道要优化建图，但是毫无头绪。后面改的时候发现码量是真的大，不知道考场切的人是怎么打出来的。

用边界和障碍将网格分成若干横段和竖段。将竖段建成可持久化线段树优化建图。

T3