Cur1ed

分类

ac自动机(12) cf(1) KMP&拓展KMP(22) 后缀数组(21) 回文串(2) 图论(9) 字典树(6) 字符串(2) 未归档(87) 计算几何(1) 计算机网络实验(1) 题解(29)

/ 注册

全部文章（共193篇）

Easygoing Single Tune Circulation（后缀自动机+字典树）

题意给定n个字符串 s[i]，再给出m个查询的字符串 t[i]，问 t[i] 是否为某个 s[i] 循环无限次的子串。题解分成两种情况 ① t[i] 比 s[j] 短，这个时候可以用后缀自动机，把每个 s[j] 重复一次，然后放到SAM中，这样直接每次直接查询就好了。...

2020-08-01

1 695

carpet

题意有一个n*m的地毯，aij表示地毯每格的元素，bij表示地毯每格的价格，要求选取一块价格最大值最小的地毯，并且这块地毯无限铺开之后，原地毯是其子矩阵。题解先找到这个矩阵的最小循环节子矩阵，求一下每行的循环节长度用map记录，取出现次数为m并且循环节长度最小的；每列也求一下...

2020-07-29

8 623

2020牛客暑期多校训练营（第六场）

BCEGK B. Binary Vector 题意大概是说有一个A={0,1}，每天可以在An (n维空间) 中生成一个新的二进制向量，n天中生成的向量线性无关的概率是，求。题解由于这N个向量线性无关,则这N个向量张成的空间秩为N,考虑将每次随机的向量加...

2020-07-27

0 625

2020牛客暑期多校训练营（第五场）

DEFI D. Drop Voicing 题意：给你一个数列，你可以进行两种操作。 Drop-2: 将n-1位置的数移到第一个位置，变成 pn−1, p1, p2, …, pn−3, pn−2, p...

2020-07-25

0 565

我不爱她

前几天打牛客的多校，今天写这个题发现是基本一样的题，改成多组输入，map改成unordered_map（不然会t），最后的乘平方改成乘一次就好了，不要取模。先对所有的字符串后缀hash，用unordered_map记录每个hash值（后缀）有多少个一样的。这个地方后缀的 hash 值可以将字...

2020-07-23

2 602

Haeder Gcd Problem

H. Haeder Gcd Problem 题意集合A和B都是{1,2,.....,n}的子集，A∩B≠∅。问A和B最多有多少对数GCD(Ap，Bq)>1。题解所有gcd>1的两个数肯定是倍数关系，最小肯定是本身和2倍。越大的数能和他匹配的就会越少，为了简单，从大的数往小的数匹配。...

2020-07-21

2 483

2020牛客暑期多校训练营（第四场）

BCFH B. Basic God Problem 题意给出c和n，求fc（n）。题解递归到最后 fc 函数肯定等于1，那么就变成了求c被乘了几次，只要找到 x 最多能被分解成多少个数相乘就好了。预处理用线性筛求出每个数最多能被分解成多少个数相乘，快速幂...

2020-07-20

0 802

2020牛客暑期多校训练营（第三场）

ABCFL A. Clam and Fish 题意一个游戏有n次，每次有四种类型： 0：没有鱼也没有蛤蜊 1：没有鱼有一个蛤蜊 2：有一个鱼没有蛤蜊 3：有一个鱼和一个蛤蜊游戏每次可以执行下面4中操作中的一种： 1：用蛤蜊换一报鱼饵 2：直接抓一条鱼 3：用鱼饵钓一条鱼 4：不做任何操作问n次...

2020-07-18

0 559

Operation Love

题意：t组测试，每次测试按顺时针或逆时针给20个点，是一个手的形状，问是左手还是右手。题解：这个题可以用凸包解，板子求出凸包的所有点记录下来，然后求一下长度为6的边（即大拇指）的下一条边是不是底下长度为9的边。是的话就是右手，否则为左手。但是，这个题他卡精度，两个边长相等判断的时候要用fabs(d...

2020-07-18

6 873

Boundary

题意：给你n个点的坐标，问最多有多少个点可以在同一个圆上，（0,0）必须在这个圆上。题解：三个点确定一个圆，所以暴力枚举两个点和（0,0）组成的圆，如果三个点不共线的话，用圆心公式求出圆心，然后用map记录以当前点为圆心的点圆的个数，边记录边判断有多少个圆圆心是同一个点，取最大值就好了。 #in...

2020-07-15

4 760