CF894A QAQ

题目链接：https://codeforces.com/contest/894/problem/A

由于题目范围是100，所以可以暴力，

#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{cin>>s;int ans=0;int len=s.size();for(int i=0;i<len;i++){for(int j=i+1;j<len;j++){for(int k=j+1;k<len;k++){if(s[i]=='Q'&&s[j]=='A'&&s[k]=='Q'){ans++;}}}}cout<<ans;return 0;
}

但是只会用暴力做就太弱了，学个别的方法吧

深搜的方法

#include <bits/stdc++.h>
using namespace std;
string s,s1="QAQ";
int ans;
void dfs(int step,int x)
{if(step==3){ans++;return;//三次都查找成功后结束递归；}for(int i=x+1;i<s.size();i++){if(s[i]==s1[step])//如果当前字符和需要找的一样dfs(step+1,i);//继续递归}
}
int main()
{cin>>s;dfs(0,-1);cout<<ans;return 0;
}