0%

简介

序列自动机是接受一个字符串的子序列的自动机。

它可以方便地维护 / 匹配字符串(数列)的所有子序列。

阅读全文 »

题目链接

题意

给定一个长度为 nn 的、只由 CT 组成的字符串 ss,每次询问给定区间 l,rl,r,表示字符串 s=slsl+1srs^\prime=s_ls_{l+1}\dots s_r,求至少删掉 ss^\prime 中的多少个字符才能保证:对于 ss^\prime 的任意一个前缀或后缀,其 C 的数量都不小于 T 的数量。

阅读全文 »

题目链接

题意

对于一棵树,你可以进行如下操作:选择两条边 (u1,v1),(u2,v2)(u_1,v_1),(u_2,v_2),将其修改成 (u1,v2),(u2,v1)(u_1,v_2),(u_2,v_1)

给定一棵树,支持加点 / 删点(保证仍为一棵树),求这棵树经过至多一次操作后的最大直径。

阅读全文 »

题目链接

题意

一个由 nn 个点、A+BA+B 条边组成的无向连通图,有一变量 xx,有 AA 条边的权值为 k+xk+x,有 BB 条边的权值为 kxk-x。保证只保留这 AA 条边或这 BB 条边时图连通。

多组数据,每次询问给定 xx,求此时图的最小生成树权值和是多少。

阅读全文 »

简介

Link Cut Tree(简称 LCT)是使用 Splay 和实链剖分来维护森林的一个数据结构,它支持以下在线操作:

  • 查询 / 修改链上的信息
  • 换根
  • 动态连边 / 删边
  • 查询连通性
  • ……
阅读全文 »