inline int read() { int x = 0; char c = getchar(); for (; c < '0' || c > '9'; c = getchar()); for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + (c ^ 48), c = getchar()); return x; }
这是一个我们平常使用的快读,他也能几乎达到所有题目的要求。但是有一些题目,比如没有加单调队列的跳房子,在我校机房的土豆评测机上经常会被卡掉一个点,而且时间就差一点,于是超快读就进入了我的必备模板。
我们知道,getchar
是每次读出一个字符,若是我们能一次性读进一大串字符,那样效率就会快很多。
cstdio
里有一个fread
函数正好能满足我们的需要。这个函数的原型是这样的:
size_t fread ( void * ptr, size_t size, size_t count, FILE * stream );
看不懂没关系,我们慢慢解释。第一个形参为读入数据存放的位置,我们一般用数组指针传入;第二个形参为每个数据的长度,单位是字节,如char
就是1
;第三个形参是理想情况下(输入数据量充足)读入多少个数据;第四个形参是读入数据的位置,也就是指定输入流,通常为stdin
。这个函数的返回值为实际读入数据的个数。
那么,稍稍改进一下我们的getchar
吧。
char buf[1 << 20], *_now = buf, *_end = buf; //buf是缓冲数组,就是读入的一串数据存放的地方;_now是字符指针,指向当前想取的那个字符;_end也是字符指针,指向这一串字符的最后一个。 inline char getchar() { if (_now == _end) {//如果这一串数据处理完了 _end = _now = buf; _end += fread(buf, 1, 1 << 20, stdin);//那就再读一串,注意指针要回归原位 if(_now == _end) {//如果没有读进来,就说明没有数据了 return EOF; } } return *_now++; }
把这个加到快读的前面就成超快读了,当然getchar
的命名要改一下。
你可能会说,我的快读已经很长了,再加上这一段,岂不是……
没事,接下来我们来压下代码,需要用到,
和&&
两个运算符。
首先是,
运算符,这个我们一般在写条件时用到,用,
并列的语句,判断真假时只取最后一个。
for (int i = 1; i <= 10, i <= 14, i <= 6; ++i) cout << i << endl;
输出是:
1 2 3 4 5 6
其次是&&
运算符,这里有一个短路求值的概念,即当且仅当左侧运算对象无法确定表达式的结果时才会计算右侧运算对象的值。
int a = 0; if(10 > 20 && (a += 1, 1));//后半句没有参与表达式的运算 if(10 < 20 && (a += 2, 1));//后半句参与了表达式的运算 cout << a << endl;
输出为:
2
所以代码就压成了:
char buf[1 << 20], *_now = buf, *_end = buf; inline char _getchar() { return _now == _end && (_end = (_now = buf) + fread(buf, 1, 1 << 20, stdin), _now == _end) ? EOF : *_now++; }
当然你也可以使用宏定义,这样就不用改getchar
的命名了。
char buf[1 << 20], *_now = buf, *_end = buf; #define getchar() (_now == _end && (_end = (_now = buf) + fread(buf, 1, 1 << 20, stdin), _now == _end) ? EOF : *_now++)
写在最后:
输入方式 | cin | scanf | cin(解绑) | 快读 | 超快读(buf[1<<2] | 超快读(buf[1<<20] |
---|---|---|---|---|---|---|
速度/ms | 140 | 110 | 23 | 34 | 15 | 5 |