紫书例题8-15 UVa 12174 （滑动窗口）

这道题就是给你一n长序列，然后把这个序列按顺序分成很多段，每段长s（最前面可以小于s，只有第一段的后半段，最后面也同样，只有最后一段的前半段），然后要求是每一段里面没有重复的数，问你有几种分法

实际上看到连续s个数，就可以想到滑动窗口，可以提前初始化所给序列的每一段里面有没有重复的数，然后再枚举第一段的终点，然后一段一段去判断是否全部都没有重复的数字，如果所有段都是的话，那么就符合题目要求， ans++

有两个地方要注意

（1）初始化的问题。这个思路有点像扫描法， 判断每一段的时候，不用从新开始，而是从相邻左边的那一段，把最前面的数字减去和新加的数字加进来就可以了，利用好前面得出的结果。我一开始每一段都重新算，然后就超时了

（2）不是完整的段的问题。如果是最前面的那一段，那么只算序列里面的那一段，然后最后面的那一段也是只算序列里面的那一段，所以要特别注意，结尾可以到n + s - 1，同时保存这个数组空间就要翻倍了。

#include<cstdio>

#include<cstring>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112345;

int a[MAXN], vis[MAXN], n, s;

bool k[MAXN<<1];  //翻倍 

void init()

{

	int cnt = 0;  //重复数字的个数

	memset(k, false, sizeof(k));

	memset(vis, 0, sizeof(vis));

	vis[a[0]]++;

	REP(i, 0, n + s)  //一定是n+s

	{

		k[i] = (cnt == 0);

		if(i + 1 < n && ++vis[a[i+1]] == 2) cnt++;  //注意这里一定是==2， 因为这代表从1到2， 而不是 > 1

		if(i - s + 1>= 0 && --vis[a[i-s+1]] == 1) cnt--; //同上， 代表从2到1。

	}

}

bool judge(int end)

{

	while(1)

	{

		if(!k[end]) return false;

		if(end >= n) return true; //如果到最后的那一段都符合的话， 那就这种情况符合要求

		end += s;

	}

}

int main()

{

	int T;

	scanf("%d", &T);

	while(T--)

	{

		scanf("%d%d", &s, &n);

		REP(i, 0, n) scanf("%d", &a[i]);

		init();

		int ans = 0;

		REP(i, 0, s) ans += judge(i);

		printf("%d\n", ans);

	}

	return 0;

}

巴特西

紫书例题8-15 UVa 12174 （滑动窗口）

最新文章

热门文章

巴特西

紫书 例题8-15 UVa 12174 （滑动窗口）

最新文章

热门文章

紫书例题8-15 UVa 12174 （滑动窗口）