现在位置: 首页 > 算法 > 文章
2017年02月22日 算法 ⁄ 共 2088字 评论关闭
哎哎。。刚刚开始学习并査集不久,就遇到这样一个问题,相当头疼,于是就搜解题报告,后面发现有一个人的思路给人很明了的赶脚....于是...盗版了过来.. 第一个代码是把rank存放敌友关系,我有点没理解find过程中的rank的转变,如果有知道的可以指点在下, 第二个代码就是加一个数组存放敌人,在这个过程中,根据 D a b 我们就把a,b互相存为敌人,合并过程中就合并对方的敌人,也就是敌人的敌人是自己的朋友,然后就转变成了并...
阅读全文
2017年02月22日 算法 ⁄ 共 1317字 评论关闭
题意:这里有N种货币,分别记为1~N,有M种货币交换的方式,每一种方式有A,B两种钱币,有RAB, CAB, RBA and CBA,四个数,表示交换率, Nick手上有其中的一种货币S,货币S的钱数为V,问你能否通过一定次数的钱币交换让Nick手中的钱增加 分析: 这里是要判断回路,那么可以用spfa 加一个入队次数的数组来判别是否有回路,也可以用bellman,这里要注意的是,松弛操作不能死用模板了,, 要有一点点的转变,这里我们可以这样处理...
阅读全文
2017年02月22日 算法 ⁄ 共 966字 评论关闭
比较简答的回路判断 我们把最后的几个是虫洞的单向路的W权值置为负数,其他的就是模板啦 // AC 248k 141ms #include<cstdio> #include<queue> using namespace std; struct node { int to,time,next; }edge[5202]; int head[502]; int tol; void add(int st,int end,int time) { edge[tol].time=time; edge[tol].to=end; edge[tol].next=head[st]; head[st]=tol++; } int N,M,W; void init() { int i; ...
阅读全文
2017年02月22日 算法 ⁄ 共 3776字 评论关闭
在学习了tarjan算法求解强连通分量之后就接触到强连通缩点,但是就是不知道怎么运用tarjan算法来找缩点,后来接触了几个有关缩点的题目,才了解到缩点的关键所在; 对于一个图,我们进行强连通分量求解之后,进行缩点操作,缩点的最大好处在于把一个杂乱无章的有向图变成一个有向无环图,而在有向无环图中,有两种点比较特殊:一种是入度为 0 的点,另一种是 出度为 0 的点。我们把入度为0的点就叫做根,出度为0的点叫做叶子,...
阅读全文
欧几里德算法: 欧几里德就是辗转相除法,调用这个gcd(a,b)这个函数求解a,b的最大公约数 公式: gcd(a,b)=gcd(b,a%b);并且gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|) 代码: int gcd(int a,int b)//递归 { if(b==0) return a; return gcd(b,a%b); } int gcd(int a,int b)//递归简化 { return b ? gcd(b,a%b) : a; } int gcd(int a, int b)//迭代 { while(b != 0) {   int r...
阅读全文
2017年02月22日 算法 ⁄ 共 1966字 评论关闭
一:二叉堆以及相关操作 二:例题 二叉堆是一个逻辑结构像堆的一个数据结构 对于这个堆,采用一维数组的存储方式,因为二叉堆是一颗完全二叉树,在一维数组的存储中可以这样表示,任何一节点下标 i,左子结点下标为 2*i , 右子结点下标为 2*i+1,其性质满足一节点的值大于(或小于,大于就是最大堆,小于就是最小堆)子树的每一个节点的值,但是对于子节点2*i 和 2*i+1之间的大小并没有关系,二叉堆有如下操作: 都用大根堆做...
阅读全文
2017年02月22日 算法 ⁄ 共 1637字 评论关闭
前两天花了时间理解了nyoj的586疯牛和nyoj619青蛙过河,满以为自己能重新写出这道题。。。谁知道。。。。。 题意:有m本书,k个人来抄,每本书有一个书本页数;求使得k个人抄完的最大页数最小,并且每个人都至少要抄一本,然后输出抄书的方案   分析: 这里又涉及到前面nyoj的586疯牛和nyoj619青蛙过河说过的最大值中的最小值,  用前面的例子去理解比较方便 1.我们应该先用二分+贪心算出一个最大页数的最小值--这里和前面的类...
阅读全文
2017年02月22日 算法 ⁄ 共 5733字 评论关闭
通过之前的博文《白话01背包》对01背包学习进行总结,几个01背包入门题解,给出顺序为难度梯度: poj3624Charm Bracelet 完全模板题 这里给出 一维和二维的三份代码...为什么有三份....??对于二维的,有两份,一维的一份..... 二维第一份: #include<stdio.h> #include<string.h> #define MAX1 3410 #define MAX2 12885 int main() { int i,j; int N,M; int w[MAX1],va[MAX1],dp[MAX1][MAX2]; scanf("%d%...
阅读全文
2017年02月22日 算法 ⁄ 共 1492字 评论关闭
第一眼看到这个题目就想到用字符串模拟....自己嫩得跟什么似得.....后面问了学长...自己想了很久,然后这里给出详细结题报告:个人觉得这个对于刚接触 dp 的人来说是一个比较好的经典题目,很有dp的思维(对于目前菜菜的我来说) 题意:给你三个字符串,A、B、C,问你A和B能否组成C,当然是有要求的,那就是所有组成C的字母一定要按照A和B的顺序来,不能乱,意思就是从C中按顺序把组成A(或B)的所有字母拿出来,剩下的就是B(或A) ...
阅读全文
动态规划的经典题型: 1.最大连续和 2.最大子矩阵和 最后几个例题:hdu1003 模板题                        poj1050=hdu1081 最大连续和: 最大连续和指的是对于一个一维数组,我们要求出其中 i 到 j 个连续的元素和最大,如(6,-1,5,4,-7),最大连续和为14,是第1个到第4个元素之和,那么对于这样一个问题,我们可以这样处理: 设 ans 为最后的最大和,初始化为负无穷大,x,y为我们ans最大的时候的区间(有的题目中不要用到),...
阅读全文