AcWing 3358. 放养但没有完全放养
原题链接
简单
作者:
H.A.H.
,
2022-03-23 19:04:06
,
所有人可见
,
阅读 252
$\Huge\color{green}{春季每日一题2022题解集合}$
分析
看见题目不要懵逼!仔细的思考一下,就会发现这题很氵
其实算最小的遍数,
只要判断 $st[i]$ 下一个字符$st[i+1]$在牛文字母歌中的下标是否小于等于 $st[i]$ 在牛文字母歌中的下标就行了
如果小于或等于,就 $ans++$ ,说明Bessie已经又开始了新的一遍
因为牛文字母歌中的字母不会重复
我可能描述的不太清
举个栗子吧
就拿样例来说
(第一个字母就不考虑了),第二个字母 $o$ ,比第一个字母 $m$ 在牛文字母歌中的下标大,所以在第一首字母歌中
第三个字母也是 $o$ ,与第二个字母 $o$ 在牛文字母歌中的下标相同,说明Bessie已经又开始了新的一遍字母歌
后面就不分析了,我太懒了
代码仅供参考
#include<bits/stdc++.h>
using namespace std;
char chi[1008611];
int main(){
int sum=1; //从1开始,因为Bessie不会唱0遍……
string st;
for(int k=1;k<=26;k++) cin>>chi[k];
cin>>st;
int x,y;
for(int i=0;i<st.size();i++){
for(int k=1;k<=26;k++){
if(chi[k]==st[i]) x=k; //记录st[i]在牛文字母歌中的下标
if(chi[k]==st[i-1]) y=k; //记录st[i+1]在牛文字母歌中的下标
}
if(x<=y) sum++; //比较大小,小于等于就ans++(我用的sum……)
}
cout<<sum;
return 0;
}