41 完全二叉树的权值

解题日期：250219
解题用时：40min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2019，二叉树，省赛

题意整理

完全二叉树，每个节点都有一个权值，现在要把相同深度的节点的权值加在一起，想指导哪个深度的节点权值之和最大？

解题思路

根据完全二叉树的性质进行公示推导。注意数组越界的问题，会导致运行错误。

完全二叉树的性质

AC代码

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 #include <iostream>
#include <climits> // 用于 INT_MIN
using namespace std;

// 计算 2^i
int fd(int i) {
    if (i == 0) return 1; // 2^0 = 1
    int result = 1;
    while (i > 0) {
        result *= 2;
        i--;
    }
    return result;
}

// 计算完全二叉树的高度
int gh(int n) {
    int height = 0;
    while (fd(height) <= n) {
        height++;
    }
    return height;
}

int main() {
    int n;
    cin >> n;
    int a[100010] = {0}; // 初始化数组
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int h = gh(n); // 计算树的高度
    int res = 1; // 记录最大和的层号
    int maxSum = INT_MIN; // 记录最大和，初始化为最小值

    for (int i = 1; i <= h; i++) {
        int sum = 0;
        int start = fd(i - 1); // 当前层的起始下标
        int end = fd(i); // 当前层的结束下标
        // 防止 end 超过 n
        if (end > n) end = n + 1;
        for (int j = start; j < end; j++) {
            sum += a[j];
        }
        if (sum > maxSum) {
            maxSum = sum;
            res = i;
        }
    }

    cout << res;
    return 0;
}

42 外卖店优先级

解题日期：250219
解题用时：37min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2019，模拟，省赛

题意整理

“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有一个优先级，初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。

如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果优先级小于等于 3，则会被清除出优先缓存。

给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优先缓存中?

解题思路

以时间为维度进行处理即可。

AC代码

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 #include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  // 请在此输入您的代码
  int n,m,t;          
  scanf("%d %d %d",&n,&m,&t);//n表示有多少家店，m表示有多少条订单，t表示有多少时刻
   int ts[100000],     //某时刻   
      id[100000];     //某家店的编号

  int book[100000];   //此时刻的订单
  int arr[100000];    //优先级的量
  int fit[100000];    //管理优先级的清除与计入
  int ret=0;     //表示有几个优先级的店

  for(int i=0;i<m;i++)                  //////--------i和m
  {
    scanf("%d %d",&ts[i],&id[i]);  //第几条订单的时刻和店的编号
  }

  for(int i=0;i<=t;i++)     //每时刻，在这一时刻发生的所有事//这个大循环用i来表示，其中所有的小循环都是用j来表示
  {

   for(int j=0;j<=n;j++)   //每家店   ////  ------j和n    
    {
      book[j]=0;            //初始化：此时刻收到订单为0     
    }

    for(int j=0;j<m;j++)    //每条订单      //// -----j和m
    {
      if(ts[j]==i)   //第j条订单（j在id[j]中，这家店收入了j）的时刻是i时刻//如果这家店收到订单
      {
        arr[id[j]]+=2;       //编号的这家店优先级+2;
        book[id[j]]=1;       //收到的订单为1    ********id[m]==n第m条订单的店的编号是n
      }
    }

    for(int j=0;j<=n;j++)   //所有店（编号）  //// -------j和n
    {
      if(arr[j]>0&&book[j]==0)  //在这一时刻i时刻订单为0且优先级>0，是0则不能再减 //这就把book[]派上用场了//
      {
        arr[j]--;       //优先级-1；
      }
      if(fit[j]>0&&book[j]==0)     //计入的优先级，与arr[]保持动态匹配
      {
        fit[j]--;
      }
    }

    for(int j=0;j<=n;j++)        //////------J和n
    {
      if(arr[j]>5)
      {
        fit[j]=arr[j];    //当这家店（j）的优先级大于5，fit存储此量，一旦小于等于3，fit内部存储清除为0，arr并不清除；
                             // 如果在3到5之间，fit之前存储过，此次不清除，依旧算入优先级
      }
      if(arr[j]<=3)
      {
        fit[j]=0;
      }
    }

  }
  
  for(int i=0;i<=n;i++)      //////-----i和n
  {
    if(fit[i]>=3)
    {
      ret++;   
    }
  }                      ////arr->fit->ret;
  
