距离蓝桥杯62天 快和小郑一起加油
真题训练1:饮料换购 考察>>简单的数学推理
这道题不难 分析易知道:实际得到的饮料数=开始拥有的饮料+兑换的饮料
如果开始拥有的饮料n<=2 不可以兑换
否则当n>=3 可以兑换 消耗3可以换1
只需统计兑换次数即可
n=int(input()) s=n if n<=2: print(n) else: count=0 while s>=3: count+=1 s=(s-3)+1 print(n+count)
真题训练2: 排序 考察>>对冒泡排序的理解
首先 冒泡排序最多次数为n(n-1)/2次 原因如果是完全逆序 第一个需要交换n-1次,第二个需要交换n-2次以此类推最后一个需要交换1次 等差数列求和公式易得上式 (n为元素个数)
分析题意:需要满足交换100次,无重复,小写字母,最短,字典序最小
无重复和小写字母处理容易 即我们只需要考虑无重复的小写字母字符串
交换100次:n=14 最多交换91次 n=15最多交换105次 n=16最多交换120次
所以如果要交换100次 n至少15 由于n为元素个数 并且要求字符串最短即n最小 所以n=15
字典序最小 那么字符串必然由‘a~o’组成 (由于本题默认了冒泡排序升序,以此为准)
那么令s='onmlkjihgfedcba' 冒泡次数为105次
现在问题在于:如何重新排列s使得次数减少5并使得新排列字典序最小
如何理解字典序最小:字符串从左到右每个字母尽可能小
尝试a放到首字母 这样子总次数减少了14次 不可
尝试b 减少了13次 不可
....尝试j 减少了5次 刚好100次!那么现在就要检验这个‘jonmlkihgfedcba’是不是最小的字典序排列 ,即现在从第二个字符开始有没有更小的可能?答案是没有的,因为onmlkihgfedcba是完全逆序的,交换次数为100次 如果更换了,那么就不会是100了 所以第二个字符也是最小的 同理....所有字符的都是对应位置上的最小字符 所以验证正确
DFS:蓝桥杯配套真题 考察>>DFS
由于小郑上面这道题没有做出来 反思自己 是DFS了解不多 所以明天主要以预习DFS为主
那道真题预计明天出炉python解析