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

BZOJ 1070 修车-神奇网络流

传送门题意：中文题。 Solution：因为这道题每个工人可以维修多个汽车，所以说没法直接用费用流，我们先想一个简单的贪心思路：假如说我们考虑一个工人的情况，那么他修车所需的时间为： t1+(t1+t2)+(t1+t2+t3)+…+(t1+…+tn) 变形一下该式...

2021-08-18

0 301

Codeforces 899F Letters Removin-线段树

传送门题意：给一个字符串和m个操作，每次给出l,r,c，把字符串中l-r这段区间的字符为c的字符删掉，求最后的字符串。（n,m<=2e5） Solution：此题显然不能离线搞，那么有什么动态的优秀的数据结构呢？我们一定会先想到线段树，我们可以维护每个区间剩余字符的个数siz和区...

2021-08-18

0 358

学习笔记——中国剩余定理（CRT）

CRT在算法竞赛中算是一个比较重要的模块，他的基本形式如下：给出n个式子： x≡a1 mod p1 x ≡ a 1 m o d p 1 x≡a2 mod p2 x ≡ a 2 m o d p 2 x≡a3 mo...

2021-08-18

0 494

hdu6039 Gear Up-线段树

题意：给出n个齿轮的半径和n个齿轮之间的关系（角速度相等或线速度相等），两种操作，第一种操作：修改一个齿轮的半径，第二种操作：给一个齿轮角速度，输出最大的角速度，答案取ln（自然对数）。 Solution：我们随意画一个图感受一下：（粗边表示角速度相等，细边表示线速度相等，图中维护...

2021-08-18

0 370

HDU6074 Phone Call-并查集

题意：给你一棵树，m个条件，每个条件给出a,b,c,d,w，表示a到b和c到d路径上的点互相到达需要w的代价，现求从1号点出发能到达哪些点以及最小代价。 Solution：不难发现这是要构造一颗最小生成树，把w按照从小到大排一遍序，对于每个条件，求出a,b的LCA和c,d的LCA，把经过他...

2021-08-18

0 293

HDU-6070 Dirt Ratio-线段树+分数规划

题意：给你一个数组，找一段区间使得区间内不同数的个数与区间长度的比值最小。 Solution：这是一道经典的分数规划题，考虑二分答案k，那么我们的目标就是找一段区间使得val/len<=k，val是区间内不同的数的个数，len是区间长度，转化一下可以得到val-k*len<=0，我...

2021-08-18

0 242

Codeforces908D New Year andArbitrary Arrangement-dp

传送门题意：给出 k,p1,p2 k , p 1 , p 2 ，一开始串为空，每次有 p1p1+p2 p 1 p 1 + p 2 的概率在串中加一个a， p2p1+p2 p 2 p 1 + p 2 的概率在串中加一个b，当串中有k个为ab的子序列停止加字符，求停止加字符后串中为ab...

2021-08-18

0 342

BZOJ5120无限之环-费用流

传送门题意：看原题吧，想不出比原题更好的描述了- - Solution：一开始思考过用网络流，但是想不出如何建图，最后还是去看了题解QwQ，建图思路很妙啊，我们先把每个点拆成四个小点，分别对应上，下，左，右，然后对应每种水管在点内分别建图（细节大家可以结合代码思考一下），由于这是一个二分图...

2021-08-18

0 283

BZOJ1901 dynamic ranking-带修主席树

题意：维护一个序列，支持单点修改，区间查询第k小。 Solution（普通的主席树相信大家都会，如果没学过建议先去学学再来看这篇文章）：我们回忆一下不带修改的主席树是怎么求出答案的：每一棵主席树维护是前缀和，然后左右端点的主席树差分一下就能求出排名。对于这个问题，我们可以先考虑如何维护一个...

2021-08-18

0 475

hdu6068 Classic Quotation-哈希

传送门题意：给定一个长度为n的串s，一个长度为m的串t。有k次询问，每次给定l,r，在[1,l]中随机一个整数i，在[r,n]中随机一个整数j，问t在s[1…i]+s[j…n]中的出现次数。 n,k<=100000，m<=100 Solution：答案可以分成三部分 ...

2021-08-18

0 328