【蓝桥杯】什么算法才是版本答案？近三年（2019-2021）蓝桥杯省赛涉及算法出现频率分析

2022年的蓝桥杯比赛已经基本报名结束，寒假来临，如何抓住重点，快速掌握各种算法知识，在4月份的蓝桥杯省赛中取得好成绩呢？本文收集了近三年的4场蓝桥杯省赛题目，（2019年，2020年第二场，2020年第三场，2021年）。并总结了题目涉及的算法，意在分析各种算法在蓝桥杯中的重要程度。算法共分为7大类，分别是：图论，数论，数据结构，动态规划，枚举模拟，搜索，贪心思维。列出如下表格：

2021年省赛C语言大学A组

2020年省赛C语言大学A组（第二场）

2020年省赛C语言大学A组（第三场）

2019年省赛C语言大学A组

出现频率分析

从题目数量来看：出现频率最多的就是枚举，模拟，以及动态规划，不愧被民间叫做暴力杯。

平均难度分析

从题目困难程度来统计：依然是枚举相对最容易得分，其次则是数论和图论，只需要记住一些关键的算法模板，就可以将题目带入得分。例如：最短路算法（Dijkstra、floyd），质因数分解，质数判断，最大公因数（gcd）等。最难的则是贪心算法和动态规划，做法相对更不确定，变形较多，仅仅动态规划就可以分成，01背包型，线性递推型，区间动态规划，状态压缩，树形动态规划等多种类别。但是只要能认真总结，动态规划也不失为一得分大项。

得分效益分析

此外因为难度不同，下面按照题目难度为分数设计收益系数，1星题目到5星题目，收益系数分别为：10,8,5,3,1。

例如一道3星难度，分值为15的题目，收益则为：5*15=75。如此按照题目困难程度加权计算收益排名如下：

算法模板：

此处给出，出现最频繁的两个基础操作的代码模板：

（1）x的k进制拆分

将任意一个数字x，进行k进制拆分，存储到数组中。几乎每一年的每个组的题目均会出现该问题，k常见的取值是10或者2。

// 返回x的k进制表示
vector<int> Split(int x, int k) {
  vector<int> ret;

  if (x == 0) { // 如果输入数据就是0那么需要返回一个单独的0数字
    ret.push_back(0);
    return ret;
  }
  while (x > 0) {
    ret.push_back(x % k);
    x /= k;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}

（2）x质因数分解

将 x x x 质因数分解表示成： x = p 0 a 0 ∗ p 1 a 1 ∗ . . . ∗ p n a n x=p_0^{a_0} * p_1^{a_1} *...*p_n^{a_n} x=p0a0​​∗p1a1​​∗...∗pnan​​，其中： p 0 , p 1 , . . . , p n p_0,p_1,...,p_n p0​,p1​,...,pn​均为质数。

/// 返回x的质因数分解结果，每一个pair的第一个元素为质因数p，第二个元素为指数a。
vector<pair<int, int> > GetPrimeFactor(int x) {
  vector<pair<int, int> > ret;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      int cnt = 0;
      while (x % i == 0) {
        cnt++;
        x /= i;
      }
      // x的质因子i出现了cnt次
      ret.push_back(make_pair(i, cnt));
    }
  }
  if (x > 1) {
    ret.push_back(make_pair(x, 1));
  }
  return ret;
}

/// 打印结果
void PrintAns(int x, const vector<pair<int, int>> ans) {
  printf("%d = ", x);
  for (int i = 0; i < ans.size(); i++) {
    if (i != 0) {
      printf(" + ");
    }
    printf("%d^%d", ans[i].first, ans[i].second);
  }
  printf("\n");
}

往届题解：

【蓝桥杯真题】2021年蓝桥杯省赛题目解析+代码（python组）
【蓝桥杯真题】2021年蓝桥杯省赛B组题目解析+代码（C/C++）
【蓝桥杯真题】2021年蓝桥杯省赛A组题目解析+代码（C/C++）

欢迎关注公众号：算法梦工厂，获取更多：往届真题题解，算法讲解课程，省赛测试数据。

蓝桥杯备赛qq群：