P10815 【模板】快速读入 题解

· · 题解

P10815 【模板】快速读入 题解

题目传送门。

题目好评！

这篇题解讲一下快读的原理，顺便讲一下快输的原理。

update on 2025-2-3：更新了原理，之前的原理是有问题的（感谢 @LionBlaze 大佬）。

update on 2025-6-28：被这个 Hack 了，真恶心，改了一下。

快读

我们都知道 getchar 的速度快于普通的 cin 或者 scanf（原因放在了最后），于是我们考虑能不能使用 getchar 读入字符代替数字。

众所周知，每个可见字符都有其对应的 ASCII 码编号，那我们就考虑使用字符的编号与数字进行联系。

上面两句其实是废话。

这显然可以做到。

于是我们就按照顺序读入数字。

我们应该先读入掉前面没用的字符，比如空格之类的。

同时应该注意如果读入减号，我们应该打一个标记表示这个数字是负数。

char c=getchar();
while(c<'0'||c>'9') // 非数字的过滤掉
{
    if(c=='-')f=-1; // 标记是负数
    c=getchar();
}

然后再读入数字，从高位到地位，每次读入一个个位数，我们应该把原来已经读入好的乘 10 再加上这个个位数。

举个例子，读入了 3，原来的是 12，我们要的效果是 123，那么我们先 12\times 10=120，再 120+3=123。

这个应该都能理解吧，如果理解不了，可以想想小学做竖式计算的过程和这个有什么联系。

while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); // 注意是数字才读入，然后 c-'0' 的意思是找到 c 对应的个位数

总快读代码：

int in()
{
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f; // 别忘记标记的负数要乘进去
}
// 调用时用 n=in();

快输

由快读同理可得，我们能使用 putchar 代替普通输出。

由于按位输出，从高到低，不好操作，这里采用递归的形式。

不知道递归的读者出门右转，度娘在等您。

先处理负数。

if(x<0)putchar('-'),x=-x;

然后分类讨论。

  1. 小于 10，代表是个位数，直接输出数字对应的字符：
if(x<10)putchar(x+'0');
  1. 大于等于 10，这个时候应该先递归输出高位，再输出低位。
else out(x/10),putchar(x%10+'0');

其中 x/10 是去掉个位后的 x；x%10 是取出 x 的个位。不懂的可以像我上面那样举例自己验证。

总快输代码：

void out(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
// 直接调用 out(n) 就行了

本题 AC 代码

注意一下本题卡常，要用 getchar_unlocked，原理跟 getchar 差不多，只不过更快一点。

不过不建议平时写题用这个，因为有些编译器会报错。

update on 2025-6-28：被卡 int 了，全部改成 long long 就能过了。

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb; // 至于这个是什么，咳咳，我不说
#define int long long
int in()
{
    int k=0,f=1;
    char c=getchar_unlocked();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar_unlocked();
    return k*f;
}
void out(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
signed main()
{
    int n=in(),sum=0;
    while(n--)sum+=in();
    out(sum);
    return 0;
}

快读快输比正常输入输出快的原因

update on 2025-2-3：将此段不合理的表述删去，加入正确的内容。

cin 和 cout 的特点

scanf 和 printf 的特点

不过上面这一段我觉得一点用都没有，快读快输比正常读入输入快这一条性质背下来就行了啊 QAQ。

后记

如果有什么写的不好或者错误的地方，欢迎评论指出！