P3672 小清新签到题

    • 45通过
    • 322提交
  • 题目提供者fjzzq2002
  • 标签 前缀和 枚举,暴力 贪心 洛谷原创 O2优化
  • 难度 提高+/省选-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    题目还是简单一点好。

    给定自然数n、k、x,你要求出第k小的长度为n的逆序对对数为x的1~n的排列$a_1,a_2 ... a_n$,然后用仙人图上在线分支定界启发式带花树上下界最小费用流解决问题,保证存在。

    注:逆序对为满足$i<j$、$a_i>a_j$的$(i,j)$。比较为字典序比较,即比较从前往后第一个不同的位置。第k小从1开始标号。一个1~n的排列定义为一个长度为n的数列,排序完可以得到1~n。

    输入输出格式

    输入格式:

    一行三个自然数n、k、x。

    输出格式:

    输出满足条件的排列,一行n个数,用空格分隔。

    输入输出样例

    输入样例#1: 复制
    3 2 2
    输出样例#1: 复制
    3 1 2
    输入样例#2: 复制
    10 6 4
    输出样例#2: 复制
    1 2 3 4 5 7 6 10 9 8
    输入样例#3: 复制
    50 233 233
    输出样例#3: 复制
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 32 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 33 35 34 31 30 29 28
    输入样例#4: 复制
    50 233333333 333
    输出样例#4: 复制
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 43 49 50 47 46 45 48 44 41 42 40 39 37 38 36 35 34 33 32 30 29 31 28 25 26 27 24

    说明

    对于10%的数据,$n \leq 8$。

    对于30%的数据,$n \leq 10$。

    对于50%的数据,$n \leq 50$。

    对于另外20%的数据,$k=1$。

    对于100%的数据,$1 \leq n \leq 300$,$1 \leq k \leq 10^{13}$,保证存在符合题意的排列。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。