[CF][构造][思维] CF1017C The Phone Number

这题官方题解给了个Dilworth’s theorem,并不懂是什么东西。。。

写出来一些后可以找规律(多写),然后可以发现就是可以把原序列分成几块连续的上升序列,只不过块之间的相对顺序反了过来。。这个也不知道怎么证明,但是感觉是找不到比这个更好的。。这样的话就相当于LIS+LDS的长度是块的大小加上块的数量。实现的时候注意最后一个块可能不完整。

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=1e5+5;


int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int n;
    scanf("%d",&n);
    int res=1<<29,mar=2;
    for (int i=2;i*i<=n;i++)
    {
        if(ceil(1.0*n/i)+i=mar)
        {
            for (int j=mar-1;j>=0;j--)
            printf("%d ",k-j);
        }
        else
        {
            for (int i=1;i<=k;i++)
                printf("%d ",i);
            break;
        }
        k-=mar;
    }

    return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据