明天就是第十三届蓝桥杯，在这最后的关头，我来抱抱佛脚，把去年的题目做一个总结和复盘，希望能够得到一些提升，其实填空题我之前做过复盘，但是嘛，那个时候还很稚嫩，写的不是很好，有时候自己也不是很懂自己在写什么东西，所以就重新写了一遍。
题
解
:
题解:
题解:我看了一些网上的题解，他们都是循环，一个一个的去计数，但是实际上我们仔细研读题目就能发现，这道题用不了这么复杂。
因为不论最后结果是百位、千位甚至万位，我们都能轻松发现，1肯定是最先用完的（因为不论几位数一开始肯定是1先打头嘛），那其实我们只用计量1出现的次数不超过2021次就好了，但是我们需要处理一个小细节。
因为最后的答案是
3181
3181
3181嘛，那么问题就是第2021个1究竟是这里面的第一个1还是第二个1，这个需要我们去检验，检验的结果是第二个1，所以直接把
3181
3181
3181贴上去就好了。
count = 0
for i in range(10000):
for j in str(i):
if j == "1":
count += 1
if count == 2021:
print(i)
break
# 太懒，就不检验了
题
解
:
题解:
题解:我们都知道，直线有两个关键的参数，一个是斜率
k
k
k，一个是截距
b
b
b，一根完整的直线应该包括这两个方面最后构成
y
=
k
x
+
b
y=kx+b
y=kx+b的形式，所以，我们需要做的判断就是寻找到这道题里面所有不同的
[
k
,
b
]
[k,b]
[k,b]的集合，当然，同时我们不能忘记有20条竖直的直线是没有斜率的，直接在最后的结果上加上它们就行了。
def check_b(x1, y1, x2, y2): # 定义方法，寻找截距
b = (x1*y2 - x2*y1) / (x1-x2)
return b
def check_k(x1, y1, x2, y2): # 寻找斜率
k = (y1-y2)/(x1-x2)
return k
if __name__ == "__main__":
coordinate, features = [], [] # 存储坐标、存储特征(b、k)
for i in range(20):
for j in range(21):
coordinate.append([i, j]) # 装下所有的坐标
for i in coordinate:
for j in coordinate:
if i != j: # 相同的点不存在或者说存在无数条直线，不符合题意
if i[0] == j[0]:
"""
排除掉x1==x2的情况，因为我们前面定义check_b、check_k的时候
是忽略掉了这种情况，不拍出去的话会报错
"""
continue
else:
b = check_b(i[0], i[1], j[0], j[1])
k = check_k(i[0], i[1], j[0], j[1])
b_k = [b, k]
if b_k not in features:
"""
如果特征[b, k]不在特征集合里面，就将它存储进去
"""
features.append(b_k)
print(len(features)+20) #ans = 40257
题
解
:
题解:
题解:找到
n
n
n的所有因数，遍历相乘即可，但是如果遍历
n
n
n一次的话跑不出结果，但其实我们不需要遍历
n
n
n，遍历
n
\sqrt{n}
n
即可，然后存储
i
i
i和
n
/
i
n/i
n/i(
i
i
i是
n
n
n的因数)，然后遍历三层，判断积是否为
n
n
n即可。
n, judge, ans = 2021041820210418, [], 0
for i in range(1, int(n**(1/2)+1)):
if n % i == 0:
judge.append(i)
judge.append(n // i)
for L in judge:
for H in judge:
for W in judge:
if L * H * W == n:
ans += 1
print(ans)
题
解
:
题解:
题解:传统的思路当然就是先创建路径，然后遍历，但是这样的话很难说深搜能不能出结果。
所以需要我们换一个思路。
我们先化简问题，将其分解为两个部分，一是创建路径，二是寻找最短路径，第一个问题跟着题意走即可，我们重点看第二个问题。
本题要求我们考虑
1
−
2021
1-2021
1−2021的最短路径，但是其实
2021
2021
2021只与
2000
−
2020
2000-2020
2000−2020相连，那么这个问题就变成了寻找
m
i
n
(
m
i
n
[
1
−
2000
]
+
d
(
2000
−
2021
)
,
m
i
n
[
1
−
2001
]
+
d
(
2001
+
2021
)
,
.
.
.
,
m
i
n
[
1
−
2020
]
+
d
(
2020
−
2021
)
min(\color{#F00}{min[1-2000]+d(2000-2021)}, \color{#F80}min[1-2001]+d(2001+2021),...,\color{#0F0}{min[1-2020]+d(2020-2021)}
min(min[1−2000]+d(2000−2021),min[1−2001]+d(2001+2021),...,min[1−2020]+d(2020−2021)
)
)
)，那么同上，对于任意一个
2000
−
2020
2000-2020
2000−2020的最短距离求解方法也是同上，然后依次递归回去，一直递归到求1-23的最短距离，即
m
i
n
[
1
−
23
]
=
m
i
n
(
m
i
n
[
1
−
2
]
+
d
(
2
−
23
)
,
m
i
n
[
1
−
3
]
+
d
(
3
+
23
)
,
.
.
.
,
m
i
n
[
1
−
22
]
+
d
(
22
−
23
)
min[1-23] = min(\color{#F00}{min[1-2]+d(2-23)}, \color{#F80}min[1-3]+d(3+23),...,\color{#0F0}{min[1-22]+d(22-23)}
min[1−23]=min(min[1−2]+d(2−23),min[1−3]+d(3+23),...,min[1−22]+d(22−23)
)
)
)，然后用同样的方法求解
m
i
n
(
1
−
24
)
,
m
i
n
(
1
−
25
)
.
.
.
m
i
n
(
1
−
2021
)
min(1-24), min(1-25)...min(1-2021)
min(1−24),min(1−25)...min(1−2021)
我们前面说过动态规划的两个要点，一是最小子问题， 二是递推公式，很明显，前面的推理是符合这两个条件的，所以这道题可以采用动态规划的方法。
那现在摆在我们面前的还有最后一个问题——递推公式是什么，如果按照前面的写法（彩色的那一堆），原则上来说是能写的，但是很麻烦，所以我们需要考虑优化一下，既然说是动态规划，那肯定要体现一个动字，那我们就对每一个点搜索后面21个点（最后21个灵活处理就是了），具体来说，对第
i
i
i个点搜索
i
+
1
,
i
+
2
,
.
.
.
i
+
21
i+1, i+2, ... i+21
i+1,i+2,...i+21，记为
j
j
j，对第
j
j
j个点就是
d
p
[
j
]
=
m
i
n
(
d
p
[
j
]
,
d
p
[
i
]
+
d
(
i
−
j
)
dp[j]=min(dp[j], dp[i]+d(i-j)
dp[j]=min(dp[j],dp[i]+d(i−j)dp记为第
1
1
1个点到当前位置的距离。
这里注意一个小细节，一开始我是直接**range(2021)**创建列表，但是这样的话，求出来的就变成了
0
0
0与后面的公倍数定义距离了，那最后距离什么的都变了，所以还是老老实实创建2022个，从 列表序第
1
1
1个开始求最小公倍数。
import math
def least_multiple(a, b): # 求最小公倍数定义两点间距离
result = a * b / math.gcd(a, b)
return int(result)
dp = [float("inf") for i in range(2022)] # 创建动规列表
dp[1] = 0 # 定义初始距离
for i in range(1, 2022):
for j in range(i+1, i+22):
if j > 2021:
break # 超过2021的点直接跳出循环
dp[j] = min(dp[j], dp[i] + least_multiple(i, j)) # 递推公式
print(dp[-1])
题 解 二 : 题解二: 题解二:;当然，这只是比较巧妙的方法，但是很明显，这是一个最短路径问题，那么很传统的、自然的， 迪 杰 斯 特 拉 算 法 迪杰斯特拉算法 迪杰斯特拉算法出现得那么自然，代码如下（思路就不贴了，可以自己搜索一下算法思路），好吧，代码也是去年的：
#路径
import math
dict1 = {} #由于这是一个加权图的问题，就用字典，它可以形象的表示每一个点与哪几个点连接，并且用key表示与它连接的点，key后面的value就表示权
def gcd(m,n): #这是一个求最大公约数的函数，放心，我没有失心疯，还记得是求最小公倍数
m,n = int(m),int(n)
s = math.gcd(m,n)
return s
for i in range(1,2022):
dict1[i] = {}
for r in range(i,i+22):
if r <= 2021:
dict1[i][r] = int(i*r/gcd(i,r)) #dict的key不用提前确定，可以临时赋名，十分方便
else:
continue
dict1[i][i] = 0 #有兴趣的可以print一下看看，当然，我用的2021，太大了，可以改小了再看
def Dijkstra(G, v0, INF=999999999999999): #重头戏来了！！！
book = set()
minv = v0
dis = dict((k, INF) for k in G.keys())
dis[v0] = 0
while len(book) < len(G):
book.add(minv)
for w in G[minv]:
if dis[minv] + G[minv][w] < dis[w]: #寻找最小
dis[w] = dis[minv] + G[minv][w]
new = INF
for v in dis.keys():
if v in book: continue book的作用与第三题的几个list一样，防止重复
if dis[v] < new:
new = dis[v] #锲而不舍地找最小
minv = v
return dis
dis = Dijkstra(dict1, v0=1)
print(max(dis.values())) #dis.value里面存储的是经历过每一个点的值，所有要找最大的
这道题不能说难吧，只能说做不出来。
不简单，在考场上属于建议放弃的题目。
闲话到此，看题。
题
解
:
题解:
题解:其实还是和上面一样，创建路径，然后搜索，但是很明显，创建的路径太多，搜索的话跑不出来。
这个时候我们就考虑动态规划，但是其实我们后验的知道，普通规划也是跑不出结果的，是需要采用状压DP才能抛出结果的，其基本思路是采用二进制存储21个楼栋的状态，比如3栋楼，访问所有楼栋状态就是
111
111
111，初始状态就是
100
100
100（二进制），那么对于
n
n
n栋楼，其状态就有
1
<
<
n
(
2
21
)
1< 对于这个状压DP来说，我们的想法就是，
d
p
[
i
]
[
j
]
d p [ i ] [ j ]
dp[i][j]对于状态
i
i
i，
i
i
i的二进制表示中为1的位置，表示走过了教学楼
j
j
j 上述引用引自CSDN博主风信子的猫Redamancy的文章，他在B站也有视频讲解，大家可以自己去看看。
挖
坑
:
挖坑:
挖坑:状压DP是一种很有效的方法，这里我们挖个坑，蓝桥杯结束后，两周之内，我会出几篇文章讲讲这种方法。 可以发现，每一条斜线对应的就是
C
n
−
1
i
−
1
C_{n-1}^{i-1}
Cn−1i−1（其中
n
n
n代表第
n
n
n行，
i
i
i代表第
i
i
i条斜线） 一、第二条斜线。
C
4
2
=
6
=
>
(
1
+
2
+
3
+
4
)
+
1
+
2
=
13
C_4^2=6 =>(1+2+3+4)+1+2=13
C42=6=>(1+2+3+4)+1+2=13 剩下的就是二分查找了，重要的就是找到
t
a
r
g
e
t
target
target等于哪个组合数 这道题想了一会，首先来说对于每一个人，我们都有两种选择，既然足够聪明，就有两种想法，第一是让自己的数更大，第二就是让别人的数更小，所以对于先手来说，由于两个人都是0，所以会选择较大的数对自己异或 我们会发现，这时候先手是一定赢的，因为他的最高位是1。 所以就可以总结一下 思路引自（
c
o
p
y
\cancel{copy}
copy
）CSDN博主风信子的猫Redamancy，因为明天就要比赛了，现在也挺晚了，就不写自己的思路了，但是我的思路和这位博主大同小异，就引用来了。 因为明天就是蓝桥杯了，然后我本人现在也在做数学建模，时间不是很够，就引用了一些别人的思路，等这周忙过去之后，我再把这些引用别人思路的题目单独写一次（又挖一个坑），争取把不会的也变会。 欢迎分享，转载请注明来源：内存溢出
我们会枚举每一个状态，对于每一位来说，我们都会判断状态
i
i
i是否包含第
j
j
j栋教学楼，如果包含的话，就会进行判断其他位，枚举所有可能从教学楼
k
k
k走到教学楼j的情况，加入我们的状态
i
i
i除去
j
j
j后还包含
j
j
j的话，我们就可以加入其中的方案
d
p
[
i
]
[
j
]
+
=
d
p
[
i
−
(
1
<
<
j
)
]
[
k
]
d p [ i ] [ j ] + = d p [ i − ( 1 < < j ) ] [ k ]
dp[i][j]+=dp[i−(1<<j)][k] ( 从 教 学 楼 k 走 到 教 学 楼 j )
最后我们就可以得到所有的方案，不过要减去j状态为0时候的方案，因为我们一开始就是从0，也就是第一件教学楼出现的。from math import gcd
n = 21
m = 1 << n # 一共有2的21次方个状态
dp = [[0]*n for i in range(m)] # dp[i][j]对于状态i，i的二进制表示中为1的位置 表示走过了教学楼j
load = [[False]*n for i in range(n)] # 存储i, j之间是否有路
for i in range(1,n + 1):
for j in range(1,n + 1):
if gcd(i, j) == 1:
load[i-1][j-1] = True
dp[1][0] = 1 # 表示初始状态，也就是第二个状态 0000...0001 第一位为1
for i in range(1,m): # 枚举每一个状态
for j in range(n): # 对每一位 判断状态i是否包含第j栋教学楼
if i >> j & 1: # 如果第j+1位为1
for k in range(n): # 判断其他位 枚举所有可能从教学楼k走到教学楼j的情况
if (i - (1<<j)) >> k & 1 and load[k][j]: # 判断状态i除去j后是否包含k
dp[i][j] += dp[i-(1<<j)][k]
print(sum(dp[m-1]) - dp[m-1][0])
题
解
:
题解:
题解:简单的处理一下，由于给的是毫秒，首先先（
n
/
/
1000
n//1000
n//1000)抛掉后三位没用的数，然后求出一天有多少秒
d
a
y
_
s
e
c
o
n
d
day\_second
day_second , 然后
n
%
d
a
y
_
s
e
c
o
n
d
n \% day\_second
n%day_second，求出一天之内的秒数，然后由秒、分、时这样算就行。
G.杨辉三角
n = int(input())
n //= 1000 # 舍去毫秒
day = 24 * 60 * 60
n %= day # 找出一天之内的秒数
s = n % 60 # 剩余的秒数
n //= 60 # 剩余分钟数
m = n % 60 # 分钟数
n //= 60
h = n
print("{:02d}:{:02d}:{:02d}".format(h,m,s))
题
解
:
题解:
题解:难就一个字，这道题的方法很巧妙，需要我们仔细观察杨辉三角。
红线代表第
那其实我们的目标就是找到
t
a
r
g
e
t
=
C
n
−
1
i
−
1
target = C_{n-1}^{i-1}
target=Cn−1i−1，然后找规律
C
5
2
=
10
=
>
(
1
+
2
+
3
+
4
+
5
)
+
1
+
2
=
1
C_5^2=10=>(1+2+3+4+5)+1+2=1
C52=10=>(1+2+3+4+5)+1+2=1
C
7
1
=
7
=
>
(
1
+
2
+
3
+
4
+
5
+
6
+
7
)
+
1
+
1
=
30
C_7^1=7=>(1+2+3+4+5+6+7)+1+1=30
C71=7=>(1+2+3+4+5+6+7)+1+1=30
规律总结如下：
C
n
q
=
∑
i
=
1
n
i
+
q
+
1
=
n
(
n
+
1
)
2
+
q
+
1
C_n^q=\sum_{i=1}^ni+q+1=\frac{n(n+1)}{2}+q+1
Cnq=i=1∑ni+q+1=2n(n+1)+q+1
H.左孩子右兄弟（不会）
I.异或数列
def C(a, b):
res = 1
for i in range(a, a-b, -1):
res *= i
for j in range(1, b+1):
res //= j
return res
def search(k):
low, high = 2 * k, target
if high <= low and C(low, k) != target:
return False
while low <= high:
mid = low + (high - low) // 2
val = C(mid, k)
if val > target:
high = mid - 1
elif val < target:
low = mid + 1
else:
print(int(mid * (mid + 1) / 2) + k + 1)
return True
return False
if __name__ == "__main__":
target = int(input())
for i in range(16, -1, -1):
"""
C(32，16)其实大于题目给定范围，所以从这里开始搜索就可以了
"""
if search(i):
break
这里要记住两个异或的重要公式：a^a = 0, a ^ 0 = a
那我们判断一下，其实我们可以发现 a^b = X1^ X2 ^ X3… Xn，若a^b = 0，也就是说明我们的a=b,也就是平局的情况，所以会对所有数进行异或，如果sum=0，就说明是平局
其次就是sum！=0的情况，对于这种情况来说，我们就需要看最高位了，比如100的最高位是第3位为1，我们就要看最高位为one的个数了
例如我们有A,B,C三个最高位都为1的数，那我们对于我们先手来说，就会先把最大数的和自己异或，保证自己的数最大
之后可能
1.后手用B与先手的a异或，使其的最高位为0，然后先手再拿C与自己的数异或，最高位还是1。
2.或者是后手用B与自己数异或，使自己的数最高位为1，然后先手就会用C使其后手的数异或，让他变为1。
但是假设，我们还有最高位为0的数，如果多一个数，那么我们的后手就会把先手的最高位变成0，那么后手就赢了，如果有两个，那么先手就可以与自己的数异或，使自己的数的最高位还是1。
1.第一种情况：sum=0,说明Alice和Bob一定平手
2.第二种情况：sum!=0
计算出最大数的最大数位，假设是第i位，设这些数中有one个数在该为1，zero个数在该位为0
a.如果one是偶数，说明判断不出来，继续枚举下一位。
b.如果one是奇数，one只有一个，一定是Alice赢
one>1,zero是偶数，一定是Alice赢
one>1,zero是奇数，一定是Bob赢
J.括号序列（不会）
写在最后
t=int(input())
for i in range(t):
a=[]
sum=0
ma=0
mp=list(map(int,input().split()))
for i in range(1,len(mp)):
a.append(mp[i])
sum^=mp[i]
ma=max(ma,mp[i])
if sum==0:
print(0)
continue
i=1
while i<ma:
i<<=1
while i>0:
one=0
zero=0
for ele in a:
if ele&i!=0:
one+=1
else:
zero+=1
if one%2==1:
if zero%2==1 and one>1:
print(-1)
else:
print(1)
break
i>>=1
最后，祝大家比赛顺利。
微信扫一扫
支付宝扫一扫
评论列表（0条）