算法竞赛开始前的准备

参加过几场信息竞赛过后,发现赛场上虽然有三四个小时的时间来做题,但是时间还是很紧。比赛时算法设计占用主要时间,编码和调试其次,上厕所最少。调试真的是非常消耗时间的,而我不可能一次性写出完美代码,所以非常有必要找到加快调试时间的方法。赛前观察其他选手,会看到大家都在调整配色方案、敲代码,做各种各样的准备。我只能干坐着,因为真的没有什么好干的。算法竞赛开始前的准备十分必要。这几天我上Codeforces膜拜大神们,又收获不少。收获最大的当然是程序前部分的实用函数,如果使用熟练了,编码、调试速度将会大大加快!

我照猫画虎,先写了一个模板出来:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cmath>
 
#define clr(x) memset(x,0,sizeof(x))
#define fort(i,n) for(int i=0;i<(n);i++)
#define forf(i,n) for(int i=(n);i>=0;i--)
#define timer() ((ldouble)clock()/CLOCKS_PER_SEC)
#define valid(x,y,m,n) ((x)>=0&&(x)<(m)&&(y)>=0&&y<=(n))
#define bitat(num,d) ((num>>d)&1)
#define synf() ios::sync_with_stdio(false),cin.tie(0)
#define debug(n) {cerr<<#n<<"="<<n<<endl;}
 
using namespace std;
typedef long long lint;
typedef long double ldouble;
template<typename T> T gcd(T a, T b){return a?gcd(b%a,a):b;}
 
int main(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
     
}

里面还有很多东西我其实没有接触过,我也没有想到过。比如说,在fort函数里的n要打上括号,因为define宏所做的仅仅是替换,所以可能造成优先级的问题;为了避免,打上括号。

template <typename T>这一句好像意思是不指定变量类型,接收到什么就是什么。在网上查template的含义,也并没有看懂。姑且这么认为吧。

synf中的第一句之前看别人的代码的时候学到的,第二句是在Codeforces上看到的。这一句的主要作用是加快cincout的读写速度,使其与scanf、printf一样快。ios::sync_with_stdio(false)取消了这两种读写方式的文件指针同步,混用可能会导致指针混乱,所以在使用的时候注意一下就好了。cin.tie(0)就更奇怪了,没怎么搞懂,我参考了这里

debug中用到了一个cerr函数。经过互联网搜索,发现cerr是一个不可重定向的窗口输出,但是用法和cout一模一样。这意味着这是一个极佳的调试工具!虽然如此,我还是建议在提交的时候注释掉这个语句,不然可能判错&增加所需时长。

debug中还有一个#n的写法。经实测发现会得到n本身构成的字符串。非常方便!这样调试输出的时候就不需要手动输入变量名了。

我还发现大家比较喜欢使用pair来储存多维的信息。pairfirstsecond储存两个值,如果有三个,大家就自己写结构体或者用pair<A,pair<B,C>>来代替。难道不能用多一维数组来储存吗?之前老师说因为C++ STL会兼顾到通用性,所以效率不会有自己写的高。

点坐标可以使用complex来储存。complex是一个STL的复数,本来想自己写一个类似的东西,没想到别人已经写出来了。

还有一些非常常用的库,我之前都十分抵触,但现在发现,这些库被创造出来就是来被使用的啊!我以前十分抵触algorithm库的sort排序,每次都坚持自己写代码;后来用多几次就发现,sort十分方便,可以大大减少编码量和编码时间!STL中,队列是queue,栈是stack,动态数组是vectorlist,集合是set……

关于vectorlist的区别我还稍稍查了一下,概括起来大概是这样:

  • vector是顺序表,表示的是一块连续的内存,元素被顺序存储;list是双向连接表,在内存中不一定连续。
  • 当数值内存不够时,vector会重新申请一块足够大的连续内存,把原来的数据拷贝到新的内存里面;list因为不用考虑内存的连续,因此新增开销比vector小。
  • list只能通过指针访问元素,随机访问元素的效率特别低,在需要频繁随机存取元素时,使用vector更加合适。
  • 当向vector插入或者删除一个元素时,需要复制移动待插入元素右边的所有元素;因此在有频繁插入删除操作时,使用list更加合适。

所以我感觉,无论是list还是vector,效率都还是大问题……

总结一下,在C++STL库的使用这方面,还有很多东西要学习,而且要谨慎考虑它们的效率。至于赛前的编码,其实都是不必要的,只是为了节省场上的时间。在之后的学习中,应该会碰到更多的可简化的代码,到时候再慢慢添加吧。

avatar
Kerry Su