题解：P13499 「Cfz Round 6」Umiyuri Kaiteitan

mohay · 2025-09-10 19:21:09 · 题解

思路

注意到文件大小取决于执行该命令时系统中已存在的文件数量和它们的文件名长度。

所以我们可以只用记录以下内容：

• 哪些文件已经被创建
• 当前总字符数（包括文件名和空格）
• 当前文件数量

接着遍历每个操作，如果是新文件，更新文件数量和总字符数，记录当前总字符数到对应文件的答案中。

时间复杂度为 O(n + m)。

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=500005;
int n,m;
int ops[MAXN];
long long ans[MAXN];
bool created[MAXN];

int digit_len(int x){
    int len=0;
    while(x){
        len++;
        x/=10;
    }
    return len;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>ops[i];
    }

    long long total=0;
    int count=0;

    for(int i=0;i<n;i++){
        int file=ops[i];
        if(!created[file]){
            created[file]=true;
            count++;
            if(count>1) total++;
            total+=digit_len(file);
        }
        ans[file]=total;
    }

    for(int i=1;i<=m;i++){
        cout<<ans[i]<<" ";
    }

    return 0;
}