(HDUACM2010版_11)搜索入门

acm知识点转一个搞ACM需要的掌握的算法.要注意,ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的.第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打出来.1.最短路(Floyd、Dijstra,BellmanFord)2.最小生成树(先写个prim,kruscal要用并查集，不好写)3.大数（高精度）加减乘除4.二分查找. (代码可在五行以内)5.叉乘、判线段相交、然后写个凸包.6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.8. 调用系统的qsort, 技巧很多，慢慢掌握.9. 任意进制间的转换第二阶段：练习复杂一点，但也较常用的算法。

如：1. 二分图匹配（匈牙利），最小路径覆盖2. 网络流，最小费用流。

3. 线段树.4. 并查集。

5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp6.博弈类算法。

博弈树，二进制法等。

7.最大团，最大独立集。

8.判断点在多边形内。

9. 差分约束系统.10. 双向广度搜索、A*算法，最小耗散优先.相关的知识图论路径问题0/1边权最短路径BFS非负边权最短路径（Dijkstra）可以用Dijkstra解决问题的特征负边权最短路径Bellman-FordBellman-Ford的Yen-氏优化差分约束系统Floyd广义路径问题传递闭包极小极大距离 / 极大极小距离Euler Path / Tour圈套圈算法混合图的 Euler Path / Tour Hamilton Path / Tour特殊图的Hamilton Path / Tour 构造生成树问题最小生成树第k小生成树最优比率生成树0/1分数规划度限制生成树连通性问题强大的DFS算法无向图连通性割点割边二连通分支有向图连通性强连通分支2-SAT最小点基有向无环图拓扑排序有向无环图与动态规划的关系二分图匹配问题一般图问题与二分图问题的转换思路最大匹配有向图的最小路径覆盖0 / 1矩阵的最小覆盖完备匹配最优匹配稳定婚姻网络流问题网络流模型的简单特征和与线性规划的关系最大流最小割定理最大流问题有上下界的最大流问题循环流最小费用最大流 / 最大费用最大流弦图的性质和判定组合数学解决组合数学问题时常用的思想逼近递推 / 动态规划概率问题Polya定理计算几何 / 解析几何计算几何的核心：叉积 / 面积解析几何的主力：复数基本形点直线，线段多边形凸多边形 / 凸包凸包算法的引进，卷包裹法Graham扫描法水平序的引进，共线凸包的补丁完美凸包算法相关判定两直线相交两线段相交点在任意多边形内的判定点在凸多边形内的判定经典问题最小外接圆近似O(n)的最小外接圆算法点集直径旋转卡壳，对踵点多边形的三角剖分数学 / 数论最大公约数Euclid算法扩展的Euclid算法同余方程 / 二元一次不定方程同余方程组线性方程组高斯消元法解mod 2域上的线性方程组整系数方程组的精确解法矩阵行列式的计算利用矩阵乘法快速计算递推关系分数分数树连分数逼近数论计算求N的约数个数求phi(N)求约数和快速数论变换……素数问题概率判素算法概率因子分解数据结构组织结构二叉堆左偏树二项树胜者树跳跃表样式图标斜堆reap统计结构树状数组虚二叉树线段树矩形面积并圆形面积并关系结构Hash表并查集路径压缩思想的应用STL中的数据结构vectordequeset / map动态规划 / 记忆化搜索动态规划和记忆化搜索在思考方式上的区别最长子序列系列问题最长不下降子序列最长公共子序列最长公共不下降子序列一类NP问题的动态规划解法树型动态规划背包问题动态规划的优化四边形不等式函数的凸凹性状态设计规划方向线性规划常用思想二分最小表示法串KMP Trie结构后缀树/后缀数组 LCA/RMQ有限状态自动机理论排序选择/冒泡快速排序堆排序归并排序基数排序拓扑排序排序网络初期:一.基本算法:(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)二.图算法:(1)差分约束系统的建立和求解. (poj1201,poj2983)(2)最小费用最大流(poj2516,poj2516,poj2195)(3)双连通分量(poj2942)(4)强连通分支及其缩点.(poj2186)(5)图的割边和割点(poj3352)(6)最小割模型、网络流规约(poj3308, )三.数据结构.(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)(2)静态二叉检索树. (poj2482,poj2352)(3)树状树组(poj1195,poj3321)(4)RMQ. (poj3264,poj3368)(5)并查集的高级应用. (poj1703,2492)(6)KMP算法. (poj1961,poj2406)四.搜索(1)最优化剪枝和可行性剪枝(2)搜索的技巧和优化 (poj3411,poj1724)(3)记忆化搜索(poj3373,poj1691)五.动态规划(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj303 4)(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)六.数学(1)组合数学:1.容斥原理.2.抽屉原理.3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数.(2)数学.1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)2.概率问题. (poj3071,poj3440)3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)(3)计算方法.1.0/1分数规划. (poj2976)2.三分法求解单峰(单谷)的极值.3.矩阵法(poj3150,poj3422,poj3070)4.迭代逼近(poj3301)(4)随机化算法(poj3318,poj2454)(5)杂题.(poj1870,poj3296,poj3286,poj1095)七.计算几何学.(1)坐标离散化.(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)(3)多边形的内核(半平面交)(poj3130,poj3335)(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高级:一.基本算法要求:(1)代码快速写成,精简但不失风格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)(2)保证正确性和高效性. poj3434二.图算法:(1)度限制最小生成树和第K最短路. (poj1639)(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)(poj3155,poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446(3)最优比率生成树. (poj2728)(4)最小树形图(poj3164)(5)次小生成树.(6)无向图、有向图的最小环三.数据结构.(1)trie图的建立和应用. (poj2778)(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法(RMQ+dfs)).(poj1330)(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)(4)左偏树(可合并堆).(5)后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)四.搜索(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)五.动态规划(1)需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)(2)四边形不等式理论.(3)较难的状态DP(poj3133)六.数学(1)组合数学.1.MoBius反演(poj2888,poj2154)2.偏序关系理论.(2)博奕论.1.极大极小过程(poj3317,poj1085)2.Nim问题.七.计算几何学.(1)半平面求交(poj3384,poj2540)(2)可视图的建立(poj2966)(3)点集最小圆覆盖.(4)对踵点(poj2079)八.综合题.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj331 5,poj2148,poj1263)。

ACM培训资料目录第一篇入门篇 (3)第1章新手入门 (5)1ACM国际大学生程序设计竞赛简介 (5)2ACM竞赛需要的知识 (8)3团队配合 (14)4练习、练习、再练习 (15)5对新手的一些建议 (16)第2章C++语言介绍 (22)1C++简介 (22)2变量 (23)3C++数据类型 (25)4C++操作符 (30)5数组 (35)6字符数组 (38)7字串操作函数 (41)8过程控制 (45)9C++中的函数 (54)10函数规则 (59)第3章STL简介 (61)1泛型程序设计 (61)2STL 的组成 (67)第二篇算法篇 (102)第1章基本算法 (103)1算法初步 (103)2分治算法 (115)3搜索算法 (124)4贪婪算法 (135)第2章进阶算法 (165)1数论基础 (165)2图论算法 (180)3计算几何基础 (222)第三篇实践篇 (246)第1章《多边形》 (247)第2章《灌溉问题》 (255)第3章《L GAME》 (263)第4章《NUMBER》解题报告 (271)第5章《J OBS》解题报告 (275)第6章《包裹运送》 (283)第7章《桶的摆放》 (290)第一篇入门篇练就坚实的基础，总有一天……我们可以草木皆兵！第1章新手入门1ACM国际大学生程序设计竞赛简介1.1背景与历史1970年在美国TexasA&M大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。

1977年，该项竞赛被分为两个级别，即区域赛和总决赛，这便是现代ACM竞赛的开始。

在亚洲、美国、欧洲、太平洋地区均设有区域赛点。

1995至1996年，来自世界各地的一千多支高校的代表队参加了ACM区域竞赛。

ACM 大学生程序设计竞赛由美国计算机协会（ACM）举办，旨在向全世界的大学生提供一个展示和锻炼其解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大学生程序设计竞赛。

零起点学算法87——打印所有低于平均分的分数Time Limit:1000MS Memory Limit:65536KTotal Submit:4704 Accepted:1633Description输入n个成绩，打印出所有低于平均分的分数(注意：ave = s/n中s 为float或ave = (float)s/n)。

