传送门（内网）
题意；给你一堆字符串，仅包含字符ASD，求出所有拼接方案中子串‘SAD’的最多出现次数。
很明显我们只需要考虑串与串相接的部分所带来的贡献最大值。
第一次分类：S+AD，SA+D。
意思是说，串后缀为S配前缀为AD，后缀为AD配前缀为D。
那我们按照串前缀普通，为S，为SA。
后缀普通，为D，为SD分类，再排列组合，共九种可能。
单独一个字母A提出来单独讨论。
因为前缀为D的不可能为SD，后缀为S的不可能是SA，也就是没有交集。
所以我们一定可以用某种方式将它们排好，让每一个都发挥用处。
除非：以S+AD为例。
1.如果S和AD的数量一样多，而且恰好分布在同样的串上，也就是全都长成SxxxxAD这样。
很明显最开头和最结尾的不能相连，方案减一。
2.不算单独的A，不算没有特殊前后缀的串，假设剩下的串有x个，那最多产生x-1个相交SAD。如果算出来是x个，那自然要减一。
对于单独的A。
A的作用就是弥补S，AD，SA，D数量不均有剩余的情况。
A可以将一个S修改成SA。所以我们可以枚举用多少个A去插进去。代码就很好理解了。
#include<bits/stdc++.h>
using namespace std;
#define in read()
int in{int cnt=0,f=1;char ch=0;while(!isdigit(ch)){ch=getchar();if(ch=='-')f=-1;}while(isdigit(ch)){cnt=cnt*10+ch-48;ch=getchar();}return cnt*f;
}
int t;
int n;
char ch[233];
int num[10],pre[5],suf[5];
int sum=0,cnta;
signed main(){t=in;while(t--){n=in;sum=cnta=0;memset(num,0,sizeof(num));memset(pre,0,sizeof(pre));memset(suf,0,sizeof(suf));for(int i=1;i<=n;i++){scanf("%s",ch+1);int len=strlen(ch+1);if(len==1&&ch[1]=='A'){cnta++;continue;}int idp=0,ids=0;if(ch[1]=='D')ids=1;if(len>1&&ch[1]=='A'&&ch[2]=='D')ids=2;if(ch[len]=='S')idp=1;if(ch[len-1]=='S'&&ch[len]=='A')idp=2;num[idp*3+ids]++;pre[idp]++;suf[ids]++;if(len>2){for(int j=1;j<=len-2;j++){if(ch[j]=='S'&&ch[j+1]=='A'&&ch[j+2]=='D')sum++;}}}int other=0;for(int i=1;i<=2;i++){int tmp=min(pre[i],suf[3-i]);if(tmp>0&&pre[i]==suf[3-i]&&suf[3-i]==num[i*3+3-i])tmp--;other+=tmp;}for(int i=1;i<=cnta;i++){if(i>pre[1])break;int tmp=min(pre[1]-i,suf[2])+min(pre[2]+i,suf[1]);other=max(other,tmp);}if(other>0&&other==n-num[0]-cnta)other--;printf("%d\n",other+sum);}return 0;
}