2023年藍(lán)橋杯??省賽真題
Python大學(xué)A組
? ? ? ??試題A：特殊日期
????????試題B：分糖果
????????試題C：三國(guó)游戲
????????試題D：平均
????????試題E：翻轉(zhuǎn)
? ? ? ??試題F：子矩陣
????????試題G：階乘的和
????????試題H：奇怪的數(shù)
????????試題I：子樹的大小
? ? ? ??試題J：反異或01串
試題A：特殊日期? ?（5分）
【問題描述】
????????記一個(gè)日期為 yy 年 mm 月 dd 日，統(tǒng)計(jì)從 2000 年 1 月 1 日到 2000000 年?1 月 1 日：有多少個(gè)日期滿足年份 yy 是月份 mm 的倍數(shù)，同時(shí)也是 dd 的倍數(shù)。
【答案提交】
????????這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一個(gè)整數(shù)，在提交答案時(shí)只輸出這個(gè)整數(shù)，輸出多余的內(nèi)容將無法得分。
【解析與方法】
? ? ?? ?最簡(jiǎn)單粗暴的方法就是直接從2000年1月1日遍歷到2000000年1月1日，使用這種方法寫建議使用C++來寫，運(yùn)行速度快一些，Python跑的滿。Python雖然有比較好用的datetime包，但是Python的datetime對(duì)象可以表示的日期范圍從公元1年1月1日到公元9999年12月31日。題目給的最大日期已經(jīng)超了，一跑就報(bào)錯(cuò)。所以還是直接暴力跑方便點(diǎn)且不容易出錯(cuò)。
【Python程序代碼】文章來源：http://www.zghlxwxcb.cn/news/detail-756085.html
mon = [0,31,28,31,30,31,30,31,31,30,31,30,31]
def run(x): #判斷是否為閏年
if x%400==0 or (x%4==0 and x%100!=0):
return True
return False
res = 0
for year in range(2000,2000000):
if run(year):
mon[2]=29
else:
mon[2]=28
for mm in range(1,13):
for dd in range(1,mon[mm]+1):
if year%mm==0 and year%dd==0:
res += 1
print(res+1) #前面只迭代到了1999999年12月31日，最后2000000年1月1日也是一個(gè)答案最終結(jié)果為：35813063
?拓展：datetime對(duì)象的使用方法
from datetime import datetime, timedelta
# 定義開始和結(jié)束日期
start_date = datetime(2023, 1, 1)
end_date = datetime(2024, 1, 1)
# 定義時(shí)間間隔
delta = timedelta(days=1)
# 迭代日期范圍
while start_date <= end_date:
year = start_date.year
mon = start_date.month
day = start_date.day
print("%04d-%02d-%02d"%(year,mon,day))
#print(start_date.strftime("%Y-%m-%d"))
start_date += delta試題B：分糖果? ? ?（5分）
【問題描述】
????????兩種糖果分別有9個(gè)和16個(gè)，要全部分給7個(gè)小朋友，每個(gè)小朋友得到的糖果總數(shù)最少為2個(gè)最多為5個(gè)，問有多少種不同的分法，糖果必須全部分完。
? ? ? ? 如果有其中一個(gè)小朋友在兩種方案中分到的糖果不完全相同，這兩種方案就算作不同的方案。
【答案提交】
????????這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一個(gè)整數(shù)，在提交答案時(shí)只輸出這個(gè)整數(shù)，輸出多余的內(nèi)容將無法得分。
【解析與方法】
? ? ? ??已知兩種糖果的數(shù)量分別為9個(gè)和16個(gè)，每個(gè)小朋友最少分2個(gè)糖果，最多分5個(gè)糖果，由此可以把每中分發(fā)情況（a，b糖果每種分幾個(gè)）都枚舉出來。如下表格：
| a | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | 5 |
| b | 2 | 1 | 0 | 3 | 2 | 1 | 0 | 4 | 3 | 2 | 1 | 0 | 5 | 4 | 3 | 2 | 1 | 0 |
? ? ? ? 因此根據(jù)已知的情況，可以采用暴力搜索的方式了，外加上方案成立的一個(gè)必要條件，糖果全部分完就可以確認(rèn)方案是否成立。
【Python程序代碼】
import sys
sys.setrecursionlimit(1000000) #設(shè)置遞歸深度可以不需要
a = [0,1,2,0,1,2,3,0,1,2,3,4,0,1,2,3,4,5]
b = [2,1,0,3,2,1,0,4,3,2,1,0,5,4,3,2,1,0]
ans = 0
def dfs(u,c1,c2):
global ans
if u==7:
if not c1 and not c2: #判斷是否全部分完
ans += 1
else:
for i in range(len(a)):
if c1>=a[i] and c2>=b[i]:
dfs(u+1,c1-a[i],c2-b[i])
dfs(0,9,16)
print(ans)最終結(jié)果：5067671
試題C：三國(guó)游戲? ? ?（10分）?
【問題描述】
? ? ? ? 小藍(lán)正在玩一款游戲，游戲中魏（X）、蜀（Y）、吳（Z）三個(gè)國(guó)家各自擁有一定數(shù)量的士兵X、Y、Z（一開始可以認(rèn)為都是0）。游戲有n個(gè)可能會(huì)發(fā)送的事件，每個(gè)事件之間相互獨(dú)立且最多只發(fā)送一次，當(dāng)?shù)趇個(gè)事件發(fā)送時(shí)會(huì)分別讓X、Y、Z增加??.
? ? ? ? 當(dāng)游戲結(jié)束時(shí)（所以事件的發(fā)生與否已經(jīng)確定），如果X,Y,Z的其中一個(gè)大于另外兩個(gè)之和，我們認(rèn)為其獲勝。例如，當(dāng)X>Y+Z時(shí)，我們認(rèn)為魏國(guó)獲勝，小藍(lán)想知道游戲結(jié)束時(shí)，如果有其中一個(gè)國(guó)家獲勝，最多發(fā)生了多少個(gè)事件？如果不存在任何一個(gè)讓某個(gè)國(guó)家獲勝的情況，請(qǐng)輸出-1。
【輸入格式】
????????輸入的第一行包含一個(gè)整數(shù)n。
????????第二行包含n個(gè)整數(shù)表示A，相鄰整數(shù)之間使用一個(gè)空格分隔
????????第三行包含n個(gè)整數(shù)表示B，相整數(shù)之間使用一個(gè)空格分隔
????????第四行包含n個(gè)整數(shù)表示C，相鄰整數(shù)之間使用一個(gè)空格分隔
【輸出格式】
? ? ? ??輸出一行包括一個(gè)整數(shù)表示答案。
【樣例輸入】
3
1 2 2
2 3 2
1 0 7【樣例輸出】
2【測(cè)評(píng)用例與規(guī)模】
????????對(duì)于 40% 的評(píng)測(cè)用例，n < 500;
????????對(duì)于 70%的評(píng)測(cè)用例，n<5000;對(duì)于所有評(píng)測(cè)用例，，.
【解析與方法】
? ? ? ? 首先明確游戲結(jié)束時(shí)（所以發(fā)事情發(fā)生與否已經(jīng)確定）僅僅只表示一次游戲會(huì)發(fā)生1，2...n這幾件事情?？赡茉谶^程中會(huì)出現(xiàn)比如X>Y+Z的情況，此時(shí)并不表示某魏國(guó)獲勝了。而是要等到全部事情發(fā)生后比對(duì)X與Y+Z的情況才能判斷（省賽中誤解了導(dǎo)致寄掉了）。理解后難度就直行下降了。因此可以枚舉魏、蜀、吳三個(gè)國(guó)家想要獲勝最多事情數(shù)量，然后取最大值即是答案。
? ? ? ? 假設(shè)魏國(guó)獲勝：令new_X =[ Ai - Bi - Ci].? 1<=i<=n
? ? ? ? 為使發(fā)生的事件最多，需要從new_Xi最大的地方開始發(fā)生，sum_X += new_Xi
? ? ? ? 當(dāng)sum_X<=0時(shí)，結(jié)束。
【Python程序代碼】? ? ? ?
n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
new_X = sorted([ A[_] - B[_] - C[_] for _ in range(n) ],reverse=True)
new_Y = sorted([ B[_] - A[_] - C[_] for _ in range(n) ],reverse=True)
new_Z = sorted([ C[_] - A[_] - B[_] for _ in range(n) ],reverse=True)
ans,resX,resY,resZ,sum_X,sum_Y,sum_Z = 0,0,0,0,0,0,0
for i in range(n):
sum_X,sum_Y,sum_Z = sum_X + new_X[i], sum_Y + new_Y[i], sum_Z + new_Z[i]
resX = resY = resZ = i + 1
if sum_X>0:ans = max(ans,resX)
if sum_Y>0:ans = max(ans,resY)
if sum_Z>0:ans = max(ans,resZ)
if sum_X<=0 and sum_Y<=0 and sum_Z<=0:break
print(ans if ans else -1)
試題D：平均? ? （10分）
【問題描述】
????????有一個(gè)長(zhǎng)度為n的數(shù)組(n是10的倍數(shù))，每個(gè)數(shù)a都是區(qū)間[0, 9]中的整數(shù)。小明發(fā)現(xiàn)數(shù)組里每種數(shù)出現(xiàn)的次數(shù)不太平均，而更改第i個(gè)數(shù)的代價(jià)為bi，他想更改若干個(gè)數(shù)的值使得這10種數(shù)出現(xiàn)的次數(shù)相等(都等于n/10)，請(qǐng)問代價(jià)和最少為多少。
【輸入格式】
? ? ? ? 輸入的第一行包括一個(gè)正整數(shù)n。
? ? ? ? 接下來n行，第i行包括兩個(gè)整數(shù)ai，bi，用一個(gè)空格分隔。
【輸出格式】
? ? ? ? 輸出包括一個(gè)正整數(shù)表示答案。
【樣例輸入】
10
1 1
1 2
1 3
2 4
2 5
2 6
3 7
3 8
3 9
4 10【樣例輸出】
27【樣例說明】?
????????只更改第 1,2,4,5,7,8個(gè)數(shù)，需要花費(fèi)代價(jià)1+2+4+5+7+8=27
【測(cè)試用例與規(guī)?！?/strong>
? ? ? ? 對(duì)于20%的評(píng)測(cè)用例，
? ? ? ? 對(duì)于所以的評(píng)測(cè)用例，
【解析與方法】
? ? ? ??應(yīng)該是屬于最簡(jiǎn)單編程題了，avg = n/10，遍歷0~9，如果某個(gè)數(shù)的數(shù)量大于avg則需要改變num[i] - avg個(gè)數(shù)字，直接選取全部i數(shù)字改變需要代價(jià)最小的前num[i]-avg個(gè)數(shù)字即可。
?【Python程序代碼】
n = int(input())
num,avg,res = [[]for i in range(10)],n//10,0
for i in range(n):
a,b = map(int,input().split())
num[a].append(b)
for i in range(10):
if len(num[i])>avg:
num[i].sort()
for _ in range(len(num[i])-avg):
res += num[i][_]
print(res)試題E：翻轉(zhuǎn)? ? ?（15分）
【問題描述】
? ? ? ? 小藍(lán)用黑白棋的n個(gè)棋子排成了一行，他在腦海里想象出了一個(gè)長(zhǎng)度為 n的01串T，他發(fā)現(xiàn)如果把黑棋當(dāng)做1，白棋當(dāng)做0，這一行棋子也是一個(gè)長(zhǎng)度為n的01串S。
????????小藍(lán)決定，如果在S中發(fā)現(xiàn)一個(gè)棋子和它兩邊的棋子都不一樣，就可以將其翻轉(zhuǎn)變成另一個(gè)顏色。也就是說，如果S中存在子串 101或者010，就可以選擇將其分別變?yōu)?11和000，這樣的操作可以無限重復(fù)。
????????小藍(lán)想知道最少翻轉(zhuǎn)多少次可以把S變成和一模一樣
【輸入格式】
????????輸入包含多組數(shù)據(jù)
????????輸入的第一行包含一個(gè)正整數(shù) D表示數(shù)據(jù)組數(shù)
????????后面2D行每行包含一個(gè)01串，每?jī)尚袨橐唤M數(shù)據(jù)，第 2i-1行為第i組數(shù)據(jù)的Ti，第2i行為第i組數(shù)據(jù)的Si，Si和Ti度均為n。
【輸出格式】
????????對(duì)于每組數(shù)據(jù)，輸出一行包含一個(gè)整數(shù)，表示答案，如果答案不存在請(qǐng)輸出-1。
【樣例輸入】
2
1000111
1010101
01000
11000【樣例輸出】
2
-1【測(cè)評(píng)用例與規(guī)?！?/strong>
? ? ? ? 對(duì)于20%的測(cè)評(píng)用例，.
? ? ? ? 對(duì)于所以的測(cè)評(píng)用例，保證.
【解析與方法】
? ? ? ? 由題目給出的S中若存在101、010.則可分別變成111、000，即任意連續(xù)三位若中間與左右兩邊不同則可以把中間的變成與左右兩邊相同。若將101或010變成111或000后，我們可以發(fā)現(xiàn)其不會(huì)對(duì)其他位置有影響，也就是不會(huì)發(fā)生連鎖反應(yīng)，也就是在比對(duì)Si和Ti時(shí)，若，則判斷Si是否符合翻轉(zhuǎn)的條件，如果不符合翻轉(zhuǎn)的條件則S不能變成T。
【Python程序代碼】
tt = int(input())
for i in range(tt):
t = list(input())#把s變成t
s = list(input())
cnt,flag = 0,1
for i in range(len(s)):
if s[i]!=t[i]:
if i-1>=0 and i+1<len(s) and s[i+1]!=s[i] and s[i-1]!=s[i]:
s[i],cnt = s[i+1],cnt+1
else:
flag = 0;break
print(cnt if flag else -1)試題F：子矩陣? ? ?（15分）
【題目描述】
????????給定一個(gè)nxm(n行m列)的矩陣。設(shè)一個(gè)矩陣的價(jià)值為其所有數(shù)中的最大值和最小值的乘積。求給定矩陣的所有大小為a xb (a 行列)的子矩陣的價(jià)值的和。
????????答案可能很大，你只需要輸出答案對(duì)998244353 取模后的結(jié)果。
【輸入格式】
????????輸入的第一行包含四個(gè)整數(shù)分別表示n，m，a，b，相鄰整數(shù)之間使用一個(gè)空格分隔。接下來
n行每行包含m個(gè)整數(shù)，相鄰整數(shù)之間使用一個(gè)空格分隔，表示矩陣中的每個(gè)數(shù)Aij。
【輸出格式】
? ? ? ? 輸出一行包含一個(gè)整數(shù)表示答案。
【樣例輸入】
2 3 1 2
1 2 3
4 5 6【樣例輸出】
58【樣例說明】
????????1x2+2x3+4x5+5x6=58.
【測(cè)評(píng)用例規(guī)模與約定】
? ? ? ? 對(duì)于40%的測(cè)評(píng)用例，.
? ? ? ? 對(duì)于70%的測(cè)評(píng)用例，.
? ? ? ? 對(duì)于所以的測(cè)評(píng)用例，.
【解析與方法】
? ? ? ? 暴力是顯然不能通過全部測(cè)試數(shù)據(jù)的，需要得到每一個(gè)a*b大小的矩陣的最大值和最小值，可以先考慮得到每一行長(zhǎng)度為b的窗口中的最大值和最小值，然后在這個(gè)基礎(chǔ)上求出每一列長(zhǎng)度為a的窗口的最大值和最小值。就可以預(yù)處理出來每個(gè)子矩陣中的最大值和最小值。要求一個(gè)滑動(dòng)窗口中的最大值和最小值是一個(gè)基本的單調(diào)隊(duì)列問題。
【Python程序與代碼】
n, m, a, b = map(int, input().split())
s,num_max,num_min,n_max,n_min,res = [[0] * (n + 2) for _ in range(n + 2)],[],[],[],[],0
for i in range(1, n + 1):
s[i][1:m + 1] = map(int, input().split())
def get_min(a, k, m):
tep,q,hh,tt = [],[0]*1010,0,-1
for i in range(1, m + 1):
if hh <= tt and q[hh] <= i - k: hh += 1 # 判斷是否出了窗口
while hh <= tt and a[i] <= a[q[tt]]: tt -= 1
tt,q[tt] = tt + 1,i
if i - k >= 0: tep.append(a[q[hh]])
return tep
def get_max(a, k, m):
tep,q,hh,tt = [],[0]*1010,0,-1
for i in range(1, m + 1):
if hh <= tt and q[hh] <= i - k: hh += 1 # 判斷是否出了窗口
while hh <= tt and a[i] >= a[q[tt]]: tt -= 1
tt,q[tt] = tt + 1,i
if i - k >= 0: tep.append(a[q[hh]])
return tep
for i in range(1, n + 1):
temp = [0] + get_max(s[i][:m + 1], b, m)
num_max.append(temp)
temp = [0] + get_min(s[i][:m + 1], b, m)
num_min.append(temp)
for i in range(1, m - b + 2):
t1 = [0]
for _ in range(n):
t1.append(num_max[_][i])
t1.append(0)
temp = get_max(t1, a, n)
n_max.append(temp)
t2 = [0]
for _ in range(n):
t2.append(num_min[_][i])
t2.append(0)
temp = get_min(t2, a, n)
n_min.append(temp)
for i in range(len(n_max)):
for j in range(len(n_max[0])):
res += n_max[i][j] * n_min[i][j]
print(res)試題G：階乘的和? ? ?（20分）
【問題描述】
????????給定n個(gè)數(shù)，問能滿足m!為的因數(shù)的最大的m是多少，其中m!表示m的階乘，即1x2x3x···xm。
【輸入格式】
????????輸入的第一行包含一個(gè)整數(shù)n。
????????第二行包含n個(gè)整數(shù)，分別表示，相鄰整數(shù)之間使用一個(gè)空格分隔。
【輸出格式】
? ? ? ? 給出一行包括一個(gè)整數(shù)表示答案。
【樣例輸入】
3
2 2 2【樣例輸出】
3【測(cè)評(píng)用例規(guī)模與約定】
????????對(duì)于40%的測(cè)評(píng)用例，.
? ? ? ? 對(duì)于所以的測(cè)評(píng)用例，.
【解析與方法】
? ? ? ? 首先明確，這個(gè)式子中num為整數(shù)時(shí)成立的條件，通過對(duì)分子提取公因數(shù)得到公因數(shù)為，則m最大的值即為S。所以求解該問題只需要模擬階乘的轉(zhuǎn)換就可以。
【Python程序代碼】
n = int(input())
a = list(map(int,input().split()))
a.sort()
st,i,cnt = a[0],0,0
while i<n:
while i<n and a[i]==st:
cnt += 1
i += 1
if cnt and cnt%(st+1)==0:
cnt,st = cnt//(st+1),st+1
if i==n:
while cnt and cnt%(st+1)==0:
cnt,st = cnt//(st+1),st+1
else:
break
print(st)試題H：奇怪的數(shù)? ? ?（20分）
【問題描述】
????????小藍(lán)最近在找一些奇怪的數(shù)，其奇數(shù)數(shù)位上是奇數(shù)，而偶數(shù)數(shù)位上是偶數(shù)同時(shí)，這些數(shù)的任意5個(gè)連續(xù)數(shù)位的和都不大于m。
????????例如當(dāng)m=9時(shí)，10101和12303 就是奇怪的數(shù)，而12345 和11111則不是。
小藍(lán)想知道一共有多少個(gè)長(zhǎng)度為n的上述的奇怪的數(shù)。你只需要輸出答案對(duì)998244353取模的結(jié)果。
【輸入格式】
????????輸入一行包含兩個(gè)整數(shù) n,m，用一個(gè)空格分隔。
【輸出格式】
????????輸出一行包含一個(gè)整數(shù)表示答案。
【樣例輸入】
5 5【樣例輸出】
6?【測(cè)評(píng)用例規(guī)模與約定】
? ? ? ? 對(duì)于30%的測(cè)評(píng)用例，n<=12;
? ? ? ? 對(duì)于60%的測(cè)評(píng)用例，n<=5000;
? ? ? ? 對(duì)于所以的測(cè)評(píng)用例，.
【解析與方法】
? ? ? ??需要連續(xù)驗(yàn)證5個(gè)數(shù)位上的數(shù)字之和是否大于m，設(shè)置狀態(tài)，表示第i-3個(gè)數(shù)位上的數(shù)字是a，i-2：b，i-1：c，i：d的奇怪的數(shù)有多少個(gè)。所以有：
? ? ? ? 時(shí)間復(fù)雜度，大概是次運(yùn)算，大概率過不了。因此考慮維護(hù)F在第二維的前綴和。
? ? ? ? 轉(zhuǎn)移方程：
????????時(shí)間復(fù)雜度為，大概是次運(yùn)算，對(duì)C++來說是可以直接過掉。都是Python可能會(huì)卡，在官網(wǎng)測(cè)試了一波，C++只需要40ms，Python只過70%。本題屬實(shí)是本組別最難的題了。
【Python程序代碼】
M,mod,ans,p,q = 12,998244353,0,1,0
n, m= map(int, input().split())
g = [[[[[0 for _ in range(M)] for _ in range(M)] for _ in range(M)] for _ in range(M)] for _ in range(2)]
for a in range(p, 10, 2): #維護(hù)二維的前綴和？ 預(yù)處理出前4位的情況
for b in range(q, 10, 2):
for c in range(p, 10, 2):
for d in range(q, 10, 2):
g[0][a + 2][b][c][d] = g[0][a][b][c][d] + int(a + b + c + d <= m)
for i in range(5, n + 1): #從第五位開始
p,q= p^1,q^1
for a in range(p, 10, 2):
for b in range(q, 10, 2):
for c in range(p, 10, 2):
for d in range(q, 10, 2):
f = m - a - b - c - d #計(jì)算f值
if q != (f & 1):f -= 1 #余數(shù)f與當(dāng)前位置的奇偶性不同則f-- q表示奇偶情況
if f > 8 + p:f = 8 + q #控制余數(shù)f在0~9范圍內(nèi)
g[i % 2][a + 2][b][c][d] = (g[i % 2][a][b][c][d] + (0 if f < q else g[(i + 1) % 2][f + 2][a][b][c])) % mod
for b in range(q, 10, 2):
for c in range(p, 10, 2):
for d in range(q, 10, 2):
f = m - b - c - d
if f < p:continue
if p != (f & 1):f -= 1
if f > 8 + p:f = 8 + p
ans = (ans + g[n % 2][f + 2][b][c][d]) % mod
print(ans)
【C語言程序代碼】
#include <stdio.h>
const int M = 12, mod = 998244353;
int n, m, ans, g[2][M][M][M][M];
int main() {
scanf("%d %d", &n, &m);
int p = 1, q = 0;
//維護(hù)二維的前綴和 預(yù)處理出前4位的情況
for (int a = p; a < 10; a += 2)
for (int b = q; b < 10; b += 2)
for (int c = p; c < 10; c += 2)
for (int d = q; d < 10; d += 2) {
g[0][a + 2][b][c][d] = g[0][a][b][c][d] + (a + b + c + d <= m);
}
//從第五位開始
for (int i = 5; i <= n; ++i) {
p ^= 1, q ^= 1; //移動(dòng)一位奇數(shù)偶數(shù)的相對(duì)位置發(fā)送變化
for (int a = p; a < 10; a += 2)
for (int b = q; b < 10; b += 2)
for (int c = p; c < 10; c += 2)
for (int d = q; d < 10; d += 2) {
int f = m - a - b - c - d; //計(jì)算f值
if (q != (f & 1)) --f; //余數(shù)f與當(dāng)前位置的奇偶性不同則f-- q表示奇偶情況
if (f > 8 + p) f = 8 + q; // 控制余數(shù)f在0~9范圍內(nèi)
//狀態(tài)轉(zhuǎn)移
g[i & 1][a + 2][b][c][d] = (g[i & 1][a][b][c][d] + (f < q ? 0 : g[~i & 1][f + 2][a][b][c])) % mod;
}
}
for (int b = q; b < 10; b += 2)
for (int c = p; c < 10; c += 2)
for (int d = q; d < 10; d += 2) {
int f = m - b - c - d;
if (f < p) continue;
if (p != (f & 1)) --f;
if (f > 8 + p) f = 8 + p;
ans = (ans + g[n & 1][f + 2][b][c][d]) % mod;
}
printf("%d", ans);
}
試題I：子樹的大小? ? ?（25分）
【問題描述】
????????給定一棵包含n個(gè)結(jié)點(diǎn)的完全m又樹，結(jié)點(diǎn)按從根到葉、從左到右的順序依次編號(hào)。例如下圖是一個(gè)擁有 11個(gè)結(jié)點(diǎn)的完全3又樹。
? ? ? ? 你需要求出第k個(gè)結(jié)點(diǎn)的子樹的結(jié)點(diǎn)數(shù)。?
【輸入格式】
????????輸入包含多組詢問。
????????輸入的第一行包含一個(gè)整數(shù)T，表示詢問次數(shù)。
????????接下來行，每行包含三個(gè)整數(shù) n，m，k，表示一組詢問。
【輸出格式】
????????輸出T行，每行包含一個(gè)整數(shù)表示對(duì)應(yīng)詢問的答案。
【樣例輸入】
3
1 2 1
11 3 4
74 5 3【樣例輸出】
1
2
24【用例規(guī)模與約定】
? ? ? ? 對(duì)于40%的測(cè)評(píng)用例，.
? ? ? ? 對(duì)于所以的測(cè)評(píng)用例，.
【解析與方法】
? ? ? ? 觀察用例規(guī)模可知，想要建樹是不可能的，所以需要從完全m叉樹的特點(diǎn)入手。如下圖：
????????先考慮當(dāng)k為3的時(shí)候，即結(jié)點(diǎn)3的子樹的結(jié)點(diǎn)個(gè)數(shù)的求法，設(shè)置一個(gè)左右指針l,r分別指向這一層子樹的最左邊和最右邊的結(jié)點(diǎn)的編號(hào)。此時(shí)l=r=3。每次向下擴(kuò)展一層并判斷此時(shí)k結(jié)點(diǎn)最下層右側(cè)的結(jié)點(diǎn)編號(hào)是否大于n，如果大于n則說明已經(jīng)達(dá)到最大深度，同時(shí)再判斷最左側(cè)結(jié)點(diǎn)的編號(hào)是否小于等于n, 如果小于等于n，則最下層一共有n - ((l-1)*m+1)個(gè)結(jié)點(diǎn)，并退出循環(huán)。小于等于n的話繼續(xù)向下擴(kuò)展此時(shí)，r=(r*m+1) 、l=(l-1)*m+2。
【Python程序代碼】
T = int(input())
def solve(n,m,k):
l,r,res,mk = k,k,0,1
while True:
res += mk
if r*m+1>n:
if (l-1)*m+2<=n:
res += n- ((l-1)*m+1)
break
mk*=m
r = (r*m+1)
l = (l-1)*m+2
return res
for _ in range(T):
n,m,k = map(int,input().split())
print(solve(n,m,k))
試題J：反異或01串? ? ?（25分）
【問題描述】
????????初始有一個(gè)空的01串，每步操作可以將0或1添加在左側(cè)或右側(cè)。也可以對(duì)整個(gè)串進(jìn)行反異或操作: 取s' = rev(s)，其中s 是目前的01串，由表示逐位異或，rev(s)代表將 s翻轉(zhuǎn)，也就是說取中心位置并交換所有對(duì)稱的兩個(gè)位置的字符。例如，rev(0101)=1010，rev(010) = 010，rev(0011)=1100。
????????反異或操作最多使用一次 (可以不用，也可以用一次)。給定一個(gè)01串T，問最少需要添加多少個(gè)1才能從一個(gè)空01 串得到T，在本題中0可以添加任意個(gè)。
【輸入格式】
輸入一行包括一個(gè)01串表示給定的T。
【輸出格式】
輸出一行包括一個(gè)整數(shù)，表示最少需要添加多少個(gè)1.
【樣例輸入】
00111011【樣例輸出】
3【測(cè)評(píng)用例與規(guī)模】
? ? ? ? 對(duì)于20%的測(cè)評(píng)用例，|T|<=10,對(duì)于40%的測(cè)評(píng)用例|T|<=500;
? ? ? ? 對(duì)于40%的測(cè)評(píng)用例，|T|<=5000;對(duì)于80%的測(cè)評(píng)用例
? ? ? ? 對(duì)于所以的測(cè)評(píng)用例，,保證T中僅包含0和1.
【解析與方法】
? ? ? ? 首先讀懂反異或操作，其實(shí)也就是一個(gè)長(zhǎng)度為偶數(shù)的回文序列只需要一半數(shù)量的1通過反異或操作就可以創(chuàng)造出來，一個(gè)奇回文串的話要求中心字符不能為1，只能為0才能通過反異或操作以一半數(shù)量的1創(chuàng)造出來。所以題目可以轉(zhuǎn)化為求一個(gè)滿足上述條件的回文串，其使用1的數(shù)量最多?？焖偾蠡匚拇拈L(zhǎng)度的算法有馬拉車算法（Manacher）通過馬拉車算法可以預(yù)處理出來一個(gè)d[i]數(shù)組，表示以i為中心的回文串的半徑，由此再用前綴和預(yù)處理優(yōu)化求解可以把復(fù)雜度降到O(n)，不過常數(shù)比較大。用Python還是比較容易被卡。以下代碼再C語言網(wǎng)中被卡了2個(gè)點(diǎn)。使用C++的話可以秒過。
【Python程序代碼】
a = input()
n, k = len(a), 1
s = ['$', '#']
for i in range(n):
k += 2
s.append(a[i])
s.append('#')
n = k
# 以上操作可以使新字符串為奇字符串
# s[0]="$"是設(shè)置的哨兵
# 設(shè)置數(shù)字1的前綴和函數(shù)
pre = [0] * (n + 1)
for i in range(1, n + 1):
if s[i] == '1':
pre[i] = pre[i - 1] + 1
else:
pre[i] = pre[i - 1]
al = pre[n]
d = [0] * (n + 1)
co = 0
# 回文半徑d[i],即以i為中心半徑為d[i],包括中心i
def get_d():
global d
global co
d[1] = 1
l, r = 0, 1
for i in range(2, n + 1):
if i <= r:
d[i] = min(d[r - i + l], r - i + 1)
while i + d[i] <= n and i - d[i] >= 0 and s[i - d[i]] == s[i + d[i]]:
d[i] += 1
if i + d[i] - 1 > r:
l = i - d[i] + 1
r = i + d[i] - 1
if s[i] != '1':
co = max(co, pre[i - 1] - pre[i - d[i]])
get_d()
print(al - co)【C++程序代碼】文章來源地址http://www.zghlxwxcb.cn/news/detail-756085.html
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
string a;
cin >> a;
int n = a.size(), k = 1;
vector<char> s(n * 2 + 3, '#');
s[0] = '$';
vector<int> pre(n * 2 + 3, 0);
for (int i = 0; i < n; ++i) {
k += 2;
s[k - 1] = a[i];
}
n = k;
for (int i = 1; i <= n; ++i) {
if (s[i] == '1') {
pre[i] = pre[i - 1] + 1;
} else {
pre[i] = pre[i - 1];
}
}
int al = pre[n];
vector<int> d(n + 1, 0);
int co = 0;
d[1] = 1;
int l = 0, r = 1;
for (int i = 2; i <= n; ++i) {
if (i <= r) {
d[i] = min(d[r - i + l], r - i + 1);
}
while (i + d[i] <= n && i - d[i] >= 0 && s[i - d[i]] == s[i + d[i]]) {
d[i] += 1;
}
if (i + d[i] - 1 > r) {
l = i - d[i] + 1;
r = i + d[i] - 1;
}
if (s[i] != '1') {
co = max(co, pre[i - 1] - pre[i - d[i]]);
}
}
cout << al - co << endl;
return 0;
}
到了這里，關(guān)于第十四屆藍(lán)橋杯大賽軟件賽省賽（Python大學(xué)A組）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