Input多个测试数据每个测试数据一行，在这行中先输入分数的个数n(1<=n<=100),然后紧跟着输入n个整数（代表分数）Output对于每个测试数据，输出一行按照输入顺序输出所有低于(<)平均分的分数，中间用一个空格隔开，如果没有低于平均分的那么只输出一个空行Sample Input3 40 50 602 90 805 10 10 90 80Sample Output408010 10∙#include<stdio.h>∙int main()∙{∙ int n,i,a[100];∙ float ave,s;∙ while(scanf("%d",&n)!=EOF)∙ {∙ for(i=0;i<n;i++)∙ {∙ scanf("%d",&a[i]);∙ s=s+a[i];∙ }∙ ave=s*1.0/n;∙ for(i=0;i<n;i++)∙ {∙ if(a[i]<ave)∙ printf("%d ",a[i]);∙ else∙ printf("");∙ }∙ printf("\n");∙ s=0;∙ }∙ return 0;∙}平方和与立方和Time Limit:1000MS Memory Limit:65536KTotal Submit:3105 Accepted:1446Description给定一段连续的整数，求出他们中所有偶数的平方和以及所有奇数的立方和。

ACM/ICPC新手入门指南前言：这篇指南不对ACM/ICPC国际大学生程序设计竞赛进行介绍，计算机学子如果不了解的可以在百度上进行搜索查询，这里介绍的只是一个计算机学生想要在ACM/ICPC里进行发展的初学者。

内容比较简单通俗，完全是给新接触的人看的，已经接触过的请飘过，该干嘛的干嘛去。

语言关:要进行程序设计，也就必然要熟悉编程语言，只要掌握了一门语言，就可以进行ACM训练了。

一般通用语言如C、C++、JAVA都可以，这三种语言都有自己的优势和缺点，C在效率方面比较好；但C++封装了输入输出流，方便了我们的操作也减少出错的可能性，而且C++提供了非常强大的标准模版库（STL），使得很多在C上实现起来比较麻烦的代码，在C++上却非常方便；JAVA在大型工程和安全方面都有比较独特的优势，但在ACM里面却不是一种优秀的语言，因为JAVA的执行效率要比C、C++慢很多，如果题目限时比较紧的话，就不适合用JAVA，当然JAVA为我们提供了很方便的高精度运算（大整数运算），所以个人认为，刚学完C的可以用纯C来写训练，在训练过程中可以学学C++，有时间的把STL也好好学学，这样可以减少很多不必要的劳动。

初次接触ACM训练的同学经常会遇到问题，就是输入和输出问题，所以如果对语言的输入输出问题不是很熟悉的话，要抽几天时间重点看看,特别有些初学者在输出时总会输出冗余信息，可能认为有交互性吧，但这是ACM不允许的，它不需要任何交互性。

不严格按照题目要求进行输入输出的程序是无法通过系统测试的。

熟悉在线评测系统在线评测系统，英文叫Online Judge，（简称OJ）里面提供了很多题目给我们平时训练之用。

这里以浙江大学的在线评测系统为例，网址是 先在上面进行注册，注册完后就可以进行题目的训练了，点击主页上的“Problems”，就可以看到里面的题库，可以选任何一个题来做，里面的题目不是由易到难进行排列，而初学者要选择比较简单的题目来做。

ACM基础算法入门教程ACM（ACM International Collegiate Programming Contest）是国际大学生程序设计竞赛的缩写，被认为是计算机领域最有权威和最具挑战性的竞赛之一、ACM竞赛要求参赛者在规定的时间内，根据给出的问题，编写出能在规定时间内运行并给出正确答案的程序。

参加ACM竞赛不仅可以锻炼算法思维，提高编程实力，还可以拓宽知识领域和增加竞争力。

在这个ACM基础算法入门教程中，我们将介绍一些常用的基础算法和数据结构，帮助初学者更好地理解和掌握ACM竞赛所需的算法知识。

一、排序算法排序算法是ACM竞赛中最常用的算法之一，能够帮助我们按照一定的规则将数据进行排序，从而解决一些需要有序数据的问题。

1.冒泡排序：通过多次比较和交换来实现，每次迭代将最大的值沉到最底部。

2.快速排序：选择一个基准元素将数组分为两部分，一部分都小于基准元素，一部分都大于基准元素，递归排序子数组。

3.归并排序：将数组不断二分，将相邻两个子数组排序后再合并成一个有序数组。

4.插入排序：从第二个元素开始，依次将元素插入已排序的子数组中。

二、查找算法查找算法可以帮助我们在一组数据中找到目标元素，从而解决一些需要查找特定数据的问题。

1.顺序查找：逐个扫描数据，直到找到目标元素或扫描结束为止。

2.二分查找：对已排序的数组进行查找，不断将数组二分直到找到目标元素的位置。

3.哈希查找：通过计算数据的哈希值找到对应的存储位置，实现快速查找。

三、字符串匹配算法字符串匹配算法可以帮助我们在一组字符串中寻找特定模式的子字符串，从而解决一些需要在字符串中查找其中一种规律的问题。

1.暴力匹配算法：对目标字符串的每个位置，逐个将模式串进行匹配，直到找到或匹配结束为止。

2.KMP算法：通过已匹配的部分信息，尽量减少字符比较的次数。

3. Boyer-Moore算法：通过预先计算模式串中每个字符最后出现位置的表格，以及坏字符规则和好后缀规则，来实现快速匹配。

