算法竞赛的一些小技巧

Love The Way You Lie 2022-10-22 09:23 325阅读 0赞

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  简介
 *  由数据范围反推算法复杂度以及算法内容
 *  熟悉常见的 2 的多少次方
 *  头文件模板
 *  全局变量定义数据范围
 *  全局变量开数组
 *  0x3f3f3f3f
 *  熟悉各种变量的数据范围
 *  蓝桥杯一定要写return 0;
 *  数组开多大?
 *  关于输入输出的速度
 *  如何处理 Segment fault 错误
 *   *  Segment fault 错误出现的原因
     *   *  内存访问越界
         *  非法指针
         *  堆栈溢出
     *  解决方法
 *  打表找规律
 *  循环 n 次与循环 n - 1 次
 *  puts()
 *  如何让 Dev C++ 支持 C++11

# 简介 #

本篇博客来总结一下博主所了解的有关算法竞赛的一些小技巧，如果有不足或者需要补充的地方欢迎大家评论留言，我会随时补充更新。

# 由数据范围反推算法复杂度以及算法内容 #

`一定要认真看题目的数据范围！一定要认真看题目的数据范围！一定要认真看题目的数据范围！` 因为有时候题目可能是以前你做过的题目，但是数据范围不一样了，那么可能就是另外一种做法了！ 。而且题目的数据范围还可以告诉我们很多信息，根据题目的数据范围甚至可以提前大概判断出用什么算法可以解决该问题，有该算法解决该问题是否合理，是否会`TLE`。

详见博客：[如何由数据范围反推算法复杂度以及算法内容][Link 1]

# 熟悉常见的 2 的多少次方 #

*  **21 ~ 210 分别是：2， 4， 8， 16， 32， 64， 128， 256， 512， 1024**
 *  **215 = 32768**
 *  **216 = 65536**
 *  **220 = 1 048 576（大概是106）**
 *  **263 = 9.2233720368548e+18（大概是1018）**

# 头文件模板 #

比赛之前可以先开几个文件来写每一个题目，先打好一个框架，然后多复制几份，可以节省时间。如果程序还需要其他的头文件比赛的时候直接添加即可。

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <stack>
    
    using namespace std;
    
    int main(){ 
        
        return 0;
    }

# 全局变量定义数据范围 #

一般使用 `const` 定义一个全局变量定义数据范围。比如数据范围为 **n = 1000000**，那么就可以定义为：

#include <iostream>
    
    using namespace std;
    
    const int N = 1000010;
    
    int main(){ 
        
        return 0;
    }

# 全局变量开数组 #

C++ 全局变量存储在 `堆空间` 中，局部变量存储在 `栈空间` 中，将较大的数组开成全局变量不容易爆栈，而且自动将变量全部初始化，如果是数字那么全部初始化为 `0`，`bool` 数组全部初始化为 `false`。而且定义为全局变量如果参数要使用的话就不用再传参了，直接在函数中使用即可。

#include <iostream>
    
    using namespace std;
    
    const int N = 1000010;
    
    int q[N][N]; // 全部自动初始化为 0 
    bool st[N];  // 全部自动初始化为 false 
    
    int main(){ 
        
        return 0;
    }

# 0x3f3f3f3f #

这是一个很神奇的数字。当需要把一个数组中的数值初始化成 **正无穷** 时，为了避免加法算数上溢或者繁琐的判断，可以使用`#include<cstring>`头文件中的 `memset()` 函数 **memset(a, 0x3f, sizeof a)** 给数组赋值成 **0x3f3f3f3f** 的值来代替。这个数转换成十进制为：**1061109567** 它的两倍为：**2122219134**。而 **int** 的最大值为：**2147483647**。所以在很多题目中用它表示正无穷可以更加方便我们写程序。

# 熟悉各种变量的数据范围 #

具体的数据范围请看：**[C/C++ 各种变量的数据范围][C_C_]**

# 蓝桥杯一定要写return 0; #

如果参加蓝桥杯不写 `return 0;` 的话即使程序写对了，运行结果也没错，也会不得分。所以在平时练题的时候要养成好习惯。

# 数组开多大? #

一般为了防止越界，会将数组大小多开 `10` 个。比如数据范围为 **1 <= n <= 10000** 那么最好将数组大小开到 **10010**。

# 关于输入输出的速度 #

当题目的数据范围为 **N ＞  1 0 5 10^5 105** 时，在解题时`最好使用 scanf() 输入，用 printf() 输出`，如果用 cin 和 cout 所需的时间会更多，可能会超时。所以当输入数据的规模超过  1 0 5 10^5 105 时 `最好使用 scanf() 输入，用 printf() 输出`。规模小于  1 0 5 10^5 105 两者消耗的时间差不多，都可以使用。

# 如何处理 Segment fault 错误 #

## Segment fault 错误出现的原因 ##

引起 `Segment fault` 错误的原因有很多种，一般在做算法题目的时候引起该错误的原因主要如下：

### 内存访问越界 ###

1.  访问数组时使用错误的下标，导致数组访问越界。
2.  搜索字符串时，依靠字符串结束符来判断字符串是否结束，但是字符串没有正常的使用结束符。

### 非法指针 ###

1.  使用空指针
2.  新申请指针忘记赋 `NULL`，也忘记分配空间，直接使用造成非法访问。

### 堆栈溢出 ###

数组开的非常大，导致堆栈溢出。

## 解决方法 ##

当做题遇到 `Segment fault` 错误时是不好调代码的，因为通常编译器只会报这个错误，但是不会报出现错误的具体地址。这时候可以使用 `exit(0)` 函数（正常退出程序）来定位错误出现的地方。具体操作方法为：结合 **二分方法**，每次将 `exit(0)` 放在整个代码段的中间，如果程序正常结束，说明错误在后半段，否则说明错误出现在前半段，这样依次二分下去很快就可以定位到出错的地方。

# 打表找规律 #

如果有些数学题目没有任何想法，可以先试试打表找找规律，可能会找到解决题目的公式，或者某些规律。

# 循环 n 次与循环 n - 1 次 #

在写 `while` 循环时，如果需要循环 **n** 次可以这样写：`while(n--)`。当需要循环 **n - 1** 次时则可以写成：`while(--n)`。

# puts() #

需要输出回车换行时，可以直接使用 `puts("");` 语句。需要包含 `#include<cstdio>` 头文件。

# 如何让 Dev C++ 支持 C++11 #

如果 Dev C++ 不设置的话可能没法使用 C++ 11。手动设置的方法为依次点击：**Tools -> compiler Options** 然后在 **compiler Options** 界面勾选 **Add the following commands when calling the compiler** ，在其下面的框中添加 `-std=c++11` 命令，最后点击 **OK** 即可。  
![演示图片][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]

--------------------

> 未完待续，持续更新中……  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70 1][]

[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[Link 1]: https://ac-fun.blog.csdn.net/article/details/108228819
[C_C_]: https://ac-fun.blog.csdn.net/article/details/108007401
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20221022/6e3b4e953bba4e0d9453a36198af950e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70 1]: /images/20221022/eac14f35638e4a2895682b28df31032a.png