UOJ219 NOI2016 优秀的拆分 二分、字符串哈希

时间:2020-12-10 09:09:07

传送门


题目可以转化为求\(AA\)的数量,设\(cnt1_x\)表示左端点为\(x\)的\(AA\)的数量,\(cnt2_x\)表示右端点为\(x\)的\(AA\)的数量,那么答案就是\(\sum cnt2_i \times cnt1_{i+1}\)

比较朴素的想法是枚举两个后缀然后哈希/SA判断这两个后缀的LCP是否足够长,能够拼成一个\(AA\)形式的串。然后这样就能拿95分???

考虑\(n\)比较大的时候优化枚举。我们对于所有\(len \in [1,\frac{N}{2}]\),在串中标记若干个关键点,两个相邻的关键点的距离为\(len\)。那么一个形如\(AA\)、长度为\(2 \times len\)的串会覆盖恰好\(2\)个关键点,而且两个关键点在覆盖了它的\(A\)串中的位置是一样的。

这意味着对于这两个关键点\(i,j = i+len\),\(min(LCP(suffix_i,suffix_j),len) + min(len,LCS(prefix_i , prefix_j)) > len\)(与\(len\)取\(min\)的原因是不能让覆盖范围超出了\(i,j\)两个点)。这给了我们需要求\(LCP\)与\(LCS\)的信息。SA与二分+Hash均可(反正这题不卡复杂度)。

当然做到上面我们仍然没有优化复杂度……

接下来,考虑算出了\(q=min(LCP(suffix_i,suffix_j),len)\)与\(p=min(len,LCS(prefix_i , prefix_j))\),这意味着串\(s_{[i-p+1 , i + q - 1]}\)与\(s_{[j-p+1,j+q-1]}\)是相等的,而\(j = i + len\)。那么我们随意取出\(s_{[i-p+1 , i + q - 1]}\)的一段长度为\(len\)的段,它的右边都一定紧接着一段长度为\(len\)并且与它相同的段。所以\(cnt1_{i-p+1,i+q-len}\)都会这一步中\(+1\),同时\(cnt2_{i-p+1+2 \times len , i + q + len}\)也会\(+1\)。使用差分数组维护,最后前缀和一下就可以统计答案了。

因为调和级数\(\sum \limits _{i=1}^n \frac{n}{i} < nlogn\),所以总复杂度为\(O(nlogn)\)(使用SA)或者\(O(nlog^2n)\)(使用二分+Hash)

#include<bits/stdc++.h>
#define ll long long
#define PLL pair < long long , long long >
//This code is written by Itst
using namespace std;

inline int read(){
    int a = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c) && c != EOF){
        if(c == '-')
            f = 1;
        c = getchar();
    }
    if(c == EOF)
        exit(0);
    while(isdigit(c)){
        a = a * 10 + c - 48;
        c = getchar();
    }
    return f ? -a : a;
}

const int MAXN = 3e4 + 7 , seed = 131 , MOD1 = 1e9 + 7 , MOD2 = 1e9 + 9;
char s[MAXN];
int L , sum1[MAXN] , sum2[MAXN];
ll Hash[MAXN][2] , poww[MAXN][2] , ans;

inline void init_hash(){
    for(int i = 1 ; i <= L ; ++i){
        Hash[i][0] = (Hash[i - 1][0] * seed + s[i]) % MOD1;
        Hash[i][1] = (Hash[i - 1][1] * seed + s[i]) % MOD2;
    }
}

inline PLL get_hash(int l , int r){
    return PLL((Hash[r][0] - Hash[l - 1][0] * poww[r - l + 1][0] % MOD1 + MOD1) % MOD1 , (Hash[r][1] - Hash[l - 1][1] * poww[r - l + 1][1] % MOD2 + MOD2) % MOD2);
}

inline int calc_LCP(int p , int q){
    int l = 0 , r = min(q - p , L - q + 1);
    while(l < r){
        int mid = (l + r + 1) >> 1;
        get_hash(p , p + mid - 1) == get_hash(q , q + mid - 1) ? l = mid : r = mid - 1;
    }
    return l;
}

inline int calc_LCS(int p , int q){
    int L = 0 , R = min(q - p , p);
    while(L < R){
        int mid = (L + R + 1) >> 1;
        get_hash(p - mid + 1 , p) == get_hash(q - mid + 1 , q) ? L = mid : R = mid - 1;
    }
    return L;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    //freopen("out","w",stdout);
#endif
    poww[0][0] = poww[0][1] = 1;
    for(int i = 1 ; i <= 3e4 ; ++i){
        poww[i][0] = poww[i - 1][0] * seed % MOD1;
        poww[i][1] = poww[i - 1][1] * seed % MOD2;
    }
    for(int T = read() ; T ; --T){
        memset(sum1 , 0 , sizeof(sum1));
        memset(sum2 , 0 , sizeof(sum2));
        scanf("%s" , s + 1);
        L = strlen(s + 1);
        init_hash();
        for(int i = 1 ; i < L ; ++i)
            for(int j = 1 ; j + i <= L ; j += i){
                int p = calc_LCS(j , j + i) , q = calc_LCP(j , j + i);
                if(p + q - 1 >= i){
                    ++sum1[j - p + 1];
                    --sum1[j + q - i + 1];
                    ++sum2[j - p + 1 + 2 * i - 1];
                    --sum2[j + q + i];
                }
            }
        for(int i = 1 ; i <= L ; ++i){
            sum1[i] += sum1[i - 1];
            sum2[i] += sum2[i - 1];
        }
        ans = 0;
        for(int i = 1 ; i < L ; ++i)
            ans += sum2[i] * sum1[i + 1];
        cout << ans << endl;
    }
    return 0;
}