目录一、数学问题 (4)1.精度计算——大数阶乘 (4)2.精度计算——乘法（大数乘小数） (4)3.精度计算——乘法（大数乘大数） (5)4.精度计算——加法 (6)5.精度计算——减法 (7)6.任意进制转换 (8)7.最大公约数、最小公倍数 (9)8.组合序列 (10)9.快速傅立叶变换（FFT） (10)10.Ronberg 算法计算积分 (12)11.行列式计算 (14)12.求排列组合数 (15)13.求某一天星期几 (15)14.卡特兰(Catalan) 数列原理 (16)15.杨辉三角 (16)16.全排列 (17)17.匈牙利算法----最大匹配问题 (18)18.最佳匹配KM 算法 (20)二、字符串处理 (22)1.字符串替换 (22)2.字符串查找 (23)3.字符串截取 (24)4.LCS-最大公共子串长度 (24)5.LCS-最大公共子串长度 (25)6.数字转换为字符 (26)三、计算几何 (27)1.叉乘法求任意多边形面积 (27)2.求三角形面积 (27)3.两矢量间角度 (28)4.两点距离（2D、3D） (28)5.射向法判断点是否在多边形内部 (29)6.判断点是否在线段上 (30)7.判断两线段是否相交 (31)8.判断线段与直线是否相交 (32)9.点到线段最短距离 (32)10.求两直线的交点 (33)11.判断一个封闭图形是凹集还是凸集 (34)12.Graham 扫描法寻找凸包 (35)13.求两条线段的交点 (36)四、数论 (37)1.x 的二进制长度 (37)2.返回x 的二进制表示中从低到高的第i 位 (38)3.模取幂运算 (38)4.求解模线性方程 (39)5.求解模线性方程组(中国余数定理) (39)6.筛法素数产生器 (40)7.判断一个数是否素数 (41)8.求距阵最大和 (42)8.求一个数每一位相加之和 (43)10.质因数分解 (43)11.高斯消元法解线性方程组 (44)五、图论 (45)1.Prim 算法求最小生成树................................................. 45 2.Dijkstra 算法求单源最短路径.. (46)3.Bellman-ford 算法求单源最短路径 (47)4.Floyd-Warshall 算法求每对节点间最短路径 (48)5.解欧拉图 (49)六、排序/查找 (50)1.快速排序 (50)2.希尔排序 (51)3.选择法排序 (52)4.二分查找 (52)七、数据结构 (53)1.顺序队列 (53)2.顺序栈 (56)3.链表 (59)4.链栈 (63)5.二叉树 (66)八、高精度运算专题 (68)1.专题函数说明 (68)2.高精度数比较 (69)3.高精度数加法 (69)4.高精度数减法 (70)5.高精度乘10 (71)6.高精度乘单精度 (71)7.高精度乘高精度 (72)8.高精度除单精度 (72)9.高精度除高精度 (73)九、标准模板库的使用 (74)1.计算求和 (74)2.求数组中的最大值 (76)3. sort 和qsort (76)十、其他 (78)1.运行时间计算 (78)一、数学问题1.精度计算——大数阶乘语法：int result=factorial(int n);参数：n：n 的阶乘返回值：阶乘结果的位数注意：本程序直接输出n!的结果，需要返回结果请保留long a[] 需要math.h源程序：int factorial(int n){long a[10000];int i,j,l,c,m=0,w;a[0]=1;for(i=1;i<=n;i++){c=0;for(j=0;j<=m;j++){a[j]=a[j]*i+c;c=a[j]/10000;a[j]=a[j]%10000;}if(c>0) {m++;a[m]=c;}}w=m*4+log10(a[m])+1;printf("\n%ld",a[m]);for(i=m-1;i>=0;i--) printf("%4.4ld",a[i]);return w;}我也可以做到..5 / 782.精度计算——乘法（大数乘小数）语法：mult(char c[],char t[],int m);参数：c[]：被乘数，用字符串表示，位数不限t[]：结果，用字符串表示m：乘数，限定10 以内返回值：null注意：需要string.h源程序：void mult(char c[],char t[],int m){int i,l,k,flag,add=0;char s[100];l=strlen(c);for (i=0;i<l;i++)s[l-i-1]=c[i]-'0';for (i=0;i<l;i++){k=s[i]*m+add;if (k>=10) {s[i]=k%10;add=k/10;flag=1;} else{s[i]=k;flag=0;add=0;}}if (flag) {l=i+1;s[i]=add;} else l=i;for (i=0;i<l;i++)t[l-1-i]=s[i]+'0'; t[l]='\0';}3.精度计算——乘法（大数乘大数）语法：mult(char a[],char b[],char s[]);参数：a[]：被乘数，用字符串表示，位数不限b[]：乘数，用字符串表示，位数不限t[]：结果，用字符串表示返回值：null注意：空间复杂度为o(n^2)需要string.h源程序：void mult(char a[],char b[],char s[]){我也可以做到..6 / 78int i,j,k=0,alen,blen,sum=0,res[65][65]={0},flag=0; char result[65];alen=strlen(a);blen=strlen(b);for (i=0;i<alen;i++)for (j=0;j<blen;j++) res[i][j]=(a[i]-'0')*(b[j]-'0');for (i=alen-1;i>=0;i--){for (j=blen-1;j>=0;j--) sum=sum+res[i+blen-j-1][j]; result[k]=sum%10;k=k+1;sum=sum/10;}for (i=blen-2;i>=0;i--){for (j=0;j<=i;j++) sum=sum+res[i-j][j];result[k]=sum%10;k=k+1;sum=sum/10;}if (sum!=0) {result[k]=sum;k=k+1;}for (i=0;i<k;i++) result[i]+='0';for (i=k-1;i>=0;i--) s[i]=result[k-1-i];s[k]='\0';while(1){if (strlen(s)!=strlen(a)&&s[0]=='0')strcpy(s,s+1);elsebreak;}}4.精度计算——加法语法：add(char a[],char b[],char s[]);参数：a[]：被加数，用字符串表示，位数不限b[]：加数，用字符串表示，位数不限s[]：结果，用字符串表示返回值：null注意：空间复杂度为o(n^2)我也可以做到..7 / 78需要string.h源程序：void add(char a[],char b[],char back[]){int i,j,k,up,x,y,z,l;char *c;if (strlen(a)>strlen(b)) l=strlen(a)+2; else l=strlen(b)+2; c=(char *) malloc(l*sizeof(char));i=strlen(a)-1;j=strlen(b)-1;k=0;up=0;while(i>=0||j>=0){if(i<0) x='0'; else x=a[i];if(j<0) y='0'; else y=b[j];z=x-'0'+y-'0';if(up) z+=1;if(z>9) {up=1;z%=10;} else up=0;c[k++]=z+'0';i--;j--;}if(up) c[k++]='1';i=0;c[k]='\0';for(k-=1;k>=0;k--)back[i++]=c[k];back[i]='\0';}5.精度计算——减法语法：sub(char s1[],char s2[],char t[]);参数：s1[]：被减数，用字符串表示，位数不限s2[]：减数，用字符串表示，位数不限t[]：结果，用字符串表示返回值：null注意：默认s1>=s2，程序未处理负数情况需要string.h源程序：void sub(char s1[],char s2[],char t[])我也可以做到..8 / 78{int i,l2,l1,k;l2=strlen(s2);l1=strlen(s1);t[l1]='\0';l1--;for (i=l2-1;i>=0;i--,l1--){if (s1[l1]-s2[i]>=0)t[l1]=s1[l1]-s2[i]+'0';else{t[l1]=10+s1[l1]-s2[i]+'0';s1[l1-1]=s1[l1-1]-1;}}k=l1;while(s1[k]<0) {s1[k]+=10;s1[k-1]-=1;k--;}while(l1>=0) {t[l1]=s1[l1];l1--;}loop:if (t[0]=='0') {l1=strlen(s1);for (i=0;i<l1-1;i++) t[i]=t[i+1];t[l1-1]='\0';goto loop;}if (strlen(t)==0) {t[0]='0';t[1]='\0';}}6.任意进制转换语法：conversion(char s1[],char s2[],char t[]);参数：s[]：转换前的数字s2[]：转换后的数字d1：原进制数d2：需要转换到的进制数返回值：null注意：高于9 的位数用大写'A'～'Z'表示，2～16 位进制通过验证源程序：void conversion(char s[],char s2[],long d1,long d2){我也可以做到..9 / 78long i,j,t,num;char c;num=0;for (i=0;s[i]!='\0';i++){if (s[i]<='9'&&s[i]>='0') t=s[i]-'0'; else t=s[i]-'A'+10;num=num*d1+t;}i=0;while(1){t=num%d2;if (t<=9) s2[i]=t+'0'; else s2[i]=t+'A'-10;num/=d2;if (num==0) break;i++;}for (j=0;j<i/2;j++){c=s2[j];s2[j]=s[i-j];s2[i-j]=c;}s2[i+1]='\0';}7.最大公约数、最小公倍数语法：resulet=hcf(int a,int b)、result=lcd(int a,int b)参数：a：int a，求最大公约数或最小公倍数b：int b，求最大公约数或最小公倍数返回值：返回最大公约数（hcf）或最小公倍数（lcd）注意：lcd 需要连同hcf 使用源程序：int hcf(int a,int b){int r=0;while(b!=0){r=a%b;a=b;b=r;}return(a);我也可以做到..10 / 78}lcd(int u,int v,int h){return(u*v/h);}8.组合序列语法：m_of_n(int m, int n1, int m1, int* a, int head)参数：m：组合数C 的上参数n1：组合数C 的下参数m1：组合数C 的上参数，递归之用*a：1～n 的整数序列数组head：头指针返回值：null注意：*a 需要自行产生初始调用时，m=m1、head=0调用例子：求C(m,n)序列：m_of_n(m,n,m,a,0);源程序：void m_of_n(int m, int n1, int m1, int* a, int head){int i,t;if(m1<0 || m1>n1) return;if(m1==n1){return;}m_of_n(m,n1-1,m1,a,head); // 递归调用t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t;m_of_n(m,n1-1,m1-1,a,head+1); // 再次递归调用t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t;}9.快速傅立叶变换（FFT）语法：kkfft(double pr[],double pi[],int n,int k,double fr[],double fi[],intl,int il);参数：我也可以做到..11 / 78pr[n]：输入的实部pi[n]：数入的虚部n，k：满足n=2^kfr[n]：输出的实部fi[n]：输出的虚部l：逻辑开关，0 FFT，1 ifFTil：逻辑开关，0 输出按实部/虚部；1 输出按模/幅角返回值：null注意：需要math.h源程序：void kkfft(pr,pi,n,k,fr,fi,l,il)int n,k,l,il;double pr[],pi[],fr[],fi[];{int it,m,is,i,j,nv,l0; double p,q,s,vr,vi,poddr,poddi;for (it=0; it<=n-1; it++){m=it; is=0;for (i=0; i<=k-1; i++){j=m/2; is=2*is+(m-2*j); m=j;}fr[it]=pr[is]; fi[it]=pi[is];}pr[0]=1.0; pi[0]=0.0;p=6.283185306/(1.0*n);pr[1]=cos(p); pi[1]=-sin(p);if (l!=0) pi[1]=-pi[1];for (i=2; i<=n-1; i++){p=pr[i-1]*pr[1];q=pi[i-1]*pi[1];s=(pr[i-1]+pi[i-1])*(pr[1]+pi[1]);pr[i]=p-q; pi[i]=s-p-q;}for (it=0; it<=n-2; it=it+2){vr=fr[it]; vi=fi[it];fr[it]=vr+fr[it+1]; fi[it]=vi+fi[it+1];fr[it+1]=vr-fr[it+1]; fi[it+1]=vi-fi[it+1]; }m=n/2; nv=2;for (l0=k-2; l0>=0; l0--){我也可以做到..12 / 78m=m/2; nv=2*nv;for (it=0; it<=(m-1)*nv; it=it+nv)for (j=0; j<=(nv/2)-1; j++){p=pr[m*j]*fr[it+j+nv/2];q=pi[m*j]*fi[it+j+nv/2];s=pr[m*j]+pi[m*j];s=s*(fr[it+j+nv/2]+fi[it+j+nv/2]); poddr=p-q; poddi=s-p-q;fr[it+j+nv/2]=fr[it+j]-poddr;fi[it+j+nv/2]=fi[it+j]-poddi;fr[it+j]=fr[it+j]+poddr;fi[it+j]=fi[it+j]+poddi;}}if (l!=0)for (i=0; i<=n-1; i++){fr[i]=fr[i]/(1.0*n);fi[i]=fi[i]/(1.0*n);}if (il!=0)for (i=0; i<=n-1; i++){pr[i]=sqrt(fr[i]*fr[i]+fi[i]*fi[i]);if (fabs(fr[i])<0.000001*fabs(fi[i])) {if ((fi[i]*fr[i])>0) pi[i]=90.0;else pi[i]=-90.0;}elsepi[i]=atan(fi[i]/fr[i])*360.0/6.283185306;}return;}10.Ronberg 算法计算积分语法：result=integral(double a,double b);参数：a：积分上限b：积分下限我也可以做到..13 / 78function f：积分函数返回值：f 在（a,b）之间的积分值注意：function f(x)需要自行修改，程序中用的是sina(x)/x 需要math.h默认精度要求是1e-5源程序：double f(double x){return sin(x)/x; //在这里插入被积函数}double integral(double a,double b){double h=b-a;double t1=(1+f(b))*h/2.0;int k=1;double r1,r2,s1,s2,c1,c2,t2;loop:double s=0.0;double x=a+h/2.0;while(x<b){s+=f(x);x+=h;}t2=(t1+h*s)/2.0;s2=t2+(t2-t1)/3.0;if(k==1){k++;h/=2.0;t1=t2;s1=s2;goto loop;}c2=s2+(s2-s1)/15.0;if(k==2){c1=c2;k++;h/=2.0;t1=t2;s1=s2;goto loop;}r2=c2+(c2-c1)/63.0;if(k==3){r1=r2; c1=c2;k++;h/=2.0;t1=t2;s1=s2;我也可以做到..14 / 78goto loop;}while(fabs(1-r1/r2)>1e-5){ r1=r2;c1=c2;k++;h/=2.0;t1=t2;s1=s2;goto loop;}return r2;}11.行列式计算语法：result=js(int s[][],int n)参数：s[][]：行列式存储数组n：行列式维数，递归用返回值：行列式值注意：函数中常数N 为行列式维度，需自行定义源程序：int js(s,n)int s[][N],n;{int z,j,k,r,total=0;int b[N][N];/*b[N][N]用于存放，在矩阵s[N][N]中元素s[0]的余子式*/if(n>2){for(z=0;z<n;z++){for(j=0;j<n-1;j++)for(k=0;k<n-1;k++)if(k>=z) b[j][k]=s[j+1][k+1]; elseb[j][k]=s[j+1][k];if(z%2==0) r=s[0][z]*js(b,n-1); /*递归调用*/else r=(-1)*s[0][z]*js(b,n-1);total=total+r;}}else if(n==2)total=s[0][0]*s[1][1]-s[0][1]*s[1][0];return total;我也可以做到..15 / 78}12.求排列组合数语法：result=P(long n,long m); / result=long C(long n,long m);参数：m：排列组合的上系数n：排列组合的下系数返回值：排列组合数注意：符合数学规则：m<＝n源程序：long P(long n,long m){long p=1;while(m!=0){p*=n;n--;m--;}return p;}long C(long n,long m){long i,c=1;i=m;while(i!=0){c*=n;n--;i--;}while(m!=0){c/=m;m--;}return c;}13.求某一天星期几语法：result=weekday(int N,int M,int d)参数：N,M,d：年月日，例如：2003,11,4返回值：0：星期天，1 星期一……注意：需要math.h适用于1582 年10 月15 日之后, 因为罗马教皇格里高利十三世在这一天启用新历法.源程序：我也可以做到..16 / 78int weekday(int N,int M,int d){int m,n,c,y,w;m=(M-2)%12;if (M>=3) n=N;else n=N-1;c=n/100;y=n%100;w=(int)(d+floor(13*m/5)+y+floor(y/4)+floor(c/4)-2*c)%7;while(w<0) w+=7;return w;}14.卡特兰(Catalan) 数列原理令h(1)＝1，catalan 数满足递归式：h(n)= h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=2)该递推关系的解为：h(n)=c(2n-2,n-1)/n (n=1,2,3,...)1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440,9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420,24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …1.括号化问题。

ACM Digital Library一．数据库简介ACM Digital Library数据库收录了美国计算机协会（Association for Computing Machinery）的各种电子期刊、会议录、快报等文献，通过设在清华大学图书馆的镜像服务器提供服务，凡IP地址在校园网范围内的读者，均可使用该数据库。

二．进入数据库从我馆主页（）上的“正式引进数据库”栏目下选取“ACM Digital Library全文数据库”，或直接输入网址/ ，即可进入该数据库的主页面。

三．检索方法用户可以通过检索和浏览两条途径获取论文。

1.检索途径（1）快速检索 (Quick Search)该数据库的首页分为上下两个区，上半区为快速检索区，有一个检索框，可检索的字段有：All fields（所有字段，不包括全文）、Full Text（全文）、All fields with Full Text（所有字段包括全文）、Title（题名）、Author（作者）、Abstract（摘要）、References（参考文献）、Category（分类）、Keyword （关键词）、Source（来源：刊名、书名或会议录名）、Publisher（出版商）。

在检索框中输入检索词，选好检索字段，单击“Search” 按钮，进行检索；也可以单击“Reset”重新设置。

首页下半区的右侧是快速检索指南，有问题可以在此寻求帮助。

（2）高级检索单击页面左上角的“Advanced Search”按钮，进入高级检索界面。

该界面有五个检索框，之间可以用“and、or、not”进行逻辑组配。

可以进行时间、文献类型（Type）、每次显示结果条数（Show results）等的限定选择。

检索规则：在快速检索状态下，可以使用逻辑算符AND、OR将检索词组成检索式；高级检索可以实现跨字段检索；AUTHORS ：文章作者及文献编者；TITLENAME：指文章题目或书目标题、副标题,在此可输入词或词组；ABST RACT：即可用词或词组，也可以用短语方式进行检索；FULLTEXT：指在所有文本字段中检索；SOURCE：指刊名、会议录名、书名等；ISBN_ISSN：国际标准刊号、标准书号；PUBLISHERS：期刊、会议、图书的出版者；INDEX_TERMS：ACM的分类表，包括类目/主类，受控词/关键词；运算符说明：逻辑运算符：AND（与）、OR（或）、NOT（非）;位置算符：ADJ：表示两词相邻,一般以空格表示，是系统默认状态；NEAR/n：表示两词之间可插入n个词，词序可颠倒；W/n：表示两词之间可插入n个词，词序不可颠倒；“?”：模糊检索,如:int??net,可检出internet, interanet…；“*”：进行词根检索，如：inter*,可检出inter, internet, international;“＋”：进行词义相同检索，如：program+,可检出program, programmed, programming, programmer…;“＃”：进行精确检索，如：program#只作该词检索。

杭州电子科技大学OJ题目分类1001 整数求和水题1002 C语言实验题——两个数比较水题1003 1、2、3、4、5... 简单题1004 渊子赛马排序+贪心的方法归并1005 Hero In Maze 广度搜索1006 Redraiment猜想数论：容斥定理1007 童年生活二三事递推题1008 University 简单hash1009 目标柏林简单模拟题1010 Rails 模拟题（堆栈）1011 Box of Bricks 简单题1012 u Calculate e 简单数学计算1013 STAMPS 搜索or动态规划1014 Border 模拟题1015 Simple Arithmetics 高精度计算1016 Shoot-out 博弈+状态压缩DP1017 Tour Guide1018 Card Trick 简单题1019 Necklace Decomposition 贪心1020 Crashing Robots 模拟题1021 Electrical Outlets 简单题1022 Watchdog 简单题1023 Taxi Cab Scheme 图论：最小路径覆盖--->最大二分匹配1024 Pseudo-random Numbers 数论1025 Card Game Cheater 简单题1026 Investment 动态规划1027 Pipes1028 SETI 数学:高斯消元法1029 Minimax Triangulation 计算几何1030 Unequalled Consumption 母函数1031 Declaration of Content1032 Laserbox 搜索：DFS1033 Bowlstack1034 Pesky Heroes1035 Reduced ID Numbers 暴力1036 Tantrix1037 Guardian of Decency 图论：匈牙利算法求二分图的最大匹配1038 Up the Stairs 简单数学题1039 Sudoku 搜索：DFS1040 The SetStack Computer1041 Pie 二分法1042 Ticket to Ride 动态规划1043 The Bookcase 动态规划1044 Printer Queue 模拟题1045 Prime Path 搜索：BFS1046 Lineland's Airport1047 Leonardo's Notebook 数学题：群置换1048 简易版最长序列简单题1049 Jesse's problem 搜索：DFS1050 Error Correction 模拟题1051 A ×B problem 高精度计算1052 Redraiment的走法动态规划1053 Word Encoding 动态规划1054 Jesse's Code 组合数学：排列1055 简单密码破解水题1056 英文金曲大赛水题1057 有假币水题1058 寄居蟹与海葵水题1059 天仙配水题1060 鹊桥相会水题1061 杨辉三角水题1062 蟠桃记水题1063 养兔子水题1064 字符统计水题1065 完美数水题1066 亲和数水题1067 成绩评估水题1068 找零钱水题1069 漂亮菱形水题1070 Least Common Multiple 水题1071 第几天水题1072 编辑距离水题1073 支配值数目水题1074 等值数目水题1075 两数组最短距离水题1076 输入入门(1) 水题1077 输入入门(2) 水题1078 输入入门(3) 水题1079 输出入门水题1080 Counterfeit Dollar 组合数学1081 Dividing 动态规划1082 Sorting It All Out 图论：拓扑排序1083 False coin 暴力法1084 File Mapping1085 Color Me Less 简单题1086 Round and Round We Go 简单题1087 Microprocessor Simulation 简单题1088 求奇数的乘积水题1089 平方和与立方和水题1090 绝对值排序水题1091 JudgeOnline 水题1092 More Beautiful 水题1093 猴子分桃水题1094 C语言实验题——一元二次方程水题1095 C语言实验题——保留字母水题1096 C语言实验题——排列水题1097 C语言实验题——矩阵转置水题1098 C语言实验题——素数水题1099 Ambiguous permutations 简单题1100 Home Work 贪心法1101 Redraiment的遭遇数学题：找规律1102 Decorate the wall 搜索or动态规划1103 Economic phone calls 动态规划or贪心1104 Any fool can do it 记忆化搜索1105 Wine trading in Gergovia 贪心法1106 Homogeneous squares 随机算法1107 Automatic Correction of Misspellings 字符串处理：字典序1108 Black and white painting 简单数学题1109 Cylinder 计算几何：公式推导1110 Deli Deli 水题1111 Expressions 数据结构：树的遍历1112 Flavius Josephus Reloaded 数论：Pollard's Rho算法1113 Annoying painting tool 贪心法1114 Frequent values RMQ区间最值问题OR 线段树1115 Anagram Groups 字符串匹配1116 Let it Bead 组合数学->Polya定理1117 Simple Computers 简单题1118 Mondriaan's Dream 动态规划1119 Equidistance 计算几何1120 How many Fibs? 高精度计算1121 Hike on a Graph 搜索：BFS1122 ASCII Art1123 Billing Tables1124 Cellular Automaton 矩阵计算1125 Exchange1126 Fool's Game1127 Java vs C++ 字符串处理1128 Kickdown 字符串处理1129 Copying Books 贪心+二分法1130 Adding Reversed Numbers 简单题1131 Glass Beads 字符串的最小表示1132 The Circumference of the Circle 计算几何题1133 Knight Moves 搜索：BFS1134 Eeny Meeny Moo 变形的约瑟夫问题1135 Lotto 组合数学1136 Humble Numbers 动态规划1137 Average is not Fast Enough! 简单题1138 Etaoin Shrdlu 简单题1139 Hard to Believe, but True! 简单题1140 Code the Tree 简单题1141 Fiber Network 图论：全源最短路径，Floyd-Warshall算法1142 Global Roaming 3D几何题1143 All in All 字符串处理1144 The Sierpinski Fractal 递归1145 Assistance Required 简单题：预处理1146 Drink, on Ice 模拟题1147 All Discs Considered 搜索：BFS1148 In Danger 模拟题1149 Run Length Encoding 字符串处理1150 Bee Maja 模拟题1151 Friends 表达式求值1152 John 博弈论1153 Double Queue 最大堆与最小堆1154 ‘JBC’1155 Loan Scheduling 贪心+堆1156 Showstopper1157 Highway 贪心法1158 Computers 动态规划1159 The Stable Marriage Problem 组合数学1160 Arne Saknussemm 模拟题1161 Sum Problem 水题1162 Fire Net 搜索题1163 统计1到N之间数字1的个数推理题1164 最大公因子水题1165 C语言实验题——三个整数水题1166 C语言实验题——大小写转换水题1167 C语言实验题——分数序列水题1168 C语言实验题——最值水题1169 C语言实验题——保留整数水题1170 C语言实验题——矩阵下三角元素之和水题1171 C语言实验题——字符逆序水题1172 C语言实验题——打印菱形水题1173 C语言实验题——分割整数水题1174 C语言实验题——删除指定字符水题1175 C语言实验题——时间间隔水题1176 C语言实验题——数组逆序水题1177 C语言实验题——打印数字图形水题1178 C语言实验题——单词统计水题1179 C语言实验题——最小公倍数和最大公约数水题1180 Crashing Balloon 搜索题1181 念数字模拟题1182 A+B for Input-Output Practice(1) 水题1183 Anagrams by Stack 搜索：回溯1184 Elevator 数学：找规律1185 Substrings 字符串处理1186 Calling Extraterrestrial Intelligence Again 搜索：枚举法1187 Do the Untwist 简单数学题1188 数字对水题1189 A+B for Input-Output Practice (2) 水题1190 火星A+B 简单题1191 三齿轮问题：三个齿轮啮合简单数学题1192 A + B Problem II 高精度计算1193 The ones to remain 数学题1194 Chinese Chess 博弈论1195 Page Replacement 数据结构：队列or hash1196 RSA Signing 数论：Pollard's Rho算法1197 Number Guessing 搜索：穷举1198 求n的阶乘高精度计算1199 Area 计算几何1200 求两直线的夹角水题1201 三角形面积水题1202 Max Sum 动态规划1203 Number Sequence 大数问题1204 u Calculate e 水题1205 斐波那契数列高精度计算1206 Fibonacci Again 大数问题1207 Let the Balloon Rise 字符串处理1208 还是A+B 水题1209 A + B 水题1210 The area 简单计算几何1211 Ignatius's puzzle 简单数学问题1212 Computer Transformation 高精度计算1213 N! 高精度计算1217 Text Reverse 水题1220 填数字游戏搜索：DFS1221 Tempter of the Bone 搜索：DFS or BFS+剪枝1226 Last non-zero Digit in N! 数论1227 三角形递推求解1228 回文数猜想简单题1229 Factorial 简单题1230 Specialized Four-Digit Numbers 简单数学题1231 Lowest Bit 简单题1232 To and Fro 简单题1233 AC Me 简单题1234 Wolf and Rabbit 数论1235 最大连续子序列动态规划1236 开门人和关门人字符串处理1237 排名排序1238 统计难题字符串处理：字典树1239 Tick and Tick 数学题1240 Quoit Design 分治法1241 钱币兑换问题递推求解1242 求出前m大的数简单题1243 角谷猜想简单题1244 Reverse Number 简单题1245 寻找素数对简单题1246 ZJUTACM 简单题1247 Hat's Fibonacci 高精度计算1248 Encoding 简单题1249 四数相加高精度计算1250 两数相减高精度计算1251 Square Coins 母函数1252 Counting Triangles 递推求解1253 2^x mod n = 1 数论：费尔马小定理1254 Minimum Inversion Number 简单题1255 Surround the Trees 计算几何：凸包1256 Number Steps 简单题1257 Binary Numbers 简单题1258 Knight Moves 搜索：BFS1259 Lotto 组合数学1260 A Simple Task 简单题1261 The Drunk Jailer 数论1262 Hanoi Tower Troubles Again! 递推求解1263 IBM Minus One 水题1264 Definite Values 简单题1265 Box of Bricks 水题1266 Perfection 简单题1267 Reverse Text 水题1268 Inversion 模拟题1269 Prime Cuts 简单题1270 How Many Fibs? 高精度计算1271 Round and Round We Go 简单题1272 Red and Black 搜索：DFS1273 What Day Is It? 简单题1274 String Matching 字符串匹配1275 A Contesting Decision 简单题1276 Doubles 简单题1277 The Snail 简单题1278 Jungle Roads 图论：最小生成树1279 Prime Ring Problem 搜索：DFS1280 Big Number 大数问题1281 Least Common Multiple 简单题1283 简单排序水题1284 Gridland 简单题1285 An Easy Task 简单题1286 Calendar Game 模拟题1287 Human Gene Functions 动态规划1288 计算几何练习题——线段相交计算几何1289 计算几何练习题——线段相交II 计算几何1290 计算几何练习题——直线交点计算几何1291 Trees Made to Order 递归求解1292 排序简单题1293 18岁生日简单题1294 吃糖果递推求解1295 变种汉诺塔递推求解1296 洗牌递推求解1297 大数求余数论1298 圆桌会议递推求解1299 畅通工程并查集1300 还是畅通工程最小生成树1301 统计同成绩学生人数水题1302 简单计算器表达式求值：栈的应用1303 改进版计算器表达式求值：栈的应用1304 FatMouse' Trade 贪心法1305 Digital Roots 大数问题1306 Uniform Generator 数论1307 A Mathematical Curiosity 穷举法1308 Safecracker 穷举法1309 The 3n + 1 problem 简单题1310 分享糖果模拟题1311 宝物收集搜索：BFS1312 Climbing Worm 简单题1313 搬桌子贪心法1314 Humble Numbers 动态规划1315 Dividing 动态规划1316 Rightmost Digit 数学问题1317 Leftmost Digit 数学问题1318 Hangover 简单数学问题1319 Exponentiation 高精度计算1320 I Think I Need a Houseboat 简单题1321 Girls and Boys DFS+二分图1322 Monkey and Banana 动态规划1323 买牛奶简单题1324 Matrix Chain Multiplication 数据结构：栈的应用1325 计算成绩简单题1326 Holding Bin-Laden Captive! 母函数1327 You can Solve a Geometry Problem too 计算几何1328 Super Jumping! Jumping! Jumping! 动态规划1329 a^b 数论1330 计算GPA 水题1331 Give me an offer! 动态规划：0-1背包1332 田忌赛马贪心法1333 Asteroids! 搜索：BFS1334 Oil Deposits 搜索：DFS1335 营救天使搜索：BFS1336 小数化分数高精度计算1337 I Hate It 线段树1338 Strange Billboard 位运算+枚举1339 Frobenius 递推求解1340 奇怪的公式数学题1341 Fibonacci again and again 博弈论1342 A New Tetris Game 博弈论1343 Sum It Up 搜索：DFS1344 速算24点搜索1345 推箱子搜索：BFS1346 Pushing Boxes 搜索：BFS1347 The Worm Turns 搜索1348 Alfredo's Pizza Restaurant 简单题1349 Broken Keyboard 字符串处理1350 Convert Kilometers to Miles 简单题1351 单词数水题1352 仙人球的残影简单题1353 Family planning 简单题1354 Rout 66 简单题1355 LC-Display 模拟题1356 A == B ? 高精度计算1357 不容易系列之一递推求解1358 折线分割平面递推求解1359 find the nth digit 二分查找1360 奇数阶魔方(II) 简单题1361 Keep on Truckin' 简单题1362 Factstone Benchmark 简单题1363 Destroy the Well of Life 模拟题1365 Brave Game 博弈论1366 ASCII码排序水题1367 计算两点间的距离水题1368 计算球体积水题1369 求绝对值水题1370 数值统计水题1371 求数列的和水题1372 水仙花数水题1373 多项式求和水题1374 素数判定水题1375 偶数求和水题1376 母牛的故事水题1377 数列有序! 水题1378 发工资咯：）水题1379 C语言合法标识符水题1380 海选女主角水题1381 查找最大元素水题1382 首字母变大写水题1383 统计元音水题1384 Palindromes _easy version 水题1385 汉字统计水题1386 进制转换水题1387 人见人爱A+B 水题1388 人见人爱A-B 水题1389 人见人爱A^B 水题1390 改革春风吹满地计算几何1391 今年暑假不AC 动态规划1392 三角形水题1393 求平均成绩水题1394 不容易系列之二递推求解1395 密码水题1396 一只小蜜蜂... 递推求解1397 不容易系列之(3)——LELE的RPG难题递推求解1398 骨牌铺方格递推求解1399 阿牛的EOF牛肉串递推求解1400 神、上帝以及老天爷递推求解1401 不容易系列之(4)——考新郎递推求解1402 Bitset 简单题1403 Picture 简单模拟题1404 Switch Game 找规律1405 An easy problem 简单模拟题1406 A + B Again 简单题1407 The sum problem 简单数学题1408 龟兔赛跑动态规划1409 Snooker 简单数学题1410 Subset sequence 简单题1411 汉诺塔III 递推求解1412 "红色病毒"问题递推求解1413 小兔的棋盘递推求解1414 RPG的错排错排+排列组合1415 无限的路简单题1416 夹角有多大数学题1417 汉诺塔IV 递推求解1418 复习时间简单题1419 选课时间暴力求解1420 手机短号字符串处理1421 找单词母函数1422 简易版之最短距离数学题1423 数塔动态规划1424 核反应堆简单题1425 A1 = ? 公式推导1426 剪花布条字符串处理1427 不要62 数学题1428 空心三角形字符串处理1429 小明A+B 简单题1430 Sky数进制转换1431 整除的尾数简单题1432 分拆素数和数论1433 正整数解数学题1434 挂盐水模拟题1435 {A} + {B} 简单题1436 小数A+B 高精度计算1437 Zigzag 简单题1438 螺旋形简单题1439 行李寄存简单题1440 判断多边形凹凸计算几何1441 The centre of polygon 计算几何1442 最小正整数简单题1443 Elevator Stopping Plan 二分+贪心法1444 TOYS 计算几何1445 The Doors 计算几何1446 Polygon And Segment 计算几何1447 Fence 计算几何1448 两圆相交面积计算几何1449 Area of Circles 计算几何1450 Pipe 计算几何1451 zero sum 搜索：DFS1452 C语言实验题——Hello World 水题1453 C语言实验题——数日子水题1454 C语言实验题——三个数排序水题1455 C语言实验题——数字串求和水题1456 C语言实验题——拍皮球水题1457 C语言实验题——求一个3*3矩阵对角线元素之和水题1458 C语言实验题——数组逆序水题1459 C实验题——求最大值水题1460 C实验题——求绝对值最大值水题1461 C语言实验题——求平均值水题1462 C语言实验题——打印直角三角形水题1463 C语言实验题——相加和最大值水题1464 C语言实验题——简单编码水题1465 C语言实验题——某年某月的天数水题1466 C语言实验题——各位数字之和排序水题1467 C语言实验题——两个数最大水题1468 C语言实验题——求级数值水题1469 Pipe II 计算几何1470 Transmitters 计算几何1471 Wall 计算几何1472 C语言实验题——逆置正整数水题1473 C语言实验题——找中间数水题1474 C语言实验题——整数位水题1475 C语言实验题——一元二次方程II 水题1476 C语言实验题——圆周率水题1477 C语言实验题——余弦水题1478 C语言实验题——打印金字塔水题1479 C语言实验题——排序水题1480 C语言实验题——约瑟夫问题水题1481 C语言实验题——鞍点水题1482 C语言实验题——计算表达式水题1483 C语言实验题——汉诺塔水题1484 C语言实验题——字符串排序水题1485 C语言实验题——整除水题1486 Solitaire 搜索：（双向）BFS1487 Abbreviation 水题1488 C语言实验题——买糖果水题1489 C语言实验题——字符编码水题1490 C语言实验题——合法的C标识符水题1491 C语言实验题——三角形面积水题1492 C语言实验题——大小写转换水题1493 C语言实验题——圆柱体计算水题1494 C语言实验题——温度转换水题1495 C语言实验题——统计字串水题1496 C语言实验题——字符过滤水题1497 Coin Change 暴力求解1498 Beautiful Meadow 搜索题1499 C语言实验题——鸡兔同笼水题1500 Coins of Luck 数学题：数学期望1501 Friends 搜索：DFS1502 Find All M^N Please 数学题1503 Incredible Cows 搜索：二分+DFS1504 计算直线的交点数递推求解1505 Number Game 动态规划1506 Sort ZOJ7 字符串处理1507 Find 7 Faster Than John Von Neumann 高精度计算1508 免费馅饼动态规划1509 Worm 动态规划1510 Common Subsequence 动态规划1511 搬寝室动态规划1512 Daydream 字符串处理1513 Ballroom Lights1514 Drop the Triples1515 Finding Seats1516 He is offside!1517 Justice League1518 星星点点搜索1519 逆波兰表达式表达式求解：栈的应用1520 十六进制高精度计算1521 Palindromic sequence1522 Hotel 模拟题1523 Intersecting Lines 计算几何1524 Heap Construction 最短路径1525 Pizza Anyone?1526 Adam's Genes1527 Risk1528 Just the Facts 数论1529 Horse Shoe Scoring 计算几何1530 哥德巴赫猜想数论1531 爱的伟大意义简单题1532 校门外的树模拟题1533 最多约数问题数论1534 Quicksum 数学题1535 找规律填数字数学题1536 Accepted Necklace 搜索：DFS1537 除法表达式数论1538 A Walk Through the Forest 图论：最短路径1539 Accurately Say "CocaCola"! 简单题1540 Build The Electric System 图论：最小生成树1541 Colorful Rainbows 计算几何1542 Easy Task 数学题1543 Faster, Higher, Stronger 简单题1544 Give Me the Number 模拟题1545 Hurdles of 110m 动态规划1546 Just Pour the Water 矩阵计算1547 Kinds of Fuwas 穷举法1548 复数运算简单题1549 元素个数排序简单题1550 Fiber Communications1551 Power Hungry Cows 搜索：BFS1552 Cow Cycling 动态规划1553 Rebuilding Roads 树型DP1554 Triangular Pastures 动态规划1555 Chores 动态规划1556 Extra Krunch1557 BUY LOW, BUY LOWER 动态规划1558 Hypnotic Milk Improvement1559 Happy Cows1560 Unary Cow Counting1561 Dairy Route1562 Calf Numbers1563 Hide and Seek1564 Mountain Majesties1565 Secret Milk Pipes1566 Circus Tickets1567 Life Cycle1568 Wiggle Numbers1569 Superwords1570 Cow Brainiacs1571 Pasture Fences1572 New Years Party1573 Strolling Cows1574 Grazing Sets1575 Factorial Power1576 Friday the Thirteenth1577 Beef McNuggets1578 Calf Flac1579 Light Bulbs1580 Cow Math 图论1581 Cow Imposters 动态规划1582 Traffic Lights 递推求解1583 Farm Tour 图论：最短路径1584 Vertical Histogram 简单题1585 Cowties 动态规划1586 Travel Games 搜索：DFS1587 Best Cow Fences 二分法1588 Cornfields RMQ问题1589 Six Degrees of Cowvin Bacon 简单题1590 Herd Sums 简单题1591 Message Decoding 简单题1592 Mountain Walking 二分+flood fill1593 Millenium Leapcow 动态规划1594 Optimal Milking 最大流+二分法1595 Bale Figures 模拟+二分法1596 Jumping Cows 动态规划1597 Lost Cows SBT树1598 Bovine Math Geniuses 简单题1599 Dividing the Path 动态规划1600 Fence Obstacle Course 动态规划1601 Cow Ski Area 图论：flood fill1602 Cleaning Shifts 贪心法1603 Bad Cowtractors 最大生成树1604 Tree Cutting 树状动态规划1605 Navigation Nightmare 并查集1606 Cow Marathon 树状动态规划1607 Distance Queries LCA，tarjan算法1608 Distance Statistics 楼天成大牛“男人八题”中的一道1609 Moo University - Team Tryouts 排序+穷举法1610 Moo University - Emergency Pizza Order1611 Moo University - Financial Aid 最大堆、最小堆1612 Cube Stacking 并查集1613 The Cow Lineup 穷举法1614 MooFest 线段树1615 Turning in Homework 动态规划1616 Alignment of the Planets1617 Finding Bovine Roots1618 Cow Bowling1619 Cow Patterns 字符串匹配的扩展1620 Barn Expansion 二分查找1621 Layout 差分约束系统1622 Knights of Ni 搜索：BFS1623 Cleaning Shifts DP＋Heap1624 Scales 搜索+剪枝1625 Secret Milking Machine 二分+网络流1626 Aggressive cows 二分法1627 Rigging the Bovine Election 穷举法1628 Feed Accounting 简单模拟题1629 Muddy Fields 穷举法1630 The Wedding Juicer 堆+flood fill1631 Naptime 动态规划1632 Sumsets 动态规划1633 Moo Volume 简单题1634 Ombrophobic Bovines Floyd-Warshall 1635 Space Elevator 动态规划1636 Yogurt factory 动态规划1637 Checking an Alibi 最短路径1638 Out of Hay1639 Satellite Photographs 搜索：BFS or DFS 1640 Asteroids 最大网络流1641 Grazing on the Run 动态规划1642 Walk the Talk 动态规划1643 City Skyline 栈的应用1644 Cow Acrobats 贪心法1645 Ant Counting 动态规划1646 Hopscotch 搜索：DFS1647 Securing the Barn 穷举法1648 Bovine Birthday 递推求解1649 Max Factor 简单题1650 Flying Right1651 Close Encounter1652 Allowance1653 Lazy Cows1654 Expedition1655 Around the world1656 Landscaping1657 Waves1658 Navigating the City1659 Disease Management1660 Muddy roads1661 Wormholes 最短路径1662 The Fewest Coins 动态规划1663 Milk Patterns 二分法or后缀树1664 Cow Picnic 搜索：BFS or DFS1665 Cow Roller Coaster 动态规划1666 River Hopscotch 二分法+贪心1667 The Moronic Cowmpouter 进制转换1668 DNA Assembly 穷举法1669 Cow Phrasebook 二分法1670 Cellphones 穷举法1671 Steady Cow Assignment 网络流1672 Treats for the Cows 动态规划1673 Backward Digit Sums 穷举法1674 Stump Removal 简单题1675 Finicky Grazers 动态规划1676 The Water Bowls 枚举二进制位1677 Redundant Paths 图论1678 Roping the Field 动态规划1679 Corral the Cows 二分法1680 The Cow Prom 图论1681 Dollar Dayz 动态规划1682 The Grove 最短路径1683 Fence Repair Huffman编码1684 Corn Fields 状态压缩DP1685 Roadblocks 图论：最短路径1686 Bad Hair Day 搜索1687 Big Square 穷举法1688 Round Numbers 枚举二进制位1689 Building A New Barn1690 Cow Sorting 置换群1691 Lilypad Pond 最短路径1692 The Cow Lexicon 动态规划1693 Silver Cow Party 最短路径1694 Problem Solving 动态规划1695 Cow School1696 Protecting the Flowers 贪心法1697 Tallest Cow 区间统计1698 Balanced Lineup RMQ问题1699 Gold Balanced Lineup RMQ问题1700 Ranking the Cows 搜索：DFS1701 Face The Right Way 穷举法1702 Cow Traffic 动态规划1703 Monthly Expense 贪心法1704 Cheapest Palindrome 动态规划1705 Dining 贪心+网络流1706 City Horizon 离散化+ 扫描1707 Catch That Cow 最短路径1708 Fliptile 枚举+位压缩1709 2-Dimensional Rubik's Cube 搜索：BFS 1710 Ball 计算几何1711 3D Camera 三维计算几何1712 Cipher 模拟题1713 Five in a Row 简单题1714 Pinhole Imaging 简单计算几何1715 URL 模拟题1716 Battle of Submarines 集合DP1717 WOJ 动态规划1718 钥匙计数之二递推求解1719 BrokenLED 模拟题1722 A+B again and again! 模拟题1723 Just calculate it! 数论1724 Guess how much I love you? 简单题1725 NBA Finals1726 Find Out an “E”1727 Judging ACM/ICPC1728 Cryptography of Alex1729 Rings of square grid1730 Fermat's Theorem1731 Cup 二分法1732 Find the Path DP+二分法1733 Five in a Row, Again 动态规划1734 Minimum Heap 递推求解1735 Name PK 模拟题1736 Pendant 动态规划1737 Radar 计算几何+搜索1738 Ring 多串模式匹配1739 Run 计算几何1740 Toxophily 简单题1741 通讯录编排简单题1742 超缘分ACM队伍简单题1743 集合运算简单题1744 矩阵计算简单题1745 Arbitrage 动态规划1746 The Tower of Babylon 动态规划1747 Binomial Showdown 组合数学1748 Dungeon Master 搜索：BFS1749 Equation Solver 表达式求值应用1750 Frogger 最短路径1751 Globetrotter 计算几何1752 Tree Recovery 数据结构：二叉树1753 Artificial Intelligence?1754 The Settlers of Catan 搜索1755 France '98 概率问题1756 Goldbach's Conjecture 数论1757 Heavy Cargo 最小生成树1758 Quadtree1759 From Dusk till Dawn or: Vladimir the Vampire 最短路径1760 Euro Cup 20001761 Quadtree II or: Florida Jones strikes back1762 HTML 简单题1763 Paths on a Grid 组合数学：T路问题1764 Balanced Food 动态规划1765 California Jones and the Gate to Freedom 组合数学1766 Diplomatic License 简单计算几何题1767 Polygon Programming with Ease 数学题1768 Hall of Fountains 搜索：BFS or DP1769 The Bottom of a Graph 图论：强连通分量1770 Edge1771 Fold1772 Largest Rectangle in a Histogram 动态规划1773 Boolean Logic1774 Code1775 In Danger 模拟题1776 Fractran1777 Huffman's Greed1778 Bullshit Bingo 字符串处理1779 A Song contest1780 Message1781 The skatepark's new ramps1782 Road1783 Warfare1784 Blackjack1785 Robintron1786 Diamond Dealer 计算几何：凸包1787 Best Compression Ever1788 Code Theft1789 Dinner1790 Event Planning1791 Getting Gold1792 Introspective Caching1793 Just A Few More Triangles!1794 Knights of the Round Table 图论：无向图的块判断奇圈1795 The Cow Doctor 穷举法1796 Wild West 线段树1797 Find the Clones1798 The Warehouse1799 Widget Factory 数论：同余方程组1800 Martian Mining 动态规划3301 字符串；AC自动机，动态规划；状态压缩3302 计算几何3303 数学；代数运算；高斯消元3304 图论；强连通分量；2-SAT3305 动态规划；凸单调性优化3306 枚举3307 贪心3308 数学；代数运算3309 最短路；佛洛伊德3310 动态规划3311 贪心3312 计数问题；递推，数状数组，二分查找3313 数论；欧拉定理，快速幂取模3314 计数问题，数状数组3315 博弈；Surreal数；Farey数列；3316 计数问题；递推，高精度3317 计数问题；容斥原理3318 递推；矩阵乘法3319 数学；概率3320 背包3321 动态规划3322 字符串；AC自动机3323 动态规划3324 博弈3325 搜索3326 贪心3327 最短路3328 数据结构（实现一种数据结构，支持要求的操作），数状数组3329 图论；二分图最大权匹配3330 数学；数论3331 递推；矩阵乘法3332 数学；数论，二分查找3333 计算几何3334 动态规划3335 字符串，后缀数组或拉宾卡普；动态规划3336 数据结构；并查集3337 计数问题，递推3338 二分查找，贪心3339 数学3340 计算几何；凸包，图论；佛洛伊德；最小环3341 动态规划3342 广搜3343 动态规划3344 计算几何3345 二分图最大匹配3346 树型DP3347 动态规划3348 数学；数论；进制3349 计数问题3350 贪心3351 数学；数论；进制3352 动态规划，数论，组合数学3353 数学；数论3354 计数；递推3355 图论；佛洛伊德3356 博弈3357 动态规划3358 数据结构；线段树，数状数组3359 计算几何，动态规划3360 博弈；SG函数3361 图论；最近公共祖先3362 图论；强连通分量；2－SAT 3363 计算几何3364 字符串；AC自动机，动态规划3365 搜索，舞蹈链3366 数学；数论3367 数学；代数运算；高斯消元3368 动态规划3369 计数问题；递推3370 网络流（错题）3371 树型DP3372 数学；高精度3373 数学；3374 RMQ3376 数学；进制3377 字符串；后缀数组3378 动态规划3379 计算几何3380 线段树3381 图论；欧拉路3382 简单题3383 字符串；AC自动机3384 广搜3385 计算几何，矩阵3386 语言处理3387 动态规划；状态压缩3388 图论；全局最小割3389 简单题3390 广搜3391 数学；Pell方程3392 背包3393 计算几何3394 广搜3395 搜索；迭代加深3396 数学；计数问题3397 数学；解方程3398 分析3399 模拟3400 数学；计数问题，数论6 热度。

Tempter of the BoneTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 37935 Accepted Submission(s): 10248/showproblem.php?pid=1010Problem DescriptionThe doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.InputThe input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:'X': a block of wall, which the doggie cannot enter;'S': the start point of the doggie;'D': the Door; or'.': an empty block.The input is terminated with three 0's. This test case is not to be processed.OutputFor each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise. Sample Input4 4 5S.X...X...XD....3 4 5S.X...X....D0 0 0Sample OutputNOYES题意：给出T，问第T秒是否能从S去到D百度到大牛的代码（看cpp就行，俺就大体讲一下）：#include <iostream>using namespace std;char map[8][8];int r, c, ttime, x2, y2; //ttime 是所给时间T，【r：行、c：列】bool flag; //x2、y2是终点坐标int x_move[4] = {0, 1, -1, 0};int y_move[4] = {1, 0, 0, -1};void dfs (int x, int y, int t) //t是走到当前坐标时的时刻{if (t > ttime) //超时return ; //下面的tmp的意义：【剩余时间(ttime - t)(记为left)】与【从当前坐标走到终点所需时间( abs(x-x2) + abs(y-y2) )(记为win)】的差，如果tmp是奇数，说明left与win的奇偶性不同！也就是说在第T秒时，不可能从当前坐标走到终点！int tmp = ttime - t - abs(x-x2) - abs(y-y2);if (tmp < 0 || tmp & 1) //奇偶剪枝，非常重要，很抽象Orz...return ;for (int i = 0; i < 4; i++){int tx = x + x_move[i];int ty = y + y_move[i];if (tx < 0 || ty < 0 || tx >= r || ty >= c)continue;if (map[tx][ty] == 'D' && t + 1 == ttime)//到达终点且该时刻t+1为所给时间，即成功到达{flag = true;return ;}if (map[tx][ty] == '.'){map[tx][ty] = 'X'; //已走格子变成墙，根据题意，已走格子不可再走dfs (tx, ty, t+1);if (flag) //成功return ;map[tx][ty] = '.'; //回溯}}}int main(){int i, j, x1, y1, empty;while (scanf ("%d%d%d", &r, &c, &ttime) != EOF){if (!r && !c && !ttime)break;empty = 0;for (i = 0; i < r; i++){scanf ("%s", map[i]);for (j = 0; j < c; j++){if (map[i][j] == 'S') //找到起点的坐标x1 = i, y1 = j;if (map[i][j] == 'D') //找到终点的坐标x2 = i, y2 = j;if (map[i][j] == '.') //计算总的可能行走的步数empty++;}}if (empty + 1 < ttime) //步数剪枝，常识，可行步数小于总时间，在T时刻肯定不可走到终点{puts ("NO");continue;}flag = false;dfs (x1, y1, 0);if (flag)puts ("YES");else puts ("NO");}return 0;}。

HDU 网址：1.注册以及做题流程登录网站，我们会看到下面这个界面：点击红线画出的Register ID，即可进入登录界面Veify Code：验证码Author Name：用户名Password：密码Confirm Psw：重复密码Email：电子邮箱Nick Name：昵称Sex：性别（其中Male为男，Famale为女）Birthday：生日Location：学校Motto：格言Submit：提交Reset：重置其中后面没打星号的可以不输输入完成后即可点提交如果提交后出现说明你的账号已被人注册，请换个账号当账号注册完成后，我们可以在右上角的填入账号密码，然后点sign in登录然后点下图中用红笔圈出来的地方来进入题目列表然后我们会看到这个界面其中上面那排数字表示的是第几页，下面每一个题号都代表一道题目，可以点题目名称就可进入题目界面题目的格式一般是这样的：其中上面那排绿色的字说明了本题的时间限制，空间限制，以及通过率，这是以后难度较大的题目需要考虑的东西，我们这里就不说了。

（提示一个经验：1s 一般可以执行10^7 次操作）Problem Description：问题描述Input：问题的输入格式Output：问题的输出格式Sample Input：样例输入Sample Output：样例输出（提示：除了题目要求输入输出的，请不要输入输出多余的东西。

比如我们要输入两个数a 和b，我们就不要在输入之前输出“请输入两个数”之类的话，这个请格外注意！！！）我们一般是在自己的电脑的c++编辑器上面编完代码，运行样例输入，看到输出跟跟样例输出一样，然后提交代码。

提交代码点这里的Submit。

然后我们会看到下面这个界面：Problem ID 就是你这道题的题号，一般是不会有问题的。

Language：是你使用的语言一般有上面这么几种语言，我们一般使用C 和C++。

（建议用C写的也用C++ 提交，这样比较保险）然后那一大片蓝色的空白就是给大家粘帖代码的。