Codeforces 1097E. Egor and an RPG game

首先考虑怎么算 $f(n)$ （就是题目里面那个 $f(n)$）

发现可以构造一组序列大概长这样： ${1,3,2,6,5,4,10,9,8,7,15,14,13,12,11,...,n(n+1)/2,n(n+1)/2-1,n(n+1)/2-2...n(n+1)/2-(n-1),(n+1)(n+2)/2,(n+1)(n+2)/2-1.....}$

然后发现这样构造的话，如果序列长度为 $k(k+1)/2$ ，那么至少需要分 $k$ 个数列

考虑证明这个即为上限，那么就是证明如果序列长度小于 $k(k+1)/2$ ，那么最多需要 $k-1$ 的数列

证明可以这样考虑，首先求出最长单调上升序列（$LIS$），如果 $LIS$ 长度大于等于 $k$ ，那么可以直接把 $LIS$ 取出

然后序列长度就从小于 $k(k+1)/2$ 变成小于 $k(k+1)/2-k=(k-1)k/2$ ，相当于更小的子问题

所以如果序列长度在 $[(k-1)k/2,k(k+1)/2)$ 内，那么只要看看 $LIS$ 是否大于等于 $k$ 然后递归处理即可

现在问题是如果 $LIS$ 长度小于 $k$ 怎么办，发现我们一定可以用 $LIS$ 长度个下降子序列覆盖整个序列

构造下降子序列的方法我不太会说，看下面的一段代码或许比较清楚：

struct dat {

    int id,val;

    dat (int _id=,int _val=) { id=_id,val=_val; }

    inline bool operator < (const dat &tmp) const {

        return val!=tmp.val ? val<tmp.val : id<tmp.id;

    }

};

void solve2(int mx)//mx是LIS长度

{

    set <dat> S;

    for(int i=;i<=mx;i++) S.insert(dat(m+i,N));

    for(int i=;i<V.size();i++)//V 是当前序列,用vector存的

    {

        auto p = S.lower_bound(dat(-,V[i]));

        ans[(*p).id].push_back(V[i]);

        S.insert(dat((*p).id,V[i])); S.erase(*p);

    }

    m+=mx; V.clear();

}

考虑证明上面做法的正确性，容易想到反证法：

首先把当前的所有下降序列按此时末尾的数从小到大排序，那么对于第 $i$ 个下降序列末尾的数，它在原序列的位置一定比左边所有序列末尾的数都大

因为如果不是这样的话左边的数完全可以接到这个数的后面（仔细想想）

那么由于这个东西对于每个当前每个下降序列都成立，那么可以发现当前所有下降序列的末尾如果取出来刚好构成了一个上升序列，设这个上升序列为 $A$

（显然发现其实 $A$ 也是原序列的 $LIS$ 之一）

回到原来的问题，

如果出现不合法的数列，说明存在某一个位置它不管接在当前哪一个下降序列后都是上升的

那么说明它比当前所有下降序列的末尾都大，并且又因为它是当前位置最右的，那么它一定可以接在 $A$ 的后面，

发现此时就找到了一个长度大于 $LIS$ 的上升序列，所以矛盾了

然后就证明完了

所以按着上面的思路搞就行了

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

#include<set>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=1e5+;

int n,m;

struct BIT {

    int t[N];

    inline void init() { for(int i=;i<=n;i++) t[i]=; }

    inline void add(int x,int v) { while(x<=n) t[x]=max(t[x],v),x+=x&-x; }

    inline int ask(int x) { int res=; while(x) res=max(res,t[x]),x-=x&-x; return res; }

}T;

int f[N];

vector <int> V,tmp,ans[N];

int work(int len)

{

    T.init(); int mx=;

    for(int i=;i<len;i++)

        mx=max(mx, f[i]=T.ask(V[i])+ ),

        T.add(V[i],f[i]);

    return mx;

}

void solve1(int len,int mx)

{

    tmp.clear(); int las=N; m++;

    for(int i=len-;i>=;i--)

        if(f[i]==mx&&V[i]<las)

            ans[m].push_back(V[i]),mx--,las=V[i];

        else tmp.push_back(V[i]);

    reverse(ans[m].begin(),ans[m].end());

    V=tmp; reverse(V.begin(),V.end());

}

struct dat {

    int id,val;

    dat (int _id=,int _val=) { id=_id,val=_val; }

    inline bool operator < (const dat &tmp) const {

        return val!=tmp.val ? val<tmp.val : id<tmp.id;

    }

};

void solve2(int mx)

{

    set <dat> S;

    for(int i=;i<=mx;i++) S.insert(dat(m+i,N));

    for(int i=;i<V.size();i++)

    {

        auto p = S.lower_bound(dat(-,V[i]));

        ans[(*p).id].push_back(V[i]);

        S.insert(dat((*p).id,V[i])); S.erase(*p);

    }

    m+=mx; V.clear();

}

int C2[N],h[N];

int main()

{

    for(int i=;i<=;i++) C2[i]=i*(i+)/;

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

        for(int j=C2[i];j<C2[i+]&&j<N;j++)

            h[j]=i;

    int T=read();

    while(T--)

    {

        for(int i=;i<=m;i++) ans[i].clear(); m=;

        n=read(); for(int i=;i<=n;i++) V.push_back(read());

        while(V.size())

        {

            int len=V.size(),mx=work(len);

            if(mx>h[len]) solve1(len,mx);

            else { solve2(mx); break; }

        }

        printf("%d\n",m);

        for(int i=;i<=m;i++)

        {

            printf("%d ",int(ans[i].size()));

            for(auto A: ans[i]) printf("%d ",A);

            puts("");

        }

    }

    return ;

}

巴特西

Codeforces 1097E. Egor and an RPG game

最新文章

热门文章