uva1608(Non-boring sequences)

题意:如果1个序列的任意连续子序列中最少有1个只出现1次的元素,则称这个序列是不无聊的。判断1个长度为n(n<=200000)的序列是否是无聊的。


解法:弄个map记录每一个数前1个数的位置,判断以每一个数结尾的所有区间是不是合法,其中用到线段树访问区间最小值。


代码:

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e⑻
#define zero(_) (abs(_)<=eps)
const double pi=acos(⑴.0);
typedef long long LL;
const int Max=200010;
const LL INF=0x3FFFFFFF;
int n;
int num[Max];
int pre[Max];
map<int,int> maps;
struct node
{
int l,r;
node* left,* right;
int ma;
} nodes[Max*3];
int tot=0;
void build(node* p,int l,int r)
{
p->l=l;
p->r=r;
p->ma=INF;
if(l==r)
return ;
int middle=(l+r)>>1;

tot++;
p->left=nodes+tot;
build(p->left,l,middle);

tot++;
p->right=nodes+tot;
build(p->right,middle+1,r);
}
void down(node* p)
{
p->ma=min(p->left->ma,p->right->ma);
}
void update(node* p,int index,int value)
{
if(p->l==p->r&&p->l==index)
{
p->ma=value;
return ;
}
int middle=(p->l+p->r)>>1;
if(index<=middle)
update(p->left,index,value);
else
update(p->right,index,value);
down(p);
}
int query(node* p,int l,int r)
{
if(p->l==l&&p->r==r)
return p->ma;
int middle=(p->r+p->l)>>1;
if(r<=middle)
return query(p->left,l,r);
else if(l>middle)
return query(p->right,l,r);
else
return min(query(p->left,l,middle),query(p->right,middle+1,r));
}
int main()
{
int t;
scanf("%d",&t);
while(t–)
{
tot=0;
maps.clear();
scanf("%d",&n);
build(nodes,1,n);
for(int i=1; i<=n; i++)
scanf("%d",num+i);
reverse(num+1,num+n+1);
for(int i=1; i<=n; i++)
pre[i]=maps[num[i]],maps[num[i]]=i;
bool flag=0;
for(int i=1; i<=n; i++)
{
if(pre[i]!=0)
update(nodes,pre[i],pre[i]);
int left=pre[i],right=i;
while(left>0)
{
int pr;
if(left+1<=right⑴)
pr=query(nodes,left+1,right⑴);
if(left+1>right⑴||pr>=left)
{
flag=1;
break;
}
right=left;
left=pr;
}
if(flag)
break;
update(nodes,i,pre[i]);
}
if(flag)
puts("boring");
else
puts("non-boring");
}
return 0;
}
/*
ababababa
*/

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » uva1608(Non-boring sequences)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