Browsed by
Category: ACM Algorithm

ACM&算法

HDU 1496 Equations 数值hash

HDU 1496 Equations 数值hash

题目: Equations Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5612    Accepted Submission(s): 2228 Problem Description Consider equations having the following form: a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 a, b, c, d are integers from the interval [-50,50] and any of them cannot be 0. It is consider a solution a system ( x1,x2,x3,x4 ) that verifies the equation, xi is an integer from [-100,100] and xi != 0, any i ∈{1,2,3,4}. Determine how many solutions satisfy the given equation. Input The input…

Read More Read More

HDU 1142 A Walk Through The Forest

HDU 1142 A Walk Through The Forest

Problem Description A Walk Through the Forest Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5891    Accepted Submission(s): 2168 Problem Description Jimmy experiences a lot of stress at work these days, especially since his accident made working difficult. To relax after a hard day, he likes to walk home. To make things even nicer, his office is on one side of a forest, and his house is on the other. A nice walk through the forest, seeing the…

Read More Read More

POJ 1300 Door Man 欧拉路&字符串处理TAT

POJ 1300 Door Man 欧拉路&字符串处理TAT

Door Man Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 2140 Accepted: 859 Description You are a butler in a large mansion. This mansion has so many rooms that they are merely referred to by number (room 0, 1, 2, 3, etc…). Your master is a particularly absent-minded lout and continually leaves doors open throughout a particular floor of the house. Over the years, you have mastered the art of traveling in a single path through the sloppy rooms and…

Read More Read More

把基本输入 scanf getchar gets 的区别

把基本输入 scanf getchar gets 的区别

在写控制台程序的时候,难免会遇到各种各样的输入格式读取,下面比较一下 scanf  getchar 和 gets的区别 首先我们要知道,当用户从键盘键入一个字符串的时候,就会在IO缓冲区内写入信息,这个缓冲区是一个队列,  我们用下面几段代码来检验一下,不同函数对缓冲区的读取效果 这一段代码是测试这三个函数到底读取了哪些字符 代码如下 /************************************************************************* > File Name: a.cpp > Author: VOID_133 > ################### > Mail: ################### > Created Time: 2014年10月26日 星期日 00时43分53秒 ************************************************************************/ #include<iostream> #include<algorithm> #include<cstdio> #include<vector> #include<cstring> #include<map> #include<queue> #include<stack> #include<string> #include<cstdlib> #include<ctime> #include<set> using namespace std; int main(void) { char s[30]; //scanf(“%s”,s); //gets(s); int len=strlen(s); for(int i=0;i<len;i++) { if(s[i]==’n’) s[i]=’#’; if(s[i]==’t’) s[i]=’$’;                 if(s[i]==’ ‘) s[i]=’@’; } printf(“%s”,s); return 0; } 这段代码中,首先用注释掉的scanf来接受输入  输入 test加回车后 输出的只有…

Read More Read More

HDU 1116 Play on words 欧拉路+并查集

HDU 1116 Play on words 欧拉路+并查集

Problem Description Play on Words Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5576    Accepted Submission(s): 1831 Problem Description Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us. There is a large number of magnetic plates on every door. Every plate has one word written on it….

Read More Read More

POJ 1860 Currency Exchange

POJ 1860 Currency Exchange

Currency Exchange Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 20346 Accepted: 7298 Description Several currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchange operations only with these currencies. There can be several points specializing in the same pair of currencies. Each point has its own exchange rates, exchange rate of A to B is the quantity of B you get for 1A. Also each exchange point…

Read More Read More

单源最短路分析及算法实现

单源最短路分析及算法实现

最短路径的理解性解释:Va 到 Vb 的最短路的意义是 在一个带权图中,从节点Va到节点Vb的权值总和最小的路径 就是Va 到 Vb的最短路,这个权值可以是距离 时间 等各种量 理解最短路径首先要理解什么是最优子结构  最优子结构是在各种动态规划,贪心以及最短路算法中都很关键的一个结构。  最优子结构的意思就是,问题局部的最优解包含在全局的最优解之中,这样才能把问题分成较小的问题先进行处理。 可以通过反证法证明,最短路问题是最优子结构,方法详见 算法导论第三版 P375 在计算最短路之前,还要考虑一个特殊情况,如果在图中存在负权值的边,就可能有一种比较特殊的情况了: 如果 图中存在负权值的边的话但不存在和的权值为负的环,那么 每一个路径的最短距离都可以精确求出,没有问题,不过,如果图中存在和为负权值的环,最短路就没有意义了  因为 总可以通过经过完整的一次环,来得到更小的一个权值 ,理论上 这个最短路径的大小为  -∞ 求最短路的某些算法假设输入的边权值全为非负 如 Dijkstra算法,而还有一些算法只要没有负权值的环就可以 如 Bellman Ford算法 ,如果存在负权值的环的环也可以通过算法报告出来 先试试如何应用这个算法,再继续研究算法的正确性;                             //参考POJ 1860  

