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

BZOJ5340: [Ctsc2018]假面-期望DP

传送门题意：有 2 个技能： 1.锁定：对一名指定的敌方单位使用，以 p 的概率对该单位造成 1 点伤害。 2.结界：在一片区域施放结界，让该区域内的所有其他单位无法动弹。如果一个单位的生命值降至 0 或 0 以下，那么该单位就会死亡。现在有 n 个敌方单位（编号从 1 至 n...

2021-08-18

0 257

AGC24 E - Sequence Growing Hard-树形DP

传送门题意：给出n,k,m，问有多少个序列组 (A0,A1,...,An) ( A 0 , A 1 , . . . , A n ) 满足以下条件：序列 Ai A i 的长度恰好为i 所有元素均在 [1,k] [ 1 , k ] 的范围内 Ai−1 A i − 1 是 Ai ...

2021-08-18

0 396

洛谷P1846 游戏-DP

传送门题意：给定两个正整数数列，你要用它们来做一个游戏：你需要对数列进行若干次操作，每一次操作，应选择两个正整数 k1 k 1 和 k2 k 2 ，并删除第一个数列的最后 k1 k 1 个数，计算出它们的和 s1 s 1 ；删除第二个数列的最后 k2 k 2 个数，计算出它们的和...

2021-08-18

0 284

洛谷P4242 树上的毒瘤-树剖+虚树+点分治

传送门题意：这棵树上有 n 个节点，每个点的初始颜色为 ci c i 。接下来进行 q 个操作： 1.修改树上某个点到另外一个点的简单路径上所有毒瘤的颜色。 2.对于给定的树上某个点集 S ，定义某个点集内的点的权值为： Wi=∑j∈ST(i,j) W i = ∑ j ∈...

2021-08-18

0 355

BZOJ4197: [Noi2015]寿司晚宴-状压DP

传送门题意： n-1个数，分别为2~n，现从中取出若干数放入两个集合中，使A集合中所有数都和B集合中的所有数互质，求满足条件的方案数。 n≤500 n ≤ 500 Solution: 根据题意，在一个集合中选择一个数相当于选择了这个数的质因子集合，所以说两个集合的质因子集合的交集必...

2021-08-18

0 339

BZOJ 3925:[Zjoi2015]地震后的幻想乡-状压DP

传送门题意：给定一个n点m边的无向图，没有重边和自环，每条边的权值为 [0,1] [ 0 , 1 ] 之间的随机变量，求最小生成树中最大边的期望权值。 n≤10,m≤n(n−1)2 n ≤ 10 , m ≤ n ( n − 1 ) 2 Solution: 题意其实可以转化为选...

2021-08-18

0 508

BZOJ2669: [cqoi2012]局部极小值-状压DP+容斥

传送门题意: 有一个n行m列的整数矩阵，其中1到 n∗m n ∗ m 之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。给出所有局部极小值的位置，判断有多少个可能的矩阵。 (1≤n≤4,1≤m≤7) ( 1 ≤ n ...

2021-08-18

0 343

BZOJ2734: [HNOI2012]集合选数-状压DP

传送门题意：给出n，求出 { 1,...,n} { 1 , . . . , n } 的所有满足以下条件的子集数量：若 x 在该子集中，则 2x 和 3x 不能在该子集中。 n≤100000 n ≤ 100000 Solution: 没见过类似做法的人见到这道题...

2021-08-18

0 266

BZOJ4565: [Haoi2016]字符合并-区间DP+状压DP

传送门题意：有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。 1≤n≤300,0≤ci≤1,1≤wi≤109,k≤8 1 ≤ n ≤ 300 , 0 ≤ c i ≤...

2021-08-18

0 365

BZOJ2727: [HNOI2012]双十字-树状数组

传送门题意：给定一个 R∗C R ∗ C 的01 矩阵，要求计算出这个 01 矩阵中有多少个双十字。双十字由两条水平的和一条竖直的“1”线段组成，要求满足以下几个限制： 1.两条水平的线段不能在相邻的两行。 2.竖直线段上端必须严格高于两条水平线段，下端必须严格低于两条水平线段。 ...

2021-08-18

0 404