欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

debug?用对拍!

程序员文章站 2023-01-12 12:49:49
很多人考noip之类的比赛永远会发生一些奇怪的问题 比如说下面这两位(来自我的两位学长) sliver n:spli,考得怎样啊? spli:就那样啦,day1T1没推出来规律,别的还好 silver n:看来你省一高分预定啊 几周后。。。 silver n:分出来了吗? spli:出来了。。。 s ......

很多人考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>

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

debug?用对拍!

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

我们有请srand()函数登场。

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

在这里他被用于改变种子

用法:

先加头文件(和rand()一样):

#include<cstdlib>

然后看下面:

debug?用对拍!

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

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

我以洛谷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批处理文件)

debug?用对拍!

如果两个文件相等,他会返回:(有点不智能,无法忽略空格和回车)

debug?用对拍!

如果不相等,他会返回错误的地方:

debug?用对拍!

很好用吧?

(2)启动程序操作

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

代码极短:

debug?用对拍!

就是这样。

(3)暂停操作

你会发现:哎,我的代码没错啊,为什么闪退了?

的确,你没写错

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

所以看起来像闪退。

怎么办呢?

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

看代码:

debug?用对拍!

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

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

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

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

#include<windows.h>

引用了这个头文件,我们就可以使用system()函数

样例:

system("pause");

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

5.Sleep挂起操作

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

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

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

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

不错才怪呢!

所以我们要写Sleep()函数(注意S大写!!)

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

怎么实现呢?很简单,看下面:

头文件:

#include<windows.h>

 实现方法:

debug?用对拍!

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

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

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

debug?用对拍!

下面我给出对拍程序的源代码(注意,数据生成器,“暴力”和“正解”务必提前编译(也就是要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;
        }
    }
}

 OK, Debug完成!你可以去写别的题了,只要时常回来看一看有没有bug就行了。