请选择 进入手机版 | 继续访问电脑版

蓝桥杯青少年创意编程大赛题解:不同数列的个数

[复制链接]
林雨宣 发表于 2021-1-1 18:33:16 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
题目形貌

一个数列                               P                          P               P 中有                               n                          n               n 个数。小蓝从中选择位置一连的                               k                          k               k 个数,并对这                               k                          k               k 个数举行升序排列。求排序后的数列有多少种?
输入形貌
                               n                                             k                          n\ k               n k
                                        P                         0                                                              P                         1                              .                      .                      .                               P                                   n                            −                            1                                           P_0\ P_1...P_{n-1}               P0​ P1​...Pn−1​
此中: 所有的输入都是整数,                                       P                         0                              ,                               P                         1                              ,                      .                      .                      .                      .                      .                      .                      ,                               P                                   n                            −                            1                                           P_0,P_1,......,P_{n-1}               P0​,P1​,......,Pn−1​数值都不相同。​
输特别式
部门排序后数列的排列数。
数据范围
                               2                      ≤                      n                      ≤                      100                          2 \le n \le 100               2≤n≤100
                               2                      ≤                      k                      ≤                      n                          2\le k\le n               2≤k≤n
                               0                      ≤                               P                         i                              ≤                      n                      −                      1                          0\le P_i\le n-1               0≤Pi​≤n−1
输入样例
  5 3
0 2 1 4 3
输出样例
  2
提示
从原数列抽取一连3个数排序后有2种大概性:                               (                      0                      ,                      1                      ,                      2                      ,                      4                      ,                      3                      )                          (0,1,2,4,3)               (0,1,2,4,3)和                              (                      0                      ,                      2                      ,                      1                      ,                      3                      ,                      4                      )                          (0,2,1,3,4)               (0,2,1,3,4)。
算法思想

题中给出的数据范围较小,因此可以使用暴力罗列的方式:罗列数列中所有一连的                               k                          k               k 个数的组合,然依次对每一个举行排序。
但是排序后大概后产生重复的数列。比方:对于输入样例                              [                      02143                      ]                          [0 2 1 4 3]               [02143]中                              [                      021                      ]                          [0 2 1]               [021]和                              [                      214                      ]                          [2 1 4]               [214]举行排序,得到的数列都是                              [                      01243                      ]                          [01243]               [01243]。
继续分析,由于数列中数值都不相同,所以排序后只大概在相邻两项中产生相同效果。因此只需记载上次产生的数列,然后和本次的排序效果举行比力即可。
时间复杂度

                               O                      (                               n                         2                              l                      o                      g                      n                      )                          O(n^2logn)               O(n2logn)
代码实现

[code]#include #include #include using namespace std;const int N = 110;//b记载本次排序后的数列//last记载上次排序得到的数列int a[N], b[N], last[N];int n, k;//查抄两个数列是否相同bool check(int a[], int b[]){    for(int i = 0; i < n; i ++)        if(a != b) return false;    return true;}int main(){    cin >> n >> k;    for(int i = 0; i < n; i ++) cin >> a;    //将原数列a拷贝到last中    memcpy(last, a, sizeof a);    int sum = 0;    //罗列所有一连k个数的起始位置    for(int i = 0; i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )