本文主要是介绍【省选模拟】20/06/02，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A A A
- 发现只需要压黑白开头存不存在为偶数的，若存在，其他偶数边随便选不选这条边的选发是唯一的， d p dp dp 即可， C o d e Code Code
B B B
- 补集转换一下，枚举两个不交的集合，考虑他们向外的连边，强制指向这个集合
对于选定的集合，要统计其联通的方案数，容斥 d p dp dp 即可， C o d e Code Code
C C C
- 性质：最后选出来的一定形如 k , k − 1 , … , 1 k,k-1,\dots,1 k,k−1,…,1，并且后一个是前一个的前缀或后缀，一个后缀若 i i i 合法，则 i − 1 i-1 i−1 也合法
- 基于这个进行 d p dp dp， d p i dp_i dpi 表示 i i i 的后缀的最大值
二分它的值，考虑转移到一个 j j j，那么需要满足 d p j ≥ m i d − 1 , m a x ( l c p ( i , j ) , l c p ( i + 1 , j ) ) ≥ m i d − 1 , j ≥ i + m i d dp_j\ge mid-1,max(lcp(i,j),lcp(i+1,j))\ge mid-1,j\ge i+mid dpj≥mid−1,max(lcp(i,j),lcp(i+1,j))≥mid−1,j≥i+mid，用主席数维护区间最大值即可
发现有性质 f i ≤ f i + 1 + 1 f_i\le f_{i+1}+1 fi≤fi+1+1，那么不需要二分，可以在均摊 O ( n log n ) O(n\log n) O(nlogn) 的时间解决这个问题， C o d e Code Code
这篇关于【省选模拟】20/06/02的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
