「ULSG-1」数字生命 题解

题目传送门

题目描述

给定一段长度为 \(n\) 的序列，找出其中长度为 \(m\) 的一段子序列，且其中各数字出现次数与给定模板中相对应的次数不相同的数字等于 \(k\)。

题目解法

容易联想到一个用于求固定长度区间最大值的 \(O(n)\) 算法——「滑动窗口」，此题可借鉴此算法。

我们以此题的样例#2进行说明

10 4 2
4 1 4 1 4 4 1 2 2 3
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0

首先创建一个长度为 \(m\) ，包含了序列上 \([1,m]\) 的窗口，易得其各数字出现次数，

[4 1 4 1] 4 4 1 2 2 3
2 0 0 2 0 0 ......

接着定义两个指针 \(l=1,r=m\)，在判断条件为 \(r<=n\) 的循环中每次右移指针 \(l,r\)，同时将移除的数字对应次数 - 1，新增的数字对应次数 + 1，例当 \(l=3\) 时，

4 1 [4 1 4 4] 1 2 2 3
1 0 0 3 0 0 ......

同时每次将该区间各数字出现次数与模板比较，若不同处数量等于 \(k\)，则判定此区间合法，答案 + 1。

综上，一个复杂度为 \(O(n)\) 的算法完成，同时，因为我们从1开始扫描，因此也满足按 \(l\) 从小到大输出答案的要求。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=6e6+2;

int n,m,k;
int a[N];
int b[17];
int cnt[17];

vector < pair<int,int> > ans;

int main()
{
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=16;i++)
	{
		scanf("%d",&b[i]);
	}
	int l=1,r=m;
	for(int i=l;i<=r;i++) 
	{
		cnt[a[i]]++;
	}
	while(r<=n)
	{
		int insame=0;
		for(int j=1;j<=16;j++)
		{
			if(cnt[j]!=b[j]) insame++;
		}
		if(insame==k) ans.push_back({l,r});
		
		l++,r++;
		cnt[a[l-1]]--;
		cnt[a[r]]++;
	}
	printf("%d\n",ans.size());
	for(int i=0;i<ans.size();i++)
	{
		printf("%d %d\n",ans[i].first,ans[i].second);
	}
	return 0;
}