首页 > > 程序设计 > C/C++ >

debug？用对拍！

2018-07-22 05:46:44来源：博客园阅读 ()

很多人考noip之类的比赛永远会发生一些奇怪的问题

比如说下面这两位（来自我的两位学长）

sliver n：spli，考得怎样啊？

spli：就那样啦，day1T1没推出来规律，别的还好

silver n：看来你省一高分预定啊

几周后。。。

silver n：分出来了吗？

spli：出来了。。。

silver n：怎么了？

spli：别提了，day2T2挂了，没拿上省一

silver n：嗯？？？你写的不是正解么？

spli：是啊，可是我边界处理出锅了。。

silver n：。。。

好吧，以上是一个本能进队的大佬无奈退役的经历

同时也告诉了我们检查的重要性

废话少说，进入正题

很多时候我们在考场上总是会手残的犯一些错误（比如边界什么，大小写，变量名）

然后你眼残也看不出来，怎么办呢？

我们今天就要讲这些的克星：对拍

对拍不能解决一切问题，但却可以解决你解决不了的问题

工具：一台电脑（没错，只用一台电脑）

软件：命令提示符（别告诉我你家电脑上没有这个东西），记事本，c++编译器

下面我们来开始愉快的对拍之旅（这里讲的是关于命令提示符的对拍，大家可以把他搬到c++里（用windows库），但容易出锅（我就出过几次））

（注意，本篇文章默认使用windows系统！！！）

首先，我们先掌握几个前置技能：

1.编写你的认为是正解的程序和暴力程序（你要不会我也没办法了）

2.数据生成器（也就是随机数）

先说随机数

相信大家一般用随机数都是用

#include<cstdlib>

库中的rand（）函数，但这显然是不正确的

因为rand（）是伪随机数！！！

只要出题人想卡你，跑两遍随机数，打个表，数据避开一下

你的答案一不小心就出锅了

所以，今天我们学如何生成真正的随机数：

首先，我们先明确一点，c++里面的随机数是一种算法

这个算法依赖于一个被称为种子的数据

种子一般情况下是1

由于算法是固定的，所以种子不同，随机数也就不同

所以关键就在于随机数种子的生成。

我们一般使用时间种子生成器(time()函数)

（如果以时间为种子，这个种子一秒钟一变，出题人想卡你的话那他简直是疯了）

怎么用呢？看下面：

首先我们要添加time（）的头文件：

#include<ctime>

之后，我们就可以使用这个函数了！！看图

有了种子，我们就要利用种子生成随机数了。

我们有请srand（）函数登场。

srand（）函数类似于cmp或者重载运算符函数之类的函数

在这里他被用于改变种子

用法：

先加头文件（和rand（）一样）：

#include<cstdlib>

然后看下面：

其实还有一点，是文件操作，我就默认你们会了（每次考试都会用）

好了，该有的都有了，下面我们就来一个制造数据的实例吧！

我以洛谷P3372【模板】线段树 1为例：

题面：

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式：

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1：格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2：格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式：

输出包含若干行整数，即为所有操作2的结果。

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=1000，M<=10000

对于100%的数据：N<=100000，M<=100000

（数据已经过加强^_^，保证在int64/long long数据范围内）

由题目可知，我们要造的是n，m，n个原始节点，m次操作，且节点值的和在long long范围内，n,m<=100000

