我永远爱Codeforces

分类

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

/ 注册

全部文章（共16篇）

线性基

线性基是用来求解数组子集最大异或和的一种方法。其思想与线性代数中的最大线性无关组相似。线性基的性质线性基有以下几种性质：数组中的所有元素都能够用线性基中的元素相互异或计算出来线性基中不存在异或值为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

ABAB--2019牛客暑期多校训练营(第一场)- E题

题目大意：构造一个长为的字符串，使得能从中按顺序挑出个"AB"子串和个"BA"子串，问这样的字符串一共有多少个。一个似乎比较明显的dp问题，类似于括号配对。二维dp,dp[i][j],表示前i个字符,字母A和字母B的差为j个，然后就可以进行dp了。...

2019-07-19

0 1121