课程安排
题目链接：
题目描述
传智播客的课表上按顺序提供 $n$ 节课程，课程可能是 Java、Python 或者前端开发等等，我们用不超过 $n$ 的正数代表每一节课程的种类。学员可以从这个课程序列选取连续的一小段的课程序列，作为一周的学习任务。
为了使学习任务不那么枯燥，学员不想连续上两节相同的课。特殊的，这一周学习任务的开头和结尾也不能是相同的课。为了保证学习效果，一周内至少要学完 $l$ 节课程。
请问，我们有多少种合法的选课方案？
两种选课方案，只要选取的课程序列在原序列的开头和结尾有至少一个位置不一致，那么就可以认为是不同的选课方案。注意，即使 $l$ 是 1，一周只安排一次课也是不合法的，至少需要安排 2 次课。
输入格式
每个测试点由多组数据组成。
第一行为一个整数 $T$，代表数据的组数。
对于每组数据，第一行输入两个正整数 $n$ 和 $l$。接下来一行输入 $n$ 个非负整数 $c_i$ 表示课程种类编号。
输出格式
对于每组数据，输出一行一个数，表示方案数。
样例 #1
样例输入 #1
1 | |
样例输出 #1
1 | |
提示
样例解释
对于第一组数据，有 [1,2] 和 [2,3] 和 [1,2,3] 三种方法。
对于第二组数据，由于至少要选 3 门课，只有 [1,2,3] 和 [2,3,1] 两种方法。
数据范围
测试数据不超过 5 组，$1\le N \le 5 \times 10^5$，$1\le l,c_i \le N$
题解
以下 l 均为左指针，k为题目中说的 l ，及课程长度。
本人错误写法1：
枚举左端点 l ，双指针找出最后一个 r ，满足 [ l , r ] 中没有两个连续的相同课的位置且 $C_r$ 不等与 $C_l$。显然这样是错的。例如 [ 1 , 2 , 3 , 1 , 2 ] 会在 r=4 结束而不会往后。
本人错误写法2：
枚举左端点 l ，双指针找出最后一个 r ，满足 [ l , r ] 中没有两个连续的相同课的位置，在这期间统计与 $C_l$ 相等且被课程数量满足题目要求数量的个数，在最后统计时减去。这样做如果 r 不重新回到 l 开始统计会导致后面在计数是漏掉一部分情况，例如 [ 1 , 2 , 3 , 2 , 1 , 1 ] 时无法正确计算前指针为 2 的个数，会漏掉。但是如果将 r 重新回到 l 开始计数会导致超时的问题。
正解：
枚举左端点 l ，双指针找出最后一个 r ，满足 [ l , r ] 中没有两个连续的相同课的位置。额外开一个数组 a ，记录下长度满足条件后的所有的课程数目。
例如上面的图片，我们扫完第一遍后得出 a 的数组如下，当 l 向后移动一位时 l + k -1 不在我们需要特殊判断的头尾是否相等的范围内，所以在做完时只需将 a [ l + k - 1 ] - 1 即可。
完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
typedef long long ll;
int c[500005] = {0};
int a[500005] = {0};
void solve()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> c[i];
}
k = max(2, k);
ll sum = 0;
int l = 1, r = l;
while (l <= n)
{
r = max(l, r);
while (c[r + 1] != c[r] && r < n)
{
r++;
if (r - l + 1 >= k)
{
a[c[r]]++;
}
}
if (r - l + 1 >= k)
{
sum = sum + r - l + 1 - k + 1 - a[c[l]];
a[c[l + k - 1]]--;
}
l++;
}
cout << sum << endl;
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}