【BZOJ2083】[Poi2010]Intelligence test 二分
2024-08-30 01:49:21
【BZOJ2083】[Poi2010]Intelligence test
Description
霸中智力测试机构的一项工作就是按照一定的规则删除一个序列的数字,得到一个确定的数列。Lyx很渴望成为霸中智力测试机构的主管,但是他在这个工作上做的并不好,俗话说熟能生巧,他打算做很多练习,所以他希望你写一个程序来快速判断他的答案是否正确。
Input
第一行为一个整数m(1<=m<=1000000)第二行包括m个用空格分开的整数ai(1<=ai<=1000000),组成了最初的序列,第三行为一个整数n(1<=n<=1000000),表示n个Lyx经过一系列删除得到的序列,每个序列两行,第一行给出长度L(1<=L<=m),然后下一行为L个由空格分开的整数bi(1<=bi<=1000000)。
Output
共n行,如果Lyx的序列确实是由最初的序列删除一些数得到,就输出TAK,否则输出NIE。
Sample Input
7
1 5 4 5 7 8 6
4
5
1 5 5 8 6
3
2 2 2
3
5 7 8
4
1 5 7 4
1 5 4 5 7 8 6
4
5
1 5 5 8 6
3
2 2 2
3
5 7 8
4
1 5 7 4
Sample Output
TAK
NIE
TAK
NIE
NIE
TAK
NIE
题解:用vector维护每个数出现的所有位置,然后查询时在vector上二分即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int maxn=1000010;
int n,m,len;
vector<int> v[maxn];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
m=rd();
int i,j,a,last,l,r,mid;
for(i=1;i<=m;i++) a=rd(),v[a].push_back(i);
n=rd();
for(i=1;i<=n;i++)
{
len=rd(),last=0;
for(j=1;j<=len;j++)
{
a=rd();
if(last==-1) continue;
l=0,r=v[a].size();
while(l<r)
{
mid=l+r>>1;
if(v[a][mid]>last) r=mid;
else l=mid+1;
}
if(r==v[a].size()) last=-1;
else last=v[a][r];
}
if(last==-1) printf("NIE\n");
else printf("TAK\n");
}
return 0;
}
最新文章
- TBitmapSurface.StretchFrom
- 安装Visual Studio的插件AnkhSvn
- 【krpano】krpano xml资源解密(破解)软件说明与下载
- 快速入门系列--WebAPI--03框架你值得拥有
- iOS开发Swift篇—(十)方法
- (转)mvc Area相关技术
- CSS居中的实现用法实例
- Content Providers的步骤,来自官网文档
- 使用iftop网络流量监控
- script defer和async一探
- HashSet TreeSet 源码
- Unity3d导出场景地图寻路
- Leetcode_9_Palindrome Number
- note10 元组
- python下载安装BeautifulSoup库
- 2.02-request_header_two
- 关于UNITY学习,给新生建议
- Android手机提示&ldquo;未安装应用程序&rdquo;
- 13-[函数进阶]-列表生成式,生成器&;迭代器
- 算法:优先级队列(PriorityQueue)