算法竞赛的一些小技巧

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

简介

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

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

 详见博客:如何由数据范围反推算法复杂度以及算法内容

熟悉常见的 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++ 全局变量存储在 堆空间 中,局部变量存储在 栈空间 中,将较大的数组开成全局变量不容易爆栈,而且自动将变量全部初始化,如果是数字那么全部初始化为 0bool 数组全部初始化为 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++ 各种变量的数据范围

蓝桥杯一定要写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 两者消耗的时间差不多,都可以使用。


未完待续,持续更新中……
算法竞赛的一些小技巧

版权声明:玥玥 发表于 2021-04-01 2:20:46。
转载请注明:算法竞赛的一些小技巧 | 女黑客导航