算法竞赛头文件与文件读写

要开始进行算法竞赛的训练了,训练的内容主要在USACO的Training和几本比较知名的算法竞赛的参考书中。这篇文章主要总结一下训练之前的准备,有关头文件的选择和基本的文件读写技巧。参考了CodeForces的Solutions和算法竞赛宝典书中的内容。

我自己用的是Ubuntu的虚拟机进行操作,然后使用的是zsh+vim+tmux的组合,配置的话是用我自己的dotfiles

头文件

这是一个小的Tip,是我在做CodeForces的题中发现的。很多竞赛者使用了<bits/stdc++.h>这个头文件。这个文件囊括了每一个C++的标准库,也就是说其实是标准库的汇总,不需要再繁琐的一个一个#include。在竞赛中,这个文件非常方便,减少了很多时间上的浪费。但是从软件工程的角度来看,这个头文件又不能很实际的用在工程项目中,因为包含了很多不必要的库,这样加大了编译时间也使得项目文件的大小变的更大了。

所以使用这个头文件的最好的场合就是算法竞赛,在平日的编程和训练中,最好还是一个一个#include,这样可以加深印象。如果有想要了解这个头文件中包含哪些库的,可以看这里

#include <bits/stdc++.h>

文件读写

通常在竞赛中,需要测试多组数据。文件的读写成为了一个非常基础的技能。在算法竞赛宝典书中列举了4种不同的文件读写方法,在这里做一个汇总和分析。

方法1:freopen重定向

这种方法是使用文件最简单的方法,将输入和输出重定向到指定文件中,在不知文件中含有多少数值的情况下,可以参照以下样例:

#include <iostream>
#include <cstdio>

using namespace std;

int a[10], i, n;
int main() {
  freopen("a.in", "r", stdin);
  freopen("b.out", "w", stdout);
  
  for (i = 0; cin >> a[i]; i++);

  n = i;
  for (i = 0; i < n; i++) {
      cout << a[i] << ' ';
  }

  return 0;
}

方法2:FILE*法

这种方法要比重定向复杂,但是其灵活度高,而且读取速度快,所以在书中推荐使用此方法。以下是样例:

#include <iostream>
#include <cstdio>

using namespace std;

int main() {
  int i, len = 0, temp[10];
  FILE* in = fopen("a.in", "r");
  FILE* out = fopen("b.out", "w");

  for (i = 0; !feof(in); i++) {
    fscanf(in, "%d", &temp[i]);
    len++;
  }

  for (i = 0; i < len-1; i++) {
    fprintf(out, "%d ", temp[i]);
  }

  fclose(in);
  fclose(out);

  return 0;
}

FILE说明:每个被使用的文件都在内存中开辟一个区,用来存放文件中的信息。这些信息是保存在一个结构体类型中,名为FILE。文件读写完毕后则需要使用fclose函数进行关闭。

feof函数说明:其作为文件的指针,拥有两个返回值。当遇到文件结束符时返回1,否则返回0。

fscanf与fprintf函数说明: 这两个函数作为格式化读写函数,读写对象为文件。

方法3:fstream法

使用了fstream头文件,书中推荐给C++学习者使用。以下是样例:

#include <iostream>
#include <fstream>

using namespace std;

int a[10], i, n;
int main() {
  ifstream fin("a.in");
  ofstream fout("b.out");

  for (i = 0; fin >> a[i]; i++);

  n = i;
  for (i = 0; i < n; i++) {
    fout << a[i] << ' ';
  }

  fin.close();
  fout.close();

  return 0;
}

方法4:fread法

fread函数:size_t fread(void* ptr, size_t size, size_t count, FILE* stream);

  1. ptr:用于接受数据的地址(指针)
  2. size:单个元素的大小,单位为字节(不是位)
  3. count:元素的个数
  4. stream:提供数据的文件指针
  5. return:读取元素的个数

需要注意的是fread是按照char类型读取的。

#include <iostream>
#include <cstdio>

using namespace std;

FILE* in = fopen("a.in", "rb");
int mark = 0;
char a[10];

int getnum() {
  int obj = 0;

  while(!(a[mark] >= '0' && a[mark] <= '9')) {
    mark++;
  }

  while (a[mark] >= '0' && a[mark] <= '9') {
    obj = obj*10 + a[mark++] - '0'; 
  }

  return obj;
}

int main() {
  freopen("b.out", "w", stdout);

  int i, temp[10];
  fread(a, 6, 10, in);

  for (i = 0; i < 10; i++) {
    temp[i] = getnum();
  }

  for (i = 0; i < 10; i++) {
    cout << temp[i] << ' ';
  }

  return 0;
}

Read more: