P13499：「Cfz Round 6」Umiyuri Kaiteitan

Andy1101 · 2025-07-27 17:16:12 · 题解

题目传送门

题目大意

当收到 ls > NAME 指令时，执行以下操作：

• 若在当前目录中不存在名为 NAME 的文件，则创建一个名为 NAME 的文件；若在当前目录中存在名为 NAME 的文件，则将该文件的内容清空；
• 将当前目录中所有文件的文件名按照递增的顺序写入到名为 NAME 的文件中，相邻两个文件名之间用一个空格分隔。

思路

前置工作

我们要定义两个数组——数组 a 和数组 h。a_x 表示文件名为 x 的文件的大小，h_x 表示文件名为 x 的文件是否出现过。

另外，我们还要定义一个变量 sum，用来记录前几个文件的文件名的总字节数（包含空格）。

解题

对于每个指令，都有以下步骤：

如果文件名为 x 的文件没有出现过（不然会重复计算），那么现在要使用 sum 累加文件名的字节数 +1（因为还有空格）。
tips：计算文件名的字节数需要用函数。

如果文件名为 x 的文件出现过了，此时将文件名为 x 的文件清空，即 a_x=0。

将 a_x 赋值为 sum-1（为什么还要 -1 呢？因为在计算每个文件名的字节时包含了空格，但在算最后一个文件名的字节时会多加一个空格，所以要减掉）。

标记文件名为 x 的文件出现过，即 h_x=1。

AC Code：

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
bool h[N];
// vector<int> v[N];
long long a[N];
int cal(int x)
{
    int cnt=0;
    while(x)
    {
        x/=10;
        cnt++;
    }
    return cnt+1;
}
int main()
{
    int n,m;
    cin >>n>>m;
    long long sum=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin >>x;
        if(h[x]==0) sum+=cal(x);
        if(h[x]==1) a[x]=0;
        a[x]=sum-1;
        h[x]=1;
    }
    for(int i=1;i<=m;i++) cout <<a[i]<<" ";
    return 0;
}