具体实现请看代码：

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#define rii register int i
#define p 100000
using namespace std;
long long seed;
long long n,m;
int main()
{
    freopen("xds1.in","w",stdout);//文件操作，得到输入文件 
    seed=time(0);
    srand(seed);
    n=rand();//windows下rand()max为32768，为了有一定的强度，我们乘一下 
    n*=n;//n,m这里你也可以手动取值 
    n%=p;
    m=rand();
    m*=m;
    m%=p;
//    n=10,m=10; 
    printf("%lld %lld\n",n,m);
    for(rii=1;i<=n;i++)//制造原始大小 
    {
        long long out=rand();
        out*=2333; 
        long long fh=rand();//添加负数 
        if(fh%2==0)
        {
            fh=1;
        } 
        else
        {
            fh=-1;
        }
        printf("%lld ",out*fh); 
    }
    printf("\n");
    for(rii=1;i<=m;i++)//制造操作 
    {
        long long cz=rand();
        if(cz%2==1)//生成修改操作的数据
        {
            printf("1 ");//生成添加操作的数据 
            long long fh=rand();//添加负数 
            if(fh%2==0)
            {
                fh=1;
            } 
            else
            {
                fh=-1;
            }
            long long l=rand(),r=rand(),val=rand();
            l*=l;
            l%=n;
            if(l==0)
            {
                l=1;
            }
            r*=r;
            r%=n;
            if(r==0)
            {
                r=1;
            }
            val*=fh;
            val*=2333;
            if(l>r)
            {
                swap(l,r);
            }
            printf("%lld %lld %lld\n",l,r,val);
        }
        else //生成查询操作的数据
        {
            printf("2 ");
            long long l=rand(),r=rand();
            l*=l;
            l%=n;
            if(l==0)
            {
                l=1;
            }
            r*=r;
            r%=n;
            if(r==0)
            {
                r=1;
            }
            if(l>r)
            {
                swap(l,r);
            }
            printf("%lld %lld\n",l,r);
        }
    }
    //区间和最大值上限在我写的数据中为
    //32768*100000*100000*2333=764477440000000000
    //    long long max=2^63-1=9223372036854775807,确保符合题意 
}

下面是一组我造出来的数据（为了能放的下，n，m我手动设定为10）

10 10
1632165 90637 4875292 6168675 -6979981 3452128 5007170 -6946895 3268524 1131914 
1 4 9 6775873
1 4 9 -1544790
1 6 9 6904023
2 5 6
1 1 4 3328405
1 1 6 2169929
2 4 9
1 1 9 3784852
1 1 6 -1164534
1 1 4 -5979013

怎么样？还不错吧？

3.windows文件操作（windows script语言）

这个大家可能不太熟悉，

不过没关系，我会把可能用到的都讲一遍。

（1）文件比较操作：

也就是比较两个文件，判断这两个文件是否相等

我们一般用命令提示符（cmd.exe）操作（也可以写成.bat批处理文件）

如果两个文件相等，他会返回：（有点不智能，无法忽略空格和回车）

如果不相等，他会返回错误的地方：

很好用吧?

（2）启动程序操作

RT，就是启动一个位于与cmd/.bat同文件夹内的程序（其实也可以启动不同文件夹里的，不过要写路径）

代码极短：

就是这样。

（3）暂停操作

你会发现：哎，我的代码没错啊，为什么闪退了？

的确，你没写错

但电脑默认执行完一个操作后自动跳出

所以看起来像闪退。

怎么办呢？

我们可以让电脑完成操作后“暂停”一下。

看代码：

电脑会停下来，直到你按一下键盘

4.在c++语言中引入windws script语言：

这个很重要，因为循环什么的在windows script中很难实现

我们首先要在c++中引用头文件：

#include<windows.h>

引用了这个头文件，我们就可以使用system（）函数

样例：

system("pause");

在括号和引号中间写你要执行的window语句即可

5.Sleep挂起操作

有的时候，你会发现对拍将两个正确的输出拍成错的了，这是为什么呢？

很简单，比如说上面那道线段树，正解跑一秒，暴力4~5秒

但程序的命令行才不管你跑了几秒，执行完一个立马执行下一个

所以喽，和可能你的数据还没来得及输出完，就已经被比较了

不错才怪呢！

所以我们要写Sleep（）函数（注意S大写！！）

暂停一段时间程序的运行，让你的暴力好好跑一跑

怎么实现呢？很简单，看下面：

头文件：

#include<windows.h>

实现方法：

好啦，前置技能讲完了，下一步我来讲实例！

我们的实例还是上面的线段树1。

首先，我们先将“正解”程序，暴力程序，数据生成器和对拍程序写好，放在一个文件夹里

下面我给出对拍程序的源代码（注意，数据生成器，“暴力”和“正解”务必提前编译（也就是要exe））：

#include<iostream>
#include<cstdio>
#include<windows.h>
using namespace std;
int main()
{
    int cnt=0;
    while(cnt<=10)
    {
        cnt++;
        system("start sjmaker.exe");//启动数据生成器 
        Sleep(500);//等待数据输出（极限数据输出大约0.5s） 
        system("start baoli.exe");//启动“正解”和”暴力“ 
        system("start zhengjie.exe");
        Sleep(10000);//这个时间取决于你写的暴力的最坏时间 
        if(system("fc baoli.out zhengjie.out"))//如果出锅，就停下来 
        {
            system("pause");
            break;
        }
    }
}