2019年第十届蓝桥杯B组国赛(c/c++)总结

这次蓝桥怎么说呢,大题感觉挺难的..填空题还好,有点脑筋急转弯的感觉


填空

  1. $2019^2, x^2, y^2$ 构成等差数列(x<y),求解最小的公差 直接暴力就行了可惜这个题没注意 x<y 直接交了个2019上去

  2. 求有多少对素数 (a,b) 使得 $a + b == 2019 (a<b)$ 因为2019必定由一个奇数和一个偶数组成,所以只有2,2017这一组

  3. $s_i$ 表示因子个数为 i 的最小的数,求$s_100$ 也是一道直接暴力的题
    gh

  4. 给出一个 7*7 的矩形,将其分成两部分,求有多少种方法使得靠右的那部分按 x = y 翻转后再和左边部分拼接出来还是 7*7的矩形 其实不难看出必须是等腰直角三角形才满足条件,所以总共 7 种方法

  5. 一个5*5的格子,从左上角沿着边走,要求最多走12步,路径不能重叠,必须回到起点.求有多少种走法 dfs从左上角走格子即可,最多12步,也就是5格,我这里用string来记录每一步的位置,把走过的路全插入到 set 里,最后set的大小是101,因为正反都可以走,所以答案是202


编程

  1. 给出两个串 s, t 求 s 串修改(只修改,不能添加 or 删除字母)多少次可以找到 t 这个子序列

pos从0开始 第一重循环i 从 0 到t.size() 第二重循环j从i到t.size(). 用26个数组分别记录’a-z’的下标,遍历t串的时候,如果有当前字母,则pos等于 当前字母中第一个>pos的位置,否则pos++

  1. 在一个排列中,每存在一个 (s[i]>s[i-1] && s[i]>[i+1])||(s[i]<s[i-1] && s[i]<[i+1]) 则这个排列的 value+1 ,最后让求在 1-n 的全排列中,value 为 k-1 的排列有多少个

这个真不会了,全排列函数暴力了n<=13时候的情况交上去了

  1. 异形魔方:第一层为 12 个字母,第二层为 8 个字母,第三层为 4 个字母,每次可以将这三层都横向转动一次,或者竖着转动一列如果第一层,第二层,第三层分别为$s[0][0],s[1][0],s[2][0]$,则竖着转动后变为 $s[1][0],s[2][0],s[3][0]$ .给出 12+8+4 个字母(共12个R,8个G,4个B).求是否能将魔方归位。

单纯dfs时间复杂度太高,于是我加了个自己都不知道正确性的剪枝上去剪到1e6左右了 策略是:设当前列混乱度为3,如果某一位要求的字母种类和此位置上的字母一致的话混乱度-1,当竖着转动当前列的时候,如果混乱度会增大且增大后==3则不转动 (我也不知道对不对)

  1. 2种操作,插入 or 查询。每次可以修改某一点的值或者查询区间$[l,r]$中第八大的数

主席树裸题,可惜我记不住板子.

  1. 概率题,没看记不清了…
觉得文章不错的话可以请我喝一杯茶哟~
  • 本文作者: bestsort
  • 本文链接: https://bestsort.cn/2019/05/27/777/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-SA 许可协议。转载请注明出处!并保留本声明。感谢您的阅读和支持!
-------------本文结束感谢您的阅读-------------