[已解决]梦想星际舰队第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

zhangjinxuan

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

你觉得呢

zhangjinxuan

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

Ex 得要过