POJ 题目分类整理 [转]

POJ 题目分类整理 [转]

OJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串 (poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书 page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学: 1.加法原理和乘法原理. 2.排列组合. 3.递推关系. (POJ3252,poj1850,poj1019,poj1942) (2)数论. 1.素数与整除问题 2.进制位. 3.同余模运算. (poj2635, poj3292,poj1845,poj2115) (3)计算方法. 1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122) 七.计算几何学. (1)几何公式. (2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039) (3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交) (poj1408,poj1584) (4)凸包. (poj2187,poj1113) 中级: 一.基本算法: (1)C++的标准模版库的应用. (poj3096,poj3007) (2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706) 二.图算法:…

Read More Read More

POJ 1018 DP入门

POJ 1018 DP入门

http://blog.csdn.net/xiaoxiaoluo/article/details/7787168      代码完全参考这个blog  刚开始学习DP真是很艰难阿,  题目如下:   We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices. By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all…

Read More Read More

DP题目列表

DP题目列表

转载非原创 ※最近更新:Poj斜率优化题目 1180,2018,3709   列表一:经典题目题号: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1191,1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740, 1742, 1887, 1926, 1936, 1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018, 2029, 2039, 2063, 2081, 2082, 2181, 2184, 2192, 2231, 2279, 2329, 2336, 2346, 2353, 2355, 2356, 2385, 2392, 2424, 不易: 1019, 1037, 1080, 1112, 1141, 1170, 1192, 1239, 1655, 1695, 1707, 1733(区间减法加并查集), 1737, 1837, 1850, 1920(加强版汉罗塔), 1934(全部最长公共子序列), 1964(最大矩形面积,O(n*m)算法), 2138, 2151, 2161, 2178, 推荐: 1015, 1635, 1636(挺好的), 1671, 1682, 1692(优化), 1704, 1717, 1722, 1726, 1732, 1770, 1821, 1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411 列表二:完整DP题目列表 1015 Jury Compromise 1029 False coin 1036 Gangsters 1037 A decorative fence 1038 Bugs Integrated, Inc. 1042 Gone Fishing 1050 To the Max 1062 昂贵的聘礼 1074 Parallel Expectations 1080 Human Gene Functions 1088 滑雪 1093 Formatting Text 1112 Team Them Up! 1141 Brackets Sequence 1143 Number Game 1157 LITTLE SHOP OF FLOWERS 1159 Palindrome 1160 Post Office 1163 The Triangle 1170 Shopping Offers 1178 Camelot 1179 Polygon 1180 Batch Scheduling 1185 炮兵阵地 1187 陨石的秘密 1189 钉子和小球 1191 棋盘分割 1192 最优连通子集 1208 The Blocks Problem 1239 Increasing Sequences 1240 Pre-Post-erous! 1276 Cash Machine 1293 Duty Free Shop 1322 Chocolate 1323 Game Prediction 1338 Ugly Numbers 1390 Blocks 1414 Life Line 1432 Decoding Morse Sequences 1456 Supermarket 1458 Common Subsequence 1475 Pushing Boxes 1485 Fast Food 1505 Copying Books 1513 Scheduling Lectures 1579 Function Run Fun 1609 Tiling Up Blocks 1631 Bridging signals 2分+DP NLOGN 1633 Gladiators 1635 Subway tree systems 1636 Prison rearrangement 1644 To Bet or Not To Bet 1649 Market Place 1651 Multiplication Puzzle 1655 Balancing Act 1661 Help Jimmy 1664 放苹果 1671 Rhyme Schemes 1682 Clans on the Three Gorges 1690 (Your)((Term)((Project)))…

Read More Read More