简单说下想法,首先把文件各路径hash,然后文件树各节点孩子用map存,配额啥的分类讨论一波。想法很简单,实现细节较多。
下为考场AC代码,可供参考。
#include <bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int BASE=20000623;
const int MAXN=110;
int M,N,A[MAXN];
struct node
{
//int ID;
bool f;
long long LD,LR;
long long sd,sr;
map<int,node *> ch;
}*root,snode[10000010],*ps=snode;
int Cnt;
char s[100010];
void newnode(node *x,bool f)
{
//x->ID=++Cnt;
x->f=f;
x->LD=x->LR=0;
x->sd=x->sr=0;
}
void Create(long long Size)
{
node *x=root;
for (int i=1;i<=N;++i)
{
if (x->ch[A[i]]==NULL) break;
x=x->ch[A[i]];
if (i==N && x->f)
{
Size=Size-x->sr;
}
}
//printf("%lld\n",Size);
x=root;
if (N==1)
{
if (x->LD && x->LD<x->sd+Size)
{
printf("N\n");
return ;
}
}
if (x->LR && x->LR<x->sr+Size)
{
printf("N\n");
return ;
}
for (int i=1;i<=N;++i)
{
if (x->ch[A[i]]==NULL) break;
node *son=x->ch[A[i]];
//printf("%d\n",son->ID);
if (i==N && !son->f)
{
printf("N\n");
return ;
}
if (i<N && son->f)
{
printf("N\n");
return ;
}
if (i<N)
{
if (son->LR)
{
if (son->LR<son->sr+Size)
{
printf("N\n");
return ;
}
}
if (i==N-1)
{
if (son->LD)
{
if (son->LD<son->sd+Size)
{
printf("N\n");
return ;
}
}
}
}
x=son;
}
printf("Y\n");
x=root;
x->sr+=Size;
if (N==1) x->sd+=Size;
for (int i=1;i<=N;++i)
{
node *son;
if (i==N)
{
if (x->ch[A[i]]==NULL)
{
x->ch[A[i]]=++ps;
son=ps;
newnode(son,1);
son->sr=Size;
}
else
{
son=x->ch[A[i]];
son->sr+=Size;
}
break;
}
if (x->ch[A[i]]==NULL)
{
x->ch[A[i]]=++ps;
son=ps;
newnode(son,0);
}
else son=x->ch[A[i]];
son->sr+=Size;
if (i==N-1)
{
son->sd+=Size;
}
x=son;
}
}
void Remove()
{
printf("Y\n");
node *x=root,*last;
for (int i=1;i<=N;++i)
{
if (x->ch[A[i]]==NULL) return ;
last=x;
x=x->ch[A[i]];
if (i<N && x->f) return ;
}
node *f=x;
last->ch[A[N]]=NULL;
x=root;
if (f->f && N==1) x->sd-=f->sr;
x->sr-=f->sr;
for (int i=1;i<N;++i)
{
x=x->ch[A[i]];
x->sr-=f->sr;
if (f->f && i==N-1) x->sd-=f->sr;
}
}
void Set(long long LD,long long LR)
{
node *x=root;
for (int i=1;i<=N;++i)
{
if (x->ch[A[i]]==NULL)
{
printf("N\n");
return ;
}
x=x->ch[A[i]];
if (x->f)
{
printf("N\n");
return ;
}
}
//printf("%d %lld %lld\n",x->ID,x->sd,x->sr);
if ((LD && x->sd>LD) || (LR && x->sr>LR))
{
printf("N\n");
return ;
}
printf("Y\n");
x->LD=LD;
x->LR=LR;
}
int main()
{
root=ps;
newnode(root,0);
cin>>M;
for (int i=1;i<=M;++i)
{
char c;
scanf(" %c",&c);
scanf("%s",s);
N=0;
int p=1;
int len=strlen(s);
bool f=0;
while (p<len)
{
if (s[p]=='/')
{
f=0;
}
else
{
if (!f) ++N,f=1,A[N]=s[p];
else A[N]=(1LL*A[N]*BASE+s[p])%MOD;
}
++p;
}
if (c=='C')
{
long long x;
scanf("%lld",&x);
Create(x);
}
else if (c=='R')
{
Remove();
}
else
{
long long LD,LR;
scanf("%lld%lld",&LD,&LR);
Set(LD,LR);
}
}
return 0;
}