[原创]SPOJ STC02 - Antisymmetry [Manacher]【思维】

2017-01-09 00:44:19 Tabris_ 阅读数：496

博客爬取于2020-06-14 22:42:22
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54263566

题目链接：http://www.spoj.com/problems/STC02/
-----------------------------------------------------------------------------------------.
STC02 - Antisymmetry
no tags
Byteasar studies certain strings of zeroes and ones. Let S be such a string. By Sr we will denote the reversed (i.e., “read backwards”) string S, and by SI we will denote the string obtained from S by changing all the zeroes to ones and ones to zeroes.

Byteasar is interested in antisymmetry, while all things symmetric bore him. Antisymmetry however is not a mere lack of symmetry. We will say that a (nonempty) string S is antisymmetric if, for every position i in S, the i-th last character is different than the i-th (first) character. In particular, a string S consisting of zeroes and ones is antisymmetric if and only if S=SIr. For example, the strings 00001111 and 010101 are antisymmetric, while 1001 is not.

In a given string consisting of zeroes and ones we would like to determine the number of contiguous nonempty antisymmetric fragments. Different fragments corresponding to the same substrings should be counted multiple times.

Input
The first line of the standard input contains an integer N (1 <= N <= 500000) that denotes the length of the string. The second line gives a string of 0 and/or 1 of length N. There are no spaces in the string.

Output
The first and only line of the standard output should contain a single integer, namely the number of contiguous (non empty) fragments of the given string that are antisymmetric.

Example
For the input data:

8
11001011
the correct result is:

7
Antisymmetric fragments are: 01 (occurs twice), 10 (also twice), 0101, 1100, and 001011.
------------------------------------------------------------------------------------------.

题目大意：
就是给你一个字符串，然你统计满足0/1互换之后在翻转等于原串的子串有多少个

解题思路:
这个可以利用求最长回文子串的Manacher算法解决，只要把check换成下述就可以

1
2
3
4
5
bool check(int x,int y){
    if(x<1||x>len) return false;
    if(y<1||y>len) return false;
    return ((a[x]=='0'&&a[y]=='1')||(a[x]=='1'&&a[y]=='0')||(a[x]=='#'&&a[y]=='#'));
}

这样题目就变得非常简单了
计算子串的方法一样,与标准的Manacher一模一样.都是用p[i]来维护以i为中心的最长子串的半径,但由于题意的限制,这个中心只能是’#'.最后累加下就好了.

但是为什么我的代码还是不能过掉 test61！！！！ 调了好久还是不知道问题出在哪里 ，最后无奈只好贴了OMRailgun的代码。。。。

然后改了改，已经和OMRailgun的代码一模一样了，但是最后一组样例还是过不去 ，ZTMDCD。。

===================Update=========================
问题已发现 ,因为!!!因为!!!
p[i]=(p[(id<<1)-i]<(mx-i))?p[(id<<1)-1]:(mx-i);
应该是
p[i]=(p[(id<<1)-i]<(mx-i))?p[(id<<1)-i]:(mx-i);
我就是个**…

附本题代码
-----------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//能AC的OMRailgun的代码
//OMRailgun博客的链接http://blog.csdn.net/omrailgun/article/details/53931521
# include<iostream>
# include<stdio.h>
# include<string.h>
# include<stdlib.h>
using namespace std;
# define ll long long
const int N=500008;
int n,len,f[N*2];
char a[N*2],str[N];
int minx(int x,int y){if(x<y)y=x;return y;}
int pan(int x,int y){return ((a[x]=='0'&&a[y]=='1')||(a[x]=='1'&&a[y]=='0')||(a[x]=='#'&&a[y]=='#'));}
int main(void)
{
    int i,m,id;ll ans=0;
    scanf("%d%s",&n,str+1);
    a[len=0]=0;a[++len]='#';
    for(i=1;i<=n;i++){a[++len]=str[i];a[++len]='#';}
    m=0;
    for(i=1;i<=len;i++)
    {
        if(m>i)f[i]=minx(f[2*id-i],m-i);else f[i]=1;
        while(i-f[i]>=1&&i+f[i]<=len&&pan(i+f[i],i-f[i]))f[i]++;
        if(a[i]=='#'&&i>1&&i<len){ans+=f[i]/2;if(i+f[i]>m){m=i+f[i];id=i;} }
    }
    printf("%lld",ans);
    return 0;
}

//能AC的我的代码 已经改正了
# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int MOD = 1e9+7;
const int N = 500000+105;
const double eps = 1e-6;
const double PI = acos(-1.0);
void fre(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}
/*************************************************/

int minx(int x,int y){if(x<y)y=x;return y;}
char a[N<<1],str[N];
int p[N<<1],slen,len;
bool check(int x,int y){
    if(x<0||x>len) return false;
    if(y<0||y>len) return false;
    if( (a[x]=='0'&&a[y]=='1')||
        (a[x]=='1'&&a[y]=='0')||
        (a[x]=='#'&&a[y]=='#') )
            return true;
    return false;
}

void solve(){

    LL ans = 0;
    a[len]   = '$', a[++len] = '#',len  = 0;
    Rep(i,0,slen-1) a[++len] = str[i],a[++len] = '#';

    memset(p,0,sizeof(p));
    int id = -1,mx = -1;
    Rep(i,0,len){
        if(mx > i) p[i] = minx(p[(id<<1)-i],(mx-i));
        else p[i]=1;
        while(check(i-p[i],i+p[i])) p[i]++;
        if(a[i]=='#') {ans+=p[i]>>1;
        if(p[i]+i>mx) mx=p[i]+i,id=i;}
    }
    printf("%lld\n",ans);
    return ;
}

int main(){
    while(~scanf("%d%s",&slen,str)) solve();
    return 0;
}