泉州市网站建设_网站建设公司_建站流程_seo优化

P9356

对于括号序系列字符串进行操作

• 将前i个字符移动到最后
• 插入一个字符

将一个括号序列变为合法最小的操作次数记作f

现在要求这个括号序列所有子串的f之和

很显然，变换操作最多只会进行一次

考虑如果有A个左括号和B个右括号，则一定存在一种方式使得变换后min(A,B)组匹配

若\(A\geq B\)，考虑把左括号看作1，右括号看作-1，因此一定能找到所有的数都非零的前缀

考虑g(l,r)表示[l,r]的括号匹配是否为上界限

答案为

\[\sum_{l=1}^n \sum_{r=l}^n |A[l,r]-B[l,r]|+g(l,r) \]

将(看作1，)看作-1，做出的前缀和称为\(c\)

则式子转化为

\[\sum_{l=1}^n \sum_{r=l}^n |c_r-c_{l-1}|+\sum_{i=1}^n \sum_{r=l}^n g(l,r) \]

考虑左半部分将c排序之后就能快速计算了，转化

\[\sum_{r=0}^n\syn)AP_{l=0-}^r c_r-c_l \]

g(l,r)=1要求\(min c_l...c_r\)<\(min(c_{l-1},c_r)\)

分类讨论，\(c_{l-1}<c_r\)

枚举l，找到最小的满足要求的点同理快速计算

单调栈维护

P9357

一棵树，最开始所有点的点权值为0

每次操作选择一个节点u，得分加上u的权值相同连通块大小的贡献，然后u权值+1

问所有操作方式下的得分之和

求和可以改成求期望再乘方案数

把连通块的贡献拆成操作的点对每个连通块里的点的贡献。记 p(u,v,w) 表示操作 u 之前 u 的权值是 w 且这一步操作时 v 在那个连通块里的概率。那么答案就是

\[\sum_{u=1}^n\sum_{w=1}^n\sum_{w=0}^{m-1}p(u,v,w) \]

p(u,v,w) 只和 u 与 v 的距离有关，所以设 d 为 u 到 v 的路径上的点数，答案写为

\[\sum_{d=1}^n c_d\sum_{w=0}^{m-1}p(d,w) \]

\(c_d\)表示路径上点数为d的有向图路径条数

先决定每一步操作是否在路径上，然后决定路径上的操作的位置。有贡献当且仅当路径上至少有 dw+1 次操作，并且在路径上的前 dw 次操作均等地分布在路径的 d 个点上，并且第 dw+1 次操作操作的是点 u。

可以发现，这三个条件中，只要满足了第一个条件，无论有多少次操作在路径上，满足后面两个条件的概率都是一样的

即前 dw 次平均分配的方案数除以前 dw 次的总方案数再乘以第 dw+1 次操作位于 u 的概率。

对于满足第一个条件的概率，可以考虑枚举有多少个操作在路径上