,真是码力太不足了,,一个大模拟 写了一万年 调了一万年,吐了,还被身边一个材料oi dalao说该题简单,*随声附和orz orz orz
其实就是一个大模拟。发现从复杂度的角度上看根本没有任何问题。最后结构体记录 1.类型:是文件还是夹子 2.map<string,int>的树状儿子表 3. ld,lr,目录配额和后代配额 4. 已用的目配和后配 5 size 是文件时的大小。
之后创建就模拟造,判断,搞,发现不对就撤回
删除和设置配额同理
纸上得来终觉浅,绝知此事要躬行
这道题着实对码力和清晰认知有所考验。
点击查看又臭又长代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<set>
#include<map>
#include<cmath>
#define ll long long
using namespace std;
const ll inf = 2e18;
struct node {
ll type;//1 文件 2 目录
map<string,ll>nt;
ll ld,lr;//目录配额 后代配额
ll size,d,r;//已用目录配额和后代配额
}z[2000005];
ll cnnt=1,rt=1;
string SS;//输入
vector<string>lj;//路径
vector<ll>ve;//一路下去搜的路
void getpath() {
SS.push_back(‘/‘);
ll sz = SS.size();
ll L = 1; ll R=1;
while(R<sz) {
while(SS[R]!=‘/‘) R++;
string tmps = SS.substr(L,R-L);
lj.push_back(tmps);
R++; L = R;
}
}
ll NSZ;//创建的大小
bool crt(ll p,ll cs) { //结点 路径层数
ll nxtp = z[p].nt[lj[cs]]; //下结点
if(cs==lj.size()-1) { //创建层
if(nxtp) {
if(z[nxtp].type==2) return 0;
if(z[nxtp].type==1) {
ll desize = NSZ-z[nxtp].size;//改变额
if(z[p].ld-z[p].d<desize) return 0;
for(ll i=0;i<ve.size();i++) {
if(z[ve[i]].lr-z[ve[i]].r<desize) return 0;
}
//成功新文件
z[nxtp].size = NSZ;
z[p].d += desize;
for(ll i=0;i<ve.size();i++) {
z[ve[i]].r += desize;
}
return 1;
}
}
ll desize = NSZ;
if(z[p].ld-z[p].d<desize) return 0;
for(ll i=0;i<ve.size();i++) {
if(z[ve[i]].lr-z[ve[i]].r<desize) return 0;
}
//yes
nxtp = ++cnnt;
z[p].nt[lj[cs]] = nxtp;
z[nxtp].size = NSZ;
z[nxtp].type = 1;
z[p].d += desize;
for(ll i=0;i<ve.size();i++) {
z[ve[i]].r += desize;
}
return 1;
//新文件
}
if(!nxtp) { //没有这个文件夹
nxtp = ++cnnt;
z[p].nt[lj[cs]] = nxtp;
z[nxtp].ld = z[nxtp].lr = inf; z[nxtp].type = 2;
ve.push_back(nxtp);
bool fla = crt(nxtp,cs+1);
if(!fla) {
z[p].nt[lj[cs]] = 0;
return 0;
} //fail
return 1;
}
if(z[nxtp].type==1) return 0;
ve.push_back(nxtp);
return crt(nxtp,cs+1);
}
void rmv(ll p,ll cs) {
ll nxtp = z[p].nt[lj[cs]];
if(!nxtp) return;
if(cs==lj.size()-1) {
ll desize = -(z[nxtp].size + z[nxtp].r);
//若文件则size,若夹子则为后代用额。
z[p].nt[lj[cs]] = 0;
if(z[nxtp].type==1) z[p].d += desize;
for(ll i=0;i<ve.size();i++) {
z[ve[i]].r += desize;
}
return;
}
ve.push_back(nxtp);
rmv(nxtp,cs+1);
}
bool QQ(ll p,ll cs,ll SZLD,ll SZLR) {
ll nxtp = z[p].nt[lj[cs]];
if(!nxtp) return 0;
if(cs==lj.size()-1) {
if(z[nxtp].type==1) return 0;
if(z[nxtp].d>SZLD||z[nxtp].r>SZLR) return 0;
z[nxtp].ld = SZLD; z[nxtp].lr = SZLR;
return 1;
}
if(z[nxtp].type==1) return 0;
return QQ(nxtp,cs+1,SZLD,SZLR);
}
char op[2];
int main(){
z[rt].type=2; z[rt].lr=z[rt].ld=inf;
z[rt].nt[""]=1;
ll n;
scanf("%lld",&n);
while(n--) {
scanf("%s",&op[1]);
cin>>SS; lj.clear();
getpath();
if(op[1]==‘C‘) {
scanf("%lld",&NSZ);
ve.clear(); ve.push_back(rt);
printf("%c\n",(crt(rt,0)?‘Y‘:‘N‘));
} else if(op[1]==‘R‘) {
ve.clear(); ve.push_back(rt);
rmv(rt,0);
puts("Y");
} else if(op[1]==‘Q‘) {
ll SZLD,SZLR;
scanf("%lld%lld",&SZLD,&SZLR);
if(SZLD==0) SZLD = inf;
if(SZLR==0) SZLR = inf;
printf("%c\n",(QQ(rt,0,SZLD,SZLR))?‘Y‘:‘N‘);
}
}
return 0;
}