小地方网站建设公司,简单的小程序开发,开封网站建设优化,东莞网站推广的公司思路#xff1a; 这道题是常规的模拟题#xff0c;根据题意写出相关代码即可。模拟题一般容易在边界条件上出错#xff0c;建议自己设计几个样例测试一下。这题纯暴力的方法不能通过所有的测试点#xff0c;对于最后的查询#xff0c;应该使用二分查找#xff0c;这样算法…思路 这道题是常规的模拟题根据题意写出相关代码即可。模拟题一般容易在边界条件上出错建议自己设计几个样例测试一下。这题纯暴力的方法不能通过所有的测试点对于最后的查询应该使用二分查找这样算法的整体复杂度是O(nlogn)
参考代码
#includebits/stdc.h
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
string s;
int k, len;
vectorint alice, bob; //用于记录两个单词成功出现在文本中时的首字母位置 bool if_letter(char c) //判断是不是字母
{if(c A c Z || c a c z)return true;elsereturn false;
}bool if_alice(int index) //判断当前位置是不是单词Alice的起始位置
{string tmp Alice;for(int i 0; i 5; i){if(tmp[i] ! s[indexi])return false;}if(index 0 if_letter(s[index-1]))return false;if(index5 len if_letter(s[index5]))return false;return true;
}bool if_bob(int index) //判断当前位置是不是单词Bob的起始位置
{string tmp Bob;for(int i 0; i 3; i){if(tmp[i] ! s[indexi])return false;}if(index 0 if_letter(s[index-1]))return false;if(index3 len if_letter(s[index3]))return false;return true;
}int main()
{ios::sync_with_stdio(false);cin k;cin.get(); //读取换行符 getline(cin, s); //读取整个字符串使用cin无法读取含空格的字符串 len s.size();for(int i 0; i len-5; i){if(if_alice(i)){alice.push_back(i);i 5;}}for(int i 0; i len-3; i){if(if_bob(i)){bob.push_back(i);i 3;}}ll cnt 0; for(int i 0; i alice.size(); i) {int t alice[i];//二分查找第一个满足条件的Bob位置 int start lower_bound(bob.begin(), bob.end(), t-k-3) - bob.begin(); //二分查找最后一个满足条件的Bob位置 int end lower_bound(bob.begin(), bob.end(), tk5) - bob.begin();cnt end - start;}cout cnt;return 0;
}
