【BZOJ】2084: [Poi2010]Antisymmetry

时间:2023-01-05 11:52:44

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的更多相关文章

  1. 【BZOJ】2086&colon; &lbrack;Poi2010&rsqb;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)\ ...

  2. 【BZOJ】【2084】【POI2010】Antisymmetry

    Manacher算法 啊……Manacher修改一下就好啦~蛮水的…… Manacher原本是找首尾相同的子串,即回文串,我们这里是要找对应位置不同的“反回文串”(反对称?233) 长度为奇数的肯定不 ...

  3. BZOJ 2084&colon; &lbrack;Poi2010&rsqb;Antisymmetry &lbrack;Manacher&rsqb;

    2084: [Poi2010]Antisymmetry Time Limit: 10 Sec  Memory Limit: 259 MBSubmit: 609  Solved: 387[Submit] ...

  4. 【BZOJ】3052&colon; &lbrack;wc2013&rsqb;糖果公园

    http://www.lydsy.com/JudgeOnline/problem.php?id=3052 题意:n个带颜色的点(m种),q次询问,每次询问x到y的路径上sum{w[次数]*v[颜色]} ...

  5. 【BZOJ】3319&colon; 黑白树

    http://www.lydsy.com/JudgeOnline/problem.php?id=3319 题意:给一棵n节点的树(n<=1e6),m个操作(m<=1e6),每次操作有两种: ...

  6. 【BZOJ】3319&colon; 黑白树(并查集&plus;特殊的技巧&sol;-树链剖分&plus;线段树)

    http://www.lydsy.com/JudgeOnline/problem.php?id=3319 以为是模板题就复习了下hld............................. 然后n ...

  7. 【BZOJ】1013&colon; &lbrack;JSOI2008&rsqb;球形空间产生器sphere

    [BZOJ]1013: [JSOI2008]球形空间产生器sphere 题意:给n+1个n维的点的坐标,要你求出一个到这n+1个点距离相等的点的坐标: 思路:高斯消元即第i个点和第i+1个点处理出一个 ...

  8. 【BZOJ】1002:轮状病毒(基尔霍夫矩阵【附公式推导】或打表)

    Description 轮状病毒有很多变种,所有轮状病毒的变种都是从一个轮状基产生的.一个N轮状基由圆环上N个不同的基原子和圆心处一个核原子构成的,2个原子之间的边表示这2个原子之间的信息通道.如下图 ...

  9. 【BZOJ】【3083】遥远的国度

    树链剖分/dfs序 其实过了[BZOJ][4034][HAOI2015]T2以后就好搞了…… 链修改+子树查询+换根 其实静态树的换根直接树链剖分就可以搞了…… 因为其实只有一样变了:子树 如果roo ...

随机推荐

  1. JS双月份显示联动效果,点击日期浮出消息提示

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...

  2. 无法嵌入互操作类型&OpenCurlyDoubleQuote;ESRI&period;ArcGIS&period;Carto&period;RectangleElementClass”。请改用适用的接口。

    右键点击应用的程序集 ESRI.ArcGIS.Controls,修改"嵌入互操作类型"的值即可

  3. SXT&lowbar;项目

    30. svn服务器运行方式: svnserve:自己做实验的时候用. svn&apache结合起来用.[常用的] 29. EXTJs not Jquery[根据项目组需求] 28. tags ...

  4. mysql 表空间

    开启了Innodb的innodb_file_per_table这个参数之后[innodb_file_per_table = 1],也就是启用InnoDB的独立表空间模式,便于管理.此时,在新建的inn ...

  5. fdisk分区

    查看文件系统: # df -hFilesystem Size Used Avail Use% Mounted on/dev/sda1 20G 1.1G 18G 6% /tmpfs 1.9G 0 1.9 ...

  6. 组以逗号分隔的子串及跨平update join

    下列语句可以对组以逗号分隔的子串 set @device_cd_array += ', ' set @device_cd_array += @nodeid ,, '') update时要join表要先 ...

  7. Codeforces Gym 100203G G - Good elements 暴力

    G - Good elementsTime Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hust.edu.cn/vjudge/contest/ ...

  8. &lbrack;摘抄&rsqb; 为什么 Linq 可以高效率查询 SQL &quest;

    From C# in Depth(3rd) - Jon Skeet using (LinqDemoDataContext db = new LinqDemoDataContext()) { var f ...

  9. 使用BSD socket编写Windows版的网络程序

    我们知道BSD Socket是标准的套接字规范,那么怎么在windows使用他们呢? 我们首先要引用<winsock2.h>和ws2_32.lib 然后,执行WSAStartup #ifd ...

  10. php简单的爬虫

    爬虫的原理是分析下载的页面,找出其中的连接,然后再下载这些链接,对链接再进行更深层次的递归,周而复始.在数据存储方面,先存储到redis里面,再有redis 写入到mysql,这样可以减轻mysql写 ...