2020-12-3 带配额的文件系统 最长的大模拟 使用指针优化数据结构
- 索引
- 2020-12-3 带配额的文件系统 最长的大模拟 使用指针优化数据结构
- 思路
- 遇到的问题(学到的东西)
- 40分stl代码
- acwing 15/15 csp官网40分代码
- 100分完整代码
索引
历年CSP认证考试真题题解总汇持续更新
2020-12-3 带配额的文件系统 最长的大模拟 使用指针优化数据结构
这题可以说是最长第三题了， 但是逻辑并不是非常的复杂，关键是使用一个好的数据结构和编程的思想，越是复杂的题就越是要暴力，这种情况下即使有一些重复的计算也没关系，有一个简洁清晰的逻辑最为重要。 这种情况下就是要用时间换取逻辑的清晰了。
写这题的经历非常曲折差不多写了快三版才写到100分，而且其中的一些问题还是没有找到，如果有大神有思路希望告知，最后是参考了别人的代码，修改了最后一版，才拿到100分，考试遇到了这题基本上就g了。
可能做题的意义就是见识这些大风大浪。
思路
除去题目给出要求，还要注意一下几点
新建文件的指令
- 指令执行不成功，文件系统不能有变化
- 新建文件要在路径上所有的目录增加大小
- 注意新建文件的时候要看，原本的文件有没有存在，目录增加的大小要根据原本的文件大小算
删除文件的指令
- 如果删除的是文件夹 则上级的目录的大小要删除文件夹的所有后代大小
配额指令
这个没啥比较简单，按题目来就行
遇到的问题(学到的东西)
- 数据结构选取的有问题，导致逻辑异常复杂
一开始想着用一个邻接表存文件之间的关系，然后用数组存文件的数据，然后用索引来建立两者的关系，然后我虽然清楚其中的逻辑，但是写代码异常的难受，就是每个模块之间耦合性非常的强，导致出问题，一出一长串，最后出现的错误，没有很长的测试数据，都找不到bug出在哪里，所以以后要尽量避免这种复杂逻辑的，用一些直观的数据结构更好。
总共写了250行。
如果代码写了超过了200行那么一定是逻辑有问题。
最后这一版过了acwing 7/15个测试数据，在官网拿到了40分
- 看了别人的思路，使用了指针的数据结构
改用了指针的数据结构，但是判断逻辑几乎没有改。使用了指针的结构方便了不少，比之前的数据结构方便不少。但是尤其是新建文件的逻辑，耦合度非常的高，要是修一个bug得好久，并且就像是的机器学习过拟合一样，只能适用于特殊情况，出了问题还得再加特殊情况，一直打补丁真的很恶心，最后这一版也是改到了
acwing 15/15个测试点 csp官网40分
期间也是出现了一些问题
- 使用指针怎么申请空间（不能是直接用声明变量的形式声明）
错误的：
if (i >= fs.size() - 1) // 还未创建 { struct dfile temp; if (i == path.size() - 1) { temp.size = file_size; temp.type = 0; } else { temp.child_size += t_file_size; temp.dir_size += i == path.size() - 2 ? t_file_size : 0; temp.type = 1; } // 建立索引 fs.back()->child[path[i]] = &temp;这样申请空间会导致，下次temp再用的时候这个就会被释放，建立了索引也没用，数据也会丢失
正确的：使用new申请空间
if (i >= fs.size() - 1) // 还未创建 { struct dfile *temp = new dfile(1); if (i == path.size() - 1) { temp->size = file_size; temp->type = 0; } else { temp->child_size += t_file_size; temp->dir_size += i == path.size() - 2 ? t_file_size : 0; temp->type = 1; } // 建立索引 fs.back()->child[path[i]] = temp;
- 初值的问题
虽然设置的结构体是全局变量，但是结构体内部的变量的值还是需要设置初值的。
struct dfile
{
long long size = 0;
long long dir_size = 0; //
long long child_size = 0; // 后代大小
long long dir_limit = 0; // 目录配额
long long child_limit = 0; // 孩子配额
bool isDir = 0; // 1是目录 0是文件
map<string, struct dfile *> child;
dfile(int t) : isDir(t) {}
};
- 优化了新建文件的逻辑
使用了耦合度比较低的逻辑，虽然要多花一些时间，但是逻辑非常清晰，然后过了样例后，直接就100分了。
这里面也学会了一些用法
- string的一些方法
vector<string> split(const string &s, const string &c = "") { vector<string> res; for (long long i = 0, j = 0; i < s.size(); i = j + 1) { j = s.find(c, i); if (j == -1) j = s.size(); res.push_back(s.substr(i, j - i)); } return res; }从i开始找到c字符串的下标，如果没有找到则返回-1
s.find(c,i)分割字符串 从i开始返回j-i个长度的字符串
s.substr(i,j-i)
- 空指针是nullptr
for (int i = 1; i < path.size() && p; i++) { // 向前判断判断i-1的时候的p 不会判断最后一个p（文件的指针） if (!p->isDir or (p->child_limit && p->child_size + sz > p->child_limit) or (i == path.size() - 1 && p->dir_limit && p->dir_size + sz > p->dir_limit)) return false; p = p->child.count(path[i]) ? p->child[path[i]] : nullptr; }可以直接判断 &&p 判断p为不为空
- c++可以直接使用 and or等
在C语言ios646.h头文件种定义了关于and、or、not逻辑运算符。
and可以代替&&
or可以替代||
not可以替代!
40分stl代码
#include <bits/stdc++.h>
using namespace std;
struct file
{
string name;
long long size;
long long dir_size;
long long child_size;
long long dir_limit;
long long child_limit;
int type = -1; // 0是普通文件 1是目录文件
int to_paths; // 用于寻找文件内的索引
} f[2000001];
long long top;
map<long long, vector<long long>> paths;
long long indexes; // 提供一个不重复的索引
vector<string> convert_string_path(string file_path)
{
vector<string> res;
string temp = "";
for (int i = 1; i < file_path.size(); i++)
{
if (file_path[i] != '/')
{
temp += file_path[i];
}
else
{
res.push_back(temp);
temp.clear();
}
}
if (!temp.empty())
res.push_back(temp);
return res;
}
int find_file_from_dir(long long dir, string name) // 返回文件位置
{
vector<long long> temp = paths[f[dir].to_paths];
for (int i = 0; i < temp.size(); i++)
{
if (name == f[temp[i]].name)
{
return temp[i];
}
}
return -1;
}
bool deal_creat(string file_path, long long file_size) // 创建普通文件
{
vector<string> path = convert_string_path(file_path);
vector<long long> real_path;
bool exist = false; // 这个文件是不是已经存在
if (f[0].child_limit && f[0].child_size + file_size > f[0].child_limit)
return false;
if (f[0].dir_limit && path.size() == 1 && f[0].dir_size + file_size > f[0].dir_limit)
return false;
long long dir = 0; // 先从根目录开始
for (int i = 0; i < path.size(); i++)
{
long long file_locate = find_file_from_dir(dir, path[i]);
if (file_locate == -1)
{
// 先申请一个目录的位置
dir = top;
real_path.push_back(top++);
}
else
{
if (i == path.size() - 1) // 如果是最后一个 则是文件不是目录
{
if (f[file_locate].type == 1)
{
return false;
}
else // 替换这个文件
{
exist = true;
real_path.push_back(file_locate);
}
}
else // 找到了文件看看是不是目录
{
if (f[file_locate].type == 0) // 如果是普通文件
{
return false;
}
else // 如果该目录存在
{
real_path.push_back(file_locate);
dir = file_locate;
}
}
}
}
long long t_file_size = file_size;
if (exist)
t_file_size = file_size - f[real_path[real_path.size() - 1]].size;
for (int i = 0; i < real_path.size() - 1; i++)
{
if (f[real_path[i]].child_limit && f[real_path[i]].child_size + t_file_size > f[real_path[i]].child_limit)
return false;
if (f[real_path[i]].dir_limit && i == real_path.size() - 2 && f[real_path[i]].dir_size + t_file_size > f[real_path[i]].dir_limit)
return false;
}
dir = 0;
if (path.size() == 1)
f[0].dir_size += t_file_size;
f[0].child_size += t_file_size;
for (int i = 0; i < path.size(); i++)
{
if (f[real_path[i]].type == -1) // 还未创建
{
f[real_path[i]].name = path[i];
if (i == path.size() - 1)
{
f[real_path[i]].size = file_size;
f[real_path[i]].type = 0;
}
else
{
f[real_path[i]].child_size += t_file_size;
f[real_path[i]].dir_size += i == path.size() - 2 ? t_file_size : 0;
f[real_path[i]].to_paths = indexes++; // 为这个文件构建索引
f[real_path[i]].type = 1;
}
// 建立索引
paths[dir].push_back(real_path[i]);
}
else // 如果已经创建了
{
if (i == path.size() - 1)
{
f[real_path[i]].size = file_size;
}
else
{
f[real_path[i]].child_size += t_file_size;
f[real_path[i]].dir_size += i == path.size() - 2 ? t_file_size : 0;
}
}
dir = f[real_path[i]].to_paths;
}
return true;
}
bool deal_remove(string file_path)
{
vector<string> path = convert_string_path(file_path);
vector<long long> real_path;
real_path.push_back(0); // 把根目录添加
int dir = 0;
for (int i = 0; i < path.size(); i++)
{
long long file_locate = find_file_from_dir(dir, path[i]);
if (file_locate == -1)
{
return true;
}
real_path.push_back(file_locate);
dir = file_locate;
}
// 删去索引
int file_locate = f[real_path[real_path.size() - 2]].to_paths;
vector<long long> temp = paths[file_locate];
for (int i = 0; i < temp.size(); i++)
{
if (temp[i] == real_path[real_path.size() - 1])
{
paths[file_locate].erase(paths[file_locate].begin() + i);
break;
}
}
int type = f[real_path[real_path.size() - 1]].type;
if (type == 1)
{
paths.erase(f[real_path[real_path.size() - 1]].to_paths);
// 删除占用
long long file_size = f[real_path[real_path.size() - 1]].child_size;
for (int i = 0; i < real_path.size() - 1; i++)
{
f[real_path[i]].child_size -= file_size;
}
}
else
{
// 删除占用
long long file_size = f[real_path[real_path.size() - 1]].size;
for (int i = 0; i < real_path.size() - 1; i++)
{
f[real_path[i]].child_size -= file_size;
if (i == real_path.size() - 2)
f[real_path[i]].dir_size -= file_size;
}
}
return true;
}
long long get_sum_size(int dir)
{
vector<long long> temp = paths[f[dir].to_paths];
long long sum = 0;
for (auto item : temp)
{
if (f[item].type == 0)
{
sum += f[item].size;
}
else if (f[item].type == 1)
{
sum += get_sum_size(item);
}
}
return sum;
}
bool deal_q(string file_path, long long ld, long long lr)
{
long long dir = 0;
vector<string> path = convert_string_path(file_path);
vector<long long> real_path;
real_path.push_back(0);
for (int i = 0; i < path.size(); i++)
{
long long file_locate = find_file_from_dir(dir, path[i]);
if (file_locate == -1)
return false;
if (f[file_locate].type == 0) // 如果不是目录文件
return false;
real_path.push_back(file_locate);
dir = file_locate;
}
long long pos = real_path[real_path.size() - 1];
if (ld != 0) // 检查孩子文件的大小是不是超过限制了
{
vector<long long> temp = paths[f[pos].to_paths];
long long sum = 0;
for (int i = 0; i < temp.size(); i++)
{
if (f[temp[i]].type == 0)
{
sum += f[temp[i]].size;
}
}
if (sum > ld) // 检查后代文件的总和是不是超过了限制
return false;
}
if (lr != 0)
{
long long sum = get_sum_size(pos);
if (sum > lr)
return false;
}
f[pos].child_limit = lr;
f[pos].dir_limit = ld;
return true;
// f[real_path[real_path.size() - 1]].child_limit
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// freopen("1.txt", "r", stdin);
int n;
cin >> n;
// 初始化根目录
f[0].name = "";
f[0].type = 1;
f[0].to_paths = indexes++;
top++;
for (int i = 0; i < n; i++)
{
string type;
cin >> type;
if (type == "C")
{
string file_path;
long long file_size;
cin >> file_path >> file_size;
if (deal_creat(file_path, file_size))
cout << "Y" << endl;
else
cout << "N" << endl;
}
if (type == "R")
{
string file_path;
cin >> file_path;
if (deal_remove(file_path))
cout << "Y" << endl;
}
if (type == "Q")
{
string file_path;
long long ld, lr;
cin >> file_path >> ld >> lr;
if (deal_q(file_path, ld, lr))
cout << "Y" << endl;
else
cout << "N" << endl;
}
}
return 0;
}
acwing 15/15 csp官网40分代码
#include <bits/stdc++.h>
using namespace std;
struct dfile
{
long long size;
long long dir_size = 0;
long long child_size = 0;
long long dir_limit = 0;
long long child_limit = 0;
int type = -1; // 0是普通文件 1是目录文件
map<string, struct dfile *> child;
dfile(int t) : type(t) {}
};
struct dfile root(1);
vector<string> convert_string_path(string file_path)
{
vector<string> res;
string temp = "";
for (int i = 1; i < file_path.size(); i++)
{
if (file_path[i] != '/')
{
temp += file_path[i];
}
else
{
res.push_back(temp);
temp.clear();
}
}
if (!temp.empty())
res.push_back(temp);
return res;
}
bool deal_creat(string file_path, long long file_size) // 创建普通文件
{
vector<string> path = convert_string_path(file_path);
bool exist = false; // 这个文件是不是已经存在
struct dfile *p = &root;
vector<struct dfile *> fs;
fs.push_back(p);
bool newdir = false; // 记录有没有新的文件夹产生
// 检查目录是不是被文件占用
for (int i = 0; i < path.size() - 1; i++)
{
if (p->child.count(path[i]))
{
// 找到了文件看看是不是目录
struct dfile *temp = p->child[path[i]];
if (temp->type == 0) // 如果是普通文件
return false;
p = temp;
fs.push_back(p);
}
else
newdir = true;
}
// 文件名是不是被目录占用
// 只有没有新建文件夹的时候才检查
if (!newdir)
{
struct dfile *last = fs.back();
if (last->child.count(path.back()))
{
if (last->child[path.back()]->type == 1)
return false;
exist = true;
fs.push_back(last->child[path.back()]);
}
else
{
fs.push_back(new dfile(0));
}
}
// 判断大小限制是不是符合
long long t_file_size = file_size;
if (exist)
t_file_size = file_size - fs.back()->size;
for (int i = 0; i < fs.size(); i++)
{
if (fs[i]->type == 1 && fs[i]->child_limit && fs[i]->child_size + t_file_size > fs[i]->child_limit)
return false;
if (fs[i]->type == 1 && !newdir && fs[i]->dir_limit && i == fs.size() - 2 && fs[i]->dir_size + t_file_size > fs[i]->dir_limit)
return false;
}
// 给路径上的文件夹增加大小
fs[0]->child_size += t_file_size;
if (path.size() == 1)
fs[0]->dir_size += t_file_size;
for (int i = 0; i < path.size(); i++)
{
if (i >= fs.size() - 1) // 还未创建
{
struct dfile *temp = new dfile(1);
if (i == path.size() - 1)
{
temp->size = file_size;
temp->type = 0;
}
else
{
temp->child_size += t_file_size;
temp->dir_size += i == path.size() - 2 ? t_file_size : 0;
temp->type = 1;
}
// 建立索引
fs.back()->child[path[i]] = temp;
fs.push_back(temp);
}
else // 如果已经创建了
{
if (i == path.size() - 1)
{
fs[i + 1]->size = file_size;
fs[i]->child[path[i]] = fs[i + 1];
}
else
{
fs[i + 1]->child_size += t_file_size;
fs[i + 1]->dir_size += i == path.size() - 2 ? t_file_size : 0;
}
}
}
return true;
}
bool deal_remove(string file_path)
{
vector<string> path = convert_string_path(file_path);
vector<struct dfile *> fs;
fs.push_back(&root);
// 判断路径存不存在
struct dfile *p = &root;
for (int i = 0; i < path.size(); i++)
{
if (!p->child.count(path[i]))
return true;
p = p->child[path[i]];
fs.push_back(p);
}
// 删去索引
fs[fs.size() - 2]->child.erase(path.back());
// 删除占用
int type = fs.back()->type;
if (type == 1) // 如果是文件夹
{
// 删除文件夹占用
long long file_size = fs.back()->child_size;
for (int i = 0; i < fs.size() - 1; i++)
{
fs[i]->child_size -= file_size;
}
}
else
{
// 删除文件占用
long long file_size = fs.back()->size;
for (int i = 0; i < fs.size() - 1; i++)
{
fs[i]->child_size -= file_size;
if (i == fs.size() - 2)
fs[i]->dir_size -= file_size;
}
}
return true;
}
bool deal_q(string file_path, long long ld, long long lr)
{
vector<string> path = convert_string_path(file_path);
struct dfile *p = &root;
vector<struct dfile *> fs;
fs.push_back(p);
for (int i = 0; i < path.size(); i++)
{
if (!p->child.count(path[i])) // 如果没有找到
return false;
if (p->child[path[i]]->type == 0) // 如果不是目录文件
return false;
p = p->child[path[i]];
fs.push_back(p);
}
struct dfile *dir = fs.back();
if (ld != 0) // 检查孩子文件的大小是不是超过限制了
{
if (dir->dir_size > ld)
return false;
}
if (lr != 0) // 检查后代文件的总和是不是超过了限制
{
if (dir->child_size > lr)
return false;
}
dir->child_limit = lr;
dir->dir_limit = ld;
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// freopen("1.txt", "r", stdin);
int n;
cin >> n;
// 初始化根目录
root.type = 1;
for (int i = 0; i < n; i++)
{
string type;
cin >> type;
if (type == "C")
{
string file_path;
long long file_size;
cin >> file_path >> file_size;
if (deal_creat(file_path, file_size))
cout << "Y" << endl;
else
cout << "N" << endl;
}
if (type == "R")
{
string file_path;
cin >> file_path;
if (deal_remove(file_path))
cout << "Y" << endl;
}
if (type == "Q")
{
string file_path;
long long ld, lr;
cin >> file_path >> ld >> lr;
if (deal_q(file_path, ld, lr))
cout << "Y" << endl;
else
cout << "N" << endl;
}
}
return 0;
}
100分完整代码
#include <bits/stdc++.h>
using namespace std;
struct dfile
{
long long size = 0;
long long dir_size = 0; //
long long child_size = 0; // 后代大小
long long dir_limit = 0; // 目录配额
long long child_limit = 0; // 孩子配额
bool isDir = 0; // 1是目录 0是文件
map<string, struct dfile *> child;
dfile(int t) : isDir(t) {}
};
struct dfile root(1);
vector<string> split(const string &s, const string &c = "")
{
vector<string> res;
for (long long i = 0, j = 0; i < s.size(); i = j + 1)
{
j = s.find(c, i);
if (j == -1)
j = s.size();
res.push_back(s.substr(i, j - i));
}
return res;
}
int get_file_size(vector<string> path)
{
struct dfile *p = &root;
for (int i = 1; i < path.size() && p; i++)
{
p = p->child.count(path[i]) ? p->child[path[i]] : nullptr;
}
return p and !p->isDir ? p->size : 0;
}
bool can_create(vector<string> path, long long sz)
{
struct dfile *p = &root;
for (int i = 1; i < path.size() && p; i++)
{
// 向前判断判断i-1的时候的p 不会判断最后一个p（文件的指针）
if (!p->isDir or (p->child_limit && p->child_size + sz > p->child_limit) or (i == path.size() - 1 && p->dir_limit && p->dir_size + sz > p->dir_limit))
return false;
p = p->child.count(path[i]) ? p->child[path[i]] : nullptr;
}
return !p or !p->isDir; // 如果没有文件、文件夹占用文件名 或者 是文件占用文件名
}
bool deal_creat(vector<string> path, long long file_size) // 创建普通文件
{
int sz = file_size - get_file_size(path);
if (!can_create(path, sz))
return false;
struct dfile *p = &root;
for (int i = 1; i < path.size() - 1 /*剩下最后一个是文件*/; i++)
{
p->child_size += sz;
if (!p->child.count(path[i]))
p->child[path[i]] = new dfile(1);
p = p->child[path[i]];
}
// p是文件的上一级
p->child_size += sz, p->dir_size += sz;
// 判断文件是不是存在
if (!p->child.count(path.back()))
p->child[path.back()] = new dfile(0);
// 设置大小 注意这里不管是新建的还是覆盖的都是+=sz
p->child[path.back()]->size += sz;
return true;
}
bool deal_remove(vector<string> path)
{
vector<struct dfile *> fs;
fs.push_back(&root);
// 判断路径存不存在
struct dfile *p = &root;
for (int i = 1; i < path.size(); i++)
{
if (!p->child.count(path[i]))
return true;
p = p->child[path[i]];
fs.push_back(p);
}
// 删去索引
fs[fs.size() - 2]->child.erase(path.back());
// 删除占用
bool type = fs.back()->isDir;
if (type) // 如果是文件夹
{
// 删除文件夹占用
long long file_size = fs.back()->child_size;
for (int i = 0; i < fs.size() - 1; i++)
{
fs[i]->child_size -= file_size;
}
}
else
{
// 删除文件占用
long long file_size = fs.back()->size;
for (int i = 0; i < fs.size() - 1; i++)
{
fs[i]->child_size -= file_size;
if (i == fs.size() - 2)
fs[i]->dir_size -= file_size;
}
}
return true;
}
bool deal_q(vector<string> path, long long ld, long long lr)
{
struct dfile *p = &root;
for (int i = 1; i < path.size(); i++)
{
if (!p->child.count(path[i])) // 如果没有找到
return false;
if (p->child[path[i]]->isDir == 0) // 如果不是目录文件
return false;
p = p->child[path[i]];
}
struct dfile *dir = p;
if (ld && dir->dir_size > ld) // 检查孩子文件的大小是不是超过限制了
return false;
if (lr && dir->child_size > lr) // 检查后代文件的总和是不是超过了限制
return false;
dir->child_limit = lr;
dir->dir_limit = ld;
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// freopen("1.txt", "r", stdin);
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
string type, file_path;
cin >> type >> file_path;
vector<string> path = split(file_path, "/");
if (type == "C")
{
long long file_size;
cin >> file_size;
cout << (deal_creat(path, file_size) ? "Y" : "N") << endl;
}
if (type == "R")
{
deal_remove(path);
cout << "Y" << endl;
}
if (type == "Q")
{
long long ld, lr;
cin >> ld >> lr;
cout << (deal_q(path, ld, lr) ? "Y" : "N") << endl;
}
}
return 0;
}
