下载文档原格式
zoj poj ural分类怕下次找麻烦就分享了ural, pku, zju -- 题目分类感谢mugu 的提供.... Ural Problem Set Volume 1: 1000-1099题号标题难度系数算法1000 A+B Problem 10% 直接加1002 Phone Numbers 50% 动态规划或最短路1003 Parity 70% 区间减法1004 Sightseeing trip 60% 最短路1005 Stone Pile 30% 动态规划或搜索1006 Square Frames 35% 模拟1007 Code Words 30% 模拟1008 Image encoding 30% 广度优先搜索1009 K-Based Numbers 20% 递推或枚举（数据规模小）1010 Discrete Function 40% 贪心1011 Conductors 25% 搜索1012K-Based Numbers 30% 递推1013 K-Based Numbers 33% 递推1014 The Product of Digits 30% 贪心1015 Test the differences 35% 模拟1016 A cube on the walk 50% 搜索或者最短路1017 The Staircases 30% 递推（母函数）1018 The Binary Apple Tree 50% 动态规划1019 A Line painting 40% 离散化处理1020 Rope 45% 一般的计算几何问题1021 Sacrament of the sum 40% 动态规划1022 Genealogical Tree 30% 拓补排序1023 Buttons 50% 动态规划1024 Permutations 25% 置换（和题目名字一样）1025 Democracy in Danger 20% 贪心1026 Questions and Answers 40% 快速排序1027 D++ again 40% 字符串处理1028 Stars 75% 线段树1029 Ministry 55% 动态规划（注意优化）1030 Titanic 60% 计算几何（注意精度！）1031 Railway Tickets 45% 动态规划1032 Find a mutilple 55% 同余问题1033 Labyrinth 30% 搜索、遍历1034 Queens in peaceful positions 35% 搜索1035 Cross-sitich 60% 欧拉路径问题1036 Lucky tickets 50% 递推1037 Memory Management 55% 模拟（注意优化）1038 Spell Checker 45% 字符串的操作及统计1039 Anniversary party 40% 树的动态规划1040 Airline company 55% 搜索1041 Nikifor 85% 线性代数问题（过了，但怀疑算法不对）1042 Central Heating 50% 解线性同余方程组1043 Cover an Arc. 58% 计算几何1044 Lucky tickets 40% 递推1045A funny game 55% 搜索1046 Geometrical dreams 88% 很复杂的计算几何1047Simple calculations 30% 数学题，解方程吧！1048 Superlong Sums 48% 高精度加法1049 Brave ballonists 30% 模拟1050 Preparing an article 63% 比较麻烦的字符串处理1051 A simple game on a grid 60% 数学杂题1052 Rabbit Hunt 28% 简单的计算几何1053 Pinocchio 32% 求最大公约数（题目意思不明）1054 Hanoi Tower 50% 数学问题1055 Combinations 40% 数学问题1056 Computer net 55% 动态规划1057 Amount of dergess 53% 数学问题1058 Chocolate 85% 复杂的计算几何问题1059 Expression 20% 简单的打印问题1060 Flip game 35% 我搜索，过了1061 Buffer Manager 45% 模拟1062 Triathlon 83% 复杂的不等式问题1064 Binary Search 48% 搜索1065 Frontier 75% 动态规划1066 Garland 40% 数学问题1067 Disk Tree 45% 模拟或排序1068 Sum 20% 简单的加法题1069 The prufer code 50% 构造1070 A local time 60% 考虑要周全1071 Nikifor - 2 45% 搜索1072 Routing 40% 最短路问题1073 A square problem 50% 动态规划1074 A very short problem 58% 模拟、判断1075 A thread in the space 65% 麻烦的计算几何1076 Trash 50% 二分图的最大权匹配1077 Travelling Tours 60% 图的遍历1078 Segments 40% 动态规划1079 Maxium 50% 数学问题1080 Map coloring 35% 深度优先搜索1081 Binary Lexicographic Sequence 40% 数学问题1082 Gaby Ivanushka 15% 没有算法，直接输出答案1083 Factorials!!! 25% 简单的数学计算1084 A goat in a kitchen garden 35% 简单的计算几何1085 Meeting 55% 最短路1086 Cryptography 45% 数学问题1087 The time to take stones 48% 递推1088 Ilya Murumetz 33% 二叉树的性质1089 verification with a vocabulary 50% 字符串处理1090 In the army now 60% 平衡二叉树1091 Tmutarakan exams 57% 运用容斥原理1092 Transversal 75% 贪心1093 Darts 65% 立体解析几何1094 E-screen 40% 字符串处理1095 Nikifor - 3 45% 同余问题1096 Get the right route plate! 40% 广度优先搜索1097 Square country - 2 63% 离散化处理1098 Questions 48% 字符串处理1099 Work scheduling 60% 图的最大基数匹配详情请见：acm - Ural专页 Posted: 2007-02-16 17:39 | [楼主] 威士忌我本楚狂人－凤歌笑孔丘级别: 管理员精华: 1 发帖: 1529 威望: 1652 点金钱: 80262 HDOJ币贡献值: 3 点在线时间:827(小时) 注册时间:2006-03-21 最后登录:2008-10-14poj--题目分类1、排序1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 13 18, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379, 1002（需要字符处理，排序用快排即可）1007（稳定的排序）2159（题意较难懂）2231 2371（简单排序）2388（顺序统计算法）2418（二*排序树）2、搜索、回溯、遍历1022 1111 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 23861010,1011,1018,1020,1054,1062,1256,1321,1363,1501，1650,1659,1664,1753,2078,208 3,2303,2310,2329 简单：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 17 45, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426, 不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 23 49, 推荐：1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 17 14, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170, 2288 , 2331, 2339, 2340,1979（和迷宫类似）1980（对剪枝要求较高）3、历法1008 2080 （这种题要小心）4、枚举1012，1046，1387，1411，2245，2326，2363，2381，1054（剪枝要求较高），1650 （小数的精度问题）5、数据结构的典型算法容易：1182, 1656, 2021, 2023, 2051, 2153, 2227, 2236, 2247, 2352, 2395, 不易：1145, 1177, 1195, 1227, 1661, 1834, 推荐：1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 2004, 2010, 21 19, 2274, 1125(弗洛伊德算法) ，2421（图的最小生成树）6、动态规划1037 A decorative fence、1050 To the Max、1088 滑雪、1125 Stockbroker Grapevine、1141 Brackets Sequence、1159 Palindrome、1160 Post Office、1163 The Triangle、1458 Common Subsequence、1579 Function Run Fun、1887 Testing the CATCHER、1953 World Cup Noise、2386 Lake Counting 7、贪心1042, 1065, 1230, 1784,1328 1755（或用单纯形方法），2054，101 7，1328，1862，1922 ，2054，2209，2313，2325，2370。
ACM术语.txt我退化了，到现在我还不会游泳，要知道在我出生之前，我绝对是游的最快的那个ACM/ICPC 术语：ICPC (International Collegiate Programming Contest) 国际大学生程序设计竞赛AC (Accepted) 程序通过WA (Wrong Answer) 错误的答案 (读做“哇”)PE (Presentation Error) 输出格式错误RE (Runtime Error) 程序执行错误 (常见于数组溢出、递归层数太多 ...)CE (Compile Error) 编译错误MLE (Memory Limit Exceeded) 内存超界 (正式比赛没有内存限制，但如果用太多可能 RE) TLE (Time Limit Exceed) 程序超时错误 (死循环或算法有问题)OLE (Output Limit Exceed) 输出超界 (一般不太常见，除非你输出了超过 1024K ...)dp (Dynamic Programming) 动态编程，动态规划dfs (Depth First Search) 深度优先搜索bfs (Breadth First Search) 宽度/广度优先搜索LCS (longest common subsequence) 最长公共子串算法常用术语英中对照Approximate String Matching 模糊匹配Arbitrary Precision Arithmetic 高精度计算Bandwidth Reduction 带宽压缩Bin Packing 装箱问题Calendrical Calculations 日期Clique 最大团Combinatorial Problems 组合问题Computational Geometry 计算几何Connected Components 连通分支Constrained and Unconstrained Optimization 最值问题Convex Hull 凸包Cryptography 密码Data Structures 基本数据结构Determinants and Permanents 行列式Dictionaries 字典Discrete Fourier Transform 离散Fourier变换Drawing Graphs Nicely 图的描绘Drawing Trees 树的描绘Edge and Vertex Connectivity 割边/割点Edge Coloring 边染色Eulerian Cycle / Chinese Postman Euler回路/中国邮路Factoring and Primality Testing 因子分解/质数判定Feedback Edge/Vertex Set 最大无环子图Finite State Machine Minimization 有穷自动机简化Generating Graphs 图的生成Generating Partitions 划分生成Generating Permutations 排列生成Generating Subsets 子集生成Graph Data Structures 图Graph Isomorphism 同构Graph Partition 图的划分Graph Problems — hard 图论-NP问题Graph Problems — polynomial 图论-多项式算法Hamiltonian Cycle Hamilton回路Independent Set 独立集Intersection Detection 碰撞测试Job Scheduling 工程安排Kd-Trees 线段树Knapsack Problem 背包问题Linear Programming 线性规划Longest Common Substring 最长公共子串Maintaining Line Arrangements 平面分割Matching 匹配Matrix Multiplication 矩阵乘法Medial-Axis Transformation 中轴变换Median and Selection 中位数Minimum Spanning Tree 最小生成树Minkowski Sum Minkowski和Motion Planning 运动规划Nearest Neighbor Search 最近点对查询Network Flow 网络流Numerical Problems 数值问题Planarity Detection and Embedding 平面性检测和嵌入Point Location 位置查询Polygon Partitioning 多边形分割Priority Queues 优先队列Random Number Generation 随机数生成Range Search 范围查询rate of convergence 收敛速度robustness 鲁棒性Satisfiability 可满足性Searching 查找Set and String Problems 集合与串的问题Set Cover 集合覆盖Set Data Structures 集合Set Packing 集合配置Shape Similarity 相似多边形Shortest Common Superstring 最短公共父串Shortest Path 最短路径Simplifying Polygons 多边形化简Solving Linear Equations 线性方程组Sorting 排序Steiner Tree Steiner树String Matching 模式匹配Text Compression 压缩Topological Sorting 拓扑排序Transitive Closure and Reduction 传递闭包Traveling Salesman Problem 旅行商问题Triangulation 三角剖分Vertex Coloring 点染色Vertex Cover 点覆盖Voronoi Diagrams Voronoi图。
北京邮电大学/onlinejudge/北京大学/JudgeOnline/ (推荐) / (内部)浙江大学/ (推荐)天津大学/toj/武汉大学/oak/FELIOJ /felioj/四川大学/soj/中科大/哈工大/http://202.118.224.210华东师范杭州电子吉林大学西南科大http://222.196.33.254/JudgeOnline/哈工程/湖南大学:8080/福州大学/北航/华中科大/judge/南开大学/北师大: /contest/index.php VIJOS / (高中生的OJ)UVA http://online-judge.uva.es/problemset/URAL http://acm.timus.ru/SGU http://acm.sgu.ru/SPOJ http://www.spoj.plEL http://acm.mipt.ru/judge/problems.plKRSU .kg/USACO /usacogate中国各大高校BBS:/forum/（杭电） (浙大) (清华) (上交) (复旦) (武大)/ (浙工大) (同济) (厦大)/ (中科大)https:/// (北大)/ (南开)/ (天大)/ (中大)/ (华科)Others：http://online-judge.uva.es/board/index.php/ (uva)Others：Topcoder：/tcACM-ICPC：/icpc/美国信息学奥林匹克竞赛官方网站：/全美计算机奥林匹克竞赛：/usacogate 信息学初学者之家：/中国教育曙光网：/aosai/福建信息学奥林匹克：/fjas/index.htm IOI：http://olympiads.win.tue.nl/ioi/ACM的例程和测试数据：/Ed/ACM/ACM社区：//lewutian推荐文章:1. POJ 2777 Count Color【简单线段树】2. POJ 3468 A Simple Problem with Integers【简单线段树】3. POJ 2528 Mayor's posters【线段树】4. POJ 3667 Hotel【经典线段树】5. poj 1318 Word Amalgamation（字符串处理）6. 转载的POJ题单7. POJ-1017-jack8. poj9. POJ 312610. poj 1917 Automatic Poetry（字符串处理）。
ACM主要算法介绍初期篇一、基本算法(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, 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, poj3034)(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, poj3315, poj2148, poj1263)附录：POJ是“北京大学程序在线评测系统”（Peking University Online Judge）的缩写，是个提供编程题目的网站，兼容Pascal、C、C＋＋、Java、Fortran等多种语言。
ACM-ICPC训练方法与竞赛策略
王春平;王卫红;韩姗姗;李曲;方赵林
【期刊名称】《计算机教育》
【年(卷),期】2014(000)006
【摘要】ACM-ICPC竞赛规模日趋增大,为了提高训练效率和竞赛成绩,文章依据ACM-ICPC的知识范畴,提出程序设计的训练方法和相应的竞赛策略,引导和增强学生的程序设计能力,提出在比赛中采取正确的组队策略、团队合作策略和答题策略.【总页数】4页(P91-94)
【作者】王春平;王卫红;韩姗姗;李曲;方赵林
【作者单位】浙江工业大学计算机科学与技术学院,浙江杭州310023;浙江工业大学计算机科学与技术学院,浙江杭州310023;浙江工业大学计算机科学与技术学院,浙江杭州310023;浙江工业大学计算机科学与技术学院,浙江杭州310023;浙江工业大学计算机科学与技术学院,浙江杭州310023
【正文语种】中文
【中图分类】G642
【相关文献】
1.面向ACM-ICPC竞赛的计算机人才培养教学与实践方法 [J], 梁冰;冯林
2.关于《数据结构》课程与ACM-ICPC竞赛结合的探讨 [J], 王伟嘉;张洪萍;宁亚辉;陈勤;李余
3.基于ACM-ICPC竞赛的C语言课程教学实践 [J], 林金珠;倪天伟
4.面向ACM-ICPC竞赛的计算机人才培养教学与实践方法 [J], 梁冰;冯林
5.基于ACM-ICPC竞赛的C语言课程教学实践 [J], 林金珠;倪天伟;
因版权原因，仅展示原文概要，查看原文内容请购买。
noc编程大赛模拟题NOC编程大赛模拟题介绍NOC编程大赛是一项面向全球的计算机程序设计竞赛，旨在提高参与者的算法和编程能力。
本文将介绍一道NOC编程大赛模拟题，并详细解析该题目的解法。
题目描述有一个长度为n的数组a，每个元素都是0或1。
现在需要对这个数组进行m次操作，每次操作会给定一个区间[l,r]，并将该区间内所有元素取反（即0变成1，1变成0）。
最后输出操作后数组a的结果。
输入格式：第一行包含两个整数n和m，表示数组a的长度和操作次数。
接下来m行每行包含两个整数l和r，表示一个操作的区间范围。
输出格式：共一行，包含n个空格隔开的整数，表示所有操作执行完毕后数组a 中的元素。
数据范围：1≤n,m≤1000001≤l≤r≤n样例输入：5 31 22 41 5样例输出：0 1 0 1 0解析这是一道非常经典且基础的线段树模板题。
我们可以使用线段树来维护区间取反和查询操作。
具体来说，在每次区间取反时，我们只需要将对应区间的取反标记进行翻转即可。
在查询操作时，我们需要将所有取反标记进行异或操作，并递归地向下查询左右子节点。
详细解析1. 线段树节点结构体定义我们可以使用一个结构体来定义线段树的节点，该结构体包含了左右子节点指针、区间范围和取反标记等信息。
struct SegTreeNode {int l, r;SegTreeNode *left, *right;bool flag; // 取反标记};2. 线段树建立函数我们可以使用递归方式来建立线段树，在每个节点处判断当前区间是否为叶子节点，如果是则直接返回该叶子节点，否则递归地创建左右子节点，并将当前节点的左右指针指向这两个子节点。
SegTreeNode* build(int l, int r) {SegTreeNode* node = new SegTreeNode();node->l = l;node->r = r;if (l == r) return node; // 叶子节点int mid = (l + r) / 2;node->left = build(l, mid);node->right = build(mid + 1, r);return node;}3. 区间取反操作函数当需要对某个区间进行取反时，我们只需要将该区间的取反标记进行翻转即可。
