C：Removal of Unattractive Pairs

题目链接：Removal of Unattractive Pairs *贪心思维 *构造算法

题意 给你一个字符串，在这个字符串中只要是两个相邻的不同字符串即可消除。问你最后这个字符串长度最小为多少。

分析 这是一道思维题，题意很简单，只要两个相邻的不同字符串就可以消除，但是我们怎么去最小化这个字符串的长度？ 我们先假设有这几个字符串：

假设1： 字符串为"aaaaaaa"等只包含一个字符的，那么答案为该字符本身长度

假设2： 字符串为”aaaabaaa”等包含两个不同字符。则答案为 字符串长度-2

假设3： 字符串为 ”aabcaabdaapala“等包含多个字符的，统计 a：8，b：2，c：1，d：1，p：1，l：1。那么由于a的数量是最多的那么我们优先选择去消除a。过程如下： a(ab)(ca)(ab)(da)(ap)(al)a，最后只剩下2个a无法消除。答案为 a的数量-非a的数量。

猜测： 根据以上三种假设，我们可以看出，字符串的最小长度为最多字符的数量-其他字符的 数量。那么猜测正确吗？验证一下：

验证 当a的数量为x，非a（用b代替)的数量为y时。得到类似于如下转换的字符: aaaaabbbbbbbbb,我们优先去抵消数量最多的那一类字符。为了使得剩下的字符数量最少，而在b中部分相邻字符为不同，我们即可提前消除。如： aaaaa(bb)b(bb)bbbb, 而因为a的数量是最多的，所以至少存在一种方法能消除bbbbbbbb其中多余的字符最后化简成aaaaabbbbb。全部依次消除即可。 那么如果a和b的顺序打乱了怎么办呢？ 答案是不影响结果，因为根据上面的推导可以知道，我们只需要将多余的字符删去，只保留与a数量相同的字符就可以了（因为一整行排列整齐的字符a肯定会有一个字符与非a字符相邻）。 注意1.当a的数量大于其他字符的数量时，最多只能消除到a多余的数量 2.当字符串的数量为奇数的时候，并且a的数量是小于其他字符数量的总和的时候，就只能消除到剩下一个字符： c++代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+12;
int t,n;
char c;
int main(){
  cin>>t;
  while(t--)
  {
    int ma=0;
    int p[200]={0};
    cin>>n;
    for(int i=1;i<=n;i++)
    {
      cin>>c;
      p[c]++;
      ma=max(ma,p[c]);
     //记录a（字符数量最多的字符）的数量
    }
    if( ma-(n-ma)<0 )  //当a的数量小于其他字符数量的时候
    {
      if( n%2 ) cout<<1;  //如果整个字符有奇数个，那么再怎么消除都会剩下一个字符
      else cout<<0;    //反之，我们就可以先消除比a多的那一部分的字符，其他的字符全拿去和a相消除
    }
    else cout<< ma-(n-ma);
    //其他的情况就只能消除其他字符的总量，a字符多余的那一部分始终无法消除
    cout<<endl;
  }
}

B：YetnotherrokenKeoard

题意：在字符串中，碰见一个’b'就删去最近的一个小写字母，如果是'B'就删除最近的大写字母。如果不存在，那么就字符串不会有变化。 思路：从后向前遍历，碰见一个b就让b的计数+1，碰见一个B就让B的计数加一。如果碰见了其他字母，1.在可以删除的情况下就执行删除操作。2.如果不可以删除就什么都不做 c++代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+12;
int t;
string s;
int main(){
cin>>t;
while(t--)
{
char ans[N];
//记录这个位置的字符有没有被删除
cin>>s;
int a=0,b=0;
//a为小写b的计数，b为大写B的计数
for(int i=s.length()-1;i>=0;i--)//从后向前遍历字符
{
if( s[i]=='b' ) a++,ans[i]=0;
//如果是b，让b的计数加1，并且当前字符b删除。
else if( s[i]=='B' ) b++,ans[i]=0;
//如果是B，让B的计数+1，并且删除当前字符B
else if( 'a'<=s[i] and s[i]<='z' and a ) a--,ans[i]=0;
//反之，如果当前字符是小写字母，就判断a有没有值，如果有代表这个小写字母要被删去
else if( 'A'<=s[i] and s[i]<='Z' and b ) b--,ans[i]=0;
//同理，如果是大写字母，会被删去
else ans[i]=s[i];
//如果以上条件都没满足，那么这个字符肯定是会被保留的
}
for(int i=0;i<s.length();i++)
if( ans[i] ) cout<<ans[i];
//if(ans[i])代表这个字符没被删除，就可以输出；反之ans[i]=0即该位置上的字符都被删了。就不需要输出。

cout<<endl;//输出换行

}
}