文章

基本思路 将坐标 $(a_i,i)$看作一个点，那么本题转化为每次资磁插入一个点，查询已插入的点中，离某个点的曼哈顿距离小于等于 $k$的点数。 曼哈顿距离转切比雪夫距离的套路，将坐标变成 $(a_i+i,a_i-i)$后，两点的距离变成 $max(|x_1-x_2|,|y_1-y_2|)$，那么查 阅读更多…

感觉哪里不好下手？ 猎人死了的话，$\sum w_i$会变。 怎么办呢？嗯，那么死了的猎人不下场，选到死了的猎人，就重新选一次。 现在 1 号猎人是最后一个死的，也就是我们要除掉别的猎人在 1 号之后死的情况。假设有几个猎人在 1 号之后死，他们的权值和为 $S$，那么这种情况的概率就是： $$f( 阅读更多…

有大佬曰过，像这种全排列计数类的问题，常常是子集 DP。 也就是可以考虑，对于树上每一个节点 x，它所在的子树，在图上的映射集合是 s，并且 x 对应着图上的点 i 的状态 f(x,i,s)，进行 DP。 这样复杂度还是太高。 发现复杂度瓶颈是在枚举子树的映射集合那里，而之所以要这么做，是因为树上点 阅读更多…

//其实 XZY 本来做的是要求询问一次复杂度 $log _ 2N$的然而 XZY 太菜了只能找了个数据范围更小的题来做了。。。 1. 题目 传送门=￣ω￣= 2. 题解 emmmm… 就是询问排名第 $k$大子串 用后缀自动机做一发 得到后缀自动机的 DAG 以后 DP 得到从某个点出 阅读更多…

假设给出数列 a，求一个单调不降的数列 b，要求最小化 $\sum |a _ i -b _ i|$。 如果 a 是单调不减的数列，考虑 b 的构造方式，如图： 那么所有的 b 要取同一个值。先假定取当前 a 序列的中位数（中位数的定义是将 a 从小到大排序后，第 $\lceil \frac{n}{2 阅读更多…

下面代码与字都是蒟蒻自己一个一个字打得，如有错误，请大佬指出（我实在太菜了）这有神犇 boish 的 树状数组心得 写得比这一篇好多了 前置知识：搞懂树状数组 树状数组最基本的操作：单点修改 ($logN$)+区间查询 ($logN$)，上方已经有了，这里就不提了； 其实树状数组还有很多作用 废话 阅读更多…

//我真的没有口吃，标题里的第一个后缀自动机是题目名称，第二个是解决问题用的算法 1. 题目 传送门=￣ω￣= 2. 题解 OvO 模板题做到要崩溃 好吧不吐槽了 自动机上每个点对应了一个 $endpos$集合，也对应了一个字符串集合 $S$，集合 $S$里的字符串在原串中的结尾位置都在且仅在 $e 阅读更多…

（真的是动态动态规划，我没有口吃！！！）1. 题目 传送门=￣ω￣=（当然 BZOJ 传题真是十分不负责任的，可以去看洛谷传送门=￣ω￣=）2. 题解 题面看了半天才看懂。。。真不知道写题面的大爷语文谁教的。。。 大概就是给你一个长度为 $n$的环，你任选环上一点作为起点，每次可以顺时针走一步 阅读更多…

1. 题目 传送门=￣ω￣= 双倍经验：SPOJ-CIRU（记得把精度 $eps$调成 $10^{-7}$）2. 题解 自适应 Simpson 积分板题 然而其实这题卡辛普森积分。。。 $eps$需要开到 $10^{-13}$。。。 惊了.jpg 所以此题需要卡卡常，直接搞很难过.avi（我最后 阅读更多…

一开始看这道题，感觉是个水题…… 显然，我们只用考虑每次离开一个矩形时的 y 坐标。如果我们离开一个矩形时，走的是相邻两矩形相交的那条线段，我们称其为一次 “关键通过”，通过点称为 “关键点”。那么一次通过，要么走一个前面的关键点和后面一个关键点，离开点连线交点，要么 “关键 阅读更多…