蓝桥杯倒计时 | 倒计时8天

时间：2023-04-02 09:03:05

作者????️‍♂️：让机器理解语言か

专栏????：蓝桥杯倒计时冲刺

描述????：蓝桥杯冲刺阶段，一定要沉住气，一步一个脚印，胜利就在前方！

寄语????：????没有白走的路，每一步都算数！????

题目一：九数分三组 

题目描述

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

1 ~ 9的数字可以组成 3 个 3 位数，设为：A,B,C, 现在要求满足如下关系：

B=2∗A

C=3∗A

请你输出 A 的所有可能答案，数字间用空格分开，数字按升序排列。

思路：

一道简单的排列问题，用Python自带的permutations函数即可

前三个作为A，中间三个作为B，后三个数作为C 

代码：

两种写法 

from itertools import *
s = [i for i in range(1,10)]
for i in permutations(s): # s的全排列
  a=i[0]*100+i[1]*10+i[2]
  b=i[3]*100+i[4]*10+i[5]
  c=i[6]*100+i[7]*10+i[8]
  if b==2*a and c==3*a:
    print(a,end=' ')
# 192 219 273 327 
from itertools import *
s = [str(i) for i in range(1,10)]
for i in permutations(s): # s的全排列
  a= int(''.join(i[:3]))
  b= int(''.join(i[3:6]))
  c= int(''.join(i[6:9]))
  if b==2*a and c==3*a:
    print(a,end=' ')
# 192 219 273 327

题目二： 最短路

题目描述

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

如下图所示，G 是一个无向图，其中蓝色边的长度是 1、橘色边的长度是 2、绿色边的长度是 3。

蓝桥杯倒计时 | 倒计时8天

则从 A 到 S 的最短距离是多少？

解法一：人脑神经网络计算法

 开个玩笑！第一种方法就是纯手算，填空题没有那么多讲究嘻嘻(#^.^#)，不过这样做可能脑子要爆炸了！！！

解法二：Floyd算法 

最短路径可以用Floyd算法（针对多对多的最短路径问题），但其实有更好的一对一的最短路径算法， 比如BFS双向广搜和A*算法。

这题最烦的就是手敲这个邻接矩阵，A到S共有19个点，所以创建一个19*19的连接矩阵用来存图 

M = float("inf")            # 无边长的设置为无穷大
mp=[
    [0,2,1,1,1,M,M,M,M,M,M,M,M,M,M,M,M,M,M],
    [2,0,M,M,M,M,1,M,M,2,M,M,M,M,M,M,M,M,M],
    [1,M,0,3,M,3,3,M,M,M,M,M,M,M,M,M,M,M,M],
    [1,M,3,0,1,M,2,1,2,M,M,M,M,M,M,M,M,M,M],
    [1,M,M,1,0,M,M,1,3,M,M,M,M,M,M,M,M,M,M],
    [M,M,3,M,M,0,1,M,M,M,M,M,M,M,M,M,M,M,M],
    [M,1,3,2,M,1,0,M,3,M,M,M,M,M,M,M,M,M,M],
    [M,M,M,1,1,M,M,0,1,M,M,2,M,M,M,M,M,M,M],
    [M,M,M,2,3,M,3,1,0,M,M,M,M,M,M,M,M,M,M],
    [M,2,M,M,M,1,M,M,M,0,M,M,M,M,M,M,M,M,2],
    [M,M,M,M,M,M,2,M,M,M,0,3,M,1,M,2,M,M,M],
    [M,M,M,M,M,M,M,2,M,M,3,0,1,M,M,M,M,1,M],
    [M,M,M,M,M,M,M,M,3,M,M,1,0,2,M,M,1,M,1],
    [M,M,M,M,M,M,M,M,M,M,1,M,2,0,M,1,M,M,M],
    [M,M,M,M,M,M,M,M,M,M,M,M,M,M,0,1,1,3,M],
    [M,M,M,M,M,M,M,M,M,M,2,M,M,1,1,0,M,M,M],
    [M,M,M,M,M,M,M,M,M,M,M,M,1,M,1,M,0,M,M],
    [M,M,M,M,M,M,M,M,M,M,M,1,M,M,3,M,M,0,1],
    [M,M,M,M,M,M,M,M,M,2,M,M,1,M,M,M,M,1,0],
]

def Floyd(mp):
  for k in range(19):#中间节点
      for i in range(19):
          for j in range(19):
              mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j])
  return mp

res=Floyd(mp)
print(res[0][18])

题目三： 左移右移

问题描述

小蓝有一个长度为 N 的数组, 初始时从左到右依次是 1,2,3,…N 。

之后小蓝对这个数组进行了 M 次操作, 每次操作可能是以下 2 种之一:

  1. 左移 x, 即把 x 移动到最左边。

  2. 右移 x, 即把 x 移动到最右边。

请你回答经过 M 次操作之后, 数组从左到右每个数是多少?

输入格式

第一行包含 2 个整数, N 和 M 。

以下 M 行每行一个操作, 其中 “L x "表示左移 x,"Rx "表示右移 x 。

输出格式

输出 N 个数, 代表操作后的数组。

样例输入

5 3
L 3
L 2
R 1

样例输出

2 3 4 5 1

样例说明

样例中的数组变化如下:

[1,2,3,4,5]→[3,1,2,4,5]→[2,3,1,4,5]→[2,3,4,5,1]

评测用例规模与约定

对于 50% 的评测用例, 1≤N,M≤10000.

对于 100%的评测用例, 1≤N,M≤200000,1≤x≤N.

一道简单的模拟问题，偷分容易，想AC比较难。

解法一：列表的简单操作 （50%）

N, M = map(int,input().split())
lst = [i for i in range(1,N+1)]
for i in range(M):
  a, b = input().split()
  if a == "L":
    lst.remove(int(b))    # remove按值删除；pop按下标删除，并返回删除的值
    lst.insert(0,int(b))
  else:
    lst.remove(int(b))
    lst.append(int(b))
print(*lst)

解法二：AC

        创建一个轨迹数组，定义两个移位计算器lefr和right，每次左移将该元素的下标（轨迹） 置为最左，每次右移将该元素的下标（轨迹） 置为最右，最后对数据数组进行从小到大排序，排序的规则按照轨迹数组来排，最后输出排序后的数据数组。

n, m = map(int, input().split())
arr = list(range(n + 1))  # 数据数组, 从a[1]开始不要a[0]
pos = list(range(n + 1))  # 轨迹数组, 从a[1]开始不要a[0]
left = -1  # 左移记录器(确保起始小于所有数)
right = n + 1  # 右移记录器(确保起始大于所有数)

for _ in range(m):
    opt, x = input().split()
    x = int(x)
    if opt == 'L':
        pos[x] = left  # 把x的位置记录为左移，-n在排序中代表第n个进行左移
        left -= 1
    else:
        pos[x] = right  # 把x的位置记录为右移，k在排序中代表第n - k个进行左移
        right += 1
arr.pop(0)  # 记得把a[0]弹掉
arr.sort(key=lambda k: pos[k])
print(*arr)

标签：

相关文章