【蓝桥杯python研究生组备赛】001 递归+二分+前缀和

题目1

【深基2.例12】上学迟到

题目描述

学校和 yyy 的家之间的距离为 $s$ 米，而 yyy 以 $v$ 米每分钟的速度匀速走向学校。

在上学的路上，yyy 还要额外花费 $10$ 分钟的时间进行垃圾分类。

学校要求必须在上午 $\text{8:00}$ 到达，请计算在不迟到的前提下，yyy 最晚能什么时候出门。

由于路途遥远，yyy 可能不得不提前一点出发，但是提前的时间不会超过一天。

输入格式

一行两个正整数 $s,v$，分别代表路程和速度。

输出格式

输出一个 $24$ 小时制下的时间，代表 yyy 最晚的出发时间。

输出格式为 $\text{HH:MM}$，分别代表该时间的时和分。必须输出两位，不足前面补 $0$。

样例 #1

样例输入 #1

100 99

样例输出 #1

07:48

提示

对于 $100\%$ 的数据，$1\le s,v\le 10^4$。

python代码

import math
s,v=map(int,input().split())
t=math.ceil(s/v)#路上的时间
h,m=divmod(t+10,60)#对应的小时和分钟

#如果h=0,不足一小时，7:00多出发
if h==0:
    print(f'07:{60-m:02d}')
elif h<=7:#没有到前一天
    print(f'{8-h-1:02d}:{60-m:02d}')
else:
    print(f'{8+24-h-1:02d}:{60-m:02d}')
    

知识点

1. 我认为竞赛题需要先理解题意才行。这道题说 提前出发 不超过一天，就是需要分成两端，今天的0：00-8：00，和0:00前。
2. 输入，两个正整数，我们利用map函数
3. 计划上的时间都需要留有裕量，所以1.2分钟这种需要向上取整 到2分钟，利用math.ceil()函数
4. 格式化输出，f-string 或.format{}相比C语言的printf更为强大，{:02d}或{:>02d}按照要求：遇到个位数的，前面需要用0填充，强制靠右排列，即07:05；宽度为2位，数据类型为10进制整数
5. 具体更多格式的输出可查看（Format Specification Mini-Language）：

format_spec     ::=  [[fill]align][sign]["z"]["#"]["0"][width][grouping_option]["." precision][type]
fill            ::=  <any character>
align           ::=  "<" | ">" | "=" | "^"
sign            ::=  "+" | "-" | " "
width           ::=  digit+
grouping_option ::=  "_" | ","
precision       ::=  digit+
type            ::=  "b" | "c" | "d" | "e" | "E" | "f" | "F" | "g" | "G" | "n" | "o" | "s" | "x" | "X" | "%"

题目2

[NOIP2002 普及组] 选数

题目描述

已知 $n$ 个整数 $x_1,x_2,\cdots ,x_n$，以及 $1$ 个整数 $k$（$k<n$）。从 $n$ 个整数中任选 $k$ 个整数相加，可分别得到一系列的和。例如当 $n=4$，$k=3$，$4$ 个整数分别为 $3,7,12,19$ 时，可得全部的组合与它们的和为：

$3+7+12=22$

$3+7+19=29$

$7+12+19=38$

$3+12+19=34$

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：$3+7+19=29$。

输入格式

第一行两个空格隔开的整数 $n,k$（$1\le n\le 20$，$k<n$）。

第二行 $n$ 个整数，分别为 $x_1,x_2,\cdots ,x_n$（$1\le x_i\le 5\times 10^6$）。

输出格式

输出一个整数，表示种类数。

样例 #1

样例输入 #1

4 3
3 7 12 19

样例输出 #1

1

提示

【题目来源】

NOIP 2002 普及组第二题

python代码

def primes(n):
    is_prime=[True]*(n+1)
    is_prime[0]=is_prime[1]=False
    for i in range(2,int(n**0.5)+1):
        for j in range(i*i,n+1,i):
            is_prime[j]=False
    return [i for i in range(2,n+1) if is_prime[i]==True ]
# n=int(input())
# print(primes(n))

from itertools import *
n,k=map(int,input().split())#5 3(有空格)
s=list(map(int,input().split()))#n个整数

ans=0#最终答案
# primes(n)#n内所有的质数
# print(primes(n))
# print(type(primes(n)))
for com in combinations(s,k):#k为长度
    sum1=0#k个数的和
    for i in range(k):#com为turple
        sum1+=com[i]
    # print(sum1)
    if sum1 in primes(sum(s)) :#k个数字的和<所有数字的和，作为质数的参数
        ans+=1
print(ans)
    

知识点

1. 质数，埃氏筛法
2. itertools 库的组合函数 combinations

题目3

黑白棋子的移动

题目描述

有 $2n$ 个棋子排成一行，开始为位置白子全部在左边，黑子全部在右边，如下图为 $n=5$ 的情况：

