题意：有n个人每人拿着一把枪想要杀死n个怪兽，大写字母代表人，小写字母代表怪兽。A只能杀死a，B只能杀死b，如题目中的图所示，枪的弹道不能交叉。人和怪兽的编号分别是1到n，问是否存在能全部杀死的情况，如果存在则输出编号1到n的每个人杀死的怪兽的编号，如果不能输出"Impossible"。
题解：贪心，用递归实现，判断相邻的是否能构成一对，优先构成相邻的，如果不能就递归到前面看是否能构成一对即可。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,e;
char data[*];
int Next[*];
bool eq(char a,char b) {
bool ta=,tb=;
if(a>='A'&&a<='Z') {
a-='A';
ta=;
}
if(a>='a'&&a<='z') a-='a';
if(b>='A'&&b<='Z') {
b-='A';
tb=;
}
if(b>='a'&&b<='z') b-='a';
if(ta&&tb) return false;
if(ta==false && tb==false) return false;
return a==b;
}
void solve(int s) {
//printf("%d %d\n",s,e);
e++;
if(e>=n) return;
while(e<n&&!eq(data[s],data[e])) {
solve(e);
}
if(e>=n) return;
Next[s]=e;
Next[e]=s;
e++;
}
int main() {
scanf("%d",&n);
scanf("%s",data);
n*=;
memset(Next,-,sizeof(Next));
e=;
while(e<=n) solve(e);
for(int i=;i<n;i++) {
//printf("%d ",Next[i]);
if(Next[i]==-) {
puts("Impossible");
return ;
}
}
//puts("");
int gid[*],g=;
for(int i=;i<n;i++) {
if(data[i]>='a'&&data[i]<='z') {
gid[i] = g++;
}
}
for(int i=;i<n;i++) {
if(data[i]>='A'&&data[i]<='Z') {
printf("%d ",gid[Next[i]]);
}
}
puts("");
}