BestCoder Round #84 Bellovin

时间：2023-03-09 05:45:06
BestCoder Round #84 Bellovin

Bellovin

题意：

给个中文链接：戳戳戳

题解：

这个题其实就是让你求每一位的最长公共子序列，之后输出就好了，求这个有2个算法，一个是n方，另一个nlogn，所以显然是nlogn的算法，其实这就是个模版题。

但当时做的好坑，比如输出是 2 4 5 2 4 应该输出 1 2 3 1 2 但我当时以为要输出 1 2 3 3 3 脑袋短路了啊 = =

代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int INF=0x3f3f3f3f;

typedef long long ll;

#define PU puts("");

#define PI(A) printf("%d\n",A)

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d%d",&(N),&(M))

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

const double EPS= 1e-9 ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN=100000 + 9 ;

int dp[MAXN];

int N;

int a[MAXN];

int b[MAXN],cnb;

int main()

{

    int o;

    SI(o);

    while(o--)

    {

        SI(N);

        rep(i,N) SI(a[i]);

        int k=N;

        int ans=-1;

        fill(dp,dp+k,INF);

        for (int i=0; i<k; i++)

        {

            *lower_bound(dp,dp+k,a[i])=a[i];

            b[i]=lower_bound(dp,dp+k,a[i])-dp;

            b[i]++;

        }

        rep(i,N) printf("%d%c",b[i],i==N-1?'\n':' ');

        cle(b,0);

        cnb=0;

    }

    return 0;

}

相关文章