http://www.lydsy.com/JudgeOnline/problem.php?id=2084
题意:一个01串,求满足字符串0和1取反后,再将整个串反过来和原串一样的子串数目。(n<=500000)
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
long long ans;
int len[N<<1], n;
char s[N<<1];
int main() {
scanf("%d%s", &n, s+1);
for(int i=n; i; --i) s[i<<1]=s[i], s[i<<1|1]='#';
n=n<<1|1; s[1]='#';
int cur=1;
for(int i=2; i<=n; ++i) {
int &now=len[i];
now=min(len[(cur<<1)-i], max(0, cur+len[cur]-i));
if(i&1) {
while(i-now-1>=1 && i+now+1<=n && (s[i-now-1]=='#' || s[i-now-1]!=s[i+now+1])) ++now;
ans+=now;
}
if(cur+len[cur]<i+now) cur=i;
}
printf("%lld\n", ans>>1ll);
return 0;
}
发现就是0和1看做相等的回文串= =
妈呀发现在做manacher的时候有各种坑爹情况= =
首先要注意只能插入的特殊字符才能拓展= =否则如果是0或1拓展的话会出现莫名的问题= =(因为当0!=1的时候可能会造成类似这种
4
1001
答案应该是2
= =因为你会发现当'#'拓展后得到的长度,对于'0'或'1'在这个长度内不一定满足回文性= =
【BZOJ】2084: [Poi2010]Antisymmetry的更多相关文章
-
【BZOJ】2086: [Poi2010]Blocks
题意 \(n(1 \le n \le 1000000)\)个数\(a_i(a_i \le 10^9)\).\(m(1 \le m \le 50)\)次询问,每次给出一个\(k(k \le 10^9)\ ...
-
【BZOJ】【2084】【POI2010】Antisymmetry
Manacher算法 啊……Manacher修改一下就好啦~蛮水的…… Manacher原本是找首尾相同的子串,即回文串,我们这里是要找对应位置不同的“反回文串”(反对称?233) 长度为奇数的肯定不 ...
-
BZOJ 2084: [Poi2010]Antisymmetry [Manacher]
2084: [Poi2010]Antisymmetry Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 609 Solved: 387[Submit] ...
-
【BZOJ】3052: [wc2013]糖果公园
http://www.lydsy.com/JudgeOnline/problem.php?id=3052 题意:n个带颜色的点(m种),q次询问,每次询问x到y的路径上sum{w[次数]*v[颜色]} ...
-
【BZOJ】3319: 黑白树
http://www.lydsy.com/JudgeOnline/problem.php?id=3319 题意:给一棵n节点的树(n<=1e6),m个操作(m<=1e6),每次操作有两种: ...
-
【BZOJ】3319: 黑白树(并查集+特殊的技巧/-树链剖分+线段树)
http://www.lydsy.com/JudgeOnline/problem.php?id=3319 以为是模板题就复习了下hld............................. 然后n ...
-
【BZOJ】1013: [JSOI2008]球形空间产生器sphere
[BZOJ]1013: [JSOI2008]球形空间产生器sphere 题意:给n+1个n维的点的坐标,要你求出一个到这n+1个点距离相等的点的坐标: 思路:高斯消元即第i个点和第i+1个点处理出一个 ...
-
【BZOJ】1002:轮状病毒(基尔霍夫矩阵【附公式推导】或打表)
Description 轮状病毒有很多变种,所有轮状病毒的变种都是从一个轮状基产生的.一个N轮状基由圆环上N个不同的基原子和圆心处一个核原子构成的,2个原子之间的边表示这2个原子之间的信息通道.如下图 ...
-
【BZOJ】【3083】遥远的国度
树链剖分/dfs序 其实过了[BZOJ][4034][HAOI2015]T2以后就好搞了…… 链修改+子树查询+换根 其实静态树的换根直接树链剖分就可以搞了…… 因为其实只有一样变了:子树 如果roo ...
随机推荐
-
JS双月份显示联动效果,点击日期浮出消息提示
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...
-
无法嵌入互操作类型“ESRI.ArcGIS.Carto.RectangleElementClass”。请改用适用的接口。
右键点击应用的程序集 ESRI.ArcGIS.Controls,修改"嵌入互操作类型"的值即可
-
SXT_项目
30. svn服务器运行方式: svnserve:自己做实验的时候用. svn&apache结合起来用.[常用的] 29. EXTJs not Jquery[根据项目组需求] 28. tags ...
-
mysql 表空间
开启了Innodb的innodb_file_per_table这个参数之后[innodb_file_per_table = 1],也就是启用InnoDB的独立表空间模式,便于管理.此时,在新建的inn ...
-
fdisk分区
查看文件系统: # df -hFilesystem Size Used Avail Use% Mounted on/dev/sda1 20G 1.1G 18G 6% /tmpfs 1.9G 0 1.9 ...
-
组以逗号分隔的子串及跨平update join
下列语句可以对组以逗号分隔的子串 set @device_cd_array += ', ' set @device_cd_array += @nodeid ,, '') update时要join表要先 ...
-
Codeforces Gym 100203G G - Good elements 暴力
G - Good elementsTime Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hust.edu.cn/vjudge/contest/ ...
-
[摘抄] 为什么 Linq 可以高效率查询 SQL ?
From C# in Depth(3rd) - Jon Skeet using (LinqDemoDataContext db = new LinqDemoDataContext()) { var f ...
-
使用BSD socket编写Windows版的网络程序
我们知道BSD Socket是标准的套接字规范,那么怎么在windows使用他们呢? 我们首先要引用<winsock2.h>和ws2_32.lib 然后,执行WSAStartup #ifd ...
-
php简单的爬虫
爬虫的原理是分析下载的页面,找出其中的连接,然后再下载这些链接,对链接再进行更深层次的递归,周而复始.在数据存储方面,先存储到redis里面,再有redis 写入到mysql,这样可以减轻mysql写 ...