CSP 202012

CSP 202012

CSP 202012-3： 带配额的文件系统。100 分 AC，虽然是事后（皮）

#include<iostream>
#include<string>
#include<vector>
#include<map> using namespace std;// 不进行提前记录，只能通过 70% 的测试用例，剩下的会超时（因为数据规模很大）
typedef struct treeNode {bool isFile; // true then file, false then dirctorylong long LD, LR; // child limit  &  after children limit. Valid only isFile is falselong long lr; // Valid only is a dir: 提前地、动态地、实时地记录后代配额，这样就不用进行庞大的递归计算了long long size; // Valid only is File is truemap<string, struct treeNode*> children; // children's name: tree
} TreeNode, * Tree;int main() {int n;long long calculateD(Tree);long long calculateR(Tree);bool create(Tree, string, long long);void remove(Tree, string);bool setQ(Tree, string, long long, long long);cin >> n;char* result = new char[n]();// initialize treeTree tree = new TreeNode();// initialization donechar command;string filePath; // directory's path or file's pathstring dirPath; // must be directory's pathlong long size;long long ld, lr;for (int time = 0; time < n; time++) {cin >> command;char success = 'Y';switch (command) {case 'C':cin >> filePath >> size;if (!create(tree, filePath, size))success = 'N';break;case 'R':cin >> filePath;remove(tree, filePath);break;case 'Q':cin >> dirPath >> ld >> lr;if (!setQ(tree, dirPath, ld, lr))success = 'N';}result[time] = success; // or 'N'}for (int i = 0; i < n; i++)cout << result[i] << endl;return 0;
}vector<string> split(string filePath) { // create a wheel by myself, split a string to strsvector<string> vs;int start, end;int len = filePath.size();string s;start = 1;for (end = 1; end < len; end++) {// mainly use string object's assign(src_str, start_i, length) functionif (filePath[end] == '/') {s.assign(filePath, start, end - start);vs.push_back(s);start = end + 1;}}if (len != 1) {s.assign(filePath, start, start - end);vs.push_back(s);}return vs;
}void remove(Tree T, string filePath) {Tree tree = T;vector<string> vs = split(filePath);int len = vs.size();map<string, Tree>::iterator iter;int i;for (i = 0; i < len - 1; i++) {map<string, Tree>& children = tree->children;iter = children.find(vs[i]);if (iter == d())return;elsetree = iter->second;}if (tree->isFile) return;map<string, Tree>& children = tree->children;iter = children.find(vs[i]);if (iter == d())return;// 现在确定指令正确，必然要删文件，tree 指向了待删结点的父结点。// for function create version 3.0, 删除目录之前，要先使用被删结点的信息 lr or size,// 以更新将要被删的文件路径上所有的目录的 lrlong long minus;if (iter->second->isFile) minus = iter->second->size;else minus = iter->second->lr; T->lr -= minus;for (i = 0; i < len - 1; i++) {map<string, Tree>& children = T->children;T = children[vs[i]];T->lr -= minus;}// 更新完成，可以删除了map<string, Tree>& c = tree->ase(vs[len-1]);
}long long calculateD(Tree tree) {map<string, Tree>& children = tree->children;map<string, Tree>::iterator iter = children.begin();long long total = 0;for (; iter != d(); iter++)if (iter->second->isFile) total += iter->second->size;return total;
}long long calculateR(Tree tree) {long long total = 0;map<string, Tree>& children = tree->children;map<string, Tree>::iterator iter = children.begin();for (; iter != d(); iter++) {if (iter->second->isFile) total += iter->second->size;else total += calculateR((Tree)iter->second);}return total;
}// previously record every directory's lr, which is the sum of all the files' sizes,
// avoiding recursively calculating.
bool create(Tree T, string filePath, long long size) {Tree tree = T;/* Step 1: 走到已存在的最后一个目录 */vector<string> vs = split(filePath);int len = vs.size();int i;map<string, Tree>::iterator iter;for (i = 0; i < len - 1; i++) {map<string, Tree>& children = tree->children;iter = children.find(vs[i]);if (iter == d())  // 不存在这个目录，就 break 出来创建后面所有的目录break;tree = iter->second;if (tree->isFile) return false; // 有重名普通文件，执行失败// else it is a directory}/* Step 2: 检测前面存在的目录是否超出 LR 配额 */long long delta;if (i < len - 1) { // 提前跳出 for，表示目录不存在，要进行创建// 此时，delta 等于 sizedelta = size;}else { // i == len - 1, 路径上所有目录都存在，看是否有此文件map<string, Tree>& children = tree->children;iter = children.find(vs[i]);if (iter != d()) { // 有此文件，看是否是普通文件// delta 等于 new size - old sizeif (iter->second->isFile)  // 是普通文件，看是否 满足 tree 的 LDdelta = size - iter->second->size;else return false; // 是个重名目录，执行失败}else  // 无此文件，要进行创建，delta 等于 sizedelta = size;if (tree->LD > 0 && calculateD(tree) + delta > tree->LD)return false;}// 至此，可以使用 delta 来检测路径上已存在目录的配额是否超出了int j;tree = T;if (tree->LR > 0 && tree->lr + delta > tree->LR)return false;for (j = 0; j < i; j++) { // i 是第一个没有找到的目录，or 路径终点的普通文件map<string, Tree>& children = tree->children;tree = children[vs[j]];if (tree->LR > 0 && tree->lr + delta > tree->LR)return false;}// 至此，所有条件都满足，能执行成功// 可以进行路径上未存在的目录和文件的创建了/* Step 3: 创建后面所有不存在的目录 */ for (; i < len - 1; i++) {map<string, Tree>& children = tree->children;children[vs[i]] = new TreeNode();tree = children[vs[i]];}// 下面这种写法，可以统一 3 种情况：目录和文件都存在、目录存在文件不存在、目录和文件都不存在map<string, Tree>& children = tree->children;iter = children.find(vs[i]);if (iter == d()) { // 新建文件children[vs[i]] = new TreeNode();tree = children[vs[i]];tree->isFile = true;tree->size = size;}else { // 已存在, 则修改文件tree = iter->second;tree->size = size;}/* Step 4: 因为成功创建了文件，所以路径上所有目录的 lr 都加上一个 delta */T->lr += delta;for (i = 0; i < len - 1; i++) {map<string, Tree>& children = T->children;T = children[vs[i]];T -> lr += delta;}return true;
}bool setQ(Tree tree, string dirPath, long long ld, long long lr) {vector<string> vs = split(dirPath);int len = vs.size();map<string, Tree>::iterator iter;for (int i = 0; i < len; i++) {map<string, Tree>& children = tree->children;iter = children.find(vs[i]);if (iter == d()) // not existsreturn false;tree = iter->second;}if (tree->isFile) return false; // not directoryif (ld > 0 && calculateD(tree) > ld|| lr > 0 && tree->lr > lr)return false;// elsetree->LD = ld;tree->LR = lr;return true;
}