蓝桥杯校内赛2.27

川长思鸟来 2022-11-05 11:51 70阅读 0赞

# 1. P1914 小书童——凯撒密码(O) #

**题目背景**  
某蒟蒻迷上了“小书童”，有一天登陆时忘记密码了（他没绑定邮箱or手机），于是便把问题抛给了神犇你。

**题目描述**  
蒟蒻虽然忘记密码，但他还记得密码是由一个字符串组成。密码是由原文字符串（由不超过 50 个小写字母组成）中每个字母向后移动 nn 位形成的。z 的下一个字母是 a，如此循环。他现在找到了移动前的原文字符串及 nn，请你求出密码。

**输入格式**  
第一行：n。第二行：未移动前的一串字母

**输出格式**  
一行，是此蒟蒻的密码  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hcmJsdWVfeQ_size_16_color_FFFFFF_t_70]  
**答案**

n = int(input())
    str = input()
    res = ''
    for i in str:
        i = chr(((ord(i) + n) - 97) % 26 + 97)
        print(i, end='')

# 2. U135054 一笔画问题(O) #

**题目背景**  
18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如左上图）。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥。  
大数学家欧拉研究并完美地解决了这个问题，并由此引导出了数学的重要分支——【图论】。  
他把哥尼斯堡七桥问题抽象成了一个拓扑图（如右上图，把陆地或者岛屿抽象为一个节点，把连接陆地和岛屿的桥抽象为边）。  
原问题等价于是否存在一条路径可以不重不漏地经过所有边，满足该条件的路径被称为【欧拉路径】，该问题也被称为“一笔画问题”。并且给出结论：连通图可以一笔画的充要条件是度数（节点的度数的定义是与该点相连的边的数量，自环会让度数增加2）为奇数的点有 0 个或 2 个。

**题目描述**  
TT 组测试数据  
每组数据给定从编号为 11 ~ nn 的 nn 个节点，mm 条边组成的一个无向图  
判断该图能否被一笔画出（是否存在欧拉路径），如果能输出Yes否则输出No，区分大小写。

**输入格式**  
第一行输入一个整数 T 为数据组数  
每组数据输入先两个整数 n,m  
接下来 m 行每行两个整数为一条边所连接的两个节点的编号

**输出格式**  
输出 T 行，每行为Yes或No  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hcmJsdWVfeQ_size_16_color_FFFFFF_t_70 1]  
**答案**

#欧拉路径就是一条能够不重不漏地经过图上的每一条边的路径
    T = int(input())  # 数据组数
    s = set()
    res = []
    for i in range(T):
        n, m = (int(x) for x in input().split())  # 点数,边数
        data = [0] * n
        num = 0
        for j in range(m):
            a, b = (int(x) for x in input().split())
            data[a - 1], data[b - 1] = data[a - 1] + 1, data[b - 1] + 1
        for x in data:
            if not x % 2 == 0:
                num += 1
        if num == 0 or num == 2:
            print('Yes')
        else:
            print('No')

# 3. P1152 欢乐的跳(O) #

**题目描述**  
一个nn个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了\[1,n-1\]\[1,n−1\]之间的所有整数，则称之符合“欢乐的跳”，如数组1 4 2 31423符合“欢乐的跳”，因为差的绝对值分别为：3,2,1。

给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

**输入格式**  
每组测试数据第一行以一个整数n(1<=n<=1000)开始，接下来n个空格隔开的在\[-10^8−10  
^8\]之间的整数。

**输出格式**  
对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出"Jolly"，否则输出"Not jolly"。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hcmJsdWVfeQ_size_16_color_FFFFFF_t_70 2]  
**答案**

i =input().split()
    n=int(i[0])
    li =i[1:]
    check = [0] * (n - 1)
    for i in range(n-1):
        a = abs(int(li[i]) - int(li[i + 1]))
        if 1 <= a <= n - 1:
            check[a - 1] = 1
    for x in check:
        if x != 1:
            print('Not jolly')
            break
    else:
        print('Jolly')

# 4. U134853 组队参赛(O) #

ACM-ICPC以团队的形式代表各学校参赛，每队由3名队员组成。每位队员必须是在校学生，有一定的年龄限制，并且每年最多可以参加2站区域选拔赛。

