链接:ccf201909-3
题解
- 超级大模拟，码农题，暂时90分，待继续debug
- 就简单的弄出树形结构，然后在树上查询就ok。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
using namespace std;
const int N=1e2+7;
string str[N],s[N];
vector<int>p[N*100],c[N];
int n,m,L,cnt,ans[N],f[N],vis[N][N],ct;
void init(){
ios::sync_with_stdio(false);
cin>>n>>m;getline(cin,str[0]);
rep(i,1,n)getline(cin,str[i]);
rep(i,1,n){
int id=0,len,size;
while(str[i][id]=='.')id++;
len=(id+1)/2;L=max(L,len);
size=str[i].length();
while(id<size&&str[i][id]!='#'){
if(str[i][id]!=' '&&str[i][id]>='A'&&str[i][id]<='Z')str[i][id]='a'+str[i][id]-'A';
id++;
}
c[len].push_back(i);
if(len==0)f[++f[0]]=i;
if(len){
size=c[len-1].size()-1;
p[c[len-1][size]].push_back(i);
}
}
}
string ptr;
void dfs(int x,int k){
if(vis[x][k])return ;
if(k>ct)return ;
if(x==1&&k==1&&str[x].find(s[k])!=ptr.npos){
if(k==ct)ans[++cnt]=x;
dfs(x,2);
}
vis[x][k]=1;
int size=p[x].size()-1;
rep(i,0,size){
int j=p[x][i];
int l=str[j].find(s[k]);
if(l!=ptr.npos&&(s[k][0]=='#'||str[j][l-1]!='#')){
if(k==ct)ans[++cnt]=j;
else dfs(j,k+1);
}
dfs(j,k);
dfs(j,1);
}
}
void find(){
getline(cin,ptr);
int size=ptr.length()-1,c=-1;ct=0;cnt=0;
rep(i,0,size){
if(ptr[i]==' ')continue;
if(ptr[i]=='#')c=ct+1;
s[++ct].push_back(ptr[i]);
int j=i+1;while(j<=size&&ptr[j]!=' '){s[ct].push_back(ptr[j]);j++;}
i=j;
}
rep(i,1,ct)if(i!=c){
size=s[i].length()-1;
rep(j,0,size)if(s[i][j]>='A'&&s[i][j]<='Z')s[i][j]='a'+s[i][j]-'A';
}
rep(i,1,f[0])dfs(f[i],1);
rep(i,1,ct)s[i].clear();
memset(vis,0,sizeof vis);
}
int main(){
init();
rep(i,1,m){
find();
sort(ans+1,ans+cnt+1);
cout<<cnt;
rep(i,1,cnt)cout<<' '<<ans[i];
cout<<endl;
}
return 0;
}