QAQ

Yesterday participated in a practice session of nowcoder,Then I met a question similar to the previous one.

nowcoder-847-A QAQ

link: QAQ

Descrption:

给定一个只包含大写字母的长度为N的字符串S,求S中不含相邻字符且长度为3的"QAQ"子序列个数。
即:
设字符串S的第i个字符为Si,求满足下列条件的三元组个数。
1≤x,y,z≤N
x<y−1
y<z−1
Sx='Q',Sy='A',Sz='Q'

输入描述:
输入仅一行一个字符串S,字符串的长度N满足(1≤N≤5000)。
N不会在输入中给出。
保证
S中只包含大写字母。
输出描述:
输出一行一个整数--满足条件的三元组个数。
示例1
输入
QQAQQ
输出
1
说明
满足条件的三元组只有一个:
<1,3,5>
示例2
输入
QAQAQ
输出
0
示例3
输入
QQHAHAQQAQ
输出
10

Intentional analysis:

QAQ,let's look it carefully.Then we can find that the amount of "QAQ" is depends on the amount of "A".So our task is find the position of "A".
Attention: You can't choose neighboring char from the original string.

For example:

QAQAQ
12345

We can find "QAQ" at:
1 2 3
1 2 5
1 4 5
3 4 5

but all of these have neighboring char,so the answer of this example is "0",not "4".

Code:

#include<bits/stdc++.h>
using namespace std;
string s;
long long ans;
int main()
{
    cin>>s;
    int l=s.size();
    for(int i=0;i<l;i++)
    {
        if(s[i]=='A')
        {
            int a=0;
            int b=0;
            for(int j=i-2;j>=0;j--)
            {
                if(s[j]=='Q')
                    a++;
            }
            for(int k=i+2;k<l;k++)
            {
                if(s[k]=='Q')
                    b++;
            }
            ans+=a*b;
        }
    }
    cout<<ans<<endl;
    return 0;
}

One more thing you should better focus on:
The answer is too big to be able to save a int type.I ffailed once because of this.

A similar question:

Descripition:
"QAQ" is a word to denote an expression of crying. Imagine "Q" as eyes with tears and "A" as a mouth.

Now Diamond has given Bort a string consisting of only uppercase English letters of length n. There is a great number of "QAQ" in the string (Diamond is so cute!).

Bort wants to know how many subsequences "QAQ" are in the string Diamond has given. Note that the letters "QAQ" don't have to be consecutive, but the order of letters should be exact.

Input
The only line contains a string of length n (1 ≤ n ≤ 100). It's guaranteed that the string only contains uppercase English letters.

Output
Print a single integer — the number of subsequences "QAQ" in the string.

Examples
input
QAQAQYSYIOIWIN
output
4
input
QAQQQZZYNOIWIN
output
3
Note
In the first example there are 4 subsequences "QAQ": "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN".

This is similar to the previois.The only thing different is choose a neighboring char is allowed here.So we just correct a number then we can solve this problem.

Code:

#include<bits/stdc++.h>
using namespace std;
string s;
long long ans;
int main()
{
    cin>>s;
    int l=s.size();
    for(int i=0;i<l;i++)
    {
        if(s[i]=='A')
        {
            int a=0;
            int b=0;
            for(int j=i-2;j>=0;j--)
            {
                if(s[j]=='Q')
                    a++;
            }
            for(int k=i+2;k<l;k++)
            {
                if(s[k]=='Q')
                    b++;
            }
            ans+=a*b;
        }
    }
    cout<<ans<<endl;
    return 0;
}

You can find the difference between these two codes which is better for you to understand this series of questions.

The most exciting thing I want to say is

1. 我中奖啦
2. I got the prize
3. Gané el premio.
4. Ek het die prys gewen.
5. Kam fituar çmimin.
6. ሽልማቱን አሸንፌያለሁ.
7. Ես հաղթել եմ մրցանակին:
8. Mükafatı qazandım.
9. Saria irabazi nuen.
10. Я выйграў латарэю сяброў
    ......

After nearly half a year of competition on the nowcoder.Participated in 18 games,I won the price at last.Congratulations!

Show off