题解 P4746 【[CERC2017]Hidden Hierarchy】

· · 题解

挺长时间不见，这个题竟然变成普及/提高-了？

[题意]

这个题大概意思是linux目录，n条记录，每条记录代表一个目录下有个大小为val文件

然后根目录为“/”；

现在给个t问对于这个目录下的所有文件大小

如果大于t那么“-”展开，

如果小于t那么“+"折叠

如果是底层目录了，那么输出""一个空格，

后面都要跟着目录信息，和目录的大小；

如果是”-“，则进入到子目录中循环操作，目录按字典序输出

[思路]

就是模拟了，节点存储用map容器里面价格set

考虑到超时问题，一律用scanf不用cincout，string转化char输出

string调用”.c_str“函数

把串截开，用charss[i+1]赋值0s就是i+1前面的内容；

目录就是一颗数，dfs遍历下去把文件大小计算出来

然后第二次dfs输出


#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+7;

map<string,set<string> >mp;
map<string,ll> mp_size;
ll t;
void dfs1(string str) {
    for(auto next_str:mp[str]) {
        dfs1(next_str);
        mp_size[str]+=mp_size[next_str];
    }
}
void dfs2(string str) {
    if(mp[str].size()==0) {
        printf("  %s %lld\n",str.c_str(),mp_size[str]);// 空
        return ;
    }
    bool flag=true;
    for( auto next_str: mp[str]) // 循环遍历当前目录下的所有目录 看是不是存在子目录 >t
        if(mp_size[next_str]>=t)
            flag=false;
    if(flag) { // 没有 直接输出 +
        printf("+ %s %lld\n",str.c_str(),mp_size[str]);
    } else { // 又有的话 下一层
        printf("- %s %lld\n",str.c_str(),mp_size[str]);
        for(auto next_str:mp[str])
            dfs2(next_str);
    }
}
int main() {
    int n;
    scanf("%d",&n);
    mp_size.clear();
    for(int i=1; i<=n; i++) {
        char s[MAXN];
        ll val;
        scanf("%s%lld",s,&val);
        string fa="//";
        for(int i=0; s[i]; i++) {
            if(s[i]=='/') {
                char temp=s[i+1];
                s[i+1]=0;
                mp[fa].insert(s);
                fa=s;
                s[i+1]=temp;
            }
        }
        mp_size[fa]+=val;
    }
    scanf("%lld",&t);
    dfs1("//");
    dfs2( *(mp["//"].begin()) );
    return 0;
}