第十三届蓝桥杯大学A组题解（Python）

发布时间：2022-12-11 17:30

写在前面：

KS感觉这次比赛....Emmm一言难尽，贴吧充斥着车队，B站传着退费视频...

Whatever ，既然报了名并且用心准备了，那就全力以赴

本次考试特点：模拟模拟模拟！从头模到尾！

学了那么久的暴力算法居然只能被冷藏...

———————————————————————————————————————————

* 这次的战果是1道填空 + 7道大题本篇博客中大题的代码都通过了样例并不能保证AC

* 如果我任何表达不清或者有任何不理解之处可以留言交流我会在看到的第一时间做出回答！

* 如有错误欢迎指出！

Start ：

第一题：没啥好说的了.. 签到题实锤注意不要想去怎样写代码这题纯纯的手算题初中数学

答案： 443

这道题KS并没有写出来除了暴力求解我也确实没想到什么好的算法（我是fw

微信群有一哥们直接写了考试日期：2022040920220409 据说是正确答案

思路：先用素数筛筛出小于n的所有素数再判断是否能被n整除

n = int(input())

Flag = [True for i in range(n+1)]
for i in range(2,int(n**(0.5))+1) : # 素数筛
    if Flag[i] :
        tmp = i+i
        while tmp < n+1 :
            Flag[tmp] = False
            tmp += i
Sum = 0
for i in range(2,n+1) : # 判断因数
    if n % i == 0 and Flag[i] :
        Sum += 1
print(Sum)

我着实没想到第二个大题就让我无从下手...

如果有哪位大佬写出来了或者有思路欢迎私信我或者在留言区教一下KS...

这道题目还是有点意思一眼看上去很难但其实只要我们对两个样例模拟一下操作过程很容易想到解决办法（实在不行直接打印EMPTY估计也能骗几个测试点

思路：用一个while循环出循环的条件是：要么字符串为空要么这轮循环得到的字符串与上一轮循环得到的字符串相同即后续的操作已经不能再影响字符串了所以2^64就是吓人用的..

Convert函数：用于转换字符串模拟裁切边缘字符的过程我们判断每两个相邻的字符若满足边缘字符的定义则取出他们的index放入备用集合中最后返回对应索引不在集合里的字符组成的新字符串


s = input()
def convert(string) :
    res = []
    tmp = set()
    string = list(string)
    for i in range(len(string)) :
        if i == 0 or i == len(string)-1 :
            continue
        else :
            if string[i] == string[i-1] and string[i] != string[i+1] :
                tmp.add(i)
                tmp.add(i+1)
            if string[i] != string[i-1] and string[i] == string[i+1] :
                tmp.add(i-1)
                tmp.add(i)
    
    for i in range(len(string)) :
        if i not in tmp :
            res.append(string[i])
    res = "".join(res)
    return res

while 1 :
    new_string = convert(s)
    if s == new_string :
        print(s)
        break
    if new_string == '' :
        print('EMPTY')
        break
    s = new_string

思路：这道题思路还是很好想的无非就是让重合次数最多的区间的值尽可能的大所以我们只需要算出每一个点被几个区间所包含再排序将原数组里的值由大到小赋给被排好序的点即可

import copy
n = int(input())
numList = list(map(int,input().split()))
temp = copy.deepcopy(numList)
temp.insert(0,0)
numList.sort()
m = int(input())
cmd = []
for i in range(m) :
    cmd.append(list(map(int,input().split())))

numList.insert(0,0)
count = dict((i,0)for i in range(1,n+1)) # 用字段储存每个点的访问次数
for item in cmd :
    for i in range(item[0],item[1]+1) :
        count[i] += 1

newCount = []
for i in count.keys() :
    newCount.append((i,count[i])) # 将字典转化为元组排序
newCount.sort(key=lambda x:x[1],reverse=True)

ans = [0 for i in range(n+1)]
for i in range(n) :
    tmp1,tmp2 = newCount[i]
    tmp = numList.pop() # 取出最大的数
    ans[tmp1] = tmp
out = 0
for i in range(m) :
    out += (sum(ans[cmd[i][0]:cmd[i][1]+1])-sum(temp[cmd[i][0]:cmd[i][1]+1]))
print(out)

这题... KS可以很明确地说不可能AC了考场时我的思路是看能不能找到每组数的规律[1,3]

