3864. 打字机

三个变换 x->ax x->axbx x-> Ø
分析：x->axbx 表明每一个b的产生前面必须有一个a，定义两个数组a[] b[]，对字符串s的任意位置pos，a[pos]记录s[0]~s[pos - 1]有多少个a,b[pos]记录 s[0]~s[pos - 1]有多少个b,递推关系为a[i + 1] = s[i] == ‘a’? (a[i] + 1):a[i] b[i + 1] = s[i] == ‘b’? (b[i] + 1:b[i]),因此对于每一个 pos,若发现b[pos] > a[pos] 则直接判断为“Dead Fang”
x->ax 表明每一个x都可以产生无数个a，那么字符串s最后一个b后面的所有a都不会影响结果，因为它们只可能由x->ax得到
注意到对于s的某一位置pos，如果a[pos] > b[pos] 那么则说明所有在0~pos之间的a既有通过x->ax产生的，也有x->axbx,这样就会产生不同的顺序.
例如 aaabab 可以是a1a2a2ba1b 也可以是a2a1a2ba1b，这表明s从0~pos的子串属于“Sad Fang“
因此，若所有的pos都满足b[pos] <= a[pos]，那么答案是”Happy Fang“或者是”Sad Fang“，忽略掉s后面的a，找到最后一个’b’的位置p来判断整个字符串属于哪个答案
如果a[p+1] == b[p+1] 则判断为”Happy Fang“如果 a[p+1] != b[p+1] 则判断为”Sad Fang“

但是使用数组的这种方法由于a[]和b[]的填写太慢会超时，使用栈来模拟上述分析
先把s后面的a去掉
遍历s，当s[i] == ‘a’ 时，将a入栈 s[i] == ‘b’时，如果栈为空，则答案为”Dead Fang“，如果栈不为空，弹出一个a
遍历结束后，如果遍历时没有判断出结果，则此时若栈为空，等价于上述的a[p+1] == b[p+1]，判断为”Happy Fang“
栈不空，等价于上述的a[p+1] != b[p+1]，判断为”Sad Fang“
代码如下

include

using namespace std;
stack sta;
int main()
{
int T;
cin >> T;
while(T–)
{
string s;
cin >> s;
int pos = s.size();
for(int i = s.size() - 1;i >= 0;i = i - 1)
{
if(s[i] == ‘a’)
pos–;
else
break;
}
s = s.substr(0,pos);
int done = 0;
for(int i = 0;i < s.size();i = i + 1)
{
if(s[i] == ‘a’)
{
sta.push(‘a’);
}
else if(s[i] == ‘b’)
{
if(sta.empty())
{
cout << “Dead Fang” << endl;
done = 1;
break;
}
else
sta.pop();
}
}
if(!done)
{
if(sta.empty())
cout << “Happy Fang” << endl;
else
cout << “Sad Fang” << endl;
}
while(!sta.empty())
{
sta.pop();
}
}
}