POJ 2485 Highways：最小生成树 Prim

2016年07月27日 37 阅读

POJ 2485 Highways：最小生成树 Prim2015-02-25Highways：http://poj.org/problem？id=2485大意：给你一个用邻接矩阵形式存储的有n个顶点的无向图，让你求它的最小生成树并求出在这个生成树里面最大的边的权值。思路：用Prim求，判断条件改一下就行。PS：dis数组初始化的时候用memset一直RE，希望有知道怎么回事的不吝赐教，谢了~#include <stdio.h>#include ...

POJ 1789 Truck History：最小生成树 Prim

2016年07月27日 40 阅读

POJ 1789 Truck History：最小生成树 Prim2015-02-25Truck History：http://poj.org/problem？id=1789大意：用一个7位的string代表一个编号，两个编号之间的距离代表这两个编号之间不同字母的个数。一个编号只能由另一个编号变化的来，变化的字母的数量就是这两个编号之间相应的距离，现在要找出一个变化方案，使得总代价最小，也就是距离之和最小。思路：将每个字符串当成一个节点，求出每个节点之间需...

POJ 1258 Agri-Net：最小生成树 Prim 模版题

2016年07月27日 31 阅读

POJ 1258 Agri-Net：最小生成树 Prim 模版题2015-02-25Agri-Net：http://poj.org/problem？id=1258大意：新镇长竞选宣言就是将网络带到每一个农场，给出农场个数，两两之间建光缆的耗费，求所有都联通的最小耗费。思路：最小生成树，因为边比较稠密，用Prim做。PS；对于比较稠密的图，用Prim，对于比较稀疏的图，用 Kruskal。Kruskal是找边的过程，稀疏的话会比较快。#include <...

POJ 1860 Currency Exchange：最短路 Bellman-Ford

2016年07月27日 34 阅读

POJ 1860 Currency Exchange：最短路 Bellman-Ford2015-02-25Currency Exchange：http://poj.org/problem？id=1860大意：有多种货币，之间可以交换，但是需要手续费，也就是说既有汇率又有手续费。问经过交换之后能不能赚。思路：Bellman_Ford，因为要求最长路，所以松弛条件改一下就好了。Tips：3 2 1 20.0货币的数量 ...

POJ 2240 Arbitrage：最短路 Floyd

2016年07月27日 38 阅读

POJ 2240 Arbitrage：最短路 Floyd2015-02-25Arbitrage：http://poj.org/problem？id=2240大意：给你m种货币，给你m种货币兑换规则，问通过这些规则最后能不能盈利。eg：1美元换0.5英镑，1英镑换10法郎，1法郎换0.21美元，这样1美元能换0.5*10*0.21=1.05美元，净赚0.05美元。思路：用Floyd找出每两种钱之间的最大兑换关系，遍历一遍，看有没有那种钱币最后能盈利，有就输出...

POJ The Doors AND NYIST：有趣的问题

2016年07月27日 37 阅读

POJ The Doors AND NYIST：有趣的问题2015-02-25题目链接：http://acm.nyist.net/JudgeOnline/problem.php？pid=227题目分析：给你横纵坐标分别表示门所在的位置，叫你求出从起点到终点的最短距离。算法分析：该题好像有多种解法，我只说我做的。我用的是几何+图论。建模分析：1、先判断两个点之间是否可以连接。2、判断两个点是否可以链接的方法是用是否判断墙与这两点连成的线段是否相交。3、如果没...

POJ 1001 Exponentiation 无限大数的指数乘法 题解

2016年07月27日 32 阅读

POJ 1001 Exponentiation 无限大数的指数乘法 题解2015-02-25POJ做的很好，本题就是要求一个无限位大的指数乘法结果。要求基础：无限大数位相乘额外要求：处理特殊情况的能力 -- 关键是考这个能力了。所以本题的用例特别重要，再聪明的人也会疏忽某些用例的。本题对程序健壮性的考查到达了变态级别了。某人贴出的测试用例数据地址： http://poj.org/showmessage？message_id=76017有了这些用例，几下调试...

POJ：DNA Sorting 特殊的排序

2016年07月27日 34 阅读

POJ：DNA Sorting 特殊的排序2015-02-25DescriptionOne measure of ``unsortedness"" in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC"", this meas...

POJ：1006 Biorhythms 周期相遇 两个思路程序

2016年07月27日 39 阅读

POJ：1006 Biorhythms 周期相遇 两个思路程序2015-02-25DescriptionSome people believe that there are three cycles in a person"s life that start the day he or she is born. These three cycles are the physical, emotional, and intellectual cycles, ...

