UVA1608 不无聊的序列 Non-boring sequences

标签：Non return int boring UVA1608 -- solve 序列 include

https://www.luogu.com.cn/problem/UVA1608

如果一个序列的任意连续子序列都至少有一个元素唯一，则称这个序列“不无聊”，否则称这个序列“无聊”。给定T个序列，求是否“无聊”。

 

思路：

 

如何方便地找一个区间内只出现过一次的元素? 比较困难,因为区间太多.

如何方便的判断一个元素在一个区间内是否只出现过一次?

记录一下当前序列中的元素$a[i]$的上一个值为$a[i]$的位置,下一个值为$a[i]$的位置,如果他们的位置分别小于$l$,$r$.就说明当前区间$[l,r]$中,a[i]只出现过一次 用last数组和next数组分别存储i号元素的前面与$a[i]$相同的元素的下标和后面与$a[i]$相同的元素的下标 具体处理方法用map配合

		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			if(m.find(a[i])==m.end())
			{
				last[i]=-1;
				m[a[i]]=i;
			}
			else
			{
				last[i]=m[a[i]];
				m[a[i]]=i;
			}
		}
		m.clear();
		for(int i=n;i>=1;i--)
		{
			if(m.find(a[i])==m.end())
			{
				nex[i]=INF;
				m[a[i]]=i;
			}
			else
			{
				nex[i]=m[a[i]];
				m[a[i]]=i;
			}		
		}

AC代码

#include<stdio.h>
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
int n;
const int N=1e5+10;
const int INF=2147483647;
int a[N];
map<int,int> m;
int last[N],nex[N];
int T;
int solve(int l,int r)
{
	if(l>=r)return 1;
	int x=l,y=r;
	while(x<=y)
	{
		if(last[x]<l&&nex[x]>r)
		{
			return solve(l,x-1)&&solve(x+1,r);
		}
		
		if(last[y]<l&&nex[y]>r)
		{
			return solve(l,y-1)&&solve(y+1,r);
		}
		x++,y--;
	}
	return 0;
}
int main()
{
	//freopen("uva.txt","r",stdin);
	scanf("%d",&T);
	while(T--)
	{
		m.clear();
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			if(m.find(a[i])==m.end())
			{
				last[i]=-1;
				m[a[i]]=i;
			}
			else
			{
				last[i]=m[a[i]];
				m[a[i]]=i;
			}
		}
		m.clear();
		for(int i=n;i>=1;i--)
		{
			if(m.find(a[i])==m.end())
			{
				nex[i]=INF;
				m[a[i]]=i;
			}
			else
			{
				nex[i]=m[a[i]];
				m[a[i]]=i;
			}		
		}
		if(solve(1,n))
		{
			printf("non-boring\n");
		}
		else printf("boring\n");		
	}

	
	return 0;
}

这是从两边向中间靠的方法,耗时120ms
然而如果改成从中间向两边靠,耗时960ms,这是为什么?

int solve(int l,int r)
{
	if(l>=r)return 1;
	int x=l+r>>1;
	int y=l+r>>1;
	while(x>=l||y<=r)
	{
		if(x>=l&&last[x]<l&&nex[x]>r)
		{
			return solve(l,x-1)&&solve(x+1,r);
		}
		
		if(y<=r&&last[y]<l&&nex[y]>r)
		{
			return solve(l,y-1)&&solve(y+1,r);
		}
		x--,y++;
	}
	return 0;
}

标签：Non,return,int,boring,UVA1608,--,solve,序列,include
From： https://www.cnblogs.com/oijueshi/p/16591250.html