Cur1ed

题解

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

/ 注册

全部文章 / 题解（共29篇）

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 553

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

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

A. B-Suffix Array 题意对于字符串t，有B函数B(t1 t2 … tk ) = b1 b2 … bk 。bi 是 i 前和 ti 相同的字符的最近的位置，如果没...

2020-07-15

0 593

All with Pairs

题意：给你n个字符串，求出，f(si,sj)的意思是字符串 si 的前缀和字符串 sj 后缀最长相等部分。题解：先对所有的字符串后缀hash，用map记录每个hash值（后缀）有多少个一样的。这个地方后缀的 hash 值可以将字符串倒过来求，每次乘以base...

2020-07-14

11 631

Fake Maxpooling

题意：给出矩阵的行数n和列数m，矩阵 Aij = lcm( i , j ) ,求每个大小为k*k的子矩阵的最大值的和。题解：如果暴力求解肯定会t，所以要智取。前几天刷蓝书的时候看到这种求区间最值的可以用单调队列，这个题就是用单调队列求解。先横着算一下每个长度为k的区间的最大值记录下来，然后再把记...

2020-07-13

14 1012

简单的数据结构

感觉指针容易错，可以用数组模拟。数组开两倍（因为如果一直从前插入从0开始下标就是负数了，数组会越界），然后双指针，l记录头的位置，r记录尾的位置，因为排序不超过十次，所以sort（nlogn）不会超时的。最开始l在2e5的位置（只要数组够大，l再往后一些也是可以的），r=l; 模拟以下操作 a从前...

2020-05-19

1 578