4084: [Sdoi2015]双旋转字符串

阅读量：299 次

发布时间：2019-03-03

本文共 925 字，大约阅读时间需要 3 分钟。

Description

给定两个字符串集合 S 和 T 。其中 S 中的所有字符串长度都恰好为 N ，而 T 中所有字符串长度都恰好为 M 。

且 N+M 恰好为偶数。如果记 S 中字符串全体为 S1，S2，…，STotalS ,而 T 中字符串全体为 T1，T2，…，TT

otalT 。现在希望知道有多少对

题解

hash 给大的集合中的每个字符串把一段按mid分成两段，然后看看要是匹配的话需要小串是什么。。

然后需要的小串用个map记录一下就好了。。

最后累加很简单

CODE：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       typedef long long LL;using namespace std;const int MOD=10037;//乘的东西const int MOD1=1000000007; const int N=4000005;int S,T,n,m,o;char ss[N],s1[N];LL shen[N];//前i为的hash值LL KK,KKK;map
        
          q;struct qq{ int x;}s[N*2];int cnt=0;bool cmp (qq a,qq b){ return a.x
         
          >1;//中间端点是什么 KK=1; for (int u=1;u<=2*o-n;u++) KK=KK*MOD%MOD1; KKK=1; for (int u=1;u<=n-o;u++) KKK=KKK*MOD%MOD1; for (int u=1;u<=S;u++) { scanf("%s",ss+1); add(); } int ans=0; for (int u=1;u<=T;u++) { scanf("%s",ss+1); LL p=0; for (int i=1;i<=m;i++) p=((p*MOD)%MOD1+ss[i]-'a')%MOD1; ans=ans+q[p]; } printf("%d\n",ans); return 0;}

转载地址：http://wbcq.baihongyu.com/

你可能感兴趣的文章

剑指offer Leetcode 39.数组中出现次数超过一半的数字

机器学习--sklearn之k-近邻算法

Latex中cases环境引入报错

Latex排版的时候把图片放在指定位置

Latex如何将题目和作者左对齐

用 Python 把你的朋友变成表情包（鼠标事件提取 ROI 版）

Tensorflow2.0：基于循环卷积网络预测剩余寿命

联邦学习（一）：通过卷积神经网络对 emnist 数据集分类

bzoj3879: SvT 后缀自动机

bzoj 1483: [HNOI2009]梦幻布丁线段树合并

4084: [Sdoi2015]双旋转字符串

bzoj3439: Kpm的MC密码（四种做法）

Nginx出现500 Internal Server Error 错误

flask 404 not found

502 bad Gateway & supervisorctl status : EXITED

pytorch loss = loss_func(output, label) 报错

51nod 1526 分配笔名

bzoj 3011: [Usaco2012 Dec]Running Away From the Barn

MySQL中drop、truncate和delete的区别？

Mysql索引底层B+树的实现原理以及Innodb和Myisam引擎存储的区别