快读攻略（详）
学委
·
2018-11-01 11:13:19
·
个人记录
读入、输出的时间也吃运行耗时。快读可以给算法部分节省时间，帮助暴力，或者占时间优势冲刺 rank1！
快读大概有多快……
读入方式
读入内容
平均耗时
C++ fread()
1~1000万整数排列
328.883ms
C++ 普通快读
1~1000万整数排列
894.201ms
C++ scanf()
1~1000万整数排列
1074.278ms
某 NOIlinux 测试，多于两千组，clock() 计时的，不加优化。
读入整数包括读取字符和计算、赋值给变量，因此 fread 省去读入时间的比例非常高。不过，scanf 灵活性好强……
快读不好写？
普通快读的原理和实现都很普通，嗯嗯。
而它可以用 fread 优化。别慌，fread 所做的事情，也就类似于
scanf("%s", a);
普通快读
知道就不用看了
原理
“如题面无特殊说明，输入文件格式如下：除两两相邻的元素之间均有单个空格符外，文件中将不会出现其他空格；包括最后一行数据在内，文件中的每一行末尾均有一个回车。”
数字之间用空格或者换行符来分隔。
关于负数，负号后面是它的绝对值。
由于数字正向给出，所以要读入 146 可以这样：
读入 1，记录 1。
读入 4，先把之前的记录乘以 10，然后加上 4。现在记录了 14。
读入 6，先把之前的记录乘以 10，然后加上 6。现在记录了 146。
读到空格、换行符或者 EOF（读不到东西），就可以返回结果：146。
我们用 getchar() 逐个读进数字字符，再减去字符 '0'(ASCII码为 48) 即得对应的数字。
实现
后面跟着解释
#include
#include
inline int getint()
{
int res = 0, neg = 0, ch = getchar();
while(!(isdigit(ch) or ch == '-') and ch != EOF)
ch = getchar();
if(ch == '-')
neg = 1, ch = getchar();
while(isdigit(ch))
res = res * 10 + (ch - '0'), ch = getchar();
return neg ? -res : res;
}
普通快读，每次读一个整数。这个函数分成五个简单的部分：
定义临时变量
上面定义了 res 用来存数字部分；neg 标记是不是负数。
通过不断 getchar 来跳过间隔符，直到负号或者数字
用 isdigit()（来自
判断是不是遇到到负号了
如果是则 neg 赋为 1，并读入下一个字符（后面一个肯定是数字）。
不断读入数字，累加数字部分
根据负号标记返回结果 res
说明
isdigit() 不慢，分析汇编代码得出的哦。
最好保留特判 ch != EOF，很有用。
现在主要花时间在 getchar() 上了。
测试
语文成绩 2000万个两位数
HH的项链 150万个五位数
如何比这个读入更快？
begin
read(n)
end.
用 fread 优化普通快读
就是优化 getchar()
语法
函数 fread() 在
fread() 是一小块一小块地读入数据的。你要给它 4 个参数：
存到哪里，“每块”包含几个字节，想要读几块，从哪里读入。
char a[1000010];
fread(a, 1, 1000000, stdin);
//从stdin（标准输入）读入了1000000个字符到a数组里，每个char占一个字节
//不连接文件的话stdin就是你的键盘输入
//freopen("data.in", "r", stdin)之后当然就是从data.in里面fread了
fread() 会返回一个数值，表示成功读入了几块。
这段代码以后字符数据都在 a 数组里了。所以 getchar 就不要了。
我们自己写一个函数来替代 getchar()。
实现
const int BUFSIZE = 1 << 20;//1048576
char tmp[BUFSIZE];
int cnt = 0, Max = 0;
inline char getch()
{
if(cnt == Max)
{
cnt = 0;
Max = fread(tmp, 1, BUFSIZE, stdin);
}
return tmp[cnt++];
}
先开了一个缓存区，因为 fread() 只是把一大堆东西塞入缓存里供你使用。（这里缓存区开了有限大小1MB，所以有分次读入。文末有一劳永逸版本）
cnt 和 Max 是缓存区的辅助变量，分别表示缓存区已经被使用到哪里、缓存区的实际容量。fread() 不需要这两个变量。这两个变量只是在 fread() 之后帮助你利用缓存区的。
想象一下，第一次调用 getch() 会怎么样？
因为刚开始 cnt 和 Max 都是 0，所以执行一次 fread() 迅速读入 1048576 个字符。
小提示：
1. 很可能一次就读完了数据所有字符，如果实际数据不足 1048576 个字符也不会出错，fread() 会返回成功读入的块数。
2. tmp 下标从 0 开始，即 tmp[0] 存的是第一个字符。而 fread() 返回的是成功的确切个数，所以 tmp[Max-1] 存的是读入到的最后一个字符，Max 是首个不合法位置。
首次读入以后很长一段时间内，调用 getch() 只需要返回 tmp[cnt]。其中 cnt++ 起到先返回、后加 1 的作用。
getch() 用了一百多万次以后，发现 cnt 与 Max 相撞，此时再次调用 fread() 迅速读入 1048576 个字符，cnt 回到 0。
下面是指针写法，推荐指针！
#include
#include
const int BUFSIZE = 1 << 20;
char ibuf[BUFSIZE], *is = ibuf, *it = ibuf;
inline char getch(){
if(is == it)
it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
return is == it ? EOF : *is++;
}
inline int getint(){
int res = 0, neg = 0, ch = getch();
while(!(isdigit(ch) or ch == '-') and ch != EOF)
ch = getch();
if(ch == '-')
neg = 1, ch = getch();
while(isdigit(ch))
res = res * 10 + (ch - '0'), ch = getch();
return neg ? -res : res;
}
说明
is 和 it 是指针，就算你之前不喜欢指针，相信也看得懂吧。数组名称也是个指针。在指针前面加一个 *，可以返回指针所指的值。
*ibuf 等效于 ibuf[0]，
*(ibuf + 1) 等效于 ibuf[1]。
“is = ibuf”就是让 is 指向数组 ibuf[] 的第一个位置。此后 is++ 就是让它指向数组中的下一个位置。
若 fread() 没有成功读入任何一个字符（is 与 it 依然相等），那就是到了文件的末尾，返回 EOF。
除了改用 getch()，快读本身没有变。
编译运行、键盘输入数据时 fread() 无法停止？因为它期望得到太多字符，键盘输入时它不知道什么时候是末尾，所以你得告诉它“已经结束输入”。按 Ctrl + Z 后再回车就好了。
普通快输
快输出场率没有快读高的？
读入规模大的题目不少，但输出规模大的题目不多；
读入数据往往格式统一，快读容易适应。但输出答案时可能有要求灵活，比如穿插字符串。这时候 printf() 的优势就很明显。
但还真有派上用场的时候……整数 fwrite() 还是有明显优化效果的。
输出方式
输出内容
平均耗时
C++ fwrite()
1~1000万整数排列
734.430ms
C++ printf()
1~1000万整数排列
1130.535ms
C++ 普通快输
1~1000万整数排列
1356.368ms
某 NOIlinux 测试，多于两千组，clock() 计时的，没加优化。
原理
关于负数，在负号后方输出绝对值。
正向输出一个数字。通过模 10 的方式我们可以直接获得它的最后一位，然后整个数除以 10 使原来最后第二位变成最后一位。但是注意这是获取了最后一位，因此不能直接逐位输出，要暂存后倒序输出。
第2步中，我们不断循环获取最后一位，退出条件是当前数剩余 0，所以，如果开始时这个数就是 0，就要特判后输出一个 0。0 确实是一个特殊的数，人为规定了用一个字符表示它。
用 putchar() 逐位输出数字。要输出的是数字字符，而我们模 10 后得到的是数，因此输出时要加上字符 '0'(或 48)。
“当同一行中有多于一个元素时，须用单个空格符以作分隔。”
间隔符号，如空格、换行，要另外输出。
代码
inline void putint(int res)
{
char q[10];
if(res == 0)
putchar('0');
else
if(res < 0)
{
putchar('-');
res = -res;
}
int top = 0;
while(res)
{
q[top++] = res % 10 + '0';
res /= 10;
}
while(top--)
putchar(q[top]);
}
定义临时变量
传入要输出的整数 res；字符数组 q 暂存数字的各个位，以便于倒序输出。
特判负数和 0 的情况
用模 10 的方式将数字从后向前转换成数字字符
除以 10 没有位运算方法。如果除以 10 有快速算法，那么模 10 也有了。
注意 q[top++]，类似于上面快读的指针 is。
倒序输出字符
注意 while(top--)，一个比较巧妙的用法，想想这个方法是怎么输出 q[0] 的——那时的 while 内，top = 1，逻辑值还是真。
用 fwrite 优化普通快输
其实只优化了 putchar()
语法
fwrite() 也在
给它四个参数：
现成的东西在哪里，“每块”包含几个字节，想要输出几块，输出到哪里。
//假设b数组存储了应该输出的字符
fwrite(b, 1, cnt, stdout);
注意这里第三个参数需要是确切的字符个数。当然，它也会返回成功输出了几块。
用自己写的函数代替 putchar()。
实现
const int BUFSIZE = 1 << 20;
char tmp[BUFSIZE];
int cnt = 0;
inline void flush()
{
fwrite(tmp, 1, cnt, stdout);
cnt = 0;
}
inline void putch(char ch)
{
tmp[cnt++] = ch;
if(cnt == BUFSIZE)
flush();
}
这里也有一个缓存区。在你调用 flush() 之前，putch() 只会把要输出的字符放到缓存区。在 flush() 中，fwrite() 就把缓存区的一大堆东西输出去。
cnt 是缓存区的辅助变量，表示缓存区已经被填充了多少。
如果 cnt 超出上限（达到 BUFSIZE 就已经不合法了），就用 fwrite() 输出缓存区的积存，清空缓存，cnt 回到 0。
在缓存区满时，putch() 会自动调用 flush()。你会发现到了最后，缓存区总还存着一些东西。程序最后需要手动调用一次 flush() 输出积存，如果数组中没有积存当然也不会出错。
int main(){
//...
flush();
return 0;
}
输出的数字之间需要间隔符，可直接以这样的方式实现
for(int i = 1; i <= n; ++i)
putint(a[i]), putch(' ');
putch('\n');
用 fwrite() 优化字符串输出也是很好的。
参考代码
剪贴板