快 CSP 了，想学生成数据。以后学到模拟退火等随机化算法也会一起写在这里。

从 rand 说起

#include <cstdlib>
#include <ctime>
//...
    srand(time(NULL));//使用当前的时间作为随机种子
    int x=rand();

以上的代码会得到一个 $[0,RANDMAX]$ 之间的数。

//rand 生成随机数，以下函数对于 int 范围的 n 都能正常运行
//随机数据生成 
#include <cstdlib>
#include <ctime>
int random(int n)
{
    return 1ll*rand()*rand()%n;
}
int main()
{
    srand((unsigned)time(0));
    //··· 
} 

缺点：随机周期短，慢

mt19937

由于 CCF 大部分开放 C++14 标准，可以使用这个高质量还快的随机函数。

#include <random>
#include <ctime>
using namespace std;
//...
mt19937 rnd(time(0));
mt19937_64 long_rnd(time(0)); 

前者是 unsigned int 范围，后者是 unsigned long long 范围。

两者都是一个类，用来定义随机数函数。调用直接像rand一样即可。

随机实数：先产生一个较大的随机整数，再除以 $10$ 的次幂。

随机负数：值域平移之后减掉 $n$ 。

shuffle

有个叫做 random_shuffle 的东西，以后不让用了，这两个东西都在 algorithm 头文件里面。

调用 shuffle(a+1,a+1+n,rnd); ，其中 rnd 是自定义的随机数生成器。

随机数据生成

//随机生成整数序列
int n=rnd()%100000+1;
int m=1e9;
for(int i=1;i<=n;i++) a[i]=rnd()%(2*m+1)-m;

//随机生成区间列
for(int i=1;i<=m;i++)
{
    int l=rnd()%n+1,r=rnd()%n+1;
    if(l > r) l^=r^=l^=r;
    printf("%d %d\n",l,r);
}

//随机生成树
for(int i=2;i<=n;i++)
{
    //从 [2,n] 之间的每个点向前面的点随机连一条边 
    int fa=rnd()%(i-1)+1;
    int val=rnd()%1000000000+1;
    printf("%d %d %d\n",fa,i,val); 
}

树的数据还可以特殊构造，链形，菊花，蒲公英（缝合怪）数据都是经常让算法复杂度退化的特殊数据。

由于考场上我应该没有时间生成图，所以这里先咕着，有空了来搞。

对拍

造数据就是为了这个。

我从 wt giegie 那里学的，参考 lyd 蓝书和洛谷日报。

注意对拍的时候不要开文件输入输出。

将对拍器和数据生成器，你写的暴力和正解放在同一个文件夹里面，就可以开始对拍了。

对拍跑一般多组小数据，如果各种数据都可以通过，基本可以拿到满分。

如果是平时调代码用，也可以生成大数据和其他人的 AC 代码进行对拍。

看文件名可以看出来啥是啥，注意对拍时注释掉文件输入输出。

对拍器长这样。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    double s,myt,stdt;
    for(int i=1;i<=10000;i++)
    {
        system("data.exe > test.in");//测试的数据输入 test.in 
        s=clock();//获取当前时间 
        system("test.exe < test.in > test.out");//将 test.in 中的数据输入 test.exe , 并将运行结果输入 test.out 
        myt=clock();
        system("std.exe < test.in > std.out");
        stdt=clock();
        //同上 
        if(system("fc /W test.out std.out"))//fc 比较两者是否相同，不相同返回真。/W 过滤多余空格和换行 
        {
            printf("Wrong Answer, 测试点 #%d, 用时 %.0lfms, std用时 %.0lfms",i,myt-s,stdt-myt);
            return 0;
        }//时间的单位在 Windows 下是毫秒，需要换算自己手算就好了 
        else printf("Accepted, 测试点 #%d, 用时 %.0lfms, std用时 %.0lfms\n",i,myt-s,stdt-myt);
    }
    return 0;
}

参考&学习 资料
1. 《算法竞赛进阶指南》——李煜东
2. 随机函数——OI Wiki
3. 深海中的STL—mt19937——attack
4. [洛谷日报#86]OIer 必知的编程技巧