悠然w

分类

BZOJ(6) cdq分治(2) CodeForces(2) DP(6) dsu on tree(2) FFTNTT(4) FWT(1) KDtree(4) loj(1) luogu(6) min-max容斥(1) ODT/珂朵莉树(6) OI无关(1) 二分(2) 二分图匹配(3) 克鲁斯卡尔重构树(1) 分块(1) 分治(3) 动态点分治(1) 区间DP(1) 单调栈(8) 双指针(1) 后缀自动机(1) 奇技淫巧(3) 学习笔记(4) 容斥定理(1) 差分(3) 广搜bfs(3) 扫描线(1) 数位DP(3) 数论(1) 整体二分(1) 文化课(1) 最小生成树(1) 最短路(3) 未归档(57) 杂记(11) 树状数组(4) 树链剖分(1) 概率&期望(3) 模拟(4) 洛谷(10) 状压DP(3) 生成函数(2) 矩阵乘法&矩阵快速幂(2) 矩阵乘法&矩阵快速幂(2) 矩阵树定理(2) 线段树(4) 组合数学(1) 结论题(2) 考试总结(20) 莫队(1) 贪心(3) 随机(2) 题解(1) 高斯消元(2) 高精度(6)

/ 注册

全部文章（共232篇）

菜吉の骗分导论

1.考虑无解的情况 2.考虑输出样例 3.概率题用生成的随机数模拟 4.从dfs杀到模拟退火 5.找规律猜答案 6.打表+分段打表 7.剪枝！最后奉上面对考试题时の奇技淫巧

2021-07-21

0 0

P3527 [POI2011]MET-Meteors 整体二分

整体二分模板题不会的这里首先横跨m的陨石降落可以拆分为不跨过m的两段我们考虑第L~R场陨石降落，设\(mid=\frac{L+R}{2}\)。把mid及以前可以完成任务的国家，丢到左边继续二分，不能完成任务的丢到右边继续二分。当L=R时，此时国家的询问的答案是L。修改&...

2021-07-20

0 0

整体二分

前置芝士整体二分就是二分的进阶版类似于cdq分治(毕竟都是分治嘛) 算法流程对于一些问题，我们回答一个询问的时候，我们可以先O(n)预处理，然后二分回答。但是如果有m个询问呢？我们不能对每个询问都做一遍预处理。此时我们需要发扬一下懒人思想：预处理中的某些处理是否可以多次利用(也...

2021-07-20

0 0

P5459 [BJOI2016]回转寿司 cdq分治

P5459 [BJOI2016]回转寿司不会cdq的看这里：cdq分治：从分治到套娃转化为求 j<i，L<=sum[i]-sum[j-1]<=R的对数的问题，其中sum为前缀和经典的三维偏序，当然也可以分治后排序再用队列来维护。你也可以试试直接用数据结构来做(话说c...

2021-07-20

0 0

P3810 【模板】三维偏序（陌上花开） cdq分治

P3810 【模板】三维偏序（陌上花开）模板题而已不会cdq的看这里：cdq分治：从分治到套娃一维排序，二维cdq，三维树状数组 #include<algorithm> #include<iostream> #include<cstdio> usin...

2021-07-20

0 0

cdq分治：从归并到cdq套cdq

感谢 mlystdcall 的透彻讲解本文里没有的代码可以去这里查看前置芝士 cdq分治可以用来解决多维偏序问题优点：代替复杂数据结构，代码好写(类似归并排序)，常数小缺点：必须离线重要优点：分治过程中区间的划分可以把数值的比较转化为看看是在左区间还是右区间，省去了一维比较...

2021-07-20

0 0

loj #6287. 诗歌哈希+树状数组

这道题思路很巧妙。我们从1到n处理每个数的时候同时维护好桶 \(t[]\)。当我们处理到 \(i\) 的时候，我们将 \(t[a[i]]\) 赋值为 \(1\)。如果这时候以 \(a[i]\) 为中心的 \(t\) 极大字符串并不是一个回文串，那么就说明存在一个 \(j\) ,满足\(t...

2021-07-20

0 0

KDtree 详解

K:K维 D:dimension 维度网上没找到KDtree在OI和c++方面的详解(可能大佬们都觉得这玩意太简单懒得写？)，累死个人.jpg KDTree相当于多维的线段树算法流程我们要构建一颗二叉树。信息有多维的时候，每往下一层就换一维进行统计。第一层：先竖着切过(7,...

2021-07-18

0 0

wqs二分/带权二分/凸优化详解

前置芝士基础二分+基础DP 算法流程 wqs二分是一个神奇的东西，经常用来把限制条件转化为二分来降低时间复杂度。常见类型：在满足A物品强制恰好选择了m个情况下总价值最大如果不考虑强制恰好选择了m个这个条件，我们只考虑总价值最大，我们能够得到一个时间复杂度比较优秀的算法。现在考...

2021-07-18

0 0

P4148 简单题 KDTree

KDtree模板题不会的看这里本题离线的话就是裸的cdq分治强制在线那就按维分割，加入新点的话类似于建树过程,同时记录一下点的范围，以便询问的时候好剪枝为了防止出题人毒瘤(比如让你建的树成了一条链)，你可以每过一段时间重构一下这棵树。代码虽长，但很好写 #include<...

2021-07-18

0 0