【蓝桥杯冲刺 day28】真题解析

文章目录

• • 36进制 -- 17届省赛真题
  • • 解题思路
  • 交换瓶子 -- 16届省赛真题
  • • 解题思路
  • 路径之谜 -- 16届国赛真题
  • • 解题思路

大家好我是秋刀鱼，今天给大家带来蓝桥杯真题题解

36进制 – 17届省赛真题

题目传送门🚪

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

对于16进制，我们使用字母 A−F 来表示 10及以上的数字。

如法炮制，一直用到字母 Z，就可以表示 36 进制。

36进制中，A 表示 10，Z 表示 35，AA 表示370。

你能算出 MANY 表示的数字用 10进制表示是多少吗?

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

解题思路

不算很难的进制转换类问题，直接上代码：

#include 
using namespace std;
int main()
{
  int val1 = 'M'-'A'+10;
  int val2 = 'A'-'A'+10;
  int val3 = 'N'-'A'+10;
  int val4 = 'Y'-'A'+10;

  cout<<val4+val3*36+val2*36*36+val1*36*36*36;
  return 0;
}

交换瓶子 – 16届省赛真题

题目传送门🚪

题目描述

有 N 个瓶子，编号 1 ~ N，放在架子上。

比如有 5 个瓶子：

2 1 3 5 4

要求每次拿起 2 个瓶子，交换它们的位置。

经过若干次后，使得瓶子的序号为：

1 2 3 4 5

对于这么简单的情况，显然，至少需要交换 2 次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

输入描述

输入格式为两行：

第一行: 一个正整数 (N<10^4) 表示瓶子的数目

第二行： N* 个正整数，用空格分开，表示瓶子目前的排列情况。

输出描述

输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。

输入输出样例

示例

输入

5
3 1 2 5 4

输出

3

解题思路

瓶子编号为 1~N 固定，通过顺序遍历到位置 i i i时，瓶子位置错误。

此时将该瓶子与其正确位置瓶子 j j j交换，使 i i i瓶位置正确，同时继续交换 j j j号瓶与其正确位置瓶子。

直到 j j j号瓶所在的位置就是其正确位置为止。

#include 
#include 
using namespace std;
#define M 10001
void S(int arr[M], int a, int b) {
    int v = arr[a];
    arr[a] = arr[b];
    arr[b] = v;
}
int main()
{
    int nums[M];
    memset(nums, 0, sizeof(nums));
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        int j = i;
        while (nums[j] != j + 1) {
            S(nums, j, nums[j] - 1);
            ++ans;
            nums[j] - 1;
        }
    }
    cout << ans;
    return 0;
}

路径之谜 – 16届国赛真题

题目传送门🚀

题目描述

小明冒充 XX 星球的骑士，进入了一个奇怪的城堡。

城堡里边什么都没有，只有方形石头铺成的地面。

假设城堡地面是 n \times nn×n 个方格。

如下图所示。

按习俗，骑士要从西北角走到东南角。

可以横向或纵向移动，但不能斜着走，也不能跳跃。

每走到一个新方格，就要向正北方和正西方各射一箭。

（城堡的西墙和北墙内各有 nn 个靶子）同一个方格只允许经过一次。

但不必走完所有的方格。

如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？有时是可以的，比如上图中的例子。

本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）

输入描述

第一行一个整数 NN (0 \leq N \leq 200≤N≤20)，表示地面有 N \times NN×N 个方格。

第二行 NN 个整数，空格分开，表示北边的箭靶上的数字（自西向东）

第三行 NN 个整数，空格分开，表示西边的箭靶上的数字（自北向南）

输出描述

输出一行若干个整数，表示骑士路径。

为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3 \cdots⋯

比如，上图中的方块编号为：

0 1 2 3

4 5 6 7

8 9 10 11

12 13 14 15

输入输出样例

示例

输入

4
2 4 3 4
4 3 3 3

输出

0 4 5 1 2 3 7 11 10 9 13 14 15

解题思路

一道简单的dfs搜索问题，因为答案唯一因此 dfs 函数返回为true时表示答案搜索完成，直接返回true实现剪枝。

#include 
#include 
#include 
#include 
using namespace std;
#define M 21
bool used[M][M];
// 记录最大次数
int t[M];
int l[M];
//方向
int directs[4][2] = { {1,0},{-1,0},{0,-1},{0,1} };
int n;
string ans = "";
//获取答案编号
int getIdx(int x, int y) {
    return n * (x - 1) + y - 1;
}
bool dfs(int x, int y,vector<int>&path) {
    --t[y];
    --l[x];
    used[x][y] = true;
    path.push_back(getIdx(x, y));
    // 到了终点
    if (x == n && y == n) {
        for (int i = 1; i <= n; ++i) {
            if (l[i] != 0 || t[i] != 0) {
                return false;
            }
        }
        for (int val : path) {
            ans.append(to_string(val)+" ");
        }
        return true;
    }
    for (int i = 0; i < 4; ++i) {
        int nx = x + directs[i][0];
        int ny = y + directs[i][1];
        if (nx <= 0 || ny <= 0 || nx > n || ny > n || used[nx][ny] ||  t[ny] == 0 || l[nx] == 0) {
            continue;
        }
        // 剪枝
        if (dfs(nx, ny, path)) {
            return true;
        }
        used[nx][ny] = false;
        ++t[ny];
        ++l[nx];
        path.pop_back();
    }
    return false;
}
int main()
{
    memset(used, 0, sizeof(used));
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> t[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> l[i];
    }
    vector<int>path;
    dfs(1, 1, path);
    cout << ans;
    return 0;
}

写在最后

代码、论述中有任何问题，欢迎大家指出，同时如果有任何疑问，也能够在评论区中留言，大家共同讨论共同进步！

如果觉得博主写的不错的话，可以点赞支持一下！