tg 78 solution

T1

依据题意模拟
首先两个只能当动词的不行
然后句末必然是名词
再然后选出来的动词前面是名词
然后就没了

T2

赛时写的deque启发式合并但是并没有过
然后一大车人拿无旋treap过了
正解链表，
考虑对于每个操作分出来的小球看做一个整体
然后\(1\)操作就是新建一个节点
\(3\)操作就是翻转一整个链表然后把两个链表接在一块
事实上不用真的翻转整个链表，维护链表头和尾
然后对于操作参数中\(x\),
把\(x\)的头接在\(y\)的头上，
\(x\)的尾当做\(y\)的新头
然后是操作\(2\)就是链表删除表头节点
当大于的时候就删点，同时维护新的\(sum\)
否则就在当前点减去，这个时候返回颜色值就好了

时间复杂度的话，
操作\(1,3\)显然单次\(O(1)\)
然后操作\(2\)的话
考虑每个操作\(1\)新加的小球被拿完的时候
表头这个节点就直接pop掉了
类比单调队列每个元素至多出队一次，所以均摊\(O(1)\)

T3

线段树维护转移矩阵
不会

T4

把输入的数看成字符串
记初始串为\(s,s_{l,r}\)表示\(s\)在区间\([l,r]\)的字符形成的\(s\)的子串
先考虑第一次增加
显然你找最靠后的位置\(pos,s_{pos,n}\)是\(s_{1,pos}\)的前缀
记\(s_{pos,n}=T,s_{1,pos}=S,f(x)\)表示一个字符串\(x\)的长度
分讨即可

原文地址：http://www.cnblogs.com/22222222STL/p/16855807.html