博文

目前显示的是 十月, 2020的博文

KDTree时间复杂度

 发现自己忘了,mark一波 最近点:O(能过) 矩形搜索:O(k*n^(1-1/k))

LOJ2978 【「THUSCH 2017」杜老师】题解

见20200804讲课课件及 https://blog.csdn.net/qq_42555009/article/details/98353445

LOJ2977 【「THUSCH 2017」巧克力】题解

 https://www.cnblogs.com/yijan/p/12319010.html 这里里面概率算的有点问题,一次随机的正确率是0.03左右

LOJ2979 【「THUSCH 2017」换桌】题解

 bfs版KM直接艹过去即可 正解应该是费用流+线段树优化建图 https://www.cnblogs.com/Narh/p/10841141.html

FWT

 https://oi-wiki.org/math/poly/fwt/

洛谷P3232 【[HNOI2013]游走】题解

 https://siyuan.blog.luogu.org/solution-p3232

min-max反演的推广

 咕咕咕

min-max反演

图片
 设 $S$ 是一个集合, $max(S)$ 和 $min(S)$ 分别表示集合的最大值和最小值,那么有 $$ max(S) = \sum_{T \subseteq S}(-1)^{|T| + 1}min(T) \\ min(S) = \sum_{T \subseteq S}(-1)^{|T| + 1}max(T) $$

洛谷P3747 【 [六省联考2017]相逢是问候】题解

 https://www.luogu.com.cn/blog/user15268/solution-p3747

生成函数

 见20200730讲课课件

不同根的有理展开定理

图片
如果 $R(x) = \frac{P(x)}{Q(x)}$ ,其中 $Q(x) = q_0(1 - \rho_1x) \cdots (1 - \rho_lx)$ 而各 $\rho_i$ 均不相同,又如果 $P(x)$ 是一个次数小于 $l$ 的多项式,那么 $[x^n]R(x) = \sum_{i=1}^la_i\rho_i^n$ ,其中 $a_i = \frac{-\rho_iP(\frac{1}{\rho_i})}{Q'(\frac{1}{\rho_i})}$

TC13764 SumOverPermutations题解

https://www.cnblogs.com/HarryGuo2012/p/4777063.html

最坏复杂度为线性时间的序列第k大查找算法

 逛知乎看到有人提到算法导论上有最坏复杂度也能保证为线性的找序列第k大就去学了一波 虽然貌似没啥用,而且有重复元素还会假掉,nth_element真香( 参考自《算法导论》P123

检测未定义行为

使用clang的诊断模式: 在编译选项中加上一条: -fsanitize=undefined PS:Linux下的g++也提供这一编译选项

斐波那契循环节

https://www.cnblogs.com/cjoierShiina-Mashiro/p/11385287.html https://www.luogu.com.cn/blog/oieremtkotori/solution-p4000

二次互反律

https://www.zhihu.com/question/59572768/answer/254653900

VIJOS1891 【学姐的逛街计划】题解

所有数据均为64位无符号整数这句话是忽悠人的,int就*过去了 https://blog.csdn.net/hongkongreporter/article/details/107467406

SGU278 【Fuel】题解

图片
  latex粘上来有些问题,就直接传截图算了