编程竞赛的C++技巧_vlambda技术博客

vlambda
2020-02-20

编程竞赛的C++技巧

尽管实践是确保在编程竞赛中提高性能的唯一方法，但是掌握一些技巧可以确保较高的优势和快速的调试。

1）在不使用％运算符的情况下检查数字是偶数还是奇数

尽管此技巧并不比使用％运算符好多少，但有时还是有效的（使用大量数字）。使用&运算符：

if (num & 1)
   cout << "ODD";
else
   cout << "EVEN";

例如:
num = 5
Binary: “101 & 1” will be 001, so true
num = 4
Binary: “100 & 1” will be 000, so false.

2）快速乘法或除以2

乘以2表示将所有位向左移动，而除以2则表示向右移动。

示例：2（二进制10）：向左移动4（二进制100），向右移动1（二进制1）

n = n << 1;   // Multiply n with 2
n = n >> 1;   // Divide n by 2

3）使用XOR交换2个数字

这种方法速度快，不需要使用第三个变量。

// A quick way to swap a and b
a ^= b;
b ^= a;
a ^= b;

4）避免使用strlen()

//  Use of strlen() can be avoided by:
for (i=0; s[i]; i++)
{
}
// loop breaks when the character array ends.

5）emplace_back（）的使用

代替STL中的push_back（），可以使用emplace_back，因为它速度更快，而不是在其他地方分配内存，然后附加它直接在容器中分配内存。

6）内置的GCD函数

C ++具有内置的GCD函数，无需显式编码。语法：

__gcd（x，y）;

7）使用内联函数

我们可以创建内联函数并使用它们，而不必在比赛中进行编码。示例：（a）用于筛子的功能，（b）用于回文法的功能。

8）数组的最大大小

我们必须知道在主函数中声明的数组的最大大小为10 ^ 6左右，但是如果全局声明数组，则可以声明其最大大小为10 ^ 7。

9）计算最高位数

要计算任何数字的最高位数，可以直接使用log进行计算。

Suppose the number is N then
Let double K = log10(N);
now K = K - floor(K);
int X = pow(10, K);
X will be the most significant digit.

10）直接计算数字位数

要计算数字中的位数，而不是循环，您可以有效地使用log：

Number of digits in N =floor(log10(N)) + 1;

11）知道一个数是2的幂的有效技巧

用普通的除法技术来证明复杂性是O（Logn），但它可以用O（v）来求解，其中V是二进制数的位数。

/* Function to check if x is power of 2*/
bool isPowerOfTwo (int x)
{
  /* First x in the below expression is
    for the case when x is 0 */
  return x && (!(x&(x-1)));
}

12）C ++ 11内置了以下算法

// are all of the elements positive?
all_of(first, first+n, ispositive());

// is there at least one positive element?
any_of(first, first+n, ispositive());

// are none of the elements positive?
none_of(first, first+n, ispositive());

有关详细信息，请参考C ++ STL中的数组算法（all_of，any_of，none_of，copy_n和itoa）。

13）复制算法

用于将元素从一个容器复制到另一个容器。

int source[5] = {0, 12, 34, 50, 80};
int target[5];
// copy 5 elements from source to target
copy_n(source, 5, target);

有关详细信息，请参考C ++ STL中的数组算法（all_of，any_of，none_of，copy_n和itoa）。

14）Iota算法

iota()创建一系列按顺序递增的值，就像通过先给**分配初始值，然后使用前缀++递增该值一样。在下面的清单中，iota()将连续值{10、11、12、13、14}分配给数组arr，并将{'a'，'b'，'c'}分配给char数组c []。

int a[5] = {0};
char c[3] = {0};
  
// changes a to {10, 11, 12, 13, 14}
iota(a, a+5, 10);
iota(c, c+3, 'a'); // {'a', 'b', 'c'}

有关详细信息，请参考C ++ STL中的数组算法（all_of，any_of，none_of，copy_n和itoa）。

15）二进制形式的初始化

在C ++ 11中，也可以二进制形式进行赋值。

// C++ code to demonstrate working of
// "binary" numbers
#include<iostream>
using namespace std;
int main()
{
    auto number = 0b011;
    cout << number;
    return 0;
}

输出：

16）使用“and”

尽管不是很高效，但该技巧可帮助您仅使用条件运算符，而不必键入＆。

// C++ code to demonstrate working of "and"
#include<iostream>
using namespace std;
int main()
{
    int a = 10;
    if (a < 20 and a > 5)
      cout << "Yes";
    return 0;
}

输出：

Yes

vlambda博客
学习文章列表