竞争性编程：征服给定问题

编程是开发和实现指令集的过程，以使计算机能够完成特定任务。ACM ICPC、Google CodeJam和IEEE Extreme等编程竞赛是探索程序员智能的令人愉快的游乐场。 从最初了解比赛到参加ACM ICPC Amritapuri Regionals，我学到了很多东西，我想和大家分享一些解决比赛问题的技巧。

在实时竞赛中，由三名学生和一台计算机组成的小组将在5小时内解决尽可能多的给定问题。解决问题最多的团队获胜，“解决”意味着为一组测试输入（琐碎和秘密）生成正确的输出。虽然团队成员的个人技能很重要，但为了成为顶级团队，有必要利用团队内部的协同作用。

然而，为了充分利用策略，尽可能磨练你的个人技能也很重要。你不一定非得是天才，因为练习可以让你走得很远。就感觉而言，有三个因素对成为一个优秀的编程团队至关重要：

1. 具备标准算法的知识，能够为集合中的每个问题找到合适的算法
2. 将算法编码到工作程序中的能力
3. 与队友制定合作策略

什么是算法？

算法 是计算机要遵循的一步一步的指令序列。

要想在编程竞赛中做一些有竞争力的事情，你需要了解很多知识 著名算法 以及识别哪些算法适用于特定问题（如果问题简单）或哪些算法组合或变体（如果问题稍微复杂一点）的能力。

快速识别问题类型的能力

在所有编程竞赛中，只有三类问题：

1. 我以前没见过这个。
2. 我以前见过这种类型，但没有或无法解决它。
3. 我以前解决过这种问题。

在编程竞赛中，你将处理一组问题，而不是一个问题。在上述上下文分类中快速识别问题的能力（还没有看到、已经看到、已经解决）将是在编程竞赛中取得好成绩的关键因素之一。就我的知识和知识库而言，问题通常分为以下几类：

1. 数学 ：素数、大整数、置换、数论、阶乘、斐波那契、序列、模
2. 动态规划 ：最长公共子序列、最长递增子序列、编辑距离、0/1背包、硬币兑换、矩阵链乘法、最大间隔和
3. 图的遍历 ：洪水填充、Floyd Warshal、MST、最大二分体匹配、网络流量、连接点
4. 分类 ：冒泡排序、快速排序、合并排序、选择排序、基数排序、桶排序
5. 搜索 ：完整搜索、暴力、二进制搜索
6. 字符串处理 ：字符串匹配，模式匹配
7. 临时问题 ：琐碎的问题

分析算法的能力

你已经发现了你的问题。你以为你知道怎么解决它。你现在必须问的问题很简单：给定最大输入范围（通常在问题描述中给出），我的算法能否以我可以计算的复杂度通过编程竞赛中给出的时间限制。

通常，解决问题的方法不止一种。然而，其中一些可能是错误的，一些可能不够快。然而，经验法则是：头脑风暴许多可能的算法-然后选择最愚蠢的工作！

记住以下顺序有助于快速确定哪种算法渐进性能更好： 常数

对问题进行编码

遵循KISS的原则：保持简单和智能，保持所有版本都正常工作，并逐步完善代码。

使用最佳算法编码后，匹配时间/空间复杂度并满足测试用例（样本测试用例很简单，所以永远不要根据它们来衡量代码的正确性，也不要尝试复杂的用例），然后提交解决方案–’ “接受” 识别一个棘手的测试用例来击倒对手，这与解决你的大脑更多地在边界条件下工作的问题一样重要。

总而言之，以下是一些关键点：

1. 阅读所有问题，按从容易到难的顺序选择问题（如果每个人都在解决选定的问题，一定要看一看）
2. 概述算法、复杂性、条件、数据结构和棘手的细节
3. 头脑风暴其他可能的算法（如果有的话）——然后选择最愚蠢的算法
4. 做所有的数学运算，选择最好的算法。
5. 尽可能快地给它编码，它必须是正确的。
6. 尝试打破算法——注意边界测试用例。

成功解决问题的主要诀窍是保持冷静，管理好自己的时间，采取一种战略性的方法，让自己的经验得到休息，并在其中发挥作用。

保持 练习 !!

本文作者 维尼·加格。 如果你喜欢Geeksforgek，并想贡献自己的力量，你也可以写一篇文章，然后把你的文章发到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论