manbetx官方网站

1893. [国家集训队2011]等差子序列(bitset)1893. [国家集训队2011]等差子序列(bitset),2011bitset

十月 11th, 2018  |  manbet体育登录

★★   输入文件:nt2011_sequence.in  
输出文件:nt2011_sequence.out   简单对比
日子限制:0.3 s   内存限制:512 MB

1893. [国家集训队2011]相当于差子序列(bitset),2011bitset

★★   输入文件:nt2011_sequence.in  
输出文件:nt2011_sequence.out   简单对比
光阴范围:0.3 s   内存限制:512 MB

【试题来源】

2011华夏国集训队命题答辩

【试题来源】

2011神州江山集训队命题答辩

【问题讲述】

被一个1到N的排{Ai},询问是不是有1<=p1<p2<p3<p4<p5<…<pLen<=N(Len>=3),使得Ap1,Ap2,Ap3,…ApLen是一个齐不同排。

【问题讲述】

吃一个1到N底排列{Ai},询问是否在1<=p1<p2<p3<p4<p5<…<pLen<=N(Len>=3),使得Ap1,Ap2,Ap3,…ApLen是一个顶不等排。

【输入格式】

输入的率先实践包含一个平头T,表示组数。
下接T组数据,每组第一推行一个平头N,每组第二表现一个1到N的排列,数字两片里为此空格隔开。

【输入格式】

输入的首先行包含一个整数T,表示组数。
下接T组数据,每组第一实施一个平头N,每组第二作为一个1到N底排,数字两点儿里因此空格隔开。

【输出格式】

对每组数据,如果有一个相当差子序列,则输出一行“Y”,否则输出一行“N”。

【输出格式】

对于每组数据,如果在一个相当于差子序列,则输出一行“Y”,否则输出一行“N”。

【样例输入】

2
3
1 3 2
3
3 2 1

【样例输入】

2
3
1 3 2
3
3 2 1

【样例输出】

N
Y

【样例输出】

N
Y

【数据证实】

对于5%的数据,N<=100
对于30%的数据,N<=1000
对于100%的数据,N<=10000,T<=7
于100%底数据,时间限制为0.3s。

 

 

思路比较好怀念,以一个屡屡为主干,

判定一下者累的相得益彰的两侧,

倘干的勤出现了但别一侧的无起。

这就是说肯定在一个得力方案

但是。

发自己表现不善了,

用bitset超时的题还改化bool类型就A了,。

而还开始着o2优化。。。。

在codevs上bool比bitset快5000+ms。。。。。。。。。。。

附带取一下,

立即道题之正解是线段树/树状数组+hash

 

 

平客不能够A的bitset:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
using namespace std;
using std::bitset;
const int MAXN=10001;
bitset<MAXN>bit;
int a;
inline void read(int &n)
{
    char c='+';int x=0;bool flag=0;
    while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
    while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
    n=flag==1?-x:x;
}
int main()
{
    freopen("nt2011_sequence.in","r",stdin);
    freopen("nt2011_sequence.out","w",stdout);
    int T;
    read(T);
    while(T--)
    {
        bit.reset();
        int n;
        read(n);
        bool flag=0;
        for(int i=1;i<=n;i++)
        {
            read(a);
            if(flag)continue;
            bit.set(a);
            for(int j=a-1;j!=0;j--)
            {
                int k=a*2-j;
                if(k>n)continue;
                if(bit.test(j)^bit.test(k))
                {
                    flag=1;
                    break;
                }
            }
        }
        flag==1?printf("Y\n"):printf("N\n");
    }
    return 0;
}

  

