StringII（求两个人操作后得到一个串）

StringII

时间限制: 1 Sec  内存限制: 128 MB

题目描述

老师给Alice和Bob出了个题，要他们把一个字符串S变成字符串T。为了增加难度，老师要求Alice只能交换字符串中任意字符的位置，Bob只能删除字符串中任意字符。
你能告诉Alice和Bob，他们要怎样合作才能解决老师的问题吗？

输入

输入的第一行为一个正整数n(n≤10)，表示老师的提问次数。
接下来共有2×n行输入。对于老师的每次提问输入两行，第一行为字符串S，第二行为字符串T。保证S和T都只包含小写字母，且S和T是不完全相同的非空字符串。

输出

输出共n行。对于老师的每次提问输出一行，由一个单词表示Alice和Bob的合作方案。
若Alice可单独完成任务，则输出“Alice”；若Bob可单独完成任务，则输出“Bob”；若需要Alice和Bob合作才能完成任务，则输出“Both”；若两人合作也不能完成任务，则输出“Impossible”。(输出不包含引号)

样例输入

复制样例数据

2
example
lamp
aunt
ant

样例输出

Both
Bob

提示

对于40%的数据，字符串长度不超过5。
对于60%的数据，字符串长度不超过100。
对于80%的数据，字符串长度不超过1000。
对于100%的数据，字符串长度不超过100000。

设原来的串为s1,改变后的为s2,分为几种情况:

1.如果s2的长度大于s1的长度，那么直接impossible；

2.vis记录各个串字符出现的次数，如果s2中有一个字母出现的次数大于s1中该字母出现的次数，那么impossible；

3.先考虑是不是Bob单独完成的(因为没有交换)，如果s1遍历一遍后s2正好也遍历完，那么只需要Bob就行了；

4.如果s1的长度和s2的长度相同，不可能为和Bob一起完成的，所以由Alice完成(因为不可能的情况已经讨论完了)；

5.上述都不满足的话，只有两个人一起完成了。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int t;
char s[100005], str[100005];
int vis[30], vistr[30];

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &t);
	while(t--){
		scanf("%s %s", s, str);
		memset(vis, 0, sizeof(vis));
		memset(vistr, 0, sizeof(vistr));
		int lens = strlen(s), lenstr = strlen(str);
		if(lens < lenstr){printf("Impossible\n"); continue;}
		for (int i = 0; i < lens; i++) vis[s[i] - 'a']++;
		for (int i = 0; i < lenstr; i++) vistr[str[i] - 'a']++;
		int f = 0, cnt = 0;
		for (int i = 0; i < 26; i++) if(vis[i] < vistr[i]) {f = 1; break;}
		if(f) {printf("Impossible\n"); continue;}
		for (int i = 0; i < lens; i++){
			if(s[i] == str[cnt] && cnt < lenstr) cnt++;
			if(cnt == lenstr) break;
		}
		if(cnt == lenstr) {printf("Bob\n");continue;}
		if(lens == lenstr) printf("Alice\n");
		else printf("Both\n");
	}

	return 0;
}
/**/