# 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;
}

最新文章

  1. window server 2008配置FTP服务器550 Access is denied. 问题解决办法
  2. js日历选择控件
  3. js运动框架之掉落的扑克牌(重心、弹起效果)
  4. php热身2:CRUD with Ajax
  5. Maven之 环境搭建
  6. 在类成员函数后面加const
  7. jQuery插件开发 格式与解析2
  8. Eclipse+Java+OpenCV246人脸识别
  9. android假设重写onDraw实现一个相似TextView能够显示表情和链接的控件(一)
  10. JavaScript截取字符串的Slice、Substring、Substr函数简单比较还有indexof函数应用
  11. Watson Explorer Analytical Components 1
  12. Python+Selenium+webdriver环境搭建(windows)以及相关资源下载链接
  13. 码农、黑客和2B程序员之间的区别
  14. Java基础---Java---网络编程---TCP、UDP、UDP-键盘录入方式数据、Socket、TCP复制文件、UDP-聊天
  15. react 高阶组件的 理解和应用
  16. 想知道谁是你的最佳用户?基于Redis实现排行榜周期榜与最近N期榜
  17. vue-标签页组件
  18. windows10 专业版的远程服务器管理工具下载
  19. Markdown 简介及基础语法
  20. DOM 操作技术【JavaScript高级程序设计第三版】

热门文章

  1. UVa 213 信息解码 (模拟 &amp;&amp; 二进制)
  2. adaptiveThreshold(自适应阈值)
  3. 一句话搞定python六剑客
  4. LeetCode_509.斐波那契数
  5. Python 写 ACM 题目的一些技巧
  6. 五大好用的开源MySQL管理工具推荐
  7. Mybaits查询返回值是List类型的
  8. vue 表格组件分享
  9. windows安装程序制作
  10. 分布式任务队列 Celery