Acwing第 45 场周赛总结（未完结）

这周第一题感觉还行，没那么难。

第二题. AcWing 4394. 最长连续子序列

贴图方便理解

先说一下这一题，这一题跟算法基础课里的799. 最长连续不重复子序列类似，799里的题目是给一个数组，求里面一个区间，这个区间里面不包含任何相同字符，而这题则是包含的不同数量小等于于k，思路基本类似。

因此推荐双指针方法，但双指针有个前提为：两个指针是单调的。

指针单调的解释，比如说右指针往后走的时候，左指针单调往后走或者单调往前走。

这种被称为两个指针具有单调性。

判断题目指针是否具有单调性，我们先定义两个指针j，i，其中j为最靠左的指针，使得j到i之间包含不同字符数量小等于k，现在我们考虑一下i往后走的时候，比如说i走到i1的时候，i1所对应的j1是否在j的前面呢？如果没可能的话，那表示i往后走的时候，j也一定往后走，那么表示两个指针单调。

我们也可以用一下反证法，比如说假设i1对应的j1在j的前面，这样我们就会发现从j1到i1这个区间包含的不同字符数量就是小等于k的，所以从j1到i包含的不同字符数量一定也小等于k。

我们知道如果一个区间的数量小等于k，那么这个区间的子区间一定也小等于k。

所以那对于i来说，满足要求的区间也应该在j1，而不应该在j，所以矛盾

所以我们可以发现，当i往后走的时候，j也是单调往后走的，所以这题可用双指针来做。

最后问题就来到了，我们该怎么快速求出这个滑动窗口中有多少个不同的元素

所以我们就需要一个数据结构来实现可以从中加一个数和删一个数，然后维护这个集合里不同数的数量。

这里的话选用数组，不用队列（队列无法判重）其实这里数组的作用也就相当于一个哈希表

下面看代码实现吧

#include 
#include 
#include 

using namespace std;

const int N = 500010, M = 1000010;//题目数据

int n, m;
int w[N], cnt[M];//定义所有数数值，开一个哈希数组

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);//读入所有数

    int res = 0, l, r;//res答案表示最长区间长度，l，r表示对应答案的左右端点
    for (int i = 1, j = 1, t = 0; i <= n; i ++ )
    {//t表示当前区间里不同数的个数
        if (cnt[w[i]] == 0) t ++ ;
        cnt[w[i]] ++ ;//如果cnt[w[i]] == 0，则表示区间里多了一个数

        while(t>m)//删去区间一个数
        {
            if (cnt[w[j]] == 1) t -- ;//判断如果cnt[w[j]] == 1，则此元素为独苗
            cnt[w[j]] -- ;//那么删去之后这个数就没有了，故t--，j++
            j ++ ;
        }

        if (i - j + 1 >res)//i-j+1为区间长度
        {
            res = i - j + 1;
            l = j, r = i;
        }
    }

    printf("%d %d\n", l, r);
    return 0;
}

 第三题还是能力之外，我好没用~~

总结：这次的第二题感觉写了这么多感觉还是一知半解，思路是懂了一些，但还是没办法自己实现，现就暂时放着，之后一定会回来再看看的！！！