移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如 $n=5$ 时，成为：

任务：编程打印出移动过程。

输入格式

一个整数 $n$。

输出格式

若干行，表示初始状态和每次移动的状态，用 $\text{o}$ 表示白子，$\text{*}$ 表示黑子，$\text{-}$ 表示空行。

样例 #1

样例输入 #1

7

样例输出 #1

ooooooo*******--
oooooo--******o*
oooooo******--o*
ooooo--*****o*o*
ooooo*****--o*o*
oooo--****o*o*o*
oooo****--o*o*o*
ooo--***o*o*o*o*
ooo*o**--*o*o*o*
o--*o**oo*o*o*o*
o*o*o*--o*o*o*o*
--o*o*o*o*o*o*o*

提示

$4\le n\le 100$

python代码

def dfs(u):
    global n
    global cnt
    if u>=4:#小于最终步数，输出状态
        print(''.join(list_s))
    else:
        return
    a,b=list_s[2*u],list_s[2*u+1]#空格移到中间，o*移到后面
    list_s[2*u],list_s[2*u+1]=list_s[u-1],list_s[u]
    list_s[u-1],list_s[u]=a,b
    cnt+=1
    if u>=4:#小于最终步数，输出状态
        print(''.join(list_s))
    #空格移到边上
    c,d=list_s[2*u-2],list_s[2*u-1]#空格移到中间，o*移到后面
    list_s[2*u-2],list_s[2*u-1]=list_s[u-1],list_s[u]
    list_s[u-1],list_s[u]=c,d
    cnt+=1
    dfs(u-1)
    return


n=int(input())
# 定义 o 和 * 的数量
num_o = n  # 假设 o 的数量为 n
num_star = n  # 假设 * 的数量为 n
num_dash = 2  # 假设 - 的数量为 2

s = 'o' * num_o + '*' * num_star + '-' * num_dash

# 将字符串转换为列表
list_s = list(s)
# print(list_s)
cnt=0#计算移动次数
dfs(n)#前面n>4的时候的规律
con=['ooo*o**--*','o--*o**oo*','o*o*o*--o*','--o*o*o*o*']#打表（n=4的情况，然后n>=4的情况是，后面加上（n-4）个‘o*’
for i in range(4):
    print(con[i]+'o*'*(n-4))

知识点

1. 从样例中找规律，会发现除了后4行，前面的排列是 两行一组，把空格和o*不断移动，找到下标规律
2. 后4行，是打表n=4的情况，然后n>=4的情况是，后面加上（n-4）个‘o*’
3. 上面也算是 分治的思想，两种情况，对于重复移动的情况 利用递归解决对于最后4行，打表实现

题目4

费解的开关

题目描述

你玩过“拉灯”游戏吗？

$25$ 盏灯排成一个 $5\times 5$ 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 $1$ 表示一盏开着的灯，用数字 $0$ 表示关着的灯。

下面这种状态

10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 $6$ 步以内使所有的灯都变亮。

输入格式

第一行输入正整数 $n$，代表数据中共有 $n$ 个待解决的游戏初始状态。

以下若干行数据分为 $n$ 组，每组数据有 $5$ 行，每行 $5$ 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出 $n$ 行数据，每行有一个小于等于 $6$ 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 $6$ 步以内无法使所有灯变亮，则输出 -1。

样例 #1

样例输入 #1

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

样例输出 #1

3
2
-1

提示

测试数据满足 $0<n\le 500$。

python代码

import copy

# 主程序入口
n = int(input())  # 输入测试用例的数量

# 反转函数，传入data和位置(x, y)
def turn(data, x, y):
    dx = [0, 1, -1, 0, 0]
    dy = [0, 0, 0, 1, -1]
    for i in range(5):  # 遍历5个方向
        xx = x + dx[i]
        yy = y + dy[i]
        if xx < 0 or xx >= 5 or yy < 0 or yy >= 5:
            continue  # 越界跳过
        data[xx][yy] = 1 - data[xx][yy]  # 反转灯的状态

for _ in range(n):
    # 输入数据
    ans=10
    data = [list(map(int, input().strip())) for i in range(5)]
    backup=copy.deepcopy(data)#备份
    for op in range(32):
        step=0
        for j in range(5):#对第一行枚举，以及相应周围灯的变化
            if (op>>j)&1:
                step+=1
                turn(data,0,j)
        for row in range(4):#对第二行以后操作
            for column in range(5):
                if data[row][column]==0:
                    step+=1
                    turn(data,row+1,column)
            
        # 判断最后一行
        flag = 0
        for i in range(5):
            if data[4][i] == 0:  # 如果最后一行有灭的灯
                flag = 1
                break

        # 如果最后一行全亮，更新最小操作次数
        if flag == 0:
            ans = min(ans, step)

        # 恢复原始数据
        data = copy.deepcopy(backup)

    # 如果操作次数大于6，输出-1
    if ans > 6:
        ans = -1
    print(ans)
    try:
        input()
    except EOFError:
        break
        

