uva专题
uva 10055 uva 10071 uva 10300（水题两三道）
情歌两三首，水题两三道。 好久没敲代码了为暑假大作战热热身。 uva 10055 Hashmat the Brave Warrior 求俩数相减。 两个debug的地方，一个是longlong，一个是输入顺序。 代码： #include<stdio.h>int main(){long long a, b;//debugwhile(scanf("%lld%lld", &
poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)
poj 3259： 题意：John的农场里n块地，m条路连接两块地，w个虫洞，虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来，看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码： #include<stdio.h>const int MaxN = 501;//农场数const int
poj 2349 Arctic Network uva 10369（prim or kruscal最小生成树）
题目很麻烦，因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚，不适合新手。自己写一个。 题意：给你点的坐标，然后两点间可以有两种方式来通信：第一种是卫星通信，第二种是无线电通信。 卫星通信：任何两个有卫星频道的点间都可以直接建立连接，与点间的距离无关； 无线电通信：两个点之间的距离不能超过D，无线电收发器的功率越大，D越大，越昂贵。 计算无线电收发器D
uva 10387 Billiard（简单几何）
题意是一个球从矩形的中点出发，告诉你小球与矩形两条边的碰撞次数与小球回到原点的时间，求小球出发时的角度和小球的速度。 简单的几何问题，小球每与竖边碰撞一次，向右扩展一个相同的矩形；每与横边碰撞一次，向上扩展一个相同的矩形。 可以发现，扩展矩形的路径和在当前矩形中的每一段路径相同，当小球回到出发点时，一条直线的路径刚好经过最后一个扩展矩形的中心点。 最后扩展的路径和横边竖边恰好组成一个直
uva 10061 How many zero's and how many digits ?（不同进制阶乘末尾几个0）+poj 1401
题意是求在base进制下的 n！的结果有几位数，末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零，以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是： 1. n阶位数：直接 lg（n！）就是得数的位数。 2. n阶末尾0的个数：由于2 * 5 将会在得数中以0的形式存在，所以计算2或者计算5，由于因子中出现5必然出现2，所以直接一
uva 568 Just the Facts（n！打表递推）
题意是求n！的末尾第一个不为0的数字。 不用大数，特别的处理。 代码： #include <stdio.h>const int maxn = 10000 + 1;int f[maxn];int main(){#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALf[0] = 1;for (int i = 1; i <=
uva 575 Skew Binary（位运算）
求第一个以（2^(k+1)-1)为进制的数。 数据不大，可以直接搞。 代码： #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =
uva 10014 Simple calculations（数学推导）
直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导，第二次没有继续下去。 代码： #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf
uva 10916 Factstone Benchmark（打表）
题意是求 k ！ <= 2 ^ n ，的最小k。 由于n比较大，大到 2 ^ 20 次方，所以 2 ^ 2 ^ 20比较难算，所以做一些基础的数学变换。 对不等式两边同时取log2，得： log2（k ! ） <= log2（2 ^ n）= n，即：log2(1) + log2(2) + log2 (3) + log2(4) + ... + log2(k) <= n ，其中 n 为 2 ^
uva 10025 The ? 1 ? 2 ? ... ? n = k problem（数学）
题意是 ? 1 ? 2 ? ... ? n = k 式子中给k，? 处可以填 + 也可以填 - ，问最小满足条件的n。 e.g k = 12 - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明，令 S（n） = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n，搜出当 S（n） >=
uva 11044 Searching for Nessy（小学数学）
题意是给出一个n*m的格子，求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码： #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col
uva 10801（乘电梯dijkstra）
题意： 给几个电梯，电梯0 ~ n-1分别可以到达很多层楼。 换乘电梯需要60s时间。 问从0层到target层最小的时间。 解析： 将进入第0层的电梯60s也算上，最后减。 坑点是如果target为0输出0。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algori
uva 10099（floyd变式）
题意： 有一个导游要带着一群旅客从一个城市到达另一个城市，每个城市之间有最大的旅客流量限制。 问最少几趟能将这些旅客从一个城市搞到另一个城市。 解析： 用floyd找出最小流量中的最大边，然后次数就是 ceil（总人数 / 最大承载量 - 1），-1的意思是导游每次也要在车上。 ps.老司机哭晕在厕所 代码： #include <iostream>#includ
uva 10048(floyd变式）
题意： 求两个点之间经过的路径中最大噪声最小的值。 解析： floyd的变式，每次取g[i][k] g[k][j]中的大边与当前边g[i][j]比较，取小。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#includ
hdu 1102 uva 10397（最小生成树prim）
hdu 1102: 题意： 给一个邻接矩阵，给一些村庄间已经修的路，问最小生成树。 解析： 把已经修的路的权值改为0，套个prim（）。 注意prim 最外层循坏为n-1。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri
uva 10154 DP 叠乌龟
题意： 给你几只乌龟，每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析： 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠，状态转移方程： dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]
uva 10131 最长子序列
题意： 给大象的体重和智商，求体重按从大到小，智商从高到低的最长子序列，并输出路径。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect
uva 10130 简单背包
题意： 背包和 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>
uva 10118 dP
题意： 给4列篮子，每次从某一列开始无放回拿蜡烛放入篮子里，并且篮子最多只能放5支蜡烛，数字代表蜡烛的颜色。 当拿出当前颜色的蜡烛在篮子里存在时，猪脚可以把蜡烛带回家。 问最多拿多少只蜡烛。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cs
uva 1342 欧拉定理（计算几何模板）
题意： 给几个点，把这几个点用直线连起来，求这些直线把平面分成了几个。 解析： 欧拉定理： 顶点数 + 面数 - 边数= 2。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc
uva 11178 计算集合模板题
题意： 求三角形行三个角三等分点射线交出的内三角形坐标。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <
uva 10069 DP + 大数加法
代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>#include <cl
uva 10066 LCS
题意： 最长公共子序列。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include
uva 10029 HASH + DP
题意： 给一个字典，里面有好多单词。单词可以由增加、删除、变换，变成另一个单词，问能变换的最长单词长度。 解析： HASH+dp 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc
Commando War-uva 贪心
大意：给你N个任务，你交代他需要J时间，完成他需要B时间，问怎么搭配可以使全部问题完成时话的时间最少 思路：贪心算法，先做完成时间长的，完成时间相同的话先做交代时间长的，用了一下结构体二级快排 #include<stdio.h>#include<string.h>#include<stdlib.h>#define MAX_SIZE 1000 + 10struct Time{int
Minimal coverage -uva 覆盖线段，贪心
一道经典的贪心问题，具体方法就是将（an,bn)区间，按照an从小到大的顺序进行排序，之后从0开始， 取最大的有效区间，这里用到了结构体的快排，否则可能会超时. #include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 100000 + 10#define BOTTOM -50000 - 10str