emerald's blog

POj 2492 关系异或加权并查集 无法确定bug具体是男还是女,只能知道他们是同性还是异性 都合并到一个数中，通过边的权值来记录是同性还是异性 开一个数组rala[]记录点i与点i的父亲节点的关系,1代表性别不同,0代表性别相同 给出的2点肯定是异性，先判2点断根节点是否一样，相同就通过2点分别推根节点的性别是否一样，一样就正好已经在树中，不一样则不满足教授推论 根节点不一样就合并根节点，(

POJ 1182 食物链 三维关系并查集 数据大了不能cin 为什么是三维? 其实相当于映射关系，且维护在一个数组中 首先肯定想着是并查集合并一个动物类A B C,但是怎么表示猎物和天敌的关系呢？ 我想着用另一个数组表示捕猎的关系a吃b->eat[a]=b，但是发现不知道如何维护， 这里我们开2个数组来维护 捕猎 和 天敌的关系,仍然用并查集来维护， 为了方便，我们将它压缩到一个数组中i表

POJ 1988 题目问的是包括x方块的堆 下面的 所有方块的个数,而不是方块x下面所有方块的个数, 将最下面的方块作为根节点（父亲节点设置时带方向） 一个数组记录此堆的数量，另一个数组记该点下面方块的个数 find(x)时，更新所有点的下面方块个数, 询问点x的结果时，首先要find(x)，使的结果为该堆的根节点下面的方块数量 12345678910111213141516171819202

POJ 1661 带权并查集模板 并查集+统计一个点集的大小123456789101112131415161718192021222324252627282930313233343536373839#include <iostream>using namespace std;const int maxn = 3e4+10;int n,m;int prv[maxn];int tot[m

HDU 1503 题意: 给出2个字符串,求出 最短的包含该两个字符串 的字符串 2个字符串的公共部分只出现一次,求LCS串时其他的点顺带累加到串中, 注意 i , j 代表的是 a[]还是b[] 就行1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253

求最长公共子序列的长度 （对我自己说的） dp打表的原因就是为了避免子问题重复计算,而递归多次重复计算(斐波那契) 最优子结构：每一个子问题都要通过上一步递推得到该状态下的最优解,且不会影响到后面的问题 既然求长度且长度要最优,用dp来表示某个状态下的长度 如何表示某个状态下的长度,我也想不到 字符串a,b，一维数组肯定不行,用dp[i][j]表示a中[1,i]的子字符串 和 b中[1,j]子

内存爆了 将所有新生从高到底排序， 在第i行插入新生时： 人数<=该行人数 如果在第一行就直接插，不在则 需要满足 ** 该行人数 <= 上一行人数** f[0][0][0][0][0] = 1 应该为0,为了不写+1则初始化为1;123456789101112131415161718192021222324252627282930313233343536#incl

自己想出来dp，但是求最小 按多少次k这里是暴力的，应该tle了 当前dp[i] = min(dp[i-1]+1,x[i])表示，从上一步按一次或者一直按x[i]次+k使得%= i1234567891011121314151617181920212223242526272829#include <iostream>#include <algorithm>using nam

blog最近没有更新因为在做并查集专题，按专题写题解，然后又要打省赛，(省三水过，题解还没时间写，现在又要准备蓝桥国赛) 并查集模板，但是我死磕路径压缩时进行保存答案 应该邻接表存图，然后在根节点不相同的地方，去dfs找成环的路上的点, 回溯是最重要的,能够回溯说明没有找到，需要取消标记然后pop路上的点 123456789101112131415161718192021222324252627

题目 一个框由2个点来确定，读图，纪律这2个点 扫描一个框上的点，出现的点一定是后来覆盖上去的， 扫的同时建有向图， dfs求出拓扑序 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697