Fizzmy

分类

--------DP--------(1) CDQ分治(1) DP(11) FFT(4) z-box(6) 主席树(1) 二分(2) 分数规划(1) 分治(1) 区间DP(3) 博弈论(2) 后缀数组(2) 哈希(1) 学习笔记(2) 容斥(1) 并查集(4) 强连通分量(1) 扫描线(1) 数位DP(3) 数论(12) 斯特林数(1) 暴力(2) 最小生成树(1) 最短路(1) 期望DP(4) 未归档(5) 树形dp(4) 模拟(1) 模板(3) 游记(1) 状态压缩(8) 线段树(12) 组合数学(1) 网络流(4) 脑洞(8) 莫比乌斯反演(2) 贡献法(3) 题解(2)

/ 注册

全部文章（共123篇）

学习笔记——带修莫队

简介普通的莫队算法相信大家都熟悉，那么如果有些问题加上修改操作是否可以用莫队维护呢？下面就介绍一种 O(n53) O ( n 5 3 ) 的带修莫队算法。算法详解只需要再维护一维表示操作的时间即可然后我们按照左边界所在块为第一关键字、右边界所在块为第二关键字，操作时间为第三关键字排...

2021-08-18

0 283

BZOJ2127 happiness-最小割

传送门题意：高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可...

2021-08-18

0 470

Codeforce 762E.Radio stations-动态开点线段树 or CDQ分治

传送门题意：数轴上有 n 个广播站。第 i 个广播站坐标为 xi x i ，信号半径为 ri r i ，频率为 fi f i 。 1.如果称两个广播站i和j（i< j）是可互相到达的，那么 min(ri,rj)>=|xi−xj| m i n ( r i , r j ) ...

2021-08-18

0 481

CS Academy 71E.Losing Nim-dp+容斥

传送门题意：如果一个包含i个可重复元素的数组合法，那么这个数组中每个元素的取值范围是[1,n]，这i个元素的和为n，异或和为0。给出一个数n，对于 i=[1,n] i = [ 1 , n ] ，求包含i个可重复元素的数组的方案数，对p取模 n<=500,p<=2^30 ...

2021-08-18

0 299

CodeChef-Little Party-爆搜+剪枝

题意：戳这里 Solution：我们可以把大小写分别看成0和1，这样我们就可以转化一下问题：构造一个最短的布尔函数，使得将m个01串作为变量代入这个布尔函数后，布尔函数的值都为1。这样就变成了一个加权覆盖子集的最小覆盖问题。因为布尔函数是由一堆“或”连起来的“和”，所以我们的一个浅显的...

2021-08-18

0 275

AGC019 E.Shuffle and Swap-DP+NTT

传送门题意：给出两个01串A,b，记 ai a i 表示A中1的出现位置， bi b i 表示B中1的出现位置，将a数组和b数组打乱后依次次交换 Aai A a i 和 Abi A b i ，求有几种方式使得A=B 字符串长度<=10000 Solution：我们可以把...

2021-08-18

0 448

BZOJ1717.产奶的模式-后缀数组+倍增

权限题。题意：求一个字符串中出现超过k次的最长子串，可重叠（n<=20000） Solution：先用后缀数组跑出height 然后我们知道一个性质：任意两个后缀的最长公共前缀就是它们之间所有height取min 那么这个问题就相当于枚举每个长为k-1的区间，在区间内部求...

2021-08-18

0 377

51nod-1893 Travel-主席树+hash

传送门题意：给出一张n个点，m条边的无向图，每个点有点权，求一条从1到n的路径，使得经过的点中点权大的个数尽量少 n<=100000 Solution：相当于求一条将这条路径中的所有点权排序后，字典序最小的路径用主席树维护当前路径经过不同点权的次数，再运用hash可以在lo...

2021-08-18

0 254

BZOJ2124 等差子序列-线段树+hash

传送门题意：给出一个N的排列，问是否存在一个长度至少为3的等差子序列 n<=10000 Solution：注意到我们给出的是一个排列，而且我们只需要找长度为3的子序列即可那么我们可以枚举中间项x，用01串S和T来表示x前面的数中[1,x-1]和[x+1,x+x-1]是否出现...

2021-08-18

0 367

BZOJ4816 数字表格-莫比乌斯反演

传送门题意：定义 f[0]=0,f[1]=1,f[n]=f[n−1]+f[n−2],n≥2 f [ 0 ] = 0 , f [ 1 ] = 1 , f [ n ] = f [ n − 1 ] + f [ n − 2 ] , n ≥ 2 给出n,m，求 Πni=1Πmj=1f[gcd(i...

2021-08-18

0 347