传智杯 2022 初赛 C 题解

chen_zhe · 2022-11-27 09:01:57 · 题解

简要题意：给定不定行数的字符串，要求给它标上行号。

解法：本题的关键点在于不定行数字符串的读入，而且字符串是可能有空格的，这使得无法直接使用 cin >> str 的方法对字符串进行读入。事实上，我们可以采取多种方式读入这种文本：其一是使用 getchar()，出题人也是这么写的，但是我不喜欢 getchar()。因此，这里就需要使用一个叫做 fgets 的函数。

fgets 的用法如下：fgets(char *str, int n, FILE *stream)，换而言之传三个参数，第一个参数是要存的字符数组，第二个参数是存多少个字符，第三个参数在竞赛语境中可以理解为 stdin。fgets 每次会读一行，而且在读完文件后会返回一个 NULL，因此可以使用这样的代码进行不定行数文件的读取：

while(fgets(buf,len,stdin)!=NULL) {
    do sth.
}

接着我们可以开一个 vector <char> s[maxn]，用 vector 存放下每一行的每个字母，以便后续我们输出。这里不能开二维数组，因为尽管累计字符长度是 2\times 10^5，但是如果开二维数组，则要开 a[200000][200000]，会爆内存，所以要用 vector 这类为我们自动分配内存的容器。

后面就是求位数了，可以用循环，也可以预处理位数数组，也可以用 log() 函数求出。这里应该就不是重难点了。

参考代码：

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
char buf[200050];
vector <char> s[200050];
int cnt;
int get_digit(int x)
{
    int digit=1,ret=1;
    while (ret<=x)
    {
        digit++;
        ret*=10;
    }
    return digit;
}
int main()
{
    while(fgets(buf,200000,stdin)!=NULL)
    {
        cnt++;
        for (int i=0;buf[i]!='\n';i++)
            s[cnt].push_back(buf[i]);
    }
    int cnt_digit=get_digit(cnt);
    for (int i=1;i<=cnt;i++)
    {
        for (int j=1;j<=cnt_digit-get_digit(i);j++)
            putchar(' ');
        cout << i << ' ';
        for (int j=0;j<s[i].size();j++)
            putchar(s[i][j]);
        putchar('\n');
    }
    return 0;
}