冷知识，这题和 KMP 算法有 000 个关系。 注意到 M 只有一个，而一个 KMP 的子序列必须需要一个 M 前面的 K，M，M 之后的 P，所以我们不妨编个样例： KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPPKKRMWYSWDPPHIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP 能够组成的 KMP 子序列有： KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{green}K\color{black}APTAPPKKR\color{red}M\color{black}WYSWD\color{blue}P\color{black}PHIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{green}K\color{black}APTAPPKKR\color{red}M\color{black}WYSWDP\color{blue}P\color{black}HIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{green}K\color{black}APTAPPKKR\color{red}M\color{black}WYSWDPPHIGROSQIDONG\color{blue}PKAPTAPPKKRMWYSWDPPHIGROSQIDONGP KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPP\color{green}K\color{black}KR\color{red}M\color{black}WYSWD\color{blue}P\color{black}PHIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPP\color{green}K\color{black}KR\color{red}M\color{black}WYSWDP\color{blue}P\color{black}HIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPP\color{green}K\color{black}KR\color{red}M\color{black}WYSWDPPHIGROSQIDONG\color{blue}PKAPTAPPKKRMWYSWDPPHIGROSQIDONGP KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPPK\color{green}K\color{black}R\color{red}M\color{black}WYSWD\color{blue}P\color{black}PHIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPPK\color{green}K\color{black}R\color{red}M\color{black}WYSWDP\color{blue}P\color{black}HIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPPK\color{green}K\color{black}R\color{red}M\color{black}WYSWDPPHIGROSQIDONG\color{blue}PKAPTAPPKKRMWYSWDPPHIGROSQIDONGP 可以发现总共子序列数量就是 M 之前的 K 的数量和 M 之后 P 的数量之积。 时间复杂度 O(∣s∣)O(|s|)O(∣s∣)。 好了，你已经学会这一题了，现在来完成这一题吧：三元上升子序列_信奥算法普及+/提高-ACGO题库 hints：树状数组可以当做集合使用，可以以 O(log⁡V)O(\log V)O(logV) 的时间复杂度快速往集合内加入、删除一个不超过 VVV 的元素，查询集合内小于等于某个元素的数量。

#include <iostream> #include <string> using namespace std; int main() { string s; cin >> s; int mid_pos = -1; for (int i = 0; i < s.size(); ++i) { if (s[i] == 'M') { mid_pos = i; break; } } if (mid_pos == -1) { cout << 0 << endl; return 0; } int countK = 0; for (int i = 0; i < mid_pos; i) { if (s[i] == 'K') { countK; } } int countP = 0; for (int i = mid_pos + 1; i < s.size(); i) { if (s[i] == 'P') { countP; } } cout << countK * countP << endl; return 0; }

T5 思路分析 本题主要考察枚举，你先要找到M 的位置 idxidxidx，然后在 idxidxidx 前面去找有多少 K，在 idxidxidx 后面有多少 PPP，最后利用排列组合乘法原理求出答案。 代码分析

这道题似乎是春节巅峰赛第五题的削弱版。 这是我巅峰赛的代码： 稍微改一下就成了这道题的标程：（Code：） 个人认为这是本次欢乐赛最难的一题。 观察后发现，如果把题目降级为统计“KM”出现的次数，那么只需要用前面“K”出现的次数加上后面“M”的次数就是答案。 而如果加上“P”，那么cnt_KMP等于cnt_KM加上“P”出现的次数，如下图：

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

#include <iostream> #include <vector> using namespace std; int main() { string s; cin >> s; int n = s.length(); vector<vector<int>> dp(n + 1, vector<int>(4, 0)); dp[0][0] = 1; }