知识点

1. (op>>j)&1:op的第j位是否是1
2. 本质考察递推，枚举出第一行的情况后，之后上一行的状态，决定下一行的开关的操作。然后对 符合条件的 中、上下、左右进行操作。最后判断 最后一行的情况，是否符合要求
3. 每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。那么我们用 try: except进行异常处理

题目5

[蓝桥杯 2017 省 AB] 分巧克力

题目描述

儿童节那天有 $K$ 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 $N$ 块巧克力，其中第 $i$ 块是 $H_i\times W_i$ 的方格组成的长方形。

为了公平起见，小明需要从这 $N$ 块巧克力中切出 $K$ 块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数。

2. 大小相同。

例如一块 $6\times 5$ 的巧克力可以切出 $6$ 块 $2\times 2$ 的巧克力或者 $2$ 块 $3\times 3$ 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小 $H_i$ 计算出最大的边长是多少么？

输入格式

第一行包含两个整数 $N$ 和 $K$。$(1\le N,K\le 10^5)$。

以下 $N$ 行每行包含两个整数 $H_i$ 和 $W_i$。$(1\le H_i,W_i\le 10^5)$。

输入保证每位小朋友至少能获得一块 $1\times 1$ 的巧克力。

输出格式

输出切出的正方形巧克力最大可能的边长。

样例 #1

样例输入 #1

2 10  
6 5  
5 6

样例输出 #1

2

提示

蓝桥杯 2022 省赛 A 组 I 题。

python代码

n,k=map(int,input().split())
data=[]
r=1 #找到最小的边长，即右边界
for i in range(n):
    a,b=map(int,input().split())
    
    data.append([a,b])
    r=max(r,a,b)
def check(s):
    sum1=0
    for i in range(n):
        l=data[i][0]//s#长切出来的
        w=data[i][1]//s#宽切出来的
        sum1+=l*w
    if sum1>=k:
        return True
    return False


l=1#左边界

while l<r:
    mid=(l+r+1)//2
    if check(mid):#向右查找
        l=mid
    else:#向左查找
        r=mid-1
print(l)

知识点

经典二分题目，那么按照步骤：

1. 边界，确保答案一定在这个边界内。左边l=1，右边不妨先取最大边长（一开始我取的是最小的边长，但是存在一种情况：某一块超级大的面包，直接满足所有需求，此时最小边长的那个面包都用不到）
2. 找一个判断条件：这道题就是，按照边长，切出来的面包数量>=人数
3. 确定是哪一种情况：满足条件的最大值，那么我们 令l=mid+1，计算r的时候，为mid-1（感觉模版太重要了，这两种模版可以解决所有的二分问题！）需要模版的可以看这篇文章：蓝桥杯python组备赛笔记（超详细版）或蓝桥杯python组备赛指南
4. 本题答案一定存在，故最后不用判别，否则，需要check(l)是否满足题目要求

题目6

[蓝桥杯 2017 省 B] k 倍区间

题目描述

给定一个长度为 $N$ 的数列，$A_1,A_2,\cdots A_N$，如果其中一段连续的子序列 $A_i,A_{i+1},\cdots A_j(i\le j)$ 之和是 $K$ 的倍数，我们就称这个区间 $[i,j]$ 是 $K$ 倍区间。

你能求出数列中总共有多少个 $K$ 倍区间吗？

输入格式

第一行包含两个整数 $N$ 和 $K$$(1\le N,K\le 10^5)$。

以下 $N$ 行每行包含一个整数 $A_i$$(1\le A_i\le 10^5)$。

输出格式

输出一个整数，代表 $K$ 倍区间的数目。

样例 #1

样例输入 #1

5 2
1  
2  
3  
4  
5

样例输出 #1

6

提示

时限 2 秒, 256M。蓝桥杯 2017 年第八届

python代码

n,k=map(int,input().split())
data=[]
N=10**5+1
s=[0 for _ in range(N)]#前缀和
for i in range(n):
    data.append(int(input()))
for i in range(1,n+1):
    s[i]=s[i-1]+data[i-1]
cnt=[0]*(n+1)#存放各余数的个数
ans=0
for i in range(n+1):
    ans+=cnt[s[i]%k]
    cnt[s[i]%k]+=1
print(ans)

知识点

1. 前缀和，注意下标一致
2. 转化问题为，右端点r固定时， (s[l]%k)==(s[r]%k),即余数相同的 方案个数：比如，余数为0的前缀和下标有3个，那么会有3种符合题意的方案
3. 前缀和需要注意下标问题，一般都是从1开始，这样才不会出错