202012-3带配额的文件系统

简介: 202012-3带配额的文件系统

本题链接 带配额的文件系统

本博客给出本题截图

5.png

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef long long LL;
const int N = 2000010;
int n;
struct Node
{
    string name;
    int id, type;  
    mutable LL ld, lr;
    mutable LL sd, sr;
    bool operator< (const Node& t) const
    {
        return name < t.name;
    }
};
set<Node> son[N];
int idx;
char str[N];
bool F;
int U;
LL SZ;
vector<string> get(char* str)
{
    vector<string> res(1, "root");
    for (int i = 0; str[i]; i ++ )
    {
        if (str[i] == '/') continue;
        string s;
        int j = i;
        while (str[j] && str[j] != '/') s += str[j ++ ];
        res.push_back(s);
        i = j - 1;
    }
    return res;
}
LL dfs_remove(vector<string>& t, int u, int p)
{
    string name = t[u];
    if (!son[p].count({name})) return -1;
    auto it = son[p].find({name});
    if (u == t.size() - 1)
    {
        if (it->type) t[u] = "#file";
        auto sz = it->sr;
        son[p].erase(it);
        return sz;
    }
    if (it->type) return -1;
    auto sz = dfs_remove(t, u + 1, it->id);
    if (sz >= 0)
    {
        it->sr -= sz;
        if (t[u + 1] == "#file") it->sd -= sz;
    }
    return sz;
}
bool dfs_create(vector<string>& t, int u, int p, LL sz)
{
    string name = t[u];
    if (u == t.size() - 1)
    {
        if (son[p].count({name}))
        {
            auto it = son[p].find({name});
            if (it->type == 0) return false;
            SZ = dfs_remove(t, 0, 0);
            Node cur{name, ++ idx, 1, 0, 0, 0, sz};
            son[p].insert(cur);
            return true;
        }
        else
        {
            Node cur{name, ++ idx, 1, 0, 0, 0, sz};
            son[p].insert(cur);
            return true;
        }
    }
    else
    {
        if (!son[p].count({name}))
        {
            if (U == -1) U = u;
            Node cur{name, ++ idx, 0, 0, 0, 0, 0};
            son[p].insert(cur);
        }
        auto it = son[p].find({name});
        if (it->type) return false;
        auto res = dfs_create(t, u + 1, it->id, sz);
        if (res)
        {
            it->sr += sz;
            if (u + 1 == t.size() - 1) it->sd += sz;
            if (it->lr && it->sr > it->lr) F = false;
            if (it->ld && it->sd > it->ld) F = false;
        }
        return res;
    }
}
bool create(char* str, LL sz)
{
    auto t = get(str);
    F = true, U = -1, SZ = -1;
    auto res = dfs_create(t, 0, 0, sz);
    auto ans = res && F;
    if (res && !F)
    {
        auto t = get(str);
        if (U != -1)
        {
            while (t.size() - 1 > U) t.pop_back();
        }
        dfs_remove(t, 0, 0);
        if (SZ != -1) create(str, SZ);
    }
    return ans;
}
bool update(char* str, LL d, LL r)
{
    auto t = get(str);
    int p = 0;
    for (int i = 0; i < t.size(); i ++ )
    {
        string& s = t[i];
        auto it = son[p].find({s});
        if (it == son[p].end()) return false;
        if (it->type) return false;
        if (i == t.size() - 1)
        {
            if (d && d < it->sd) return false;
            if (r && r < it->sr) return false;
            it->ld = d, it->lr = r;
        }
        p = it->id;
    }
    return true;
}
int main()
{
    scanf("%d", &n);
    char op[2];
    sprintf(str, "/tmp");
    create(str, 1);
    auto t = get(str);
    dfs_remove(t, 0, 0);
    while (n -- )
    {
        scanf("%s", op);
        bool res;
        if (*op == 'C')
        {
            LL sz;
            scanf("%s%lld", str, &sz);
            res = create(str, sz);
        }
        else if (*op == 'R')
        {
            scanf("%s", str);
            auto t = get(str);
            dfs_remove(t, 0, 0);
            res = true;
        }
        else
        {
            LL d, r;
            scanf("%s%lld%lld", str, &d, &r);
            res = update(str, d, r);
        }
        if (res) puts("Y");
        else puts("N");
    }
    return 0;
}

总结

csp史上最难的一道模拟题…

后续会补上每个函数的实现原理

大模拟 + dfs

细节点:类似图论问题的思考逻辑,先建立一个虚拟原点,然后进行拓展

注意:mutable 用法

目录
相关文章
|
2月前
|
存储 Linux 开发工具
逻辑卷和磁盘配额
逻辑卷和磁盘配额
|
存储 Linux 开发工具
LVM逻辑卷管理与磁盘配额
LVM逻辑卷管理与磁盘配额
LVM逻辑卷管理与磁盘配额
|
存储 Linux
11.1 磁盘配额是什么
磁盘配额(Quota)就是 Linux 系统中用来限制特定的普通用户或用户组在指定的分区上占用的磁盘空间或文件个数的。
178 0
11.1 磁盘配额是什么
|
Shell 开发工具
|
开发工具 数据库