HDU 4724 If You Know This,You Must Have NO GF 解题报告
题目题意：
Make一个文件有三种命令：
1、形如Target: ，表示要生成Target，必须要先有所有的components，如果某个component还不存在，就先生成它。如果还是不行，就不生成Target。依赖关系不会成环。
2、形如g++ a.o b.o -o main，完全可以忽略。
3、如果行中有‘#’，则‘#’后的是注释，不用管。
如果一行最后有‘\'，表示和下一行是连在一起的，原本是同一行。
这里的“This command will not get executed“有歧义，如果不能执行，究竟还是否生成那些能生成的components？我是能生成则生成，据说热身赛当天的标程是生成到第一个不能生成的component就停止。
题解：
就一个模拟，将文件名分离出来，用数字代替，然后就会得到一棵依赖树，dfs一遍即可。
//Time:31ms
//Memory:372KB
//Length:2361B
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
#define MAXN 10005
map<string,int> ma;
int he,to,nex,ntop,ans;
char s1,s2,*s3;
bool vi,ty;
void add(int u,int v)
{
to=v;
nex=he;
he=ntop++;
}
bool cal(int h)
{
bool flag=true,f2=false;
if(vi) return true;
for(int i=he;i!=-1;i=nex)
flag&=cal(to),f2=true;
vi=flag&&f2;
ans+=flag&&f2;
return vi;
}
char *mget(char *s)
{
if(s==NULL) return NULL;
for(int i=0,j=0;s&&s!='#';++i)
if(ty])
{
for(;ty];++j) s2=s;
s2='\0';
return s+i+j;
}
return NULL;
}
int main()
{
//freopen("/home/moor/Code/input","r",stdin);
int ncase,len,q,top,now;
scanf("%d",&ncase);
memset(ty,0,sizeof(ty));
for(int i=0;i<26;++i) ty=ty=1;
for(int i=0;i<10;++i) ty=1;
ty['.']=1;
for (int hh=1;hh<=ncase;++hh)
{
ntop=0;
top=1;
memset(he,-1,sizeof(he));
memset(vi,0,sizeof(vi));
ma.clear();
printf("%sCase #%d:\n",hh>1?"\n":"",hh);
s1='\0';
while(gets(s1)&&(s1=='\0'||s1=='\n'||s1=='\r'));
while(s1!='=')
{
len=strlen(s1);
while(s1=='\\')
{
gets(s2);
strcpy(&s1,s2);
len+=strlen(s2)-1;
}
if(strstr(s1,":")==NULL)
{
gets(s1);
continue;
}
s3=s1;
s3=mget(s3);
if(ma.find(s2)==ma.end()) ma=top++;
now=ma;
while((s3=mget(s3))!=NULL)
{
if(ma.find(s2)==ma.end()) ma=top++;
add(now,ma);
}
gets(s1);
}
scanf("%d",&q);
while(q--)
{
scanf("%s",s1);
if(ma.find(s1)!=ma.end()) vi]=1;
}
scanf("%d",&q);
while(q--)
{
ans=0;
scanf("%s%s",s1,s2);
printf("%d\n",ma.find(s2)!=ma.end()?(cal(ma)?ans:0):0);
}
gets(s1);
}
return 0;
}
页:
[1]