[已解决]梦想星际舰队第18关 && FCOI #8 第五题QAQ题解【原创】

zhangjinxuan

梦想星际舰队第18关 && FCOI #8 题解

第五题：QAQ

题目描述
给定由 A, Q 组成的字符串 S，你要统计三元组 (i,j,k) 的个数，满足 1≤i<j<k≤|S|,Si= Q, Sj= A, Sk= Q。

其实上就是要求 S 里面有多少子串为 QAQ。

本题使用多测，一共有 T 个测试用例。

输入格式
第一行一个整数 T。

接下来 T 行，每行一个字符串 S，表示一个测试用例。

输出格式
T 行，每行一个整数表示对应测试用例的答案。

输入输出样例
输入 #1

1. 6
   
2. QAQQ
   
3. QAAQQ
   
4. QQQ
   
5. QQAQAAQ
   
6. AAAQQQAAAQQQAAA
   
7. QQAQAQAQAQAAAQAAQAQAQAQAQAAAQAQQAQ

复制代码

输出 #1

1. 2
   
2. 4
   
3. 0
   
4. 10
   
5. 27
   
6. 916

复制代码

数据范围

对于 100% 的数据，保证 3≤|S|≤5000,1≤T≤1000，S 仅包含 A, Q 两个字符。

其他说明
本题目为 zhangjinxuan 原创题目。
测试链接：https://www.luogu.com.cn/problem/U325168

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳战士排行榜

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳答案

月排行榜 / 总排行榜

Ewan-Ahiouy

2023-8-23 20:21:33

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int t, n, Q[5001], QA[5001], QAQ[5001];
   
5. string s;
   
6. 
   
7. int main() {
   
8.     cin >> t;
   
9.     while (t--) {
   
10.         cin >> s;
    
11.         memset(Q, 0, sizeof(Q));
    
12.         memset(QA, 0, sizeof(QA));
    
13.         memset(QAQ, 0, sizeof(QAQ));
    
14.         for (int i = 0; i < s.size(); i++) {
    
15.             Q[i] = Q[i - 1], QA[i] = QA[i - 1], QAQ[i] = QAQ[i - 1];
    
16.             if (s[i] == 'Q') Q[i]++, QAQ[i] += QA[i - 1], QAQ[i] %= (long long)1e9 + 7;
    
17.             else QA[i] += Q[i - 1], QA[i] %= (long long)1e9 + 7;
    
18.         }
    
19.         cout << QAQ[s.size() - 1] << endl;
    
20.     }
    
21. 
    
22.     return 0;
    
23. }

复制代码

借鉴一下代码

跳转到最佳答案楼层

zhangjinxuan

@sfqxx @Ewan-Ahiouy

isdkz

这个问题可以使用动态规划来解决。我们可以定义一个数组dp，dp[ i]表示以第i个字符结尾的字符串中包含的QAQ的个数。那么我们可以根据前面的状态来计算dp[ i]的值。

具体的算法如下：

1. 遍历字符串S，初始化一个长度为|S|的数组dp，初始值都为0。
2. 如果S[ i]等于'Q'，那么dp[ i]等于dp[i-1]，表示以第i个字符结尾的字符串中包含的QAQ的个数不变。
3. 如果S[ i]等于'A'，那么dp[ i]等于dp[i-1]加上以第i-1个字符结尾的字符串中包含的QA的个数。因为我们要找的是以第i个字符结尾的字符串中包含的QAQ的个数，所以我们只需要在以第i-1个字符结尾的字符串中找到以第i-1个字符结尾的字符串中包含的QA的个数即可。
4. 如果S[ i]等于'Q'，那么dp[ i]等于dp[i-1]加上以第i-1个字符结尾的字符串中包含的QAQ的个数。因为我们要找的是以第i个字符结尾的字符串中包含的QAQ的个数，所以我们只需要在以第i-1个字符结尾的字符串中找到以第i-1个字符结尾的字符串中包含的QAQ的个数即可。
5. 遍历完整个字符串S后，dp的最后一个元素就是我们要求的答案。

下面是具体的代码实现：

1. def countQAQ(S):
   
2.     n = len(S)
   
3.     dp = [0] * n
   
4. 
   
5.     for i in range(n):
   
6.         if S[ i] == 'Q':
   
7.             dp[ i] = dp[i-1]
   
8.         elif S[ i] == 'A':
   
9.             dp[ i] = dp[i-1] + dp[i-1]
   
10. 
    
11.     return dp[-1]
    
12. 
    
13. T = int(input())
    
14. for _ in range(T):
    
15.     S = input()
    
16.     print(countQAQ(S))
    

复制代码

这样就可以求解出每个测试用例的答案了。输出的结果与题目给出的输出样例是一致的。

陶远航

题目要求统计给定字符串中有多少个子串是符合特定条件的，即形如 "QAQ" 的子串，其中 Q 代表 'Q' 字符，而 A 代表 'A' 字符。对于每个测试用例，需要输出符合条件的子串个数。

