二分/双指针都行
先按照位置处理出来两个数组
然后枚举开头的位置,二分出结尾在另一个数组的合法位置,直接累加答案
#include<iostream>
#include <vector>
using namespace std;
int k;
char st,ed;
string p;
void solve()
{
cin >> k;
cin >> p >> st >> ed;
vector<int> ps, pe;
for (int i = 0; i < p.size(); i ++)
{
if(p[i] == st) ps.push_back(i);
if(p[i] == ed) pe.push_back(i);
}
long long ans = 0;
for (int i = 0; i < ps.size(); i ++)
{
int x = ps[i];
int X = x + k - 1;
int l = 0, r = pe.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if(pe[mid] >= X) r = mid;
else l = mid + 1;
}
if(pe[l] >= X) ans += pe.size() - l;
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
都用vector了为什么不直接用
lower_bound
?for (auto& x:pbeg){ int y=x+k-1; //最小的 int nums=pend.end()-std::lower_bound(pend.begin(),pend.end(),y); ans+=nums; }
lower_bound时间复杂度我查了下是log n, 有可能超时吧
hh, 在acwing 里没有超时qaq刚刚试过了
#include [HTML_REMOVED]
using namespace std;
typedef long long LL;
typedef pair[HTML_REMOVED] PII;
const int N = 500100;
int k;
string s;
char a, b;
int main()
{
LL ans = 0;
cin >> k >> s >> a >> b;
vector[HTML_REMOVED] st, sw;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == a) st.push_back(i);
if (s[i] == b) sw.push_back(i);
}
for (int i = 0; i < st.size(); i ++) { int j = st[i] + k - 1; int pos = lower_bound(sw.begin(), sw.end(), j) - sw.begin(); if (pos < sw.size()) ans += sw.size() - pos; } cout << ans;
}
#include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N = 5e5 + 10; int n; char str[N]; char a, b; int main() { cin >> n; cin >> str + 1 >> a >> b; queue<int> start; queue<int> end; for(int i = 1; str[i]; i ++ ) { if(str[i] == a) start.push(i); if(str[i] == b) end.push(i); } int res = 0; while(start.size() && end.size()) { while(end.front() - start.front() <= n - 2) end.pop(); res += end.size(); start.pop(); } cout << res << endl; return 0; }
大佬求查,为什么我这个写法会导致segmentation fault啊
刚开始想到二分+离散化+前缀和,想了半天咋离散化。结果发现,只需c2的位置记成一个数组,数组的下标就是前缀和+离散化的结果。跟大佬的差不多了
用二分卡时间卡的好极限,我把二分写在main里就ac了qwq
#include[HTML_REMOVED]
using namespace std;
const int N=5e5+10;
int search(int num,vector[HTML_REMOVED]vt)//在vt中找到第一个大于等于num的数字的下标
{
int l=0,r=vt.size(); if(vt[r-1]<num)return -1; while(l<r) { int mid=l+r>>1; if(vt[mid]>=num)r=mid; else l=mid+1; } return r;
}
int main(void)
{
ios::sync_with_stdio(0);cin.tie(0);
int k; string s; char a,b; cin>>k>>s>>a>>b; vector<int>v1,v2; for(int i=0;i<s.size();i++) { if(s[i]==a) v1.push_back(i); if(s[i]==b) v2.push_back(i); } long long res=0; for(int i=0;i<v1.size();i++) { int c=v1[i]+k-1; int j=search(c,v2); if(j==-1)break; else res+=v2.size()-j; } cout<<res<<endl; return 0;
}
为啥我的二分只能过七个qwq
大佬,请问怎么查看自己通过的测试点数量啊
# 点这里
谢谢啦
那真的是泰库拉!!!