常见技巧

本页面记载一些常用的技巧（有待完善）

由于本页面内容较杂，所以加入目录

IO优化

众所周知，在某些数据结构题当中，IO量极大。而输入和输出有需要一定的时间。这个时候，我们的程序运行起来就会出现如下的情况：

~~留给那位大♂人的时间不多了~~

所以这时候，我们就需要一个叫做IO优化的东西。（OI需要IO优化）

（限于作者水平，本文仅讲述当下被称作“龟速快读”的OI优化）

读入优化：

原理：getchar()函数的效率相对较高

代码：

int get() {
    int x = 0, f = -1; char c = getchar();
    while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

解释：

第一行：变量，c是字符，读入数字减去'0'的ASCII码值，x是读入数的绝对值，f是符号

第二行：吃掉多余字符，并且在其中识别出'-'号（!isdigit()表示不是数位）

第三行：读入数字，举个例子，现在x=123，我们接受到了一个字符c='4'，下一个x就是10x+c-'0'，即1234

最后返回一个带有符号的数

当然前面的int可以换成template<typename T>这类东西

我们在对它进行一些更改，使得它能够读入实数

double getlf(){
    double x = 0, y = 1.0; int f = 1; char c = getchar();
    while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
    if(c != '.') return x * f;
    c=getchar();
    while(isdigit(c)) { x += (y /= 10) * (c - '0'); c = getchar(); }
    return x * f;
}

注意第五行不能省去，因为如果给出一组这样的数据：1 2，会被读成1.2

输出优化：

警告：这里可能是负优化！

原理：同样，putchar比其他函数更快

代码：

void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

这个是用递归实现的。流程大概如下：

有一个数1234需要输出：
目前的范围：[1234]
下一层调用：[123]4
下一层调用：[12]34
下一层调用：[1]234，此时的x=1，已经小于9了，所以输出'1'
返回上一层：输出'2'
以此类推，输出'3'，'4'，合起来就是1234了，输出完毕

输出实数太毒瘤了，所以这里就不写了

对拍

在OI中，我们常常需要将正解和暴力优势互补，暴力慢，正解的正确性有时懒得证，于是我们干脆直接将它们对比。

但是

一组一组手敲数据真的慢，还不一定查得出来

所以，我们就需要对拍

对拍四要素：

正解
暴力
数据生成器
对拍器

正解、暴力根据题目。

数据生成器：根据题目要求随机生成数据。但是可能造不出HACK数据

对拍器：将两个程序对比的机器。它的流程为：

生成一组数据
正解、暴力算结果
对比，判断是否一样
重复执行以上过程直到出错

这就要依靠<windows.h>库中的system()函数。

代码：

#include<iostream>
#include<windows.h>
using namespace std;
int main()
{
    while(1)
    {
        system("数据生成器.exe > data.txt");
        system("正解.exe < data.txt > yours.txt");
        system("暴力.exe < data.txt > expected.txt");
        if(system("fc expected.txt yours.txt"))   break;
    }
    cout<<"发现错误，请查看！"<<endl;
    system("pause");
    return 0;
}

例如我们要检查\(\text{BigInt A+B}\)的正确性。

数据生成器：

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int main()
{
	srand(time(NULL));
	int a=rand();
	int b=rand();
	cout<<(int)a<<" "<<(int)b;
}

两个程序：

#include<iostream>
using namespace std;

int main()
{
	int a,b;
	cin>>a>>b;
	cout<<a+b<<endl;
}

大整数程序略

对拍器：

#include<iostream>
#include<windows.h>
using namespace std;
int main()
{
	int T=0;
    while(1)
    {
    	T++;
    	cout<<"testdata<"<<T<<">"<<endl;
        system("datamaker.exe > data.txt");
        system("A+B.exe < data.txt > yours.txt");
        system("A+B_1.exe < data.txt > expected.txt");
        if(system("fc expected.txt yours.txt")) return 0;
    }
    return 0;
}

如果没有错，运行下来是这样的：

我们把BigInt的输出改为：cout<<a+b+rand()%2;

考验rp的时候到了。

事实证明我还是太非了，才五组就挂了。

如何卡常

答：“我不会。”

这部分有待补充