对于这个问题，我们可以使用动态规划来解决。定义一个长度为 n 的数组 dp，其中 dp[i] 表示以第 i 个字符结尾的子串中符合条件的子串数量。

根据题目要求，我们可以得出以下状态转移方程：

如果当前字符是 'A'，则 dp[i] = dp[i-1]，因为 'A' 不能作为结尾，所以以当前字符结尾的子串中符合条件的子串数量与前一个字符结尾的子串中相同。

如果当前字符是 'Q'，则 dp[i] = dp[i-1] + dpQ[i-1]，其中 dpQ[i-1] 表示以第 i 个字符前的所有字符中 'Q' 的个数，这是因为以当前字符结尾的子串中，前面的 'Q' 可以和后面的 'A' 构成符合条件的子串。

初始条件为 dp[0] = 0，表示空字符串不包含符合条件的子串。

下面是对应的 Python 代码实现：

1. def count_QAQ_substrings(s):
   
2.     n = len(s)
   
3.     dp = [0] * n
   
4.     dpQ = [0] * n
   
5.     if s[0] == 'Q':
   
6.         dpQ[0] = 1
   
7.    
   
8.     for i in range(1, n):
   
9.         if s[i] == 'Q':
   
10.             dpQ[i] = dpQ[i-1] + 1
    
11.         else:
    
12.             dpQ[i] = dpQ[i-1]
    
13.             dp[i] = dp[i-1] + dpQ[i-1]
    
14.    
    
15.     return sum(dp)
    
16. 
    
17. # 读入测试用例数量
    
18. T = int(input())
    
19. results = []
    
20. 
    
21. # 逐个处理测试用例
    
22. for _ in range(T):
    
23.     S = input()
    
24.     results.append(count_QAQ_substrings(S))
    
25. 
    
26. # 输出结果
    
27. for res in results:
    
28.     print(res)

复制代码

你可以将上述代码保存到一个 .py 文件中，并在命令行中运行，然后输入测试用例的数量和对应的字符串，最终会输出对应的答案。

陈尚涵

看看

sfqxx

1. t = int(input())
   
2. for _ in range(t):
   
3.     s = input().strip()
   
4.     n = len(s)
   
5.     QAQ = 0
   
6.     for i in range(n):
   
7.         if s[i] == 'Q':
   
8.             for j in range(i + 1, n):
   
9.                 if s[j] == 'A':
   
10.                     for k in range(j + 1, n):
    
11.                         if s[k] == 'Q':
    
12.                             QAQ += 1
    
13.     print(QAQ)

复制代码

要全部过吗？

zhangjinxuan

sfqxx 发表于 2023-8-23 18:34
要全部过吗？

你觉得呢

Ewan-Ahiouy

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int t, p[5010], qnum, alist[5010], qlist[5010], anum, len, qqnum;
   
5. long long ans;
   
6. string s;
   
7. 
   
8. int main() {
   
9.     scanf("%d", &t);
   
10.     while (t--) {
    
11.         ans = 0;
    
12.         qnum = 0;
    
13.         qqnum = 0;
    
14.         anum = 0;
    
15.         cin >> s;
    
16.         len = s.size();
    
17.         for (int i = len - 1, j = 0; i >= 0; i--, j++) {
    
18.             if (s[i] == 'Q') qqnum++;
    
19.             p[i] = qqnum;
    
20.             if (s[j] == 'A') alist[anum++] = j;
    
21.             else qlist[qnum++] = j;
    
22.         }
    
23.         if (qnum == 0 || anum == 0) printf("0\n");
    
24.         else {
    
25.             for (int i = 0; i < qnum; i++)
    
26.                 for (int j = 0; j < anum; j++)
    
27.                     if (qlist[i] < alist[j]) ans += p[alist[j]];
    
28.             printf("%lld\n", ans);
    
29.         }
    
30.     }
    
31. 
    
32.     return 0;
    
33. }

复制代码

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-23 19:29

Ex 得要过

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-23 19:30
Ex 得要过

QAQ

Ewan-Ahiouy

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int t, n, Q[5001], QA[5001], QAQ[5001];
   
5. string s;
   
6. 
   
7. int main() {
   
8.     cin >> t;
   
9.     while (t--) {
   
10.         cin >> s;
    
11.         memset(Q, 0, sizeof(Q));
    
12.         memset(QA, 0, sizeof(QA));
    
13.         memset(QAQ, 0, sizeof(QAQ));
    
14.         for (int i = 0; i < s.size(); i++) {
    
15.             Q[i] = Q[i - 1], QA[i] = QA[i - 1], QAQ[i] = QAQ[i - 1];
    
16.             if (s[i] == 'Q') Q[i]++, QAQ[i] += QA[i - 1], QAQ[i] %= (long long)1e9 + 7;
    
17.             else QA[i] += Q[i - 1], QA[i] %= (long long)1e9 + 7;
    
18.         }
    
19.         cout << QAQ[s.size() - 1] << endl;
    
20.     }
    
21. 
    
22.     return 0;
    
23. }

复制代码

借鉴一下代码