[1,4],[1,5]... 奈何时间有限消磨了不少时间最后也没找到规律不知道是不是思路错了没有办法只能写了个暴力上去... 能骗几分算几分吧...


import itertools

n = int(input())
numList = [i for i in range(1,n+1)]
def check(lst) :
    res = []
    for i in range(len(lst)) :
        tmp = 0
        for j in range(i) :
            if lst[i] > lst[j] :
                tmp += 1
        res.append(tmp)
    return sum(res)%998244353
ans = 0
for item in itertools.permutations(numList) :
    ans = (ans + check(list(item)))%998244353
print(ans)

思路：最长上升子序列模版题了特判一下是否为全上升的序列若不是直接输出最长上升子序列+K即可否则输出N


def check(lst) :
    for i in range(1,len(lst)) :
        if lst[i] < lst[i-1] :
            return False
    return True

N,K = map(int,input().split())
numList = list(map(int,input().split()))
if check(numList) :
    print(N)
else :
    dp = [1 for i in range(N)]
    for i in range(N) :
        for j in range(i) :
            if numList[i] >= numList[j] :
                dp[i] = max(dp[i],dp[j]+1)
    ans = dp[-1] + K
    print(ans)

思路：贪心+模拟 while循环只要还有相邻的两个数都不为0 就一起-1 直到不能再减为止此时剩下数的和是几就加几

import copy
n,K = map(int,input().split())
numList = list(map(int,input().split()))
count = 0
def check(lst) :
    if 0 in lst :
        return False
    return True
while 1 :
    tmp = copy.deepcopy(numList)
    for i in range(n-K+1) :
        if check(numList[i:i+K]) :
            count += 1
            for j in range(i,i+K) :
                numList[j] -= 1
    if tmp == numList :
        break
for i in range(n) :
    count += numList[i] 
print(count)

思路：这题考查方向主要还是数论具体来说：有这样几类数是表示不出来的：

1 质数

2 合数但该合数不断除2或者不断除3后得到了个质数

3 不断除2直到不能除再不断除3 若只能除一次3 则不符合

或者不断除3 再不断除2 若只能除一次2 则不符合

import copy
T = int(input())
cmd = []
for i in range(T) :
    cmd.append(int(input()))
maxNum = max(cmd)
flag = [True for i in range(maxNum+1)]
for i in range(2,int(maxNum**(0.5))+1) :
    if flag[i] :
        tmp = i + i
        while tmp <= maxNum :
            flag[tmp] = False
            tmp += i
flag[0],flag[1] = False,False

def check1(num) :
    tmp1 = copy.deepcopy(num)
    while tmp1%3 == 0 :
        tmp1 //= 3
    count = 0
    while tmp1%2 == 0 :
        tmp1 //= 2
        count += 1
    if count == 1 :
        return False
    tmp2 = copy.deepcopy(num)
    count = 0
    while tmp2%2 == 0 :
        tmp2 //= 2
    while tmp2%3 == 0 :
        tmp2 //= 3
        count += 1
    if count == 1 :
        return False
    return True
def check2(num) :
    if flag[num] == False :
        return True
    return False
def check3(num) :
    tmp1 = copy.deepcopy(num)
    tmp2 = copy.deepcopy(num)
    while tmp1 % 2 == 0 :
        tmp1 //= 2 
    if flag[tmp1] == True and tmp1 != 3:
        return False
    while tmp2 % 3 == 0 :
        tmp2 //= 3 
    if flag[tmp2] == True and tmp2 != 2:
        return False
    return True

for item in cmd :
    if check2(item) :
        if check3(item) :
            if check1(item) :
                print('yes')
            else :
                print('no')
        else :
            print('no')
    else :
        print('no')

————————————————————————————

写在最后：一年一次蓝桥杯省赛就这样结束了我相信认真准备的人一定会有所收获如果我运气够好我们国赛再见！

第十三届蓝桥杯大学A组题解（Python）

本次考试特点 ：模拟模拟模拟！从头模到尾！

学了那么久的暴力算法居然只能被冷藏...

Start ：

————————————————————————————

写在最后 ： 一年一次蓝桥杯省赛就这样结束了 我相信认真准备的人一定会有所收获 如果我运气够好 我们国赛再见！

相关推荐

本次考试特点：模拟模拟模拟！从头模到尾！

写在最后：一年一次蓝桥杯省赛就这样结束了我相信认真准备的人一定会有所收获如果我运气够好我们国赛再见！