**题目描述**  
现在已知某个学校有 nn 名选手，求共可以组出多少种本质不同的参赛队伍。

两个队伍本质相同当且仅当两支队伍的三名队员都相同。

**输入格式**  
输入一个整数 nn 为该校备选参赛选手数量

**输出格式**  
输出一个整数作为结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hcmJsdWVfeQ_size_16_color_FFFFFF_t_70 3]  
**答案**

n=int(input())
    res=1
    if n<3:
        res=0
    else:
        for i in range(n,n-3,-1):
            res=res*i
    print(int(res/6))

# 5. P1164 小A点菜(O) #

**题目背景**  
uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家……餐馆，很低端的那种。uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。

**题目描述**  
不过uim由于买了一些辅（e）辅（ro）书，口袋里只剩M元(M≤10000)。  
餐馆虽低端，但是菜品种类不少，有N种(N≤100)，第i种卖ai元(ai ≤1000)。由于是很低端的餐馆，所以每种菜只有一份。

小A奉行“不把钱吃光不罢休”，所以他点单一定刚好吧uim身上所有钱花完。他想知道有多少种点菜方法。

由于小A肚子太饿，所以最多只能等待11秒。

**输入格式**  
第一行是两个数字，表示N和M。

第二行起N个正数ai  
  
(可以有相同的数字，每个数字均在1000以内）。

**输出格式**  
一个正整数，表示点菜方案数，保证答案的范围在int之内。  
![在这里插入图片描述][20210306131107966.png]  
**答案**

N, M = (int(x) for x in input().split())
    a=[]
    # a = [int(x) for x in input().split()] # a[i]第i道菜的价格
    while not len(a)>=N:
        t=[int(x) for x in input().split()]
        a.extend(t)
    f = [[0 for i in range(M + 2)] for j in range(N + 2)]  # f[i][m]: 在前i道菜中点m元的菜,产生最多的点菜方法
    a.insert(0,0)
    for i in range(1,N + 1):
        for m in range(1,M + 1):
            if m == a[i]:  # 身上的钱=本菜菜价 -->m元买i-1道菜+1(只买本菜)
                f[i][m] = f[i - 1][m] + 1
            elif m > a[i]:  # 身上的钱>本菜菜价 -->不买(m元买i-1菜)+买(m-a[i-1]元买i-1道菜)
                f[i][m] = f[i - 1][m] + f[i - 1][m - a[i]]
            else:  # 买不起 -->m元买i道菜方法数=m元买i-1道菜方法数
                f[i][m] = f[i - 1][m]
    print(f[N][M])

# 6. U133962 数的统计(O) #

**题目描述**  
给定一个长度为 nn 序列，序列中的第 ii 个数为ai  
给出 m 个询问，每次询问一个数 x 在序列中出现过多少次

**输入格式**  
第一行输入一个整数 n 表示序列长度

第二行输入 n 个整数为题中的序列 ，用空格隔开

第三行输入一个整数 m 表示询问次数

接下来 m 行每行输入一个整数 x， 询问 x 在序列中出现过多少次

**输出格式**  
输入 m 行，每行一个整数为询问的结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hcmJsdWVfeQ_size_16_color_FFFFFF_t_70 4]  
**答案**

n = int(input())
    data = [int(x) for x in input().split()]
    m = int(input())  # 询问次数
    
    from collections import Counter
    c = Counter(data)
    for i in range(m):
        quest = int(input())  # 本轮查询的内容
        print (c[quest])

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hcmJsdWVfeQ_size_16_color_FFFFFF_t_70]: /images/20221023/17ff7c700e3f43a888ef6658907cec8e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hcmJsdWVfeQ_size_16_color_FFFFFF_t_70 1]: /images/20221023/93f2a409d71d4457b4f5775652b18b23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hcmJsdWVfeQ_size_16_color_FFFFFF_t_70 2]: /images/20221023/2340d9979f334075b20c94da44877e20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hcmJsdWVfeQ_size_16_color_FFFFFF_t_70 3]: /images/20221023/d2af8c2b4072499c949973a792cc7465.png
[20210306131107966.png]: /images/20221023/e228cb27c63545b2a848bd59aec64262.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hcmJsdWVfeQ_size_16_color_FFFFFF_t_70 4]: /images/20221023/e437ef7417014a83bdaabd67de903b50.png