手记

如何准备ACM - ICPC?

首先先科普一下,非科班好多不知道ACM的。ACM ICPC(国际计算机协会 - 国际大学生程序设计竞赛)是一项世界范围的年度多层次编程竞赛,已举办了十三年。比赛由IBM赞助。

然后去年的比赛规则看这里:https://icpc.baylor.edu/worldfinals/rules

ICPC问题示例:通常的ICPC问题具有以下特点:

  1. 问题陈述:描述问题和要生成的输出。
  2. 输入:确保您完整阅读题目,因为错过任何细节都可能导致您错误回答区域。
  3. 输出:就像上面一样,这个也应该仔细阅读。
  4. 约束:这些约束可能包括输入,时间,内存,代码大小等方面的限制。
  5. 时间限制:查看该算法是否可以在此时间范围内工作。如果没有,转换思路!
    6.内存限制:如果你喜欢为每一件小事物分配内存,现在是你改变它的好时机。

准备ACM - ICPC

首要步骤:实践 - 以下是可用于实践ACM-ICPC竞赛和问题的资源。对于所有这些OJ,从最大提交的问题开始,并检查其他解决方案以检查可能的改进。参加每月的比赛以保持达标。

  • ACM-ICPC Past Problems
  • ACM-ICPC Past Problems – ICPC Archive, Practice at Codechef
  • TopCoder – Proceed by increasing problem levels gradually
  • Codeforces -List of Problem Sets
  • Codechef – Beginers can start with Codechef Beginners and proceed further
  • SPOJ – Move from easy to tough problems
  • USACO – Excellent training resource
  • uvaOnline Judge – Huge repositry of problems
  • Hackerrank – Practice problems topic wise and participate in preparatory series
  • Hackerearth – Participate in preparatory series
  • Practice – Good for beginners. Has problems ranging from difficulty level School to Hard.
    • List of various Competitive Programming Contests available online all through the year

学什么?

只知道编程的基础知识对于ACM ICPC的志向者来说并不是富有成效的。我们需要对所使用的高级算法有全面的了解。以下主题列出了必须知道的必要的主题和算法,以改善并在实际竞争中站稳脚跟。

基本数据结构:从竞争性编程开始,必须掌握数据结构。以下是最常用的数据结构列表:

  • Array
  • Stack
  • Queue
  • String
  • Heap
  • Hash
  • Extensive list of Data structures

高级数据结构

优先级队列,并查集,(增广)间隔树,(增广)平衡BST和二进制索引树

  • 二进制索引树或Fenwick树(二叉索引树)Binary Indexed Tree or Fenwick tree
  • 线段树(RMQ,范围和,延迟传播)Segment Tree (RMQ, Range Sum and Lazy Propagation)
  • K-D树(插入,最小和删除)K-D tree (See insert, minimum and delete)
  • 联合查找不相交集(循环检测和按等级和路径压缩)Union Find Disjoint Set (Cycle Detection and By Rank and Path Compression)
  • 前缀树 Tries
  • 区间树 Interval Tree

    排序和搜索:专注于学习基本概念,并熟悉所有可用的库函数。

  • 二分查找 Binary Search
  • 快排 Quick Sort
  • 归并 Merge Sort
  • 顺序统计 Order Statistics

    字符串操作

    字符串使编程问题变得既有趣又困难,也许这就是他们在这种竞赛中广泛使用的原因。学习String的库函数实际上证明非常有用(C ++:请参阅this和this,Java中的String)。

  • KMP 算法 KMP algorithm
  • 字符串匹配算法 朴素算法 Rabin karp
  • Z’s algorithm
  • Aho Corasick字符串匹配

选择正确的语言:在编程竞赛中,C ++是除了Java的首选语言,但应该始终选择一种您熟悉的语言。在任何语言中保持“CONFIDENT”是最重要的。
对于C++来说,标准模板库非常重要

  • Power up C++ STL by Topcoder – Part 1, Part 2
  • C++ Magicians – STL Algorithms

    动态编程

  • 最长的常见子序列 Longest Common Subsequence
  • 最长的递增子序列 Longest Increasing Subsequence
  • 编辑距离 Edit Distance
  • 最小分区 Minimum Partition
  • 覆盖距离的方法 Ways to Cover a Distance
  • 矩阵中最长的路径 Longest Path In Matrix
  • 子集总和问题 Subset Sum Problem
  • 一个博弈的最优策略 Optimal Strategy for a Game
  • 0-1背包问题 0-1 Knapsack Problem
  • 流水线调度 Assembly Line Scheduling
  • 最佳二叉搜索树 Optimal Binary Search Tree
  • 动态规划 DP Algorithms

