POJ 1182_食物链(三倍关系) POJ 1182 食物链 三维关系并查集 数据大了不能cin 为什么是三维? 其实相当于映射关系,且维护在一个数组中 首先肯定想着是并查集合并一个动物类A B C,但是怎么表示猎物和天敌的关系呢? 我想着用另一个数组表示捕猎的关系a吃b->eat[a]=b,但是发现不知道如何维护, 这里我们开2个数组来维护 捕猎 和 天敌的关系,仍然用并查集来维护, 为了方便,我们将它压缩到一个数组 2019-05-16 算法
POJ 1988(带权并查集) POJ 1988 题目问的是包括x方块的堆 下面的 所有方块的个数,而不是方块x下面所有方块的个数, 将最下面的方块作为根节点(父亲节点设置时带方向) 一个数组记录此堆的数量,另一个数组记该点下面方块的个数 find(x)时,更新所有点的下面方块个数, 询问点x的结果时,首先要find(x),使的结果为该堆的根节点下面的方块数量 123456789101112131415161718192 2019-05-16 算法
POJ 1661(带权并查集模板) POJ 1661 带权并查集模板 并查集+统计一个点集的大小123456789101112131415161718192021222324252627282930313233343536373839#include <iostream>using namespace std;const int maxn = 3e4+10;int n,m;int prv[maxn];int tot 2019-05-16 算法
LCS模板题(HDU 1503) HDU 1503 题意: 给出2个字符串,求出 最短的包含该两个字符串 的字符串 2个字符串的公共部分只出现一次,求LCS串时其他的点顺带累加到串中, 注意 i , j 代表的是 a[]还是b[] 就行123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 2019-05-16 算法
LCS(最长公共子序列) 求最长公共子序列的长度 (对我自己说的) dp打表的原因就是为了避免子问题重复计算,而递归多次重复计算(斐波那契) 最优子结构:每一个子问题都要通过上一步递推得到该状态下的最优解,且不会影响到后面的问题 既然求长度且长度要最优,用dp来表示某个状态下的长度 如何表示某个状态下的长度,我也想不到 字符串a,b,一维数组肯定不行,用dp[i][j]表示a中[1,i]的子字符串 和 b中[ 2019-05-16 算法
poj 2279(线性 dp) 内存爆了 将所有新生从高到底排序, 在第i行插入新生时: 人数<=该行人数 如果在第一行就直接插,不在则 需要满足 ** 该行人数 <= 上一行人数** f[0][0][0][0][0] = 1 应该为0,为了不写+1则初始化为1;123456789101112131415161718192021222324252627282930313233343 2019-05-16 算法
2018蓝桥杯国赛.调手表 自己想出来dp,但是求最小 按多少次k这里是暴力的,应该tle了 当前dp[i] = min(dp[i-1]+1,x[i])表示,从上一步按一次或者一直按x[i]次+k使得%= i1234567891011121314151617181920212223242526272829#include <iostream>#include <algorithm>using 2019-05-15 算法
2017.发现环(并查集水题) blog最近没有更新因为在做并查集专题,按专题写题解,然后又要打省赛,(省三水过,题解还没时间写,现在又要准备蓝桥国赛) 并查集模板,但是我死磕路径压缩时进行保存答案 应该邻接表存图,然后在根节点不相同的地方,去dfs找成环的路上的点, 回溯是最重要的,能够回溯说明没有找到,需要取消标记然后pop路上的点 12345678910111213141516171819202122232425 2019-05-14 算法
拓扑序(poj1128) 题目 一个框由2个点来确定,读图,纪律这2个点 扫描一个框上的点,出现的点一定是后来覆盖上去的, 扫的同时建有向图, dfs求出拓扑序 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686 2019-05-05 算法 拓扑序
dfs bfs拓扑序列+判断 想要得到拓扑序的图一定是有向图. 拓扑序列虽然不止1个,但都满足,每个点的前驱后继点的顺序,某点的后继点在拓扑序中不可能出现在该点的前面, 基本思想: 拓扑序列满足,入度为0的点进入序列,且该点的出边点的入度-1, 如果该点出边的入度为0,则重复第1步 邻接表+bfs 开一个数组记录所有点的入度,将入度为0的点加入到队列 取出队头,加入到拓扑序. 更新出边的点的入度,判断是否为0,为0 2019-05-05 算法 拓扑序列