NC24014. [USACO 2016 Feb B]COW
描述
Bessie the cow has stumbled across an intriguing inscription carved into a large stone in the middle of her favorite grazing field. The text of the inscription appears to be from a cryptic ancient language involving an alphabet with only the three characters C, O, and W. Although Bessie cannot decipher the text, she does appreciate the fact that C, O, and W in sequence forms her favorite word, and she wonders how many times COW appears in the text.
Bessie doesn't mind if there are other characters interspersed within COW, only that the characters appear in the correct order. She also doesn't mind if different occurrences of COW share some letters. For instance, COW appears once in CWOW, twice in CCOW, and eight times in CCOOWW.
Given the text of the inscription, please help Bessie count how many times COW appears.
输入描述
The first line of input consists of a single integer N <= 105. The second line contains of a string of N characters, where each character is either a C, O, or W.
输出描述
Output the number of times COW appears as a subsequence, not necessarily contiguous, of the input string.
Note that the answer can be very large, so make sure to use 64 bit integers ("long long" in C++, "long" in Java) to do your calculations.
示例1
输入:
6 COOWWW
输出:
6
C 解法, 执行用时: 10ms, 内存消耗: 396K, 提交时间: 2021-08-06 23:14:54
#include <stdio.h>
#define ullt unsigned long long int
int main()
{
int n; scanf("%d",&n);
char a[n+1];
for(int i=0;i<n;i++) scanf(" %c",&a[i]);
ullt b1=0,b2=0,sum=0;//C、CO、COW的数目
for(int i=0;i<n;i++)
{
if(a[i]=='C') b1++;
else if(a[i]=='O') b2+=b1;
else sum+=b2;
}
printf("%llu",sum);
return 0;
}
Python3(3.9) 解法, 执行用时: 49ms, 内存消耗: 2992K, 提交时间: 2021-01-02 12:25:06
import sys
if __name__ == "__main__":
n = int(input().strip())
s = str(input().strip())
curC = 0
curP = 0
ans = 0
for c in s:
if c=='C':
curC+=1
elif c=='O':
curP += curC
else:
ans += curP
print( ans)
C++11(clang++ 3.9) 解法, 执行用时: 7ms, 内存消耗: 608K, 提交时间: 2019-08-14 14:24:03
#include<bits/stdc++.h>
using namespace std;
string v;
int main(){
long long n,s=0,t=0,ans=0;
cin>>n;
cin>>v;
for(int i=0;i<v.size();i++){
if(v[i]=='C')t++;
if(v[i]=='O')s+=t;
if(v[i]=='W')ans+=s;
}
cout<<ans<<"\n";
return 0;
}