现在位置: 首页 > 算法 > 文章
2017年10月18日 算法 ⁄ 共 2183字 评论关闭
 题目大意:在等级差距的范围之内,用最少的金币换取酋长的答应。  解题思路:将每个物品看作是一个节点,每个节点包含2个值,这个节点所代表的物品的价值,这个物品的等级,  因为有些物品可能通过几种方式来换取,所以这不是树,而是一张图,一张永久静态图。  是图,还是静态的,那么就好办了。我们先可以不管接下去的步骤会是如何,先建图。  题目所求的最少金币,可以从图中看出来,它求的是物品1即节点1到其他点的最短...
阅读全文
2017年10月18日 算法 ⁄ 共 2656字 评论关闭
    这个题目纠结的我要死。。。    首先是最大流的第一次应用,  我一直认为是求最大流那错了。。。   事实上,那里确实出错了一次。。。不过,那也无关紧要,主要是对那个字符串的处理,即将题目给的输入转化成一个图。    这个过程,我仍然没有完全的清楚。所以导致了卡的太久。。。    这个题,开始我自己想的时候,是想到了二分图,其实二分图,也差不多。     最主要,最关键的还是建图。。。这个图你转化不过来的话,没...
阅读全文
2017年10月18日 算法 ⁄ 共 1444字 评论关闭
这个题,第一次做的时候,感觉好麻烦,       那个时候,不怎么清楚拓扑排序。     所以,那个时候借鉴网友的代码,用到了Floyd。 拓扑排序就是 1、找入度为0的点 2、将入度为0的点输出,然后将这点的出边全部删了。 3、继续循环。      现在想来感觉真的麻烦多了。  于是自己亲手来A。    题目的大意明了:    每输入一组数据,就用拓扑排序一次。    如果排序出来了。 就保存这个值。也就是在第 i 组数据时,确定了顺序...
阅读全文
2017年10月18日 算法 ⁄ 共 853字 评论关闭
最小路径覆盖问题:用尽量少的不相交的简单路径覆盖有向无环图的所有顶点 将每个顶点分成两个,分别在X集和Y集,如果存在有向边(a,b),对应在图中就有(Xa,Yb)。 建好图,匈牙利算法一上,1A。 参考资料:http://wenku.baidu.com/view/3e756f335a8102d276a22f16.html 代码奉上: #include <iostream> #include <cstring> #include <cstdio> using namespace std; #define N 101 #define MIN -0xfffff...
阅读全文
2017年10月18日 算法 ⁄ 共 2275字 评论关闭
题意:给出K个数,p1,p2,……pk,不一定是素数,给这些数添加指数,0-10之间,最终的乘积为n,他的所有因子和为m,问是否存在一个m为2的幂,如果有多个输出最大的指数,如果没有输出NO。 梅森素数  我们把满足 E = 2 ^ i - 1 的素数E称作梅森素数。关于梅森素数,有一个重要的定理:“一个数能够写成几个不重复的梅森素数的乘积” 等价于 “这个数的约数和是2的幂次”,但是不能重复,比如说3是梅森素数,9就不满足约数和为2的幂。还有...
阅读全文
2017年10月18日 算法 ⁄ 共 735字 评论关闭
题意:给出一个数S,从1到N个数,每个数前面可以是负号或者是正号,这样累加起来,结果可以等于S,问最小的N是多少。 题解:因为从1一直加到n的值(假设为sum(n))等于sum的n是最小的。所以我们先算出sum(n)大于等于sum的那个n。 这样我们可以得出一个值m = sum(n) - sum.如果m==0那么n就是我们要求的最小的n。否则 因为你减一个数相当于在sum(n)里减去这个数的两倍。 所以如果m是奇数的话,那么这时你不可能在前面把某些+号变...
阅读全文
2017年10月18日 算法 ⁄ 共 1171字 评论关闭
题解:给定一串字符串,按杨辉三角一次从上到下,从左到右摆放,每个字符最多出现3次。问那些字符构成了一个等边三角形。将其输出之,如没有输出loser。 题解:暴力根据杨辉三角的性质,将每个字符赋予一个坐标(根据数学公式,下面给出),然后从a到z判断是否有三点,有就判断是否等边。输出答案即可。 数学公式: 将第一个点设置成(10000,10000) 其后的点是没下降一层 y 要减去3,x减去根号3。这是根据等边三角形的性质,...
阅读全文
2017年10月18日 算法 ⁄ 共 1876字 评论关闭
终止状态是从初始状态由开关组合影响而形成的,那么就有一个等式使得初始状态可以到达终止状态, 例如a,b,c三个开关 E[a] = (xa * mp[a][a]) ^ (xb * mp[a][b]) ^ (xc*map[a][c]) ^ S[a] E[b] = (xa * mp[b][a]) ^ (xb * mp[b][b]) ^ (xc*map[b][c]) ^ S[b] E[c] = (xa * mp[c ][a]) ^ (xb * mp[c][b]) ^ (xc*map[c][c]) ^ S[c] E数组为开关的终止状态(a,b,c为开关),S数组为开关的初始状态,mp[i][j] 代表j开关是否影响i开关...
阅读全文
2017年10月18日 算法 ⁄ 共 1636字 评论关闭
n(1<=n<=10000) 头牛,有 m(1<=m<=50000) 个推举关系。推举关系具有传递性,即 A 推举 B, B 推举 C,那么 A 也推举 C 问你,能够得到所有牛推举的牛有多少头? 题解:强连通分支+缩点 强连通分支为最大的连通子图,在这个子图中任意两点都是可达的。 在一个强连通分支里面,根据推举关系可知,这个强连通分支里的所有的牛都能得到其他所有的牛的推举。 我们将题目给的推举关系,看成是牛群推举图里的一条...
阅读全文
2017年10月18日 算法 ⁄ 共 765字 评论关闭
题目大意: 题目给出n个点,求出有多少点满足没有横纵坐标同时大于等于这个点的个数。也就是在这所有的点中,这样的点有多少个?什么样的点呢?设这个点(x0,y0),那么如果不存在(x,y)使得x>=x0并且y>=y0,那么这就算一个点,求出所有这样的点。   题解:对于任意一点,以x轴为水平线,对这点来说,如果他要是king点(即题目要求的点),那么它的y必须比在它后面,也就是x比它大或者等于它的所有点的y都要大,而x比它...
阅读全文