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

BZOJ5250: [2018多省省队联测]秘密袭击-树形DP

传送门题意：给一棵n个点的树，每个点的点权在 1到 W之间求所有连通块的权值第k大的和模 64123 k≤n≤1666,W≤1666 Solution：正解貌似是线段树合并+FFT 但是我并不会写QAQ 所以说我们考虑暴力碾标算：我们可以考虑每个点对于答案的贡献：我们把...

2021-08-18

0 207

BZOJ2459:残缺的字符串-FFT

权限题题意：有两个仅包含小写字母的字符串A和B，其中A串长度为m，B串长度为n。这两个串已经老化了，每个串都有不同程度的残缺。你想对这两个串重新进行匹配，其中A为模板串，那么现在问题来了，请回答，对于B的每一个位置i，从这个位置开始连续m个字符形成的子串是否可能与A串完全匹配? 1&...

2021-08-18

0 223

BZOJ3742: Painting-树形DP+费用流

权限题。题意：给出一颗n个节点的树，要给每一条边染一个1~n-1的颜色，染颜色i的代价为i，要求同一个节点连出的所有边所染颜色都互不相同，求一个为整棵树染色的方案，使得代价之和尽量小 n<=150 n <= 150 Solution: 网络流真的是万能的… f[x...

2021-08-18

0 414

BZOJ1063: [Noi2008]道路设计-树形DP

传送门题意： Z国是一棵树，为了使Z国的交通更加便利顺畅，现决定在Z国的公路系统中确定若干条规划路线，将其中的公路全部改建为铁路。我们定义每条规划路线为一个长度大于1的城市序列，每个城市在该序列中最多出现一次。任意两条规划路线不能有公共部分。一般情况下是不可能将所有的公路修建为铁路的，因此从有...

2021-08-18

0 261

BZOJ2159: Crash 的文明世界-树形DP+第二类斯特林数

传送门题意：给你k和一棵n个点的树，每个边边权为1，对每个点i求 ∑nj=1dis(i,j)k ∑ j = 1 n d i s ( i , j ) k n≤50000 k≤150 n ≤ 50000 k ≤ 150 Solution: 首先有一个结论： xn=∑ni=1C...

2021-08-18

0 352

BZOJ5093: [Lydsy1711月赛]图的价值-斯特林数+FFT

传送门题意： “简单无向图”是指无重边、无自环的无向图（不一定连通）。一个带标号的图的价值定义为每个点度数的k次方的和。给定n和k，请计算所有n个点的带标号的简单无向图的价值之和。因为答案很大，请对998244353取模输出。 1≤n≤109,1≤k≤200000 1 ≤ n...

2021-08-18

0 293

BZOJ4833: [Lydsy1704月赛]最小公倍佩尔数-数论

传送门题意：令 (1+2–√)n=e(n)+f(n)∗2–√ ( 1 + 2 ) n = e ( n ) + f ( n ) ∗ 2 ,其中 e(n),f(n) e ( n ) , f ( n ) 都是整数。令 g(n) g ( n ) 表示 f(1),f(2)…f(n) f (...

2021-08-18

0 333

BZOJ4836: [Lydsy1704月赛]二元运算-分治FFT

传送门题意：定义二元运算 opt 满足 x opt y={ x+yx−y,,x<yx≥y x o p t y = { x + y , x < y x − y , x ≥ y 现在给定一个长为 n 的数列 a 和一个长为 m ...

2021-08-18

0 438

BZOJ 2448: 挖油-区间DP+单调队列

题意： [0,x]中全是1，判断[1,n]中的点i中是0还是1需要权值 ai a i ，最坏情况下求得到x的最小权值 n<=2000 n <= 2000 Solution: f[i][j] f [ i ] [ j ] 表示只考虑[i,j]，最坏情况下求得到x的最小权值...

2021-08-18

0 389

BZOJ5339: [TJOI2018]教科书般的亵渎-组合数学

传送门题意：在炉石传说中有这样的一个场面：n个随从，血量为1~n，现在去除m个随从，然后开始释放“亵渎”。每使用一张“亵渎”会获得一定的分数，分数计算如下：在使用一张“亵渎”之后，每一个被亵渎造成伤害的怪会产生 xk x k 的分数，其中x是造成伤害前怪的血量，k是需要杀死所有怪物所需的“...

2021-08-18

0 478