[BZOJ2320]最多重复子串 Description 一个字符串P的重复数定义为最大的整数R,使得P可以分为R段连续且相同的子串.比方说,“ababab”的重复数为3,“ababa”的重复数为1. Your Task 对于给定的串S,找出S的一个子串K使得K的重复数最大. Input 第一行T表示数据组数 对于每组数据,一行中一个仅包含小写字母的字符串S Output 对于每组数据,在一行中输出K,如果有多个解,输出字典序最小的那一个 Sample Input 2 ccabababc daa

2018.12.18 1.[USACO Platinum C] 2.[Gym 102028H] 3.[BZOJ 2750] 4.[BZOJ 3238] 5.[BZOJ 4310] 6.[BZOJ 3879] 2018.12.19 1.[BZOJ 4278] 2.[BZOJ 3832] 3.[ZROI #138] 4.[ZROI #139] 5.[ZROI #140] 2018.12.20 1.[BZOJ 2320] 2.[BZOJ 2119] 3.[BZOJ 4892] 4.[POJ 1743]

BZOJ 洛谷 建出AC自动机,每个点向两个儿子连边,可以得到一张有向图.参照 [SDOI2012]走迷宫 可以得到一个\(Tarjan\)+高斯消元的\(O((nm)^3)\)的做法.(理论有\(60\)分啊但是第\(5.6\)个点WA了smg) 其实\(O((nm)^3)\)就是 [JSOI2009]有趣的游戏...只需建出AC自动机一遍高斯消元即可,比上面那个不知道好写到哪里去.. \(40\)分的做法问题在于状态(变量)太多.考虑把类似的状态合并成一个. 假设现在一共有两个串\(TTH\

BZOJ 洛谷 \(Description\) 给定\(n\)棵无根树.对每棵树,输出与它同构的树的最小编号. \(n及每棵树的点数\leq 50\). \(Solution\) 对于一棵无根树,它的重心最多不超过两个. 所以从两个重心分别DFS,可以将无根树转为有根树.选Hash值较小或较大的做整棵树的Hash值好了. 然后可以用树哈希,或者括号序(直接用string)来表示每棵树. 对于每个点的每棵子树,可以对哈希值或字符串sort一下用最小表示法记录. //936kb 20ms #incl

BZOJ 1014 火星人 题意 有一个字符串,三中操作:在某位置后面插入一个字符.修改某位置的字符.询问两个后缀的最长公共前缀. 题解 看到网上的dalao们都说这道题是平衡树,我就很懵x--平衡树维护什么啊? 最后发现某个节点维护的是它所代表的区间的哈希值--显然这个哈希值可以从左右子树的哈希值和这个节点上的字符算出来. #include <cstdio> #include <cmath> #include <cstring> #include <algori

3555: [Ctsc2014]企鹅QQ Time Limit: 20 Sec  Memory Limit: 256 MBSubmit: 2046  Solved: 749[Submit][Status][Discuss] Description PenguinQQ是中国最大.最具影响力的SNS(Social Networking Services)网站,以实名制为基础,为用户提供日志.群.即时通讯.相册.集市等丰富强大的互联网功能体验,满足用户对社交.资讯.娱乐.交易等多方面的需求.小Q是Pe

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2351 题意:给出一个n*m的01矩阵.再给出10个A*B的小01矩阵.判断这些小的矩阵是不是原矩阵的子矩阵. 思路:将原矩阵的每个A*B的矩阵哈希成一个值.给出的小矩阵也哈希成一个值.则直接查找即可. char s[N][N];int n,m,A,B;u64 h[N][N],f[N][N];u64 p[N]; void init(){    if(B>m) return;    int

2761: [JLOI2011]不重复数字 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 3210  Solved: 1186[Submit][Status][Discuss] Description 给出N个数,要求把其中重复的去掉,只保留第一次出现的数. 例如,给出的数为1 2 18 3 3 19 2 3 6 5 4,其中2和3有重复,去除后的结果为1 2 18 3 19 6 5 4.   Input 输入第一行为正整数T,表示有T组数据.

3198: [Sdoi2013]spring 题意:n个物品6个属性,求有多少不同的年份i,j满足有k个属性对应相等 一开始读错题了,注意是对应相等 第i个属性只能和第i个属性对应 容斥一下 \[ 恰好k个相等=\ge k个相等 \ -\ \ge k+1个相等\ +\ \ge k+2个相等 \ ... \] \(2^6\)枚举哪些属性对应相等,哈希一下计算这些属性相等的个数,这时候其他是任意的因为是\(\ge\) 这样还不行,容斥系数还要乘上\(\binom{i}{k}\),因为两个k+1个属性

https://www.lydsy.com/JudgeOnline/problem.php?id=5285 |0 和 &1 没有影响 若填‘|’,记为0,若填‘&’,记为1 先只考虑最后一位 若要求最后=1 那么最后一个|1 要在最后一个 &0 后面 将n个数的最后一位拿出来构成一个01序列 填在所有数最后一位之前的运算符也拿出来构成一个01序列 将第n个数所在位置视为最高位 对于最高位来说 如果数字序列 和 运算符序列 都是0或都是1,没有影响 如果数字序列是0,运算符序列是1,

题意:给定一个子串,询问一些子区间内的最短循环节(循环节是越短条件约束越多) 开始一看那就哈希处理然后暴力枚举循环节,然后按照循环节长度暴力向后比较,本地测试40,洛谷60 #include<bits/stdc++.h> #define rep(i,x,y) for(register int i=x;i<=y;i++) using namespace std; ; typedef unsigned long long ull; char s[N];int q; ull p[N],sum[

暴力的哈希,注意: 将一个串当作另一个串的前缀,需要乘上p[len],len=后面串的长度 这是自己的代码,拿数据在本地测A掉了,但是bz上wa了??bz换数据了难道?? #include<cstdio> #include<cstring> #define rep(i,x,y) for(register int i=x;i<=y;i++) using namespace std; ; typedef unsigned long long ull; int n,mid; cha

题目链接 这道题是一道判断无根树同构的模板题,判断同构主要的思路就是哈希. 一遇到哈希题,一百个人能有一百零一种哈希方式,这篇题解随便选用了一种--类似杨弋<Hash在信息学竞赛中的一类应用>中的这种,可能不是最简洁好写的,但是能用. 我的哈希规则:子树\(u\)的哈希值由它的每一个子树\(v_i\)的哈希值得来,首先将所有\(f(v)\)排个序(防止顺序不同造成影响),然后\(f(u) = size(u) * \sum_i f(v_i)W^{i - 1} \bmod P\),\(W\)是事先

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2351 就是先把每行单独从左到右扫着乘一个 b1 哈希起来,然后再按列从上往下乘一个 b2 哈希起来. 如果要取模的话,行的哈希和列的哈希应该模一样的数. 当然不是读入询问再枚举所有位置看哈希值啦……应该先把合法位置的哈希值用一个 map 之类的存一下存在性,询问的时候直接查 map 就行了. #include<cstdio> #include<cstring> #includ

传送门   题解 听说大佬们这题都是用SA秒掉的 然而SA的时间复杂度的确很优秀,缺点就是看不太懂…… 然后发现一位大佬用哈希华丽的过了此题,而且讲的特别清楚->这里 我们只要考虑以每一个点结尾的$AA$串的个数$u[i]$和以每一个点开头的AA串的个数$v[i]$,答案就是$\sum _{i=1}^{n-1} u[i]*v[i+1]$ 那么考虑如何求出$u$和$v$呢 我们考虑一下,枚举串$A$的长度$len$,然后每隔$len$个单位设置一个关键点.不难发现,每一个长度为$len*2$的$A

[Cqoi2014]通配符匹配 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 541  Solved: 235[Submit][Status][Discuss] Description 几乎所有操作系统的命令行界面(CLI)中都支持文件名的通配符匹配以方便用户.最常见的通配符有两个,一个是星号(“”’),可以匹配0个及以上的任意字符:另一个是问号(“?”),可以匹配恰好一个任意字符.现在需要你编写一个程序,对于给定的文件名列表和一个包含通配符的字

先把两个串能匹配模式串的位置找出来,然后标记为$1$(标记在开头或末尾都行),然后对标记数组求一个前缀和,这样可以快速查到区间内是否有完整的一个模式串. 然后二分子串(答案)的长度,每次把长度为$md$的串扔到哈希表里,查一波匹不匹配. #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define ull unsigned long long #define

昨天卡了一天常数...然后发现吧$unsigned\space long\space long$改成$unsigned$就可以过了$qwq$ 先把每一行的前缀哈希求出,然后再竖着把每个前缀哈希值哈希起来(相当于二维前缀哈希) 注意横着和竖着哈希的$Base$不能相同 #include<cstdio> #include<iostream> #define ll long long #define ull unsigned #define R register int using na

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1014 用splay维护字符串,每个点记录子树的哈希值,然后二分查询. 二分不是把两个点的哈希值拿出来二分!因为取模了所以不能还原:因为splay维护了字符串,所以二分答案后把对应一段转出来看看哈希值一不一样就行了. 如果一开始不是用给出的序列直接建一个树(就是递归 l,mid-1 和 mid+1,r 那样的),而是像我一开始一样一个一个往进插入的话,不知为何过不了呢. 有些卡时间.据说%m

Description PenguinQQ是中国最大.最具影响力的SNS(Social Networking Services)网站,以实名制为基础,为用户提供日志.群.即时通讯.相册.集市等丰富强大的互联网功能体验,满足用户对社交.资讯.娱乐.交易等多方面的需求. 小Q是PenguinQQ网站的管理员,他最近在进行一项有趣的研究--哪些账户是同一个人注册的.经过长时间的分析,小Q发现同一个人注册的账户名称总是很相似的,例如Penguin1,Penguin2,Penguin3--于是小Q决定先对

题目 给定一个M行N列的01矩阵,以及Q个A行B列的01矩阵,你需要求出这Q个矩阵哪些在 原矩阵中出现过. 所谓01矩阵,就是矩阵中所有元素不是0就是1. 输入 输入文件的第一行为M.N.A.B,参见题目描述. 接下来M行,每行N个字符,非0即1,描述原矩阵. 接下来一行为你要处理的询问数Q. 接下来Q个矩阵,一共Q*A行,每行B个字符,描述Q个01矩阵. 输出 你需要输出Q行,每行为0或者1,表示这个矩阵是否出现过,0表示没有出现过,1表 示出现过. 样例输入 3 3 2 2 111 000