UVA 1608 Non-boring sequences 分治

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4483
题目大意:给一个数字序列,若该序列的任意一个连续子序列中都有唯一出现的值,那么这个序列是nonboringnon-boringnon−boring的,否则这个序列是boringboringboring的。

思路:分治。若a[i]a[i]a[i]在区间[l,r][l,r][l,r]内只出现了一次,那么任意包含iii的子区间所对应的的序列一定是nonboringnon-boringnon−boring的,此时只需要判断[l,i1][l,i-1][l,i−1]和[i+1,r][i+1,r][i+1,r]是否满足题意。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;

const int maxn=2e5+5;

int t,n;
int a[maxn],nxt[maxn],pre[maxn];
map<int,int> m;

bool dfs(int l,int r)
{
	if(l>=r)
		return true;
	int t1=l,t2=r;
	while(t1<=t2)
	{
		if(pre[t1]<l&&nxt[t1]>r)
			return dfs(l,t1-1)&&dfs(t1+1,r);
		if(pre[t2]<l&&nxt[t2]>r)
			return dfs(l,t2-1)&&dfs(t2+1,r);
		++t1,--t2;
	}
	return false;
}

int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		m.clear();
		for(int i=1;i<=n;i++)
		{
			if(!m.count(a[i]))
				pre[i]=0;
			else
				pre[i]=m[a[i]];
			m[a[i]]=i;
		}
		m.clear();
		for(int i=n;i>=1;i--)
		{
			if(!m.count(a[i]))
				nxt[i]=n+1;
			else
				nxt[i]=m[a[i]];
			m[a[i]]=i;
		}
		if(dfs(1,n))
			printf("non-boring\n");
		else
			printf("boring\n");
	}
}

上一篇:HDU4358 Boring counting【dsu on tree】


下一篇:LeetCode 有趣的电影