Codeforces：cAPS lOCK 大小写字母转换问题

2016年07月27日 35 阅读

Codeforces：cAPS lOCK 大小写字母转换问题2015-02-25按如下规则转换字母：Let"s consider that a word has been typed with the Caps lock key accidentally switched on, if:either it only contains uppercase letters;or all letters except for the first one are ...

Codeforces：Tram 列车载人问题 题解

2016年07月27日 36 阅读

Codeforces：Tram 列车载人问题 题解2015-02-25题目：一列电车，已经知道每站上下车的人数，那么问电车最小需要多大的容量才能让所有乘客都能搭车？Sample test（s）input40 32 54 24 0output6每站都是先下后上的，那么其实就是个很简单的问题了，可以使用贪心法：1 初始化第一站乘客为零2 每站计算上一站有的乘客加上上站的乘客，减去下站的乘客3 每站剩下乘客的最大量就是结果了#include <iostre...

EI judge 002 Set Intersection 算法题解

2016年07月27日 34 阅读

EI judge 002 Set Intersection 算法题解2015-02-25Set IntersectionTime limit = 5 second（s）Memory limit = 33000 KbYour task is to find the intersection of two sets of positive integers.Input The input consists of two sets of positive int...

COJ：General Election 题解

2016年07月27日 39 阅读

COJ：General Election 题解2015-02-25DescriptionGeneral Election is over, now it is time to count the votes！ There are n （2 <= n <= 5） candidates and m （1 <= m <= 100）vote regions. Given the number of votes for each candid...

COJ：Traversing Grid 遍历格子的问题 题解

2016年07月27日 37 阅读

COJ：Traversing Grid 遍历格子的问题 题解2015-02-25很有趣的题目：在一个方格上从最左上角面向右出发，每次行走一个，碰到边右走，或者碰到已经访问过的格子右转，问最后遍历所有格子的时候你是面向那个方向？For example: Consider the case with N = 3, M = 3. The path followed will be （0,0） -> （0,1） -> （0,2） -> （1,2）...

Ural - Timus - 1009 K-based Numbers 题解

2016年07月27日 41 阅读

Ural - Timus - 1009 K-based Numbers 题解2015-02-25Let’s consider K-based numbers, containing exactly N digits. We define a number to be valid if itsK-based notation doesn’t contain two successive zeros. For example:10102...

code chef：Cool Guys题解

2016年07月27日 36 阅读

code chef：Cool Guys题解2015-02-25All submissions for this problem are available.Given an integer N. Integers A and B are chosen randomly in the range [1..N]. Calculate the probability that the Greatest Common Divisor（GCD） of A and B...

code chef：Counting Matrices题解

2016年07月27日 36 阅读

code chef：Counting Matrices题解2015-02-25题目：给定一个数值，找出2*2矩阵的对角和等于N（N<2500）和行列式大于0的个数。这里是考数学知识了，程序不难，不过要精确计算好却也不容易。最原始的程序，但是会超时：void CountingMatrices（）{int T = 0, N = 0;cin>>T;while （T--）{cin>>N;long long ans = 0;for （i...

SPOJ 查找下一个回文Palindrome 算法题解

2016年07月27日 35 阅读

SPOJ 查找下一个回文Palindrome 算法题解2015-02-25给出一个数值，well，其实不是数值了，而是一大串数字，比如 98237482340328490328490324893024，非常长的数字。找出下一个Palindrome，这个Palindrome在数值上要比当前数值大（不能等于）。如：9 9 9 9->1 0 0 0 11 2 3 4 5 ->1 2 4 2 1本算法时间效率是O（n），其中n是指数值的位数，不是数值，...

code chef：Divide the Tangerine 橘子分块算法题解

2016年07月27日 32 阅读

code chef：Divide the Tangerine 橘子分块算法题解2015-02-25Once Chef decided to divide the tangerine into several parts. At first, he numbered tangerine"s segments from1 to n in the clockwise order starting from some segment. Then he intend...

SPOJ Transform the Expression 逆波兰式算法题解

2016年07月27日 39 阅读

SPOJ Transform the Expression 逆波兰式算法题解2015-02-25把带括号的一般正常的算式，转换成逆波兰式。输入和输出如下例子：Input:3（a+（b*c））（（a+b）*（z+x））（（a+t）*（（b+（a+c））^（c+d）））Output:abc*+ab+zx+*at+bac++cd+^*总结规律是很困难的事情，总结好就能很快解决：1 字母直接放结果2 ‘（’入栈3 ‘）&rsqu...