Gym10198-Mediocre String Problem-2018南京ICPC现场赛

（有任何问题欢迎留言或私聊 && 欢迎交流讨论哦

Catalog

Catalog
- Problem：传送门
Solution：
- AC_Code：
- Problem Description：

Problem：传送门

Portal

原题目描述在最下面。

Solution：

二分+\(hash\)+\(manacher\)
题意要我们在s串中找一个子串，和在t串中找一个前缀串，组合成回文串，但是串1长度要大于串2的长度。
其实就是要找三个串，在s中找连续的串a和串b，在t中找一个前缀串c
满足b是回文串且长度至少为1，a串和c串对称
到这一步思路就十分明确了，可以用\(manacher\)预处理出以\(i\)点为左端点的串是回文串的个数，差分一下就可以了。
然后就很简单了，先把t串反转。
枚举\(i\)，\(i\)表示a串的末尾，则\(i+1\)就是b串的起点，然后求s串[0,i]的子串和反转后t串的最长公共后缀，这一步就直接二分+\(hash\)就可以了。累计贡献\(len_{最长公共后缀}\times pre[i+1]\)

AC_Code：

#include<bits/stdc++.h>

#define lson rt<<1

#define rson rt<<1|1

#define fi first

#define se second

#define lowbit(x) (x&(-(x)))

#define mme(a,b) memset((a),(b),sizeof((a)))

#define fuck(x) cout<<"* "<<x<<"\n"

#define iis std::ios::sync_with_stdio(false)

using namespace std;

typedef long long LL;

const int N = 1e6+7;

const int MXN = 1e6+7;

const long long MOD = 2078526727;

const long long BASE = 1572872831;

LL pw[MXN], hs1[MXN], hs2[MXN];

int n, m;

char ar[N<<1], br[N<<1], t[N];

int p[N<<1], pre[N];

void manacher(){

  int Len = strlen(ar), id = 0, ans_id = 0, right = 0;

  memset(p, 0, sizeof(p));

  memset(br, 0, sizeof(br));

  for(int i = Len; i >= 0; --i){

    ar[2 * i + 1] = '#';

    ar[2 * i + 2] = ar[i];

  }

  ar[0] = '*';p[0] = p[1] = 1;

  for(int i = 2; i < 2 * Len + 1; ++i){

    if(i < right)p[i] = min(p[2 * id - i], right - i);

    else p[i] = 1;

    while(i - p[i] >= 0 && ar[i + p[i]] == ar[i - p[i]])p[i]++;

    if(p[ans_id] < p[i])ans_id = i;

    if(i + p[i] > right){

      id =i;

      right = i + p[i];

    }

  }

}

LL get(LL *a, int l, int r) {

    return ((a[r]-a[l-1]*pw[r-l+1])%MOD+MOD)%MOD;

}

bool ok(int len, int P, int lent) {

    if(get(hs1, P-len+1, P) == get(hs2, lent-len+1, lent)) return true;

    return false;

}

int main() {

    pw[0] = 1;

    for(int i = 1; i < 1000003; ++i) pw[i] = pw[i-1] * BASE % MOD;

    scanf("%s%s", ar, t);

    int len = strlen(ar);

    hs1[0] = hs2[0] = 1;

    for(int i = 0; i < len; ++i) {

        hs1[i+1] = (hs1[i]*BASE + ar[i]) % MOD;

    }

    manacher();

    for(int i = 2; i < 2 * len + 1; ++ i) {

        pre[(i-p[i]+2)/2-1] ++;

        pre[i/2] --;

        //printf("%d %d %d %d\n", i, p[i], (i-p[i]+2)/2-1, i/2);

    }

    for(int i = 1; i < len; ++i) {

        pre[i] += pre[i-1];

    }

    /*for(int i = 0; i < len; ++i) {

        printf("%d ", pre[i]);

    }

    printf("\n");*/

    int lent = strlen(t);

    reverse(t, t + lent);

    for(int i = 0; i < lent; ++i) {

        hs2[i+1] = (hs2[i]*BASE + t[i]) % MOD;

    }

    int k = 0;

    for(int i = 2; i < 2*len-1; ++i) {

        if(i%2 == 0) ar[k++] = ar[i];

    }

    LL res = 0;

    for(int i = 0; i < len - 1; ++i) {

        //二分LCP,[?,i],[1,?]

        if(ar[i] != t[lent-1]) continue;

        int l = 1, r = min(lent, i+1), mid, ans = 0;

        while(r >= l) {

            mid = (l+r)>>1;

            if(ok(mid, i+1, lent)) ans = mid, l = mid+1;

            else r = mid-1;

        }

        res += (LL)ans * pre[i+1];

        //printf("%d %d\n", i, ans);

    }

    printf("%lld\n", res);

    return 0;

}

巴特西

Gym10198-Mediocre String Problem-2018南京ICPC现场赛

Catalog

Problem：传送门

Solution：

AC_Code：

Problem Description：

最新文章

热门文章