021017模拟 string 无旋Treap+并查集 数据结构

021017模拟 string 无旋Treap+并查集

区间翻转非常水,搞个无旋treap就好了,但是垃圾出题人居然卡常,没办法只能强开O3+节点内存池了。可以看出,在操作过后,问号之间形成了若干联通块,同一联通块内部所填字符必须相同,所以如果一个节点已经确定,那么整个联通块也就确定了,否则整个联通块随便填26个字母。 如果要求字典序第k小,就给并查集加···
BZOJ3712 [PA2014]Fiolki 重构树+并查集 杂题

BZOJ3712 [PA2014]Fiolki 重构树+并查集

又是一道思路非常好的题目。考虑到每个反应最多只进行一次,每个瓶子也只能往外倒一次,我们可以把每个瓶子想成一棵树。初始时,所有节点都是根节点,构成森林,每操作一次,就将两个瓶子表示的节点合并起来,可以用并查集维护,合并后的点重新标号,成为原来两个点的父节点,从下往上建树。注意到当两个物质能发生反应时,···