BZOJ NOI10十连测 7thtest
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
------------------------------------------------------------
T2从8点做到12点半是怎样一种体验...
各种犯SB错..我最近怎么了...?
------------------------------------------------------------
T1:
还不会...
------------------------------------------------------------
T2:
题意是给你一个字符串,每次询问[l,r]内回文串的个数,两个回文串不同当且仅当他们的位置不同
设r[i]表示以i为中心的最长回文串半径
d[i]表示以i和i-1的空隙为中心的最长回文串半径
列出公式:
$res = \sum_{i=L}^{R}min\{r[i],R-i+1,i-L+1\}+min\{d[i],R-i+1,i-L\}$
$ = \sum_{i=L}^{mid}min\{r[i],i-L+1\}+min\{d[i],i-L\} + \sum_{i=mid+1}^{R}min\{r[i],R-i+1\}+min\{d[i],R-i+1\}$
以$min\{r[i],i-L+1\}$为例:
若r[i]<=i-L+1,那么有i-r[i]>=L-1
因此只需要询问这个区间内i-r[i]>=L-1的r[i]之和以及i-r[i]<=L-2的i-L+1之和
用可持久化线段树就可以解决辣
------------------------------------------------------------
T3:
好像是ZJOI的原题
做法是这样的
设f[i][j]表示最近一个记者站在i这个位置,已经有j个记者站了
转移:f[i][j]=min{f[k][j-1] + cost(k,i) | 1<=k<=i}
YY一下就知道这个决策是单调的
那么只需要快速求cost的值
预处理出i这个村庄最左边可以建站的位置lef[i]
然后把村庄按他最右边可以建站的位置rig[i]排序
考虑比如说在右边加入了一个村庄r+1,那么需要额外付出代价的村庄就是那些rig<=r且lef>=l+1的位置,这个用一个可持久化线段树处理就行了
其他的也差不多
------------------------------------------------------------
评论 (0)
