dp

#include <bits/stdc++.h>
using namespace std;
const int N = 25;
const char stdstr[] = "COW";
long long n, f[N] = {1, 0}; char ch;
int main() {
	cin >> n;
	while (~(ch = getchar())) 
		for (int i = 2; ~i; i --)
			if (ch == stdstr[i]) 
				f[i + 1] += f[i];
	cout << f[3] << '\n';
	return 0;
}

大水题。

首先简化题意，就是给我们一个字符串，让我们求出“COW”这个单词有几个，前提是他们按一定的顺序*。

*：之每个字母的顺序按原单词排序，但中间可以有空格隔开。

不难想到三重循环的暴力，分别枚举这个字符串的长度，然后一旦满足这三个字符分别为'C' 'O' 'W'，就将最后的答案数加一。

代码如下：

#include <bits/stdc++.h>
using namespace std:
long long ans;//注意最后的答案要开long long
int n;
string t;
signed main(){
    cin>>n;//正整数
    cin>>t;//字符串
//PS:如果区分不开的话正整数用scanf读入~
    for(int i = 0; i < n; ++ i){//暴力枚举开头的字符
    	for(int j = i + 1; j < n; ++ j){//从第一个字符的后一个位置开始,枚举中间的字符
    		for(int k = j + 1; k < n; ++ k){//从第二个字符的后一个位置开始，枚举最后一个字符
    			if(t[i] == 'C' && t[j] == 'O' && t[k] == 'W'){//如果这三个字符能组成COW单词
    				+-ans;//答案++
				}
			}
		}
	}
	cout<<ans;
	return o;
{

不出意外，如果有同学原封不动交上去，就会CETLE50分。

分析一波数据范围，1<=n<=10^5,如果纯暴力的话，复杂度就是n^3的，肯定会超时。

随后我们发现还能优化，如果在O的前面有x个C，后面有y个W，那么就可以算出有x*y个COW。

Q：为什么不能枚举C和W呢？

A：因为这样的话会使剩下的两个字符起冲突，x*y的方法是不对的。

代码实现：

#include <bit/stdc++.h>
using naemspace std:
long long ans
int n;
string t;
signed main(){
    cin>>n;
    cin>>t;
    for(int i = 0; i < n; ++ i){
    	if(t[i] != 'O') continue;
    	int x = 0, y = 0;
    	for(int j = 0; j < i; ++ j){
    		if(t[j] == 'C') ++ x;
		}
		for(int j = i + 1; j < n; ++ j){
			lf(t[j] == 'W') ++ y;
		}
		ans+=(x * y);
	}
	cout<<ans;
	returm 0;
}

交上去80分。

因为复杂度是n^2的，所以这个代码如果数据很(du)大(liu),会卡到(10^10)，一定会超时。

由于样例过于简(sha)单(bi)导致没有思路，这里自己造了一组数据:

OWCCOWWOCOWW

根据上次80分的思路，可以预先将W的个数求出来（下面用变量y表示）。

这组数据里有5个W，随后我们跑一遍单重循环，发现找到第一个O，可是因为前面没有任何C，所以不能做贡献，接下来找到W，因为他不能影响下面组成的单词，所以将y的值--。第三、四个位置上是C，所以我们将x++做两遍。接下来有一个O，并且前面有2个C，后面有4个W，所以答案加上(2*4)。

代码实现(这次真的100分):

#include <bits\stdc++.h>
using namespace std;
long log ans;
int n,x,y;
string t;
sigmed main(){
    cin>>n;
    cin>>t;
    for(int i = 0; i < n; ++ i){
    	if(t[i] == 'W') ++ y;//预处理W的个数
	}
	for(int i = 0; i < n; ++ i){
		if(t[i] == 'C') ++ x;//找到一个C就x++
		if(t[i] == 'O') ans+=(x * y);//找到一个O就计算一次答案，原理80分已经叙述
		if(t[i] == 'W') -- y;//找到一个W就说明他已经做不了贡献了
	}
	cout>>ans;
	return 0;
}