[转]如何考试(比赛)

转自:lkb的小屋-如何:考试
前言:我们啊,我感觉我们南海区的这些OIers还要学习一个。我们以为自己非常熟悉算法跟数据结构这些东西,我们毕竟还too young。明白我的意思吧?一些高中的学了OI将近10年的学长,或者是像江老师、梁老师这样多年的教练,他们是身经百战了,见得多啦!石中的哪一个神犇没去过省赛?我们要知道,高一的罗梓璋,那比我们不知要高到哪里去了,昨晚来跟我们谈笑风生。所以说OIers呀还是要提高自己的知识水平,我也替自己着急呀。

这篇博文主要是基于昨晚LZZ学长的presentation以及后来江老师的一些人生经验,加上本人一些各方面搜集的资料整理而成。应该还是比较全面的。

  1. 忘记屏蔽调试信息:cerr
    考试中,写一次代码就能正确的程序基本上几乎没有,绝大多数的代码都要经过调试。
    如果是像某些神犇一样用gdb调试,那么好吧,你赢了;不过大多数像在下一样的蒟蒻都会选择使用输出中间结果的方法进行调试。那么这样做有时候就可能会导致某些很尴尬的后果了——做完之后忘记把调试输出信息给删掉,或者说是屏蔽掉。然后WA,然后爆零。
    那么,这里介绍一种之前没有接触过的输出调试信息的方法:输出到cerr流中。
    这个所谓的cerr包含在iostream中,注意要using namespace std或使用的时候std::cerr。
    输出的时候直接cerr<<”hello, world”<<endl;,格式类似cout。
    直接输出到屏幕上而非文件中,因此忘记屏蔽也无大碍(但是输出这些调试信息毕竟会占用一部分时间。)
    或者,其实也可以通过宏定义+条件编译的方法来解决调试信息的问题。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include<cstdio>
    #include<iostream>
    using namespace std;
    #define __DEBUG
    int a,b;
    int main()
    {
    #ifndef __DEBUG
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    #endif
    cin>>a>>b;
    cout<<a+b<<endl;
    return 0;
    }

其中#define __DEBUG表示程序是还在调试阶段,还是已经完成了。如果你已经做完这题,就可以把这句话删掉,那么程序就会重定向到文件输入输出。
不过这种方法仍然不够保险,有可能我们忘了删掉define,那就呵呵了。
我们还可以使用另一种方法,编译选项!!
G++里面有一个叫-DDEBUG的编译选项,如果在编译的时候加上它,相当于已经define了一个DEBUG这个符号,那么你的程序就可以直接这么写:

1
2
3
4
5
6
7
8
#include<iostream>
using namespace std;
int main(){
#ifdef DEBUG
cout<<"hello, world"<<endl;
#endif
return 0;
}

而当这个程序交付评测时,由于评测机在编译的时候并没有-DDEBUG这个指令,自然也不会有DEBUG符号,你的调试信息也就自然而然不会被输出(准确的说,这一句话甚至不会被编译)。
我讲的意思不是我推荐大家用以上的方法,毕竟太麻烦;但是你一定要问我竞赛的时候可不可以用这些方法,我是告诉你可以用的,我就明确告诉你这一点。
所以,最好的方法还是,做完题目之后确定没问题了,检视一遍代码,用文件IO跑一遍。

  1. 对拍
    不得不说,对拍是一种非常好用的技巧,特别是在大型的OI竞赛中。
    所谓对拍,其实就是为了检验自己的算法是否正确,将自己程序的输出跟一个绝对正确的暴力程序的输出进行对比。我们需要写一个数据生成器(暂且命名为gen.exe),自己的程序(a.exe),暴力程序(a1.exe),然后通过批处理脚本进行对拍。
    举一个简单例子,求∑i(1<=I<=n)。各文件的模板如下(以C++为例)
    数据生成器
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #include<windows.h>
    int main()
    {
    Sleep(1000);
    freopen("a.in","w",stdout);
    int n;
    srand((int)time(0)); //调用srand()函数,以系统时间为随机种子
    n = 1 + rand()%10000; //随机生成一个1到10000的自然数
    printf("%dn",n); // 输出随机生成的自然数
    return 0;
    }