UOJ219 NOI2016 优秀的拆分 二分、字符串哈希的更多相关文章

  1. BZOJ4650&sol;UOJ219 &lbrack;Noi2016&rsqb;优秀的拆分

    本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作. 本文作者:ljh2000 作者博客:http://www.cnblogs.com/ljh2000-jump/ ...

  2. &lbrack;UOJ&num;219&rsqb;&lbrack;BZOJ4650&rsqb;&lbrack;Noi2016&rsqb;优秀的拆分

    [UOJ#219][BZOJ4650][Noi2016]优秀的拆分 试题描述 如果一个字符串可以被拆分为 AABBAABB 的形式,其中 A 和 B 是任意非空字符串,则我们称该字符串的这种拆分是优秀 ...

  3. &lbrack;NOI2016&rsqb;优秀的拆分&lpar;SA数组&rpar;

    [NOI2016]优秀的拆分 题目描述 如果一个字符串可以被拆分为 \(AABB\) 的形式,其中 A和 B是任意非空字符串,则我们称该字符串的这种拆分是优秀的. 例如,对于字符串 \(aabaaba ...

  4. 题解-NOI2016 优秀的拆分

    NOI2016 优秀的拆分 \(T\) 组测试数据.求字符串 \(s\) 的所有子串拆成 \(AABB\) 形式的方案总和. 数据范围:\(1\le T\le 10\),\(1\le n\le 3\c ...

  5. &lbrack;NOI2016&rsqb;优秀的拆分&amp&semi;&amp&semi;BZOJ2119股市的预测

    [NOI2016]优秀的拆分 https://www.lydsy.com/JudgeOnline/problem.php?id=4650 题解 如果我们能够统计出一个数组a,一个数组b,a[i]表示以 ...

  6. luogu1117 &lbrack;NOI2016&rsqb;优秀的拆分

    luogu1117 [NOI2016]优秀的拆分 https://www.luogu.org/problemnew/show/P1117 后缀数组我忘了. 此题哈希可解决95分(= =) 设\(l_i ...

  7. 【BZOJ4560】&lbrack;NOI2016&rsqb;优秀的拆分

    [BZOJ4560][NOI2016]优秀的拆分 题面 bzoj 洛谷 题解 考虑一个形如\(AABB\)的串是由两个形如\(AA\)的串拼起来的 那么我们设 \(f[i]\):以位置\(i\)为结尾 ...

  8. 并不对劲的bzoj4650&colon;loj2083&colon;uoj219&colon;p1117&colon;&lbrack;NOI2016&rsqb;优秀的拆分

    题目大意 "优秀的拆分"指将一个字符串拆分成AABB的形式 十次询问,每次给出一个字符串S(\(|S|\leq3*10^4\)),求它的所有子串的优秀的拆分的方案数之和 题解 此题 ...

  9. &lbrack;BZOJ&rsqb;4650&colon; &lbrack;Noi2016&rsqb;优秀的拆分

    Time Limit: 30 Sec  Memory Limit: 512 MB Description 如果一个字符串可以被拆分为 AABBAABB 的形式,其中 AA 和 BB 是任意非空字符串, ...

随机推荐

  1. PHP中的全局变量global和&dollar;GLOBALS的区别

    1.global Global的作用是定义全局变量,但是这个全局变量不是应用于整个网站,而是应用于当前页面,包括include或require的所有文件. 但是在函数体内定义的global变量,函数体 ...

  2. OGRE的学习资源

    本文介绍从哪儿开始学习OGRE(Object-Oriented Graphics Rendering Engine的简称,又叫做OGRE 3D),如何在网上找寻OGRE的学习资源. 首先是wikipe ...

  3. HTML5 video 支持air play

    < video src="/path/to/video.mp4" x-webkit-airplay="allow" preload controls&gt ...

  4. jQuery中position&lpar;&rpar;与offset&lpar;&rpar;区别

    使用jQuery获取元素位置时,我们会使用position()或offset()方法,两个方法都返回一个包含两个属性的对象-左边距和上边距,它们两个的不同点在于位置的相对点不同. 可以看看下边的图: ...

  5. struts2漏洞原理及解决办法

    1.原理 Struts2的核心是使用的webwork框架,处理action时通过调用底层的getter/setter方法来处理http的参数,它将每个http参数声明为一个ONGL(这里是ONGL的介 ...

  6. Struts2配置文件讲解

    解决在断网环境下,配置文件无提示的问题我们可以看到Struts.xml在断网的情况下,前面有一个叹号,这时,我们按alt+/ 没有提示,这是因为” http://struts.apache.org/d ...

  7. HTML&plus;CSS笔记 CSS中级 颜色&长度值

    颜色值 在网页中的颜色设置是非常重要,有字体颜色(color).背景颜色(background-color).边框颜色(border)等,设置颜色的方法也有很多种: 1.英文命令颜色 语法: p{co ...

  8. Egret学习笔记 &lpar;Egret打飞机-4&period;添加主角飞机和实现飞行效果&rpar;

    今天继续写点击了开始之后,添加一个飞机到场景中,然后这个飞机的尾巴还在冒火的那种感觉 先拆解一下步骤 1.首先完成飞机容器的图片加载 2.然后把容器添加到场景中 3.然后实现动画 -首先,我们新建一个 ...

  9. 用Maven实现一个protobuf的Java例子

    注:试验环境在Mac Idea环境下 1. 介绍Protocol Buffers Protocal Buffers(简称protobuf)是谷歌的一项技术,用于结构化的数据序列化.反序列化,常用于RP ...

  10. Java并发编程(五)锁的使用(下)

    显式锁 上篇讲了使用synchronized关键字来定义锁,其实Java除了使用这个关键字外还可以使用Lock接口及其实现的子类来定义锁,ReentrantLock类是Lock接口的一个实现,Reen ...