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

Codeforces 274E. Mirror Room-模拟+STL

传送门题意： n×m的网格上，有k个镜子，光线反射规则如下：现在给出初始光线的位置以及光线的射出方向，求光线能经过多少个格子的中心光线走到边缘也会被反射 n,m,k<=1e5 Solution: 暴力模拟即可，但是大家可能会想到一点：光线可能会经过重复的砖块的中心，但是...

2021-08-18

0 374

Codeforces 932E. Team Work-数学

传送门题意：给定n,k,求 ∑nr=1Crnrk ∑ r = 1 n C n r r k n<=1e9,k<=5e3 n <= 1 e 9 , k <= 5 e 3 Solution: 冥思苦想数论方式……..最后GG 题解让人眼前一亮：定义函数...

2021-08-18

0 380

AtCoder AGC14E-Blue and Red Tree 并查集+启发式合并+STL

传送门题意：给出一颗树，初始每条边是蓝色，可以选择一条全是蓝色的路径，删去其中一条边，在这条路径的两个端点连上一条红色边，现给你两棵树，判断第一棵树能不能变成第二棵树（n<=1e5） Solution：我们只考虑蓝色边，注意到这是一棵树，所以每次删除一条边后会把图分成两部分，...

2021-08-18

0 440

HDU6109 数据分割-并查集+启发式合并

传送门题意：给出一些限制形如 xi≠xj x i ≠ x j 或 xi=xj x i = x j 判断最早出现矛盾的位置（n<=1e5） Solution：等于关系满足传递性，可以用并查集来维护而不等关系呢？可以这样做：把相等元素放在一个集合里，每个集合看做一个...

2021-08-18

0 414

Codeforces 331D3-线段树+扫描线+倍增

传送门题意：在n*n的坐标内给出一些箭头，给出一些出发点、出发方向以及出发时间，遇到箭头就需要改变方向为箭头的方向，对每个出发点求最后能走到哪数据范围1e5 Solution：口胡起来特别简单：对于不同方向的箭头和出发点分别用线段树+扫描线建出相应的图，最后在建出的图上跑倍增就可以...

2021-08-18

0 291

Codeforces 939F.Cutlet-单调队列优化dp

传送门题意：有2∗n的时间去煎一块两面的肉,给你k个可以翻转的区间 [li,ri] [ l i , r i ] ,可以在区间内翻转任意次, 保证区间不相交问是否存在合法的方案使得两面恰好都只煎了 n 分钟,并求最小翻转次数 n<=100000,k<=100 Soluti...

2021-08-18

0 652

Codeforces 935E.Fafa and Ancient Mathematics-树形dp

传送门题意：给出一个算式，由括号和小于10的正整数和问号组成，问号是算式中的符号，现给出原式中加号的个数p和减号的个数m，对于所有填放方式对应的结果，求最大值。算式长度<=1e4 min(p,m)<=100 Solution：考试时这种题居然没想到转换模型…好菜啊我 ...

2021-08-18

0 375

Codeforces 935F. Fafa and Array-线段树

传送门题意：给出一个序列A，定义函数 f(A)=∑n−1i=1|ai−ai+1| f ( A ) = ∑ i = 1 n − 1 | a i − a i + 1 | 先给出两种操作： 1.在区间[l,r]内找一个位置，使得把这个位置的值加上x后，f(A)最大，求这个最大值 2.把区...

2021-08-18

0 346

Codeforces 201D.Brand New Problem-状压dp

传送门题意：给出一个有n个字符串的匹配串，和m个有k个字符串的文本串，将匹配串进行全排列和文本串进行匹配，找到能全匹配成功的最小的逆序对数 n<=15,m<=10,k<=500000 Solution：通过哈希+map把字符串变成数字那么问题就转化成了把一个1到...

2021-08-18

0 351

Codeoforces 201E. Thoroughly Bureaucratic Organization-贪心+二分+脑洞题

传送门题意：有一个长度为n的排列A，你想通过一些询问知道它是什么样的. 每次你构造一个长度为k(0<k≤m)的序列B,满足 1 ≤ B i ≤ n 1≤B_i≤n 1≤Bi≤n且B中没有相同的元素，系统会根据序列B生成一个长度为k的序列C，Ci的值为 A B i A_{B_i} AB...

2021-08-18

0 431