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

Posted on 2021-04-08 In 题解 5.5k 5 mins.

CCF认证202012-3，一道很复杂的大模拟

题目

题目很复杂，代码也很复杂。

代码

感觉需要多学习一下C++中string的stl

#include <bits/stdc++.h>
using namespace std;

const int maxn = 4e6 + 5;

typedef long long ll;
struct Node {
    map<string, int> child;
    int kind; // 类型：0为文件，1为目录 
    ll max_ld, max_lr;
    ll ld, lr;
    ll filesize;
    int fa;
};

int n;
Node nodes[maxn];
vector<pair<int, string>> reback; // 输入的路径，id对应父节点，string对应添加的节点 
int index = 0; // 当前的节点数 

// 回滚之前的操作，删除创建的文件夹 
void Reback()
{
    for (int i = 0; i < reback.size(); i++) {
        int f_id = reback[i].first;
        string son_name = reback[i].second;
        nodes[f_id].child.erase(son_name);
    }
}

// 创建文件 
bool doC(string path, ll size)
{
    int id = 0; // 当前遍历到的节点 
    int origin_index = index; // rollback之前回复index 
    
    int last = path.rfind("/");
    reback.clear();
    int p = 1;
    // 路径检查并创建路径 
    while (p < last) {
        string t = "";
        for (; p < last && path[p] != '/'; p++) {
            t.push_back(path[p]);
        }
        p++;
        
        // 路径不存在 
        if (nodes[id].child.find(t) == nodes[id].child.end()) {
            // 创建路径 
            index++; 
            nodes[id].child[t] = index;
            nodes[index].fa = id;
            nodes[index].kind = 1;
            nodes[index].max_ld = LLONG_MAX / 3;
            nodes[index].max_lr = LLONG_MAX / 3;
            nodes[index].ld = 0;
            nodes[index].lr = 0;
            reback.push_back(make_pair(id, t));
            id = index;
        }
        // 路径存在 
        else {
            int sonid = nodes[id].child[t];
            if (nodes[sonid].kind == 0) {
                index = origin_index;
                Reback();
                return false;
            }
            id = sonid;
        }
    }
    
    // 文件检查并创建文件
    string filename = path.substr(last + 1);
    // 已经存在文件名 
    if (nodes[id].child.find(filename) != nodes[id].child.end()) {
        int sonid = nodes[id].child[filename];
        // 且该文件为目录文件： 执行失败 
        if (nodes[sonid].kind == 1) {
            index = origin_index;
            Reback();
            return false; 
        }
    }
    ll py; // 需增加的配额 
    if (nodes[id].child.find(filename) == nodes[id].child.end()) py = size;
    else py = size - nodes[nodes[id].child[filename]].filesize;
    
    // 检查目录配额
    if (nodes[id].ld + py > nodes[id].max_ld) {
        index = origin_index;
        Reback();
        return false;
    }
    
    // 检查后代配额
    int tmp_id = id;
    while (tmp_id != -1) {
        if (nodes[tmp_id].lr + py > nodes[tmp_id].max_lr) {
            index = origin_index;
            Reback();
            return false;
        }
        tmp_id = nodes[tmp_id].fa;
    }
    
    // 配额满足条件，创建文件
    if (nodes[id].child.find(filename) == nodes[id].child.end()) {
        index++;
        nodes[id].child[filename] = index;
        nodes[index].fa = id;
        nodes[index].kind = 0;
        nodes[index].filesize = size;
    }
    // 配额满足条件，替换原有文件 
    else {
        int sonid = nodes[id].child[filename];
        nodes[sonid].filesize = size;
    }
    
    // 更新目录当前占用空间 
    nodes[id].ld += py;
    int tmp_id2 = id;
    while (tmp_id2 != -1) {
        nodes[tmp_id2].lr += py;
        tmp_id2 = nodes[tmp_id2].fa;
    }
    
    return true;
}

// 移除文件 
bool doR(string path)
{
    int id = 0;
    
    int last = path.rfind("/");
    
    int p = 1;
    // 路径检查
    while (p < last) {
        string t = "";
        for (; p < last && path[p] != '/'; p++) t += path[p];
        p++;
        
        if (nodes[id].child.find(t) == nodes[id].child.end()) return true;
        else {
            int sonid = nodes[id].child[t];
            if (nodes[sonid].kind == 0) return true;
            id = sonid;
        }
    }
    
    // 文件删除
    string filename = path.substr(last + 1);
    if (nodes[id].child.find(filename) == nodes[id].child.end()) return true;
    else {
        int sonid = nodes[id].child[filename];
        // 普通文件 
        if (nodes[sonid].kind == 0) {
            nodes[id].child.erase(filename);
            nodes[id].ld -= nodes[sonid].filesize;
            int tmp_id = id;
            while (tmp_id != -1) {
                nodes[tmp_id].lr -= nodes[sonid].filesize;
                tmp_id = nodes[tmp_id].fa;
            }
        }
        // 目录文件
        else {
            nodes[id].child.erase(filename);
            int tmp_id = id;
            while (tmp_id != -1) {
                nodes[tmp_id].lr -= nodes[sonid].lr;
                tmp_id = nodes[tmp_id].fa;
            }
        } 
    }
    
    return true;
}

// 设置配额 
bool doQ(string path, ll ld, ll lr)
{
    if (ld == 0) ld = LLONG_MAX / 3;
    if (lr == 0) lr = LLONG_MAX / 3;
    
    int id = 0;
    
    int last = path.rfind("/");
    int p = 1;
    while (p < last) {
        string t = "";
        for (; p < last && path[p] != '/'; p++) t += path[p];
        p++;
        
        if (nodes[id].child.find(t) == nodes[id].child.end()) return false;
        else {
            int sonid = nodes[id].child[t];
            if (nodes[sonid].kind == 0) return false;
            id = sonid;
        }
    }
    
    string filename = path.substr(last + 1);
    int filenode;
    if (filename == "") filenode = 0;
    else {
        if (nodes[id].child.find(filename) == nodes[id].child.end()) return false;
        else filenode = nodes[id].child[filename];
    }
    if (nodes[filenode].kind == 0) return false;
    else { // 如果是目录 
        if (ld < nodes[filenode].ld || lr < nodes[filenode].lr) return false;
        else {
            nodes[filenode].max_ld = ld;
            nodes[filenode].max_lr = lr;
            return true;
        }
    }
}

int main()
{
//    freopen("data.in", "r", stdin);
    
    // 创建根节点 
    nodes[0].fa = -1;
    nodes[0].kind = 1;
    nodes[0].max_ld = LLONG_MAX / 3;
    nodes[0].max_lr = LLONG_MAX / 3;
    nodes[0].ld = 0;
    nodes[0].lr = 0;
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        string op;
        cin >> op;
        if (op == "C") {
            string path;
            ll size;
            cin >> path >> size;
            bool res = doC(path, size);
            if (res) printf("Y\n");
            else printf("N\n");
        }
        else if (op == "R") {
            string path;
            cin >> path;
            bool res = doR(path);
            if (res) printf("Y\n");
            else printf("N\n");
        }
        else if (op == "Q") {
            string path;
            ll ld, lr;
            cin >> path >> ld >> lr;
            bool res = doQ(path, ld, lr);
            if (res) printf("Y\n");
            else printf("N\n");
        }
    }
    
    return 0;
}

Reference

[1] 带配额的文件系统