Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 3160: 万径人踪灭

题目链接

传送门



想说的话

这题看着就让人不愿意做

一句话题意

在一个仅仅含有a,b的字符串里选取一个子序列,使得:
1.位置和字符都关于某条对称轴对称;
2.不能是连续的一段。

题解

这个0分算法有点骚


不能连续看起来特别难
所以我们转化成总共减去连续
连续的用manacher就可以轻松搞定
现在看总共
求总的回文串个数稍微复杂一些。我们用f[i]表示以i为对称中心,两边有多少个对称的字符。对于每个中心i我们有(2^f[i])-1种方案 答案即Σ1<=i<=n*2+1
显然f[i]=(Σ[1<=j<=i-1]bool(str[j]==str[i-j]))+1>>1。
至于如何求出f[i],我们分别用a[]、b[]记录下每一位是否出现'a'或'b'。比如ababa这样一个数组,a={10101},b={01010}
a[]的卷积就是'a'的贡献,b[]的卷积就是'b'的贡献,两者相加+1再除以2即可。
卷积的话
baidu上面搜索fft或者通过我的友链进入GGN_2015的博客
讲解很棒

下面的是官方的题解



提醒

看错mod炸翻你

看错mod炸翻你

看错mod炸翻你

看错mod炸翻你

为什么呢
我们看几张图
这道题我整整做了4个小时
然后前一个半小时敲代码 调对了manacher和fft
然后接下来的两个半小时我的进展是0
都是


直到接下来我一个特别虎的想法救了我
我该不会是mod写错了吧
然后接下来 好玩了

我TM?!
然后发现自己成功AC
我TM?!
AFO吧。。瞎子不适合学OI

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