「POI2010」反对称 Antisymmetry (manacher算法)
2024-09-05 18:26:32
# 2452. 「POI2010」反对称 Antisymmetry
【题目描述】
对于一个 $0/1$ 字符串,如果将这个字符串 $0$ 和 $1$ 取反后,再将整个串反过来和原串一样,就称作「反对称」字符串。比如 $00001111$ 和 $010101$ 就是反对称的,而 $1001$就不是。
现在给出一个长度为 $n$ 的 $0/1$ 字符串,求它有多少个子串是反对称的,注意这里相同的子串出现在不同的位置会被重复计算。
【算法】
0\1取反和对称操作的前后顺序显然不影响,先考虑对称操作再考虑取反,于是可以发现子串长度显然是偶数而且关于对称轴0/1对称(一边为0则另一边为1)。
算法1: 枚举对称轴,二分+hash。时间复杂度$O(nlog(n))$。
算法2: manacher算法,$O(n)$的时间算出所有子串最长回文子串长度(此题改下判断条件就好)。
【代码】
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
int n;
ull ans;
int r[1001000];
char s[500100],c[1001000];
int main() {
scanf("%d%s",&n,s+1);
c[0]='$';
for(int i=1;i<=n;i++) {
c[2*i-1]='#';
c[2*i]=s[i];
}
c[2*n+1]='#'; c[2*n+2]='$';
int mx=0,po=0;
for(int i=1;i<=2*n;i+=2) {
if(mx>i) r[i]=min(mx-i,r[2*po-i]);
else r[i]=1;
while((c[i+r[i]]==c[i-r[i]]&&c[i+r[i]]=='#')||(c[i+r[i]]-'0'+c[i-r[i]]-'0'==1))
r[i]++;
if(i+r[i]>mx) mx=i+r[i],po=i;
ans+=r[i]>>1;
}
printf("%lld\n",ans);
return 0;
}
最新文章
- window server 2008配置FTP服务器550 Access is denied. 问题解决办法
- js日历选择控件
- js运动框架之掉落的扑克牌(重心、弹起效果)
- php热身2:CRUD with Ajax
- Maven之 环境搭建
- 在类成员函数后面加const
- jQuery插件开发 格式与解析2
- Eclipse+Java+OpenCV246人脸识别
- android假设重写onDraw实现一个相似TextView能够显示表情和链接的控件(一)
- JavaScript截取字符串的Slice、Substring、Substr函数简单比较还有indexof函数应用
- Watson Explorer Analytical Components 1
- Python+Selenium+webdriver环境搭建(windows)以及相关资源下载链接
- 码农、黑客和2B程序员之间的区别
- Java基础---Java---网络编程---TCP、UDP、UDP-键盘录入方式数据、Socket、TCP复制文件、UDP-聊天
- react 高阶组件的 理解和应用
- 想知道谁是你的最佳用户?基于Redis实现排行榜周期榜与最近N期榜
- vue-标签页组件
- windows10 专业版的远程服务器管理工具下载
- Markdown 简介及基础语法
- DOM 操作技术【JavaScript高级程序设计第三版】