进行竞争性编程时需要重点关注的点

原文:https://www . geeksforgeeks . org/边做边专注于竞争编程/

竞争性编程对于一个人在编码领域的发展至关重要。这篇文章将讨论一些在比赛中应该记住的基本要点。

  • 制作一个函数列表来执行问题中经常遇到的任务，并以模板的形式将其添加到您的代码中。这可以节省竞赛时间，并有助于快速提交解决方案。模板中需要添加的一些有价值的功能如下:
  • 在思考解决问题的方法时，关注约束。基于约束，通过计算方法的时间复杂度，检查设计的解决方案是否能够通过所有的测试用例。
  • 只有约束足够小(比如说 2 N )不超过时间限制的情况下，才能想到位掩码或者蛮力。因此，该方法应该包括检查所有可能的结果组合。
  • 如果有一个问题涉及到输入形式的排序数据，那么考虑一个使用二分搜索法的方法。
  • 如果有与树、图 ( 循环检测等相关的问题，养成一种思维定势，想出一种围绕深度优先搜索或广度优先搜索的方法，这是解决这类问题的基本要求。
  • 数论 :
    • 两个或两个以上奇数素数的相加将始终是偶数(例如 13 + 3 = 16，19 + 5 = 24)。
    • 哥德巴赫猜想是数学(更精确地说是数论)中众所周知的未解问题之一。注:对于较大的数不证明。
    • 数论中还有其他几个概念需要掌握才能做好 CP。
  • 如果一个状态依赖于未来状态，那么用贪婪解解决问题是不可能的。此外，不能采用幼稚的方法，因为它会超过时间限制。因此，对于所有此类问题，请始终尝试使用动态规划解决方案。 如果一个人能写出一个简单的递归解就非常简单了，这个解以指数复杂度运行。将访问过的每条路径存储在内存中，以便以后用于解决问题，这称为记忆。一旦学习了记忆方法，逐渐学习制表方法。

  • If there is a question related to Bitwise Operators like XOR, OR, and AND it can changes the array by those operations then, sometimes naive approach will work as there will be at most 64 numbers with different MSBs (264 ). But in this approach, the main task is to identify the base case. Let’s take an example where a sorted array in increasing order is given and the task is to make it non-increasing by replacing two adjacent elements with their Bitwise XOR of the two minimum number of times.

    输入: arr[] = {2，5，6，8} 输出: 1 解释: 操作 1: 选择元素 2 和 5，用 2⊕5 = 7 替换 2。 现在，数组将为{7，6，8}，不递增。 因此，操作计数为 1。

    方法:这个也可以用天真的方法解决，即找到一个子阵，它的 XOR 小于子阵起点前的元素，或者小于子阵终点后的元素。

    但是，在处理基本情况之前，即如果存在 3 个连续元素，则 MSB 是相同的(例如的 MSB 的arr[I–1]= arr[I]= arr[I+1]【T3])，然后通过用 arr[i] ⊕ arr[i + 1] 替换它来获得结果。

    所以，对于天真的阵中进场只有当 N > 60 因为2*(⌊log2109⌋+1)= 60。(Let，a[i] < = 10 9 )。乘以 2，因为这是唯一可能的最后一种情况。如果乘以 3，那么肯定会有 3 个连续元素具有相同的 MSB(最高有效位)。

  • The GCD of the array elements can also be expressed as:

    gcd(a 1 ，a 2 ，⋯，an 2，an 1，a n ) = gcd(a 1 ，a2–a1，⋯，an–1–an 2，a

    证明:

    gcd(a，b) = gcd(a，b–a) gcd(a，b，c)= = gcd(a，gcd(b，c)) = gcd(gcd(a，b)，c) 那么，可以概括为: gcd(a 1 ，a 2 ，⋯，an 1，a n ) = gcd(a 1 an) = gcd(a1，a 2 ，⋯，an 2，gcd(an 1，anan 1) = gcd(a1，a 2 ⋯，gcd(an 2，an 1，anan 1) = gcd(a1，a 2 ，⋯，gcd(an 2，an 1a

  • Some of the most used Bitwise Operator properties can be:

    • a-b = a | b-a 和 b
    • a+b = a-b+2 *(a 和 b)
    • a + b = a | b + a & b

    这里的“a”和“b”是整数，⊕表示 XOR，&表示 and，|表示 OR。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://moonapi.com/news/38187.html