Blog
I use blog to record something.
woj1505 美丽数
题面 美丽数是指能被它的每一位非0的数字整除的正整数。 输入 包含若干组数据，每组数据一行两个数n,m，表示求[n,m]之间的美丽数的个数。 输出 对于每组数据输出一个答案，各占一行。 样例输入 1 9 12 15 样例输出 ...
AHOI2009同类分布
题面 给出两个数$a,b$，求出$[a,b]$中各位数字之和能整除原数的数的个数。 输入格式： 一行，两个整数$a$和$b$ 输出格式： 一个整数，表示答案 样例数据 输入样例 10 19 输出样例 3 解答 众所周知，题目越短，...
unknown title
题面 求给定区间 [X,Y][X,Y] 中满足下列条件的整数个数：这个数恰好等于 KK 个互不相等的 BB 的整数次幂之和。例如，设 X=15,Y=20,K=2,B=2X=15,Y=20,K=2,B=2，则有且仅有下列三个数满足题意：...
树形DP
树形DP 树的特征 有N个点，N-1条边的无向图，任意两顶点间可达 无向图中任意两个点间有且仅有一条路 一个点至多有一个前趋，但可以有多个后继 无向图中没有环 树形DP 树可以描述比较复杂的关系，对选手分...
主席树
主席树 eg1 :第k大的数woj 1903 题意：n个数，m次查询，查询任意区间第k大。 首先我们发现这个题满足区间减法。如果[1,l-1]中有k个比x小的数，[1,r]中有k2个比x小的数，那么[l,r]中一共有k2-k个数比x小...
左偏树
左偏树 左偏树是可并堆得一种实现方式。 定义一个树的斜深度为从根节点开始一直向右走走到叶子节点的步数 左偏树是一种特殊的堆，满足左儿子的斜深度大于等于右儿子。 左偏树的基本操作：合并 左偏树的性质 满足左偏的...