AcWing 1884. 记忆化搜索
原题链接
简单
作者:
cyzh
,
2022-01-21 21:04:45
,
所有人可见
,
阅读 2077
记忆化搜索
- 输入字符串
- 从前往后遍历
- 如果遍历到‘O’,它只会与前面的‘C’组成”CO“,所以不需要管后面的‘C’的数量
- 同理如果遍历到‘W’,它只会与前面的‘CO’组成”COW“,所以不需要管后面的‘CO’的数量
- 记录当前‘C’,“CO”,“COW”的个数
时间复杂度O(N)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; string s;
cin >> n >> s;
long long c = 0, o = 0, w = 0;//分别代表C,CO,COW的数量
for(auto ch : s){
if(ch == 'C') c++;
else if(ch == 'O') o += c;
else w += o;
}
cout << w;
return 0;
}
位运算
#include<bits/stdc++.h>
using namespace std;
long long n, c, o, w;
string s;
int main(){
cin >> n >> s;
for(auto ch : s) c += !(ch ^ 0x43), o += c * !(ch ^ 0x4f), w += o * !(ch ^ 0x57);
cout << w;
return 0;
}
大佬
o += c * !(ch ^ 0x4f) 这个*有啥作用呢
乘法
厉害了
大佬膜拜
妙啊~大佬
大佬Orz
大佬Orz
%%%
厉害厉害关注了哈哈
位运算看不懂 QAQ
‘C’ 是 0x43
‘O’ 是 0x4f
‘W’ 是 0x57
谢谢大佬
哇 位运算好妙,学到了!
妙啊 tql
帥 !
补充一份py代码(膜拜楼主orz)
妙啊~大佬
你也可以(dog)