AcWing 4960. 子串简写

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 4960. 子串简写原题链接简单

作者：

yxc的小迷妹 , 2023-04-15 19:59:31 , 所有人可见 , 阅读 3468

37

5

二分/双指针都行
先按照位置处理出来两个数组
然后枚举开头的位置，二分出结尾在另一个数组的合法位置，直接累加答案

#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;
}

13 评论

hugeYlh 2023-05-18 15:20

都用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;
    }

siyuehuaichun 2023-11-01 18:39

lower_bound时间复杂度我查了下是log n, 有可能超时吧

siyuehuaichun 2023-11-01 19:03

hh, 在acwing 里没有超时qaq刚刚试过了

siyuehuaichun 2023-11-01 19:04 回复了 siyuehuaichun 的评论

#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;

}

jrpajkyzwkycg 8个月前

#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啊

SDkfw181 10个月前

刚开始想到二分+离散化+前缀和，想了半天咋离散化。结果发现，只需c2的位置记成一个数组，数组的下标就是前缀和+离散化的结果。跟大佬的差不多了

Kingah 2023-05-03 17:23

用二分卡时间卡的好极限，我把二分写在main里就ac了qwq

Kingah 2023-05-03 17:05

#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;

}