我永远爱Codeforces

算法

ACM水题(1) DFS(1) HDU(1) 学校练习赛(3) 栈和队列(1) 算法知识点(1) 素数筛选法(1) 题解(1)

/ 注册

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

title: Cotree 2019CCPC-江西省赛-A题

题目大意：给你两棵树，在这两棵树上分别找一个点，将其连接，使得\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}dis(i,j) 最小，其中dis(i,j)表示从节点 i 到节点 j 的边数。 Part1 首先我们需要判断我们找的这两个点应该是哪个点，对于两棵树，他们的 dis ...

2019-07-27

0 701

线性基

线性基是用来求解数组子集最大异或和的一种方法。其思想与线性代数中的最大线性无关组相似。线性基的性质线性基有以下几种性质：数组中的所有元素都能够用线性基中的元素相互异或计算出来线性基中不存在异或值为0的子集满足性质1的前提下，...

2019-07-27

0 718

四大dp系列--状压dp

状压dp 状态压缩dp，是一种将复杂的状态压缩成二进制数字的算法。旅行商问题我们来看一个经典的旅行商问题：给定一个n个顶点组成的带权有向图的距离矩阵d(i,j)(INF表示没有边)。要求从顶点0出发，经过每个顶点恰好一次后再回到顶点0。问所经过的边的总权重的最小值...

2019-07-19

0 709

四大dp系列--数位dp

数位dp (本文参考于大佬博客) 数位dp是一种高速求解给定区间内符合一定条件的数的个数的算法。其基本思想为记忆化搜索。数位dp一般应用于：求出在给定区间[A,B]内，符合条件P(i)的数i的个数. 条件P(i...

2019-07-19

0 578

四大dp系列--区间dp

区间dp 区间dp有点道家的思想：一生二，二生三，三生万物。区间dp的思想就是化繁为简，将大的区间化成两个小的区间，然后递推求解。石子合并石子归并 N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子...

2019-07-19

0 756

Nim博弈--简单证明

Nim博弈是ACM入门的博弈之一，其基本描述为：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。这游戏看上去有点复杂，先从简单情况开始研究吧。...

2019-07-19

0 591