(́安◞౪◟排‵)

算法

奇怪的题(19) 未归档(2) 题解(41)

/ 注册

全部文章 / 算法（共5篇）

同类分布（数位DP入门）

题目描述给出两个数a,b，求出[a,b]中各位数字之和能整除原数的数的个数。输入格式一行，两个整数a和b 输出格式一个整数，表示答案输入输出样例输入 10 19 输出 #1复制 3 说...

2019-10-15

2 619

二进制拆分优化多重背包

我们都知道多重背包可以转化为01背包来做，最朴素的就是直接通过枚举个数来判断。不过通过二进制优化，可以节省一些时间。二进制是一个神奇的东西，应用到计算机里面有很多的妙用。二进制优化的原理如下： 1、2、4可以组合出所有小于8的数； 1、2、4、8可以组合出所有小于16的数。 …… ...

2019-10-07

1 1122

单调队列优化多重背包问题

题目： https://www.acwing.com/problem/content/6/ 多重背包问题可以转换为01背包问题将 S 个数量的物品转换为 S 个单独的物品，然后做01背包问题（然后时间复杂度就爆炸了……）于是我们就来理解一下多重背包的单调队列做法...

2019-10-07

1 1483

Tarjan算法离线求LCA

需要知识 dfs序和并查集伪代码 tarjan(u) { for each(u, v) { // 枚举u的子节点v tarjan(v) merge(v, u) // 把v合并到u上 vis[v] = 1 } for each(...

2019-10-04

2 858

倍增求LCA

公共祖先问题函数名解释deep[i]：i点的深度fa[i][j]：第i点上面第2^j的祖先的编号伪代码 int lca(int x,int y) { if(deep[y]>deep[x]) swap(x,y);//假设x的深度大于y的深度 for(int...

倍增求lca

2019-10-04

2 528