如出一辙份可以A的bitset

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;
const int SIZEN=10010;
int N;
int A[SIZEN];
bitset<SIZEN> pre,suf;
bool test(void){//只能检测递增的
    pre.reset();suf.reset();
    for(int i=1;i<=N;i++) suf[i]=1;
    static bitset<SIZEN> tmp;
    for(int i=1;i<=N;i++){
        suf[A[i]]=0;
        if(i>1) pre[N+1-A[i-1]]=1;
        tmp=(suf>>A[i])&(pre>>(N+1-A[i]));
        if(tmp.any()) return true;
    }
    return false;
}
void work(void){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&A[i]);
    if(test()){
        printf("Y\n");
        return;
    }
    reverse(A+1,A+1+N);
    if(test()){
        printf("Y\n");
        return;
    }
    printf("N\n");
}
int main(){
    freopen("nt2011_sequence.in","r",stdin);
    freopen("nt2011_sequence.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--) work();
    return 0;
}

 

如出一辙卖可以A的bool

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
using namespace std;
using std::bitset;
const int MAXN=10001;
bool bit[MAXN];
int a;
inline void read(int &n)
{
    char c='+';int x=0;bool flag=0;
    while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
    while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
    n=flag==1?-x:x;
}
int main()
{
    freopen("nt2011_sequence.in","r",stdin);
    freopen("nt2011_sequence.out","w",stdout);
    int T;
    read(T);
    while(T--)
    {
        memset(bit,0,sizeof(bit));
        //bit.reset();
        int n;
        read(n);
        bool flag=0;
        for(int i=1;i<=n;i++)
        {
            read(a);
            if(flag)continue;
            bit[a]=1;
            for(int j=a-1;j!=0;j--)
            {
                int k=a*2-j;
                if(k>n)continue;
                if(bit[j]^bit[k])
                {
                    flag=1;
                    break;
                }
            }
        }
        flag==1?printf("Y\n"):printf("N\n");
    }
    return 0;
}

  

【数据说明】

对于5%的数据,N<=100
对于30%的数据,N<=1000
对于100%的数据,N<=10000,T<=7
对100%底多少,时间范围也0.3s。     思路比较好纪念,以一个数也主导,
判断一下之累的对称的两侧, 如果一侧的勤起了而别一侧的从未有过出现。
那么得是一个可行方案 但是。 感觉好表现不善了,
用bitset超时之写还改化bool类型就A了,。 而且还开在o2优化。。。。
在codevs上bool比bitset快5000+ms。。。。。。。。。。。 顺就领一下,
这道题之正解是线段树/树状数组+hash     一客不能够A的bitset:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
using namespace std;
using std::bitset;
const int MAXN=10001;
bitset<MAXN>bit;
int a;
inline void read(int &n)
{
 char c='+';int x=0;bool flag=0;
 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
 n=flag==1?-x:x;
}
int main()
{
 freopen("nt2011_sequence.in","r",stdin);
 freopen("nt2011_sequence.out","w",stdout);
 int T;
 read(T);
 while(T--)
 {
  bit.reset();
  int n;
  read(n);
  bool flag=0;
  for(int i=1;i<=n;i++)
  {
   read(a);
   if(flag)continue;
   bit.set(a);
   for(int j=a-1;j!=0;j--)
   {
    int k=a*2-j;
    if(k>n)continue;
    if(bit.test(j)^bit.test(k))
    {
     flag=1;
     break;
    }
   }
  }
  flag==1?printf("Y\n"):printf("N\n");
 }
 return 0;
}

  

一致份可以A的bitset

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;
const int SIZEN=10010;
int N;
int A[SIZEN];
bitset<SIZEN> pre,suf;
bool test(void){//只能检测递增的
 pre.reset();suf.reset();
 for(int i=1;i<=N;i++) suf[i]=1;
 static bitset<SIZEN> tmp;
 for(int i=1;i<=N;i++){
  suf[A[i]]=0;
  if(i>1) pre[N+1-A[i-1]]=1;
  tmp=(suf>>A[i])&(pre>>(N+1-A[i]));
  if(tmp.any()) return true;
 }
 return false;
}
void work(void){
 scanf("%d",&N);
 for(int i=1;i<=N;i++) scanf("%d",&A[i]);
 if(test()){
  printf("Y\n");
  return;
 }
 reverse(A+1,A+1+N);
 if(test()){
  printf("Y\n");
  return;
 }
 printf("N\n");
}
int main(){
 freopen("nt2011_sequence.in","r",stdin);
 freopen("nt2011_sequence.out","w",stdout);
 int T;
 scanf("%d",&T);
 while(T--) work();
 return 0;
}

 

同等卖可以A的bool

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
using namespace std;
using std::bitset;
const int MAXN=10001;
bool bit[MAXN];
int a;
inline void read(int &n)
{
 char c='+';int x=0;bool flag=0;
 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
 n=flag==1?-x:x;
}
int main()
{
 freopen("nt2011_sequence.in","r",stdin);
 freopen("nt2011_sequence.out","w",stdout);
 int T;
 read(T);
 while(T--)
 {
  memset(bit,0,sizeof(bit));
  //bit.reset();
  int n;
  read(n);
  bool flag=0;
  for(int i=1;i<=n;i++)
  {
   read(a);
   if(flag)continue;
   bit[a]=1;
   for(int j=a-1;j!=0;j--)
   {
    int k=a*2-j;
    if(k>n)continue;
    if(bit[j]^bit[k])
    {
     flag=1;
     break;
    }
   }
  }
  flag==1?printf("Y\n"):printf("N\n");
 }
 return 0;
}

  

http://www.bkjia.com/cjjc/1221091.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1221091.htmlTechArticle1893.
[国家集训队2011]对等差子序列(bitset),2011bitset ★★ 输入文件:
nt2011_sequence.in 输出文件: nt2011_sequence.out 简单对比
时间限定:0.3 s 内存…

标签:,

Your Comments

近期评论

    功能


    网站地图xml地图