回溯

  • 回溯法解迷宫
  • N皇后问题
  • 子集总和 Subset Sum
  • 着色问题 m Coloring Problem
  • 哈密​​尔顿周期 Hamiltonian Cycle

贪婪算法

  • 活动选择问题 Activity Selection Problem
  • Kruskal的最小生成树算法
  • 霍夫曼编码
  • 用于排序输入的高效霍夫曼编码 Efficient Huffman Coding for Sorted Input
  • Prim的最小生成树算法

图算法

在准备ACM - ICPC时,你不能忽视的最重要的主题之一。

  • 广度优先搜索(BFS)
  • 深度优先搜索(DFS)
  • 从源到所有顶点的最短路径 Dijkstra Shortest Path from source to all vertices Dijkstra
  • 从每个顶点到每个其他顶点的最短路径 Floyd Warshall Shortest Path from every vertex to every other vertex Floyd Warshall
  • 最小生成树 Prim
  • 最小生成树 Kruskal
  • 拓扑排序
  • 约翰逊的算法 Johnson’s algorithm
  • 图形中的关节点(或切割顶点) Articulation Points (or Cut Vertices) in a Graph
  • Bridges in a graph

基础数学

算术:程序员必须知道计算机内部是如何表示整数和实数的,并且应该能够编写高精度数字。位操作技巧和知道数字基本算术的库函数将非常有帮助。

数论:知道这些概念中的一些会在竞赛中编程时节省大量的时间和精力。

  • 模幂运算 modular exponentiation
  • 模乘逆元 Modular multiplicative inverse
  • 原始性测试|第2套(费马法)Primality Test | Set 2 (Fermat Method)
  • 欧拉的Totient函数 Euler’s Totient Function
  • 找质数算法之埃拉托色尼筛选法 Sieve of Eratosthenes
  • 凸包 Convex Hull
  • 欧几里德算法的基本和扩展 Basic and Extended Euclidean algorithms
  • Segmented Sieve
  • 中国余数定理 Chinese remainder theorem
  • 卢卡斯定理 Lucas Theorem

    组合数学

    组合对于估计算法的渐近复杂性非常重要。

  • 算法分析
  • 组合博弈论 Combinatorial Game Theory | Set 1 (Introduction)

几何算法

  • 凸包
  • Graham扫描算法
  • Line Intersection
  • 矩阵求幂
  • 在线构建3D凸包
  • Bentley Ottmann算法列出n条线段的所有交点
  • Rotating Calipers Technique
  • 矩形结合的面积/周长 Area/Perimeter of Union of Rectangles
  • 最近对点 Closest pair of points
  • Area of Union of Circles
  • Delaunay Triangulation of n points
  • Voronoi Diagrams of n points using Fortune’s algorithm
  • Point in a polygon problem 指出多边形问题

网络流算法

  • Maxflow Ford Furkerson Algo and Edmond Karp Implementation
  • 最小割与最大流 mincut maxflow
  • 穩定婚姻问题 Stable Marriage Problem
  • Dinic的最大流和Wiki算法
  • 最小费用流问题
  • 连续最短路径算法
  • 循环取消算法 Cycle Cancelling algorithm
  • 最大加权二分匹配 Maximum weighted Bipartite Matching (Kuhn Munkres algorithm/Hungarian Method)
    • 匈牙利算法Wiki Hungarian Algorithm Wiki
    • 匈牙利分配问题算法 Hungarian Algorithm for Assignment Problem
    • 最大二分配匹配 Maximum Bipartite Matching
  • Stoer Wagner最小化算法
  • 一般图中的最大匹配(Blossom Shrinking)
  • Gomory-Hu树
  • 中国邮差问题 Chinese Postman problem
  • 用于最大匹配的Hopcroft-Karp算法

高级算法

位算法,随机算法,分支界定法(Branch and Bound),数学算法(Mathematical Algorithms),树链剖分(Heavy Light Decomposition),A *搜索

原文:https://www.geeksforgeeks.org/how-to-prepare-for-acm-icpc/
翻译:含笑666(对算法不了解,给小白涨涨见识吧)

7人推荐
随时随地看视频
慕课网APP