K-D树

看到BZOJ上有道新数据结构题,A的人挺多的,但感觉不太会做,于是发现了这个数据结构

继续阅读

卢卡斯定理大组合数取模及扩展

卢卡斯定理内容:Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)=n!/(m!*(n-m)!)*Lucas(n/p,m/p,p)

当p<10^5次时可以用卢卡斯定理进行组合数取模

继续阅读

启发式搜索

继续阅读

置换群与Póyla定理

一直想研究一下可爱的置换,但是蒟蒻数学水平极低,意志力极差,当看到这些复杂的定义时,就失去了看下去的勇气

 

继续阅读

高斯消元&线性基

由于期望DP要用到高斯消元,这几天我学习了一下高斯消元,终于差不多学会了

继续阅读

用树链剖分解决LCA问题

周日和黄主力吃饭的时候他问我,你会用树链剖分写LCA吗?我说,树链剖分上的LCA和普通倍增LCA有什么区别吗?然后被黄主力大骂一通。。

继续阅读

树套树

省选前想把CTSC2008树链剖分+区间线段数+权值平衡树写出来,但是失败了,代码也找不到了,于是找了到二逼的区间线段数+权值平衡树做做,没想到做了4个多小时。。。。但终于学会了写树套树的正确姿势

继续阅读

BZOJ刷题记录

终于刷到800题啦 终于刷进第一页啦

阅读全文

DP单调性优化

单调性似乎一直没有解决,水平一直停留在只会单调求最长上升子序列的阶段。。。。

继续阅读

启发式合并

这两天做了两道“启发式合并”的题,似乎“启发式合并”就是每次把节点数小的依次放到节点数大的地方,对只有合并操作的题能做到logn的时间复杂度

继续阅读

强连通分量&2-SAT&双联通分量&Dorminator Tree

这两天把tarjan算法好好理解学习了下,应该大致搞懂了

继续阅读

可并堆

看到BZOJ2809做对的人挺多,想了一会感觉要写Splay什么的,代码不可能只有1KB,就看了看标算,发现并深深爱上了这个算法

继续阅读