21 机器人塔

解题日期：250217
解题用时：63min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2016，位运算，国赛，DFS

题意整理

有两种机器人A和B，A只能站在AA或者BB之上，B只能站在AB或者BA之上。输入A和B人数，求能形成的花样总数。

解题思路

枚举底层的所有可能性，先不考虑m和n的数量，在枚举的过程中进行判断。
由底层计算出上一层，循环往复，统计总共的1和0的数目，再与m和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
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<bitset>
#include<cmath>
using namespace std;


int n, m;

bool check(int now, int num){
    int num_a = 0, num_b = 0;

    for(int i = num ; i >= 1 ; i--){//i是层数也是机器人个数
        //bitset类可以用.count()方法可快速求出二进制下1的个数
    //创建了一个32位的bitset， 初始化值为 now
        bitset<32>bs = now;
    num_b += bs.count();//now里面有多少1
        num_a += i - bs.count();//now里面有多少0
    //下面开始求上一层的now
        now ^= now >> 1;
        now &= (1 << (i - 1)) - 1;
    }
    return num_a == m && num_b == n;
}

int main(){
    cin >> m >> n;
  //num是层数  
  //利用double转int类型向下取整得性质，由(num + 1) * (num) / 2 == n + m 推导得
    int num = sqrt((n + m) * 2);
    
    int ans = 0;
    for(int i = 0 ; i < (1 << num) ; i++){//num层的最下层是num个机器人，摆法有2的num次方种，每一种可以转化为数字i
        if(check(i,num))ans++;
    }
    cout << ans << endl;
}

22 交换瓶子

解题日期：250217
解题用时：
题目来源：蓝桥杯真题
题目难度：中等
题目标签：

题意整理

n个编号1~n，乱序通过两两换位变成正序，至少需要几次

解题思路

如果某个位置实际的数和正确的数不相等，则让这个数和它对应位置的数交换swap(a[i], a[a[i]])，直到这个位置的数和正确的数对应。

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>
#include<algorithm>
#include<string.h>
#include<set>
#include<queue>
#define ll long long
using namespace std;

int a[10005], ans, n;
int main(void) {
//如果某个位置实际的数和正确的数不相等，则让这个数和它对应位置的数交换swap(a[i], a[a[i]])，
//直到这个位置的数和正确的数对应。
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    for(int i=1; i<=n; i++) {
        while(a[i]!=i) {
            swap(a[i], a[a[i]]);
            ++ans;
        }
    }
    printf("%d", ans);
    
    return 0;
}

23 移动距离

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

题意整理

蛇形排列，告诉排号宽度w，待计算的楼号m和n。求最短移动距离，不能往斜线方向移动。

解题思路

直接分析，注意特判w=1的情况（也许可以不用特判）。
分成行和列。注意列的计算需要谨慎。

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
#include <iostream>
using namespace std;

int fas(int k){
  if(k<0){return -k;}
  else{
    return k;
  }
}
int main()
{
  
  int w,m,n;
  cin>>w>>m>>n;
  int res=0;
  if(w==1) {res=fas(n-m);cout<<res;return 0;}
  if((m/w)%2==(n/w)%2){
    int a=fas(n-m)%w;
    int b=(n-n%w)/w-(m-m%w)/w;
    b=fas(b);
    res=a+b;

  }
  else{
    int a=w-m%w-n%w+1;
    a=fas(a);
    int b=(n-n%w)/w-(m-m%w)/w;
    b=fas(b);
    res=a+b;
  }
  cout<<res;
  return 0;
}

24 奇怪的数列

解题日期：250217
解题用时：14min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2015，模拟，国赛

题意整理

第一行的数字随便是什么，以后每一行都是对上一行”读出来”
13

1113

3113

132113

1113122113

⋯⋯

解题思路

字符串操作。直接模拟即可。注意传递的方式以及直接读的方式是只统计连续的数字个数。

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
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    string s, s1, s2;
    int b, count;
    cin >> s;
    cin >> b;
    while (b--)
    {
        int x = s.length();
        count = 1;
        s2 = "";
        for (int i = 0; i < x; i++)
        {
            s1 = "";
            if (s[i + 1] == s[i])
            {
                count++;
            }
            else
            {
                s1 += to_string(count) + s[i];
                count = 1;
                s2 += s1;
            }
        }
        s = s2;
    }
    cout << s;
    return 0;
}

25 穿越雷区

解题日期：250217
解题用时：80min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2015，暴力，国赛，搜索

题意整理

X 星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。

某坦克需要从 A 区到 B 区去（ A，B 区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？

已知的地图是一个方阵，上面用字母标出了 A，B 区，其它区都标了正号或负号分别表示正负能量辐射区。

例如：

A + - + -

B + - + -