这里要注意一个细节,我们的随机数种子是根据当前时间来取,如果两次运行间隔时间太短会导致生成的数据相近(或者根本就是一样的),因此在程序运行时先Sleep个1秒。
暴力程序,时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>
#include<stdlib.h>
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int i,n;
long int sum = 0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
sum += i;
}
printf("%dn",sum);
return 0;
}

你的解答,时间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>
#include<stdlib.h>
int main()
{
freopen("a.in","r",stdin);
freopen("a1.out","w",stdout);
int n;
long int sum = 0;
scanf("%d",&n);
sum = n*(n+1)/2;
printf("%dn",sum);
return 0;
}

对拍文件,命名为*.bat,用任意的文本编辑器都可以进行编辑

1
2
3
4
5
6
7
8
9
@echo off
:start
gen.exe
type a.in
a.exe
a1.exe
fc a.out a1.out
if not ERRORLEVEL 1 goto :start
pause

完成这一切之后,双击你的bat文件就可以开始对拍。一旦发现两个程序的输出不同,对拍便会中止,然后你可以观察输出的相异处,或者直接打开a.in来看是什么数据。

  1. 如何考试
    昨晚LZZ神犇也讲了很多考场的考试步骤、思维方法等,这里不再赘述。
  2. 文件输入输出的效率问题
    这一点其实相差不大,主要是注意freopen和cin/cout搭配会很慢,如果要用freopen的话还是跟scanf/printf搭配比较好,或者直接用ifstream/ofstream也可以。实在想用cin/cout的话就关同步吧,程序开头加一句std::ios::sync_with_stdio(false);
  3. 优化输入输出
    (其实像gdoi这样的比赛应该还是用不到这一步的……好吧day3倒是有可能,不过也没有我们这些蒟蒻的份了。无论怎样还是写一写,记录下来吧,万一派得上用场呢!)
    所谓在输入方面进行一些常数优化,其实就是手写一个整数输入。因为C++自带的整数输入是很慢的(但不知道为什么,读字符/字符串却是很快),所以我们还不如一个字符一个字符地读进来,这样效率上会更快一些。在读入大规模的整数数据时比较有效。
    代码如下:

    1
    2
    3
    4
    5
    inline void read_int(int &num)
    {
    char c; while (c = getchar(), c < ‘0‘ || c > ‘9‘);
    num = c - ‘0‘; while (c = getchar(), c >= ‘0‘ && c <= ‘9‘) num = num * 10 + c - ‘0‘;
    }
  4. 数组的负数下标
    关于这个问题,其实我已经在之前的一篇博文里面提到过,不过其实当时的前两种方法都比较low,大多数同学都能熟练地使用。主要是第三种方法,大家不太了解。这里我们再复习一下:
    定义一个数组指针在原数组的中间,对这个指针进行操作,例:

    int a[100], *b = a + 50;
    b[-1] = 1; //实际上也就相当于a[49]=1;

  5. 内存占用过大?动态申请
    这个问题主要是针对有时候所开的空间太大,可能会导致爆空间。这种不确定的情况下,我们就可以动态申请数组的空间。而且这个动态申请是不同于我们平时所说的局部变量,那个是保存在栈里面,容易爆;这个动态申请使用的是堆空间,比那个不知道高到哪里去了。
    附示例代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #include<iostream>
    using namespace std;
    int main(){
    int n;
    cin>>n;
    int *p=new int[n];
    for(int i=0;i!=n;++i)cin>>p[i];
    for(int i=0;i!=n;++i)cout<<p[i]<<" ";
    return 0;
    }
  6. 数组的指针妙用。
    众所周知,数组名实际上就是指向该数组第一个元素的地址的一个指针。那么同理,&a[i]实际上也可以用a+i指代。至于效率相差如何,尚未可知。用scanf输入的时候也就可以直接这么写:scanf(“%d”,a+i);你问我支不支持?我是支持的!
    暂时想到的就这么多,等有时间想到能补充的再修改吧。
    总而言之:竞赛之中,实力固然是决定成绩的重要标准;但技巧也不可缺少,希望这篇献丑的博文能抛砖引玉,见到更多神犇的心得。