printf("%d",ret);
  return 0;
}

43 特别的数

解题日期：250219
解题用时：3min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2019，暴力，枚举，省赛

题意整理

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 n 中，所有这样的数的和是多少？

解题思路

直接判断即可。

AC代码

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
 #include <iostream>
using namespace std;
bool isfit(int k){
  while(k>0){
    int temp=k%10;
    if(temp==2||temp==0||temp==1||temp==9){
      return true;
    }
    k/=10;
  }
  return false;
}
int main()
{
  int n;
  cin>>n;
  int count=0;
  for(int i=1;i<=n;i++){
    if(isfit(i)){
      count+=i;
    }
  }
  cout<<count;
  return 0;
}

44 等差数列

解题日期：250219
解题用时：28min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2019，GCD

题意整理

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中N个整数。现在给出这N个整数，小明想知道包含这N个整数的最短的等差数列有几项？

解题思路

先排序，找到最小的两个数之差，然后遍历所有的两个数字之差进行gcd操作即可。

AC代码

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
 #include <iostream>
#include <algorithm> 
using namespace std;
long long a[100001];
int y(int a,int b)//求最大公约数
{
  if(b==0)return a;
    else
  return y(b,a%b);
}
int main()
{
    int n,i;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);//排序
    int d=a[1]-a[0];
    for(int i=2;i<n;i++)
    {
        d=y(d,a[i]-a[i-1]);
    }
    if(a[n-1]==a[0])cout<<n<<endl;//考虑特殊情况
    else
    cout<<((a[n-1]-a[0])/d)+1<<endl;//等差数列公式
    return 0;
}

45

解题日期：250219
解题用时：
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2019，暴力，省赛

题意整理

图片旋转是对图片最简单的处理方式之一，在本题中，你需要对图片顺时针旋转 90 度。

我们用一个 n×m 的二维数组来表示一个图片，例如下面给出一个 3×4 的 图片的例子：

1 3 5 7

9 8 7 6

3 5 9 7

这个图片顺时针旋转 90 度后的图片如下：

3 9 1

5 8 3

9 7 5

7 6 7

给定初始图片，请计算旋转后的图片。

解题思路

注意二维数组开太大会爆内存！！先按照正常读入即可，然后输出的时候想一下先输出的是第一列、最后一行的数，依次类推得到输出的循环嵌套形式。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 #include <iostream>
using namespace std;
int main()
{
  int n,m;
  cin>>n>>m;
  int a[100][100];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin>>a[i][j];
    }
  }
  for(int j=0;j<m;j++){
    for(int i=n-1;i>=0;i--){
      cout<<a[i][j];
      if(i==0)cout<<endl;
      else cout<<" ";
    }
  }
  return 0;
}

46 大臣的旅费

解题日期：250219
解题用时：40min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2013，省赛，树形dp，搜索

题意整理

很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。

J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

解题思路

  1. 问题n个节点n-1一条边实际上是树，同时，要求求花最多的路费是多少，也即最长距离，转化为求树的直径

  2. 从任意一个节点开始，dfs第一遍求直径的一个端点u

  3. 从u节点开始，继续dfs，求解距离当前节点最远的点，就是直径的另一个端点，继续u记录即可

  4. 按照题意根据距离计算ans即可

AC代码

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 #include<bits/stdc++.h>

#define rep(i, a, b) for(int i = a; i < b; i++)

using namespace std;

const int N = 1e5 + 10;

struct edge{
    int id, w;
};
vector<edge> h[N]; //存储n个节点的有向边
int dis[N]; //节点编号[1, n]
bool vis[N];
int n;

void dfs(int u, int distance)
{
    dis[u] = distance;
    vis[u] = 1;
    
    for(auto x : h[u]) //遍历 当前节点的邻接节点
        if(!vis[x.id])
            dfs(x.id, distance + x.w);
}
int main()
{
    cin >> n;
    rep(i, 0, n - 1)
    {
        int a, b, w;
        cin >> a >> b >> w;
        h[a].push_back({b, w}); //存储无向图
        h[b].push_back({a, w}); 
    }
    
    dfs(1, 0); //直径的一个端点
    
    int u = 1; //记录距离当前节点距离最大的点
    rep(i, 1, n + 1)
        if(dis[i] > dis[u])
            u = i;

    memset(vis, 0, sizeof vis);
    
    dfs(u, 0); //直径的另一个端点
    
    rep(i, 1, n + 1)
        if(dis[i] > dis[u])
            u = i;

    //距离当前节点最远的点，就是直径的另一个端点
    int s = dis[u];
    printf("%lld", s * 10 + s * (s + 1ll) / 2); //可能溢出，强制类型转化即可

    return 0;    
}

