英语作文

英语作文

•  比赛主页
•  我的提交

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

在写英语作文的时候，两个相同单词靠的太近肯定不好。现在 ZHR 给了你一段nn个单词的英文，问你有多少对相同单词中间间隔的单词数小于等于kk 。

第一行两个整数，为nn 和 kk 。

第二行nn个由仅小写字母组成的单词。每个单词长度小于等于1010 。

1le k le n le 10^51≤k≤n≤105。

一行一个正整数，表示有多少对单词中间间隔的单词数小于等于kk 。

示例1

复制

11 2
i love you you love mi mixue ice cream and tea

复制

2

只有 you 和 love 两个单词间隔的单词数小于等于22

示例2

复制

10 2
a a a a a a a a a a

复制

24

#include
#include
#include
#include

using namespace std;

const int mas=1e5+5;
int n,k;
string v[mas];
long long res;
unordered_mapmp;

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        cin>>v[i];
    
    for(int i=1;i<=n;i++)//i对应的是右端点
    {
        if(i-k-1>1)mp[v[i-k-2]]--;
        mp[v[i]]++;
        res+=mp[v[i]]-1;
    }
    cout< 
总结：
 
区间的长度一定，进行空的维护
 
2003. 找到牛！_浅唱，，笑竹神易的博客-CSDN博客
 
这道题相当于是这个的简化版，区间的长度不是固定的，不需要进行删除，只需要进行添加