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篇）

Codeforces587B-DP+优化

Codeforces587B-Duff in Beach 传送门题意：给出一个有l个数的序列，序列每n个数一循环，在每个循环里取一个数，一共取1-k个数，要求取出来的子序列要递增，求方案数。n×k≤1e6 l≤1e18 Solution： DP，f[i][j]表示取了i次，最后一项取的...

2021-08-18

0 355

AtCoder Code festival 2017qualC-D-dp+优化

传送门题意：给你一个字符串s，问s最少分成几块，使得每一块在经过组合后都能成为一个回文串。（|s|≤2e5） Solution：我们可以转化一下“回文串”这个定义，对于每个字母我们可以把它分别转化到二进制的0-25位，然后如果一段字符串是回文串，那么这段字符串每个字符的异或一定是0或者...

2021-08-18

0 372

Codeforces 313D- Ilya and Roads

传送门题意：给一个区间[1,n]，再给出m个区间 [li,ri] [ l i , r i ] 以及每个区间的维修成本 vi v i ，问修好k个不同的整点所需的最小成本。（n≤300，m≤1e5） Solution：这道题首先想到了朴素的 n2m n 2 m 的dp（按照右端...

2021-08-18

0 303

bzoj2427-tarjan+树形dp+背包

传送门一道练习综合代码能力的好题先把被依赖的点连向依赖这个点的点，再tarjan缩点，缩点后会形成多棵树，对每棵树进行dp，最后进行一次背包即可，注意要倒着枚举。代码： #include<cstdio> #include<iostream> #include&l...

2021-08-18

0 254

BZOJ1226-学校食堂Dining

传送门题意：中文题，非权限题。 Solution：显然不能贪心，那么考虑dp，注意到 b[i]≤7 b [ i ] ≤ 7 ，所以说可以考虑状压怎么做，再结合n<=1000，想到了一个状态：f[i][j][k]表示前i-1个人都吃过饭了，j表示后面7人和i的吃饭状态，上一个吃过饭的...

2021-08-18

0 361

Codechef MARCH14 GERALD07-莫队+并查集

传送门这道题也是bzoj3514离线版题意：给你n个点，m条边，询问k个区间[L,R]，求只保留[L,R]间的边，有多少个联通块。n,m,k<=200000 Solution：既然是离线那么显然可以搞事[滑稽]，询问区间有什么暴力方法呢？莫队！因为在图上所以每次操作不是 O（...

2021-08-18

0 384

大整数类-高精度模板

在大部分oier看来，只要有高精度的题就是毒瘤题（雾），之前的我遇到高精度的题就直接弃疗了，但是如果考试考到，这些分就白丢了，所以说抽出时间整理了一下高精度模板，主要包括：高精加，高精减，高精乘，高精除单精先说说如何定义： struct bigint{ int s[10100]; ...

2021-08-18

0 569

ASC1 E-Nice Patterns Strike Back

传送门（codeforces GYM）题意：给你一个n*m的矩形，对其进行上色，要求每个2*2的小正方形中的颜色不能相同，求方案数模p。（n<=10100,m<=5,p<=10000） Solution: 看到计数题，首先考虑组合数或者dp，组合数发现行不通，考虑dp，...

2021-08-18

0 415

BZOJ3039-玉蟾宫

权限题。题意：给一个n × m的01矩阵，求一个最大的全1矩阵，输出答案 × 3。（n,m≤1000） Solution：非常经典的一个模型，有两种方法，一种是贪心一种是dp，这里介绍一种dp方法——悬线法（安利王知昆dalao论文《浅谈用极大化思想解决最大子矩形问题》）悬线法的本质是...

2021-08-18

0 319

bzoj1101[POI2007]Zap-莫比乌斯反演

bzoj 1101[POI2007]Zap-莫比乌斯反演题意：T组数据，每组给出m，n，d 求 ∑ni=1∑nj=1[gcd(i,j)==d](T≤50000,n,m,d<=50000) Solution: 首先大家要记住一些结论： μ∗1=[n==1] 类似地， ...

2021-08-18

0 327