47 翻硬币

解题日期：250219
解题用时：40min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2013，贪心，省赛

题意整理

小明正在玩一个”翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：** oo*** oooo;

如果同时翻转左边的两个硬币，则变为：oooo*** oooo。

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

解题思路

反向思维。遇到不匹配就反转这一个和下一个，按照顺序遍历即可。

AC代码

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
28
 #include<iostream>
#include<string.h>
using namespace std;

void swap(char x[1005],int i){
    if(x[i]=='*'){
        x[i] = 'o';
    }else
        x[i] = '*';
}
int main()
{
    char s[1000];
    char x[1005];
    cin>>s;
    cin>>x;
    int count = 0;
    int len = strlen(x);
    for(int i=0;i<len;i++){
        if(s[i]!=x[i]){
            swap(x,i); 
            swap(x,i+1); 
            count ++ ;
        }
    }
    cout<<count<<endl;
    return 0;
}

48 核桃的数量

解题日期：250219
解题用时：3min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2013，省赛

题意整理

小张是软件项目经理，他带领 3 个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。他的要求是：

  1. 各组的核桃数量必须相同

  2. 各组内必须能平分核桃（当然是不能打碎的）

  3. 尽量提供满足 1,2 条件的最小数量（节约闹革命嘛）

解题思路

找三个数的最小公倍数。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 #include <iostream>
using namespace std;
int main()
{
  int a,b,c;
  cin>>a>>b>>c;
  int max=a;
  if(b>max)max=b;
  if(c>max)max=c;
  for(int i=max;;i++){
    if((i%a==0)&&(i%b==0)&&(i%c==0)){
      cout<<i;
      return 0;
    }
  }
  return 0;
}

49 剪格子

解题日期：250219
解题用时：-
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2013，省赛，搜索

题意整理

https://doc.shiyanlou.com/courses/uid1580206-20210202-1612250769606
我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是60。

本题的要求就是请你编程判定：对给定的m×n的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。如果无法分割，则输出0。

解题思路

dfs+剪枝

AC代码

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
28
29
30
31
32
33
34
35
36
37
38
39
 #include<iostream>
using namespace std;
const int N = 15;
int mp[N+5][N+5];//地图
int vis[N+5][N+5];//判断是否被访问过
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };//移动方向
int sum, ans = 100000;
int n, m;//n行，m列
void dfs(int x, int y, int c, int s)
{
    if (2 * s > sum)return;
    if (2 * s == sum )//符合题目要求并且包含左上角那一部分
    {
        if (c < ans && vis[0][0])
        {
            ans = c;
        }
        return;
    }
    vis[x][y] = 1;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny])
            dfs(nx, ny, c + 1, s+mp[x][y]);
    }
    vis[x][y] = 0;
}
int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &mp[i][j]),sum+=mp[i][j];
    dfs(0, 0, 0, 0);
    cout << (ans==100000?0:ans);
    return 0;
}

50

解题日期：250219
解题用时：-
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2014，省赛，动态规划

题意整理

观察这个数列：

1 3 0 2 −1 1 −2 ⋯

这个数列中后一项总是比前一项增加 2 或者减少 3。

栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种呢？

解题思路

由于x是任意取的，题目可以简化为在总和为s 的情况下，一共包含n项 的数列中的数字只能是a或者-b，求方案总数。使用动态规划。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 #include <iostream>
using namespace std;
const int N = 1010, MOD = 1e8 + 7;
int n, s, a, b;
int f[N][N];

int main() {
    cin >> n >> s >> a >> b;
    
    f[0][0] = 1;
    for (int i = 1; i < n; i++)
        for (int j = 0; j < n; j++) {
            f[i][j] = (f[i-1][((j-i*a)%n+n)%n] + f[i-1][((j+i*b)%n+n)%n]) % MOD;
        }
    
    cout << f[n-1][(s%n+n)%n] % MOD << endl;
    
    return 0;
}