P10815【快速读入】题解

· · 题解

模板讲解

快读模板

ok，我们先把模板拉上来。

int read ()
{
    int s = 0, f = 1;
    char c = getchar ();
    while (c < '0' || c > '9')
    {
        if (c == '-')f = -1;
        c = getchar ();
    }
    while (c >= '0' && c <= '9')
    {
        s = s * 10 + c - '0';
        c = getchar ();
    }
    return s * f;
}

快读快写的本质其实就是用字符读入替换数字读入。

第一个 while 的作用是去掉前面无用的字符，并且检测是否有负号。

第二个 while 的作用就是读入数字符，再用数字符一位一位计算成数字。

以 114514 为例。

读入字符 数字 s
1 0\times 10+1=1
1 1\times 10+1=11
4 11\times 10+4=114
5 114\times 10+5=1145
1 1145\times 10+1=11451
4 11451\times 10+4=114514

快写模板

void write (int c)
{
    if (c > 9)write (c / 10);
    putchar ((c % 10) + '0');
}

快写用递归的思想，把一个数字分解成若干个数位，同样是用字符替换为数字。

如果当前要输出的数是 2 位及以上的数，递归该数 \div 10，直到该数为 1 位数，直接输出，然后再输出以上数的个位。

同样以 114514 为例。

因为函数先递归到底，再返回输出，所以是表中从下向上输出。

递归参数 输出数
114514 4
11451 1
1145 5
114 4
11 1
1 1

题目解法

我们不能使用单一的快读模板，因为这样会 TLE。我们可以将原来的 getchar () 函数改成 getchar_unlocked () 函数，复杂度接近 fread。但是该函数只能在 Linux 系统上运行，所以就算报错也没关系。

剩下的操作部分随便写一写就好了。