坦克车只能水平或垂直方向上移动到相邻的区。

解题思路

BFS图搜。

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
#include<iostream>
using namespace std;
char g[110][110];
int visited[110][110];
int y[4]={1,0,-1,0};
int x[4]={0,1,0,-1};
int n;
int bfs(int ax,int ay){
    visited[ax][ay]=1;
    if( g[ax][ay]=='B' )
        return 0;
    int d=n*n;
    for(int i=0;i<4;i++){
        int dx=x[i]+ax;
        int dy=y[i]+ay;
        if( visited[dx][dy] || dx>n || dy>n || dx<1 || dy<1)
            continue;
        if( g[ax][ay]!=g[dx][dy]){
            int nd=bfs(dx,dy)+1;
            d=nd<d?nd:d;
            visited[dx][dy]=0;
        }
            
    }
    
    return d;
    
} 
int main(){
    int ax,ay;
    cin>>n;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>g[i][j];
            getchar();
            if(g[i][j]=='A'){
                ax=i; ay=j;
            }
        }
    }
    int d=bfs(ax,ay);
    if(d==n*n)
      cout<<-1;
    else cout<<d;
    return 0;
}

26 饮料换购

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

题意整理

三个饮料的盖子可以换一瓶新饮料，输入初始购买n。求最多可以喝多少瓶。

解题思路

让n可以增加。直接模拟喝的过程。一瓶一瓶喝。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int main()
{
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    if(i%3==0)n++;
  }
  cout<<n;
  return 0;
}

27 数位递增的数

解题日期：250218
解题用时：4min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2020，构造，省模拟赛

题意整理

输入n，判断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
26
#include <iostream>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int res=0;
  for(int i=1;i<=n;i++){
    bool flag=true;
    int temp=i;
    int ct=temp%10;
    while(temp>0){
      if(ct>=temp%10){
        ct=temp%10;
        temp/=10;
      }
      else{
        flag=false;
        break;
      }
    }
    if(flag==true) res++;
  }
  cout<<res;
  return 0;
}

28 长草

解题日期：250218
解题用时：30min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2020，模拟，省模拟赛，BFS

题意整理

小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。

小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。

这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，

这四小块空地都将变为有草的小块。请告诉小明，k 个月后空地上哪些地方有草。

解题思路

BFS直接模拟，采用一个辅助数组记录每一次的初始状况。

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
#include <iostream>
using namespace std;
int a[1000][1000];
int b[1000][1000];
int n, m;
void bfs() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            b[i][j] = a[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (b[i][j] == 1) {
                if (i - 1 >= 0) {
                    a[i-1][j] = 1;
                }
                if (i + 1 < n) {
                    a[i+1][j]=1;
                }
                if(j - 1 >= 0) {
                    a[i][j-1] = 1;
                }
                if (j + 1 < m) {
                    a[i][j+1]=1;
                }
            }
        }
    }
}

int main(void) {
    char ch;
    int k;
    
    cin>>n>>m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> ch;
            if (ch == '.') {
                a[i][j] = 0;
            } 
            else if (ch == 'g') {
                a[i][j] = 1;
            }
        }
    }
    cin >> k;
    for (int i = 0; i < k; i++)
        bfs();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 0) {
                cout<<'.';
            } 
            else if (a[i][j] == 1) {
                cout << 'g';
            }
        }
        cout<<endl;
    }
    return 0;
}

29 反倍数

解题日期：250218
解题用时：5min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2020，暴力，省模拟赛

题意整理

给定三个整数 a,b,c 如果一个整数既不是 a 的整数倍也不是 b 的整数倍还不是 c 的整数倍，则这个数称为反倍数。

请问在 1 至 n 中有多少个反倍数。

解题思路

数据范围不大，o(n)即可，直接暴力。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int main()
{
  int n;
  int a,b,c;
  int count=0;
  cin>>n;
  cin>>a>>b>>c;
  if(a==1||b==1||c==1){
    cout<<0<<endl;
    return 0;
  }
  for(int i=1;i<=n;i++){
    if(i%a==0||i%b==0||i%c==0){
      continue;
    }
    count++;
  }
  cout<<count<<endl;
  return 0;
}

30 洁净数

解题日期：250218
解题用时：5min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2020，暴力，省模拟赛

题意整理

小明非常不喜欢数字 2，包括那些数位上包含数字 2 的数。如果一个数的数位不包含数字 2，小明将它称为洁净数。

请问在整数 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
26
#include <iostream>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int count=0;
  for(int i=1;i<=n;i++)
  {
    bool flag=true;
    int temp=i;
    while(temp>0){
      int ck=temp%10;
      if(ck==2){
        flag=false;
        break;
      }
      temp/=10;
    }
    if(flag){
      count++;
    }
  }
  cout<<count;
  return 0;
}