如何做一个企业网站,浙江邮电建设工程有限公司网站,深圳网站建设迈,关键词查网址目录
一、试题B#xff1a;寻找整数
1、题目描述
2、我的想法
3、官方题解
4、另解
二、试题E#xff1a;蜂巢
1、题目描述
2、我的想法
3、官方题解
三、试题F#xff1a;消除游戏
1、题目描述
2、我的想法#xff08;AC掉58.3%#xff0c;剩下全超时#x…目录
一、试题B寻找整数
1、题目描述
2、我的想法
3、官方题解
4、另解
二、试题E蜂巢
1、题目描述
2、我的想法
3、官方题解
三、试题F消除游戏
1、题目描述
2、我的想法AC掉58.3%剩下全超时
3、官方题解
四、试题G全排列的价值
1、问题描述
2、我的想法AC掉25%剩下全超时
3、官方题解
五、试题H技能升级
1、题目描述
2、我的想法AC掉40%剩下全超时
3、官方题解
六、试题I最长不下降子序列
1、题目描述
2、我的想法
3、官方题解 一、试题B寻找整数
1、题目描述 本题为填空题只需要算出结果后在代码中使用输出语句将所填结果输出即可。 有一个不超过 10^17 的正整数 n知道这个数除以 2 至 49 后的余数如下表所示求这个正整数最小是多少。 运行限制 最大运行时间1s最大运行内存: 512M2、我的想法
填空题用C代码暴力判断估计跑久一点也会有结果吧。但是结果跑不出来。
3、官方题解
首先看出这是对 “中国剩余定理” 的考察不过需要选出质数作为模数。 证明不用考虑非质数 若x % a b 对于非质数a存在一个质数k使得a kt x am b k(tm) b x % k b % k b 非质数的等式可以替换为质数的等式故只需考虑质数 【中国剩余定理】 这里不探讨证明更多证明内容见中国剩余定理 - OI Wiki
【求逆元yk】 Mk*yk % mk 1 推出 Mk*yk mk*_ 1套用扩展欧几里得算法yk, _ exgcd(Mk, mk)扩展欧几里得算法 # 已知a, b求x, y使得ax by gcd(a, b)
def exgcd(a, b):if b 0: return 1, 0 #显然按照题目axby1的限制当b为0了a和x只能是1了y, x exgcd(b, a % b) #bn(a%b)mgcd(a,b)d故返回的是n,mreturn x, y - a // b * x 证明拓展欧几里得算法 (a,b) (b,a % b) 存在 x 和 y 使得 ax by gcd(a, b) d 存在 n 和 m 使得 bn (a%b)m d因为 b 和 a%b 的最大公约数也是 d 有 bn (a - a/b * b)m am b(n - a/b * m) d 因此 x m y n - a/b * m exgcd(b, a % b) 这一递归调用即求出 n 和 m分别赋值给 y 和 x 补充 计算两个正整数的最大公因数有两个比较常用的方法更相减损术和辗转相除法其中辗转相除法也叫欧几里得算法(,)(,%)。而扩展欧几里得算法是欧几里得算法的扩展废话广泛应用于 RSA 加密等领域。 定理若 a 和 b 为正整数则存在整数 x, y 使得 gcd(a,b)axby; 换句话说 gcd(a,b) 可以表示为 a,b 的整系数线性组合例如gcd(6,14)2而2(-2)*61*14。 已知整数 a、b扩展欧几里得算法可以在求得 a、b 的最大公约数的同时能找到整数x、y其中一个很可能是负数使它们满足贝祖等式 axbygcd(a,b)。有两个数 a,b对它们进行辗转相除法可得它们的最大公约数然后收集辗转相除法中产生的式子倒回去可以得到 axbygcd(a,b) 的整数解。 欧几里德算法停止的状态是 agcdb0 上面的思想是以递归定义的因为 gcd 不断的递归求解一定会有个时候 b0所以递归可以结束。 裴蜀定理 (,) 得名于法国数学家艾蒂安·裴蜀也叫贝祖音译问题说明了对任何整数 、 和它们的最大公约数 (,)关于未知数 和 的线性二元一次不定方程称为裴蜀等式一定存在整数 , 使 (,) 成立。它的一个重要推论是, 互质的充要条件是存在整数 , 使 1 。证明略去。代码如下
ps {2:1,3:2,5:4,7:4,11:0,13:10,17:0,19:18,23:15,29:16,31:27,37:22,41:1,43:11,47:5}
# ax by gcd(a, b)
def exgcd(a, b):if b 0: return 1, 0y, x exgcd(b, a % b)return x, y - a // b * xM 1
ans 0
for k in ps: M * k
for m, r in ps.items():Mi M // mt, _ exgcd(Mi, m) # t是Mi关于m的逆元ans r * Mi * tprint(ans % M)4、另解
解1
import os
import sys# 请在此输入您的代码
dp [(2,1),(3,2),(5,4),(7,4),(13,10),(19,18),(23,15),(29,16),(31,27),(37,22),(41,1),(47,5)]
lcm 187
res 187 #显然答案必定能整除11和17故res是按11*17187的倍数加
i 0
while i len(dp):if res % dp[i][0] dp[i][1]: #发现某一个187的倍数能“余”正确的数lcm * dp[i][0] #lcm就扩大为dp[i][0]位,这样res加上目前lcm就肯定能保持对应余数i 1else:res lcm
print(res)这个模拟让我十分震惊这个编程非常优秀。说明了一个事情不了解题目对应算法的时候也可以解题这时候你要尽量尝试用代码模拟一个可行的思路。补充这种查找为了加快时间初步判断就必须加大步长
解2
s 187
c 0
# 该整数是187的倍数且不能被2整除既为奇数
for i in range(187, 10 ** 17, 374): # 开始为187既步长为374if i % 49 46 and i % 48 41 and i % 47 5 and i % 46 15 and i % 45 29: # 因为需要哦的步长需要很大所以选数量较大的数c 1print(i)if c 5:break
print(12590206409 - 5458460249) # 7131746160
print(19721952569 - 12590206409) # 7131746160 发现规律开始满足条件的数是5458460249以后的间隔是7131746160的倍数mod [(2, 1), (3, 2), (4, 1), (5, 4), (6, 5), (7, 4), (8, 1), (9, 2), (10, 9),(11, 0), (12, 5), (13, 10), (14, 11), (15, 14), (16, 9), (17, 0), (18, 11), (19, 18),(20, 9), (21, 11), (22, 11), (23, 15), (24, 17), (25, 9), (26, 23), (27, 20), (28, 25), (29, 16),(30, 29), (31, 27), (32, 25), (33, 11), (34, 17), (35, 4), (36, 29), (37, 22), (38, 37), (39, 23),(40, 9), (41, 1), (42, 11), (43, 11), (44, 33), (45, 29), (46, 15), (47, 5), (48, 41),(49,46)]for i in tqdm(range(5458460249, 10 ** 17, 7131746160)): # 开始位置是5458460249 步长为7131746160for a, b in mod:if i % a ! b:breakelse:print(i) # for else结构当for正常执行结束则运行else语句break
二、试题E蜂巢
1、题目描述 【问题描述】 蜂巢由大量的六边形拼接而成定义蜂巢中的方向为0 表示正西方向1 表示西偏北 60 度2 表示东偏北 60 度3 表示正东4 表示东偏南 60 度5 表示西偏南 60 度。 对于给定的一点 O我们以 O 为原点定义坐标系如果一个点 A 由 O 点先向 d 方向走 p 步再向 (d2) mod 6 方向 ( d 的顺时针 120 度方向 ) 走 q 步到达则这个点的坐标定义为 (d, p, q)。在蜂窝中一个点的坐标可能有多种。 下图给出了点 B(0, 5, 3) 和点 C(2, 3, 2) 的示意。 给定点 (d1, p1, q1) 和点 (d2, p2, q2)请问他们之间最少走多少步可以到达? 【输入格式】 输入一行包含 6 个整数 d1, p1, q1, d2, p2, q2 表示两个点的坐标相邻两个整数之间使用一个空格分隔。 【输出格式】 输出一行包含一个整数表示两点之间最少走多少步可以到达。 【样例输入】 0 5 3 2 3 2 【样例输出】 7 【评测用例规模与约定】 对于 25% 的评测用例p1,p2≤10^3; 对于 50% 的评测用例p1,p2≤10^5; 对于 75% 的评测用例p1,p2≤10^7; 对于所有评测用例0≤d1,d2≤50≤q1p1≤10^90≤q2p2≤10^9。 【运行限制】 最大运行时间1s最大运行内存512M2、我的想法
该题令我不知如何下手一开始我是想以原点为中转计算距离后面发现这样走需要较复杂的逆处理且算不出最短距离遂作罢。
3、官方题解 本题是一道构造题考点有两个坐标转换、距离计算。蜂巢有 6 个方向看起来比较复杂但实际上走步非常简单。例如样例中从 B 走到 CC 在 B 的右下方B 只要一直向右向下走且不超过 C 的行和列不管怎么走一定能以最小步数走到 C。本题的难点是对坐标的处理。如果是简单的直角坐标系很容易计算。本题是六角形的蜂巢每个蜂巢的中心点是否能转为直角坐标显然是能转换成直角坐标的我们先巧妙的构建 “蜂巢” 坐标系。 先计算得到起点坐标 (x1y1)、终点坐标 (x2y2)。如何计算起点到终点的步数下面给出一个简单巧妙的方法。(确实很巧妙我他喵还能这么计算)坐标之差的绝对值 dx |x1-x2|dy |y1-y2|有以下结论结论自己观察一下图找找规律你会恍然大悟 1若 dx dy那么最少步数是 (dxdy)//2即先横着走再斜着走 2若 dx dy一直斜着走就行最少步数是dy。 代码如下
dx[-2,-1,1,2,1,-1]
dy[0,1,1,0,-1,-1]def walk(d,p,x,y):xxdx[d]*pyydy[d]*preturn x,yd1,p1,q1,d2,p2,q2map(int,input().split())
x1,y1walk(d1,p1,0,0)
x1,y1walk((d12)%6,q1,x1,y1)
x2,y2walk(d2,p2,0,0)
x2,y2walk((d22)%6,q2,x2,y2)ax,ayabs(x1-x2),abs(y1-y2)
if axay:print(ay)
else:print((axay)//2)当然也有其他解法这里就不另作讨论了。 这道题属于杂题杂题没有用到复杂算法不懂数据结构和算法的初学者也能做题目可难可易考核参赛者的思维和编码能力杂题在蓝桥杯和其他算法竞赛中都是常见且必不可少的题型三、试题F消除游戏
1、题目描述 【问题描述】 在一个字符串 S 中, 如果 SiS(i−1) 且 Si≠S(i1)则称 Si 和 Si1 为边缘字符。如果 Si≠Si−1 且 SiSi1, 则 S(i−1) 和 Si 也称为边缘字符。其它的字符都不是边缘字符。 对于一个给定的串 S一次操作可以一次性删除该串中的所有边缘字符 (操作后可能产生新的边缘字符)。 请问经过 2^64 次操作后字符串 S 变成了怎样的字符串, 如果结果为空则输出 EMPTY。 【输入格式】 输入一行包含一个字符串 S。 【输出格式】 输出一行包含一个字符串表示答案如果结果为空则输出 EMPTY。 【样例输入 1】 edda 【样例输出 1】 EMPTY 【样例输入 2】 sdfhhhhcvhhxcxnnnnshh 【样例输出 2】 s 2、我的想法AC掉58.3%剩下全超时
既然是一次性删除所有的边缘字符那么我就把当前字符串的所有边缘字符先选出来然后做好标记筛掉即可需要注意的是由于同一个边缘字符可能被选出2次我就用集合进行去重。
#这个模拟题解只能过58.3%
from copy import deepcopy
slist(input())
stop0
while stop2**64:pset()for i in range(1,len(s)-1):if s[i]s[i-1] and s[i]!s[i1]:p.add(i)p.add(i1)if s[i]!s[i-1] and s[i]s[i1]:p.add(i)p.add(i-1)if len(p)0: #提前结束标志s.join(s)print(s)breaks1[]for i in range(len(s)): #注意这里的范围啊每个位置都要判断一次if i not in p:s1.append(s[i])sdeepcopy(s1)p.clear()if len(s)0:print(EMPTY)breakstop1
可惜没办法全部AC掉。
3、官方题解 当删除字符后下一轮的边缘字符只与当前删除的字符有关即与当前删除字符的左右字符有关则在下一轮的判断中就不需要再遍历一遍新字符串了我们只需要标记住字符的左右字符然后循环处理即可。要想加快时间就必须牺牲空间。这告诉我要学会利用空间标记信息。代码如下
N10**610
pos[]
l,r[0]*N,[0]*N
st[False]*N
sinput()
nlen(s)
ss
# 构建双向链表
for i in range(1,n1):l[i]i-1r[i]i1
# 查找所有边缘字符
def check(i):if s[l[i]] or s[r[i]]:returnif s[l[i]]s[i] and s[r[i]]!s[i]:pos.append(r[i])pos.append(i)if s[l[i]]!s[i] and s[r[i]]s[i]:pos.append(l[i])pos.append(i)
def remove(j):r[l[j]]r[j]l[r[j]]l[j]# 删除j结点置为Truest[j]True
for i in range(1,n1):check(i)
while pos:ne[] #存储左右邻居for p in pos:if st[p]:continueremove(p)。 #删除当前结点的同时要更新左边的邻居邻居、更新右边邻居的邻居ne.append(l[p]) ne.append(r[p])pos[] #清空posfor e in ne: #对当前删除结点的左右邻居进行筛选判断是不是边缘字符因为新一轮的边缘字符只能在此产生if not st[e]:check(e)
ans
for i in range(1,n1):if not st[i]:anss[i]
if ans:print(ans)
else:print(EMPTY)
四、试题G全排列的价值
1、问题描述
蓝桥杯2022年第十三届省赛真题-全排列的价值 - C语言网
2、我的想法AC掉25%剩下全超时
对题目的描述进行简单模拟。
from itertools import *
nint(input())
lst[i for i in range(1,n1)]
cnt0
for i in permutations(lst):for j in range(1,n):for k in range(j):if i[k]i[j]:cnt1
print(cnt%998244353)
显然过不了。
3、官方题解 假定4个数排序 正排序1,2,3,4价值和为6反排序4,3,2,1的价值和为0正排序1,3,2,4价值和为5反排序4,2,3,1的价值和为1……依次推下去就会发现这种正排序和对应的反排序的价值和相加为一个定值6所以4个数排序就是24种排序方式12对排列式价值和也就有12个6总价值和就是72所以当输入n个数时就有 n!/2 对排列式而我们可以靠第一个正排序就能推出这个定值价值和说白了就是 0123就是一个简单的等差数列求和一对排列式的价值和就是 n(n-1)/2那么总价值和为 n!*n(n-1)/4 后面还是错了搜了半天才发现要边循环边取余不然后面数太大了要占时间。a int(input())
s a*(a-1)/4
for i in range(1,a1):s*is%998244353
print(int(s))
这提醒我们什么草稿纸和笔也很重要对于可能存在规律的题目我们可以用纸笔举例来推测规律。
五、试题H技能升级
1、题目描述
蓝桥杯2022年第十三届省赛真题-技能升级 - C语言网
2、我的想法AC掉40%剩下全超时
模拟每次升最大的攻击力然后更新攻击力和减少一次更新次数。
from math import *
n,mmap(int,input().split())
p[]
cnt0
for _ in range(n):a,bmap(int,input().split())p.append([a,b][ceil(a/b)])
p.sort(keylambda x:x[0],reverseTrue)
#print(p)
for _ in range(m):if p[0][2]0 and p[0][0]0:cntp[0][0]p[0][2]-1p[0][0]-p[0][1]p.sort(keylambda x:x[0],reverseTrue)
print(cnt)技巧用好列表的 sort()同时利用数组存储同一个“关系”的信息。
3、官方题解
二分法。有一说一这代码我也没看懂这道题估计考试的时候拿40%我就很满足了。
def check(x):res 0for i in range(n):if A[i] x:res (A[i]-x)//B[i] 1return resn,m map(int,input().split())
A [-1]*(n1) #首次提升的攻击力
B [-1]*(n1) #每次提升后减少的点数
for i in range(n):a,b map(int,input().split())A[i],B[i] a,bl,r 0,2*10**6
while l r:mid (lr1) 1 #最后一次技能加点的攻击力if check(mid) m: l midelse: r mid - 1
ans 0
for i in range(n): #遍历每一个攻击力看每一个被减了多少次if A[i] r:t (A[i]-r) // B[i] 1 # 减了多少次if A[i]-(t-1)*B[i] r : t-1m - t # m的次数减去tans (t * (2 * A[i] - (t - 1) * B[i])) / 2print(int(ans m*r))六、试题I最长不下降子序列
1、题目描述
蓝桥杯2022年第十三届省赛真题-最长不下降子序列 - C语言网 (dotcpp.com)
2、我的想法
世上最痛苦的事情莫过于此悲我看着这题第一反应就是dp第一思路如下代码所示。
n,kmap(int,input().split())
Alist(map(int,input().split()))for i in range(n-k): #枚举每一种更换成k的情况for j in range(i,ik):# 1.换数# 2.求不下降子序列的长度# 3.更新最值
我卡在了 “1.换数” 这一步。该换什么数要怎么换是我没有想清楚的。
3、官方题解
暂无找到python版很好的相关题解其中有个C的 权值线段树离散化动态规划 解法比较不错待后面我复习一下相关算法内容弄懂C代码再复刻一个Python代码出来。 以上第十三届蓝桥杯省赛Python大学B组复盘
祝好
