第十四屆藍(lán)橋杯Python B組省賽復(fù)盤
試題 A: 2023
【問題描述】(5 分)
請求出在 12345678 至 98765432 中,有多少個數(shù)中完全不包含 2023 。
完全不包含 2023 是指無論將這個數(shù)的哪些數(shù)位移除都不能得到 2023 。
例如 20322175,33220022 都完全不包含 2023,而 20230415,20193213 則 含有 2023 (后者取第 1, 2, 6, 8 個數(shù)位) 。
【思路】
-
正則表達(dá)式
''' 正則表達(dá)式 ''' import re def check(s) : if re.match(r'.*2.*0.*2.*3.*', s) : return False else : return True st = 12345678 ed = 98765432 res = 0 while st <= ed : if check(str(st)) : res += 1 st += 1 print(res)
-
信號量機(jī)制(哨兵)
從后往前,s1,s2,s3,s4分別標(biāo)記3,2,0,2是否已經(jīng)找到。大致思路是只有前面的數(shù)全找到后才能找下一個數(shù)。比如當(dāng)找0時,必須確保從后往前已經(jīng)找到了3,2這個兩個數(shù)。def check(n) : s1, s2, s3, s4 = False, False, False, False for i in range(8) : if n % 10 == 3 and not s1 : s1 = True elif n % 10 == 2 and s1 and not s2 : s2 = True elif n % 10 == 0 and s1 and s2 and not s3: s3 = True elif n % 10 == 2 and s1 and s2 and s3 and not s4: s4 =True n //= 10 return not (s1 and s2 and s3 and s4) st = 12345678 ed = 98765432 res = 0 while st <= ed : if check(str(st)) : res += 1 st += 1 print(res)
試題 B: 硬幣兌換(5 分)
【問題描述】
小藍(lán)手中有 2023 種不同面值的硬幣,這些硬幣全部是新版硬幣,其中第
i
(
1
≤
i
≤
2023
)
i(1 ≤ i ≤ 2023)
i(1≤i≤2023) 種硬幣的面值為
i
i
i ,數(shù)量也為
i
i
i 個。硬幣兌換機(jī)可以進(jìn)行硬幣兌換,兌換規(guī)則為:交給硬幣兌換機(jī)兩個新版硬幣
c
o
i
n
1
coin_1
coin1? 和
c
o
i
n
2
coin_2
coin2? ,硬幣兌換機(jī)會兌換成一個面值為
c
o
i
n
1
+
c
o
i
n
2
coin_1 + coin_2
coin1?+coin2? 的舊版硬幣。小藍(lán)可以用自己已有的硬幣進(jìn)行任意次數(shù)兌換,假設(shè)最終小藍(lán)手中有
K
K
K 種不同面值的硬幣(只看面值,不看新舊)并且第
i
(
1
≤
i
≤
K
)
i(1 ≤ i ≤ K)
i(1≤i≤K) 種硬幣的個數(shù)為
s
u
m
i
sum_i
sumi?。小藍(lán)想要使得
m
a
x
{
s
u
m
1
,
s
u
m
2
,
?
?
?
,
s
u
m
K
}
max\{sum_1, sum_2, · · · , sum_K\}
max{sum1?,sum2?,???,sumK?} 的值達(dá)到最大,請你幫他計算這個值最大是多少。
注意硬幣兌換機(jī)只接受新版硬幣進(jìn)行兌換,并且兌換出的硬幣全部是舊版硬幣。
【思路】
我們知道硬幣的數(shù)量是隨著面值單調(diào)增加,那么兩個面值要拼湊出一個大的面值,取決于小的面值。
假設(shè)有n中面值硬幣,
a
n
?
1
,
a
n
a_{n - 1}, a_n
an?1?,an?分別表示盡可能拼湊出最多個面額分別為
n
?
1
,
n
n - 1,n
n?1,n的硬幣。
a
n
?
1
=
n
?
1
+
1
+
.
.
.
+
i
n
t
(
n
?
1
/
2
)
a_{n - 1} = n - 1 + 1+ ...+int(n - 1 / 2)
an?1?=n?1+1+...+int(n?1/2)
a
n
=
n
+
1
+
.
.
.
+
n
/
2
a_n = n + 1 + ... + n/2
an?=n+1+...+n/2
顯然
a
n
a_n
an?更大。所以最終拼湊出的數(shù)是大于等于
a
n
a_n
an?
res = 0
for t in range(2023, 4047) :
ans = 0
for i in range(1, 2024) :
ta = t - i
if i == ta :
ans += (i // 2)
if ta <= i or ta > 2023 :
continue
ans += i
if t == 2023 :
ans += 2023
res = max(res, ans)
print(res)
'''
682425
'''
試題 C: 松散子序列
時間限制: 10.0s 內(nèi)存限制: 512.0MB 本題總分:10 分
【問題描述】
給定一個僅含小寫字母的字符串 s ,假設(shè) s 的一個子序列 t 的第 i 個字符
對應(yīng)了原字符串中的第 pi 個字符。我們定義 s 的一個松散子序列為:對于 i > 1
總是有
p
i
?
p
i
?
1
≥
2
p_i ? p_{i?1} ≥ 2
pi??pi?1?≥2 。設(shè)一個子序列的價值為其包含的每個字符的價值之和 (
a ~ z 分別為 1 ~ 26 ) 。
求 s 的松散子序列中的最大價值。
【輸入格式】
輸入一行包含一個字符串 s 。
【輸出格式】
輸出一行包含一個整數(shù)表示答案。
【樣例輸入】
azaazaz
【樣例輸出】
78
【評測用例規(guī)模與約定】
思路
本題大概意旨是,不能選連續(xù)兩個字符組成的序列,典型的打家劫舍板子
-
狀態(tài)機(jī)
- 狀態(tài)表示
f
[
i
,
0
/
1
]
f[i, 0/1]
f[i,0/1]:
- 集合:表示0~i的字符串(不0)選取1第i個字符的松散序列價值的集合
- 屬性:max
- 狀態(tài)計算: f [ i , 0 ] = m a x ( f [ i ? 1 , 0 ] , f [ i ? 1 , 1 ] ) f[i, 0] = max(f[i - 1, 0], f[i - 1, 1]) f[i,0]=max(f[i?1,0],f[i?1,1]), f [ i , 1 ] = f [ i ? 1 , 0 ] + s [ i ] f[i, 1] =f[i - 1, 0] + s[i] f[i,1]=f[i?1,0]+s[i]
s = list(input()) n = len(s) for i in range(n) : s[i] = ord(s[i]) - ord('a') + 1 f = [[0, 0] for _ in range(n + 1)] for i in range(1, n + 1) : f[i][0] = max(f[i - 1][0], f[i - 1][1]) f[i][1] = f[i - 1][0] + s[i - 1] print(max(f[n][0], f[n][1]))
- 狀態(tài)表示
f
[
i
,
0
/
1
]
f[i, 0/1]
f[i,0/1]:
-
線性DP
- 狀態(tài)表示
f
[
i
]
f[i]
f[i]:
- 集合:表示以i字符結(jié)尾的松散序列價值的集合
- 屬性:max
- 狀態(tài)計算: f [ i ] = m a x ( f [ j ] ) + o r d ( s [ i ] ) , j < = i ? 2 f[i] = max(f[j]) + ord(s[i]),j <=i-2 f[i]=max(f[j])+ord(s[i]),j<=i?2
''' 狀態(tài)表示:f[i] 集合:表示以i結(jié)尾的滿足條件的子序列的價值集合 屬性:max 狀態(tài)計算:f[i] = max(f[j]) + ord(s[i]),j <=i-2 ''' s = list(input()) n = len(s) f = [0] * (n + 2) maxx = 0 # 記錄到i-2的最大值 for i in range(1, n + 1) : f[i] = maxx + ord(s[i - 1]) - ord('a') + 1 maxx = max(f[i - 1], maxx) print(max(maxx, f[n]))
- 狀態(tài)表示
f
[
i
]
f[i]
f[i]:
試題 D: 管道
時間限制: 10.0s 內(nèi)存限制: 512.0MB 本題總分:10 分
【問題描述】
有一根長度為 len 的橫向的管道,該管道按照單位長度分為 len 段,每一段
的中央有一個可開關(guān)的閥門和一個檢測水流的傳感器。
一開始管道是空的,位于
L
i
L_i
Li? 的閥門會在
S
i
S_i
Si? 時刻打開,并不斷讓水流入管
道。
對于位于
L
i
L_i
Li? 的閥門,它流入的水在
T
i
(
T
i
≥
S
i
)
T_i (T_i ≥ S_i)
Ti?(Ti?≥Si?) 時刻會使得從第
L
i
?
(
T
i
?
S
i
)
L_i?(T_i?S_i)
Li??(Ti??Si?)
段到第
L
i
+
(
T
i
?
S
i
)
L_i + (T_i ? S_i)
Li?+(Ti??Si?) 段的傳感器檢測到水流。
求管道中每一段中間的傳感器都檢測到有水流的最早時間。
【輸入格式】
輸入的第一行包含兩個整數(shù) n, len,用一個空格分隔,分別表示會打開的閥
門數(shù)和管道長度。
接下來 n 行每行包含兩個整數(shù)
L
i
,
S
i
L_i, S_i
Li?,Si?,用一個空格分隔,表示位于第
L
i
L_i
Li? 段
管道中央的閥門會在
S
i
S_i
Si? 時刻打開。
【輸出格式】
輸出一行包含一個整數(shù)表示答案。
【樣例輸入】
3 10
1 1
6 5
10 2
【樣例輸出】
5
【評測用例規(guī)模與約定】
思路
要求檢測到水流的最短時間,看到len的數(shù)據(jù)范圍是
1
0
9
10^9
109應(yīng)該用一個低于
O
(
n
)
O(n)
O(n)的算法。
這就讓我們想到了二分。通過二分右半段,可以查找滿足全部覆蓋的最短時間。
對于確定的時刻
t
t
t,一個在
s
s
s時刻
(
t
>
=
s
)
(t >= s)
(t>=s)打開并位于
l
l
l的管道,在此時此刻可以覆蓋的區(qū)間是
[
m
a
x
(
l
?
(
t
?
s
)
,
1
)
,
m
i
n
(
l
+
(
t
?
s
)
,
l
e
n
)
]
[max(l - (t - s), 1), min(l + (t - s), len)]
[max(l?(t?s),1),min(l+(t?s),len)].
下面考慮區(qū)間覆蓋問題,對于n個區(qū)間,可以一個個枚舉區(qū)間,并對覆蓋區(qū)間進(jìn)行標(biāo)記,然而這樣的復(fù)雜度是
O
(
n
l
e
n
)
O(nlen)
O(nlen)。怎么優(yōu)化呢?我們想到對區(qū)間進(jìn)行操作的一個基礎(chǔ)算法差分,類似于LeetCode中的區(qū)間覆蓋原題。
'''
覆蓋問題,二分
'''
from sys import stdin
def check(x) :
st = [0] * (m + 2)
for item in a :
if item[1] <= x :
l, r = max(item[0] - (x - item[1]), 1), min(item[0] + (x - item[1]), m)
st[l] += 1
st[r + 1] -= 1
for i in range(1, m + 1) :
st[i] += st[i - 1]
if st[i] <= 0 :
return False
return True
n, m = map(int, input().split())
a = []
for _ in range(n) :
l, s = map(int, stdin.readline().split())
a.append([l, s])
l, r = 0, m + 1
while l < r :
mid = (l + r) >> 1
if check(mid) :
r = mid
else :
l = mid + 1
print(l)
試題 E: 保險箱
時間限制: 10.0s 內(nèi)存限制: 512.0MB 本題總分:15 分
【問題描述】
小藍(lán)有一個保險箱,保險箱上共有 n 位數(shù)字。
小藍(lán)可以任意調(diào)整保險箱上的每個數(shù)字,每一次操作可以將其中一位增加
1 或減少 1 。
當(dāng)某位原本為 9 或 0 時可能會向前(左邊)進(jìn)位/退位,當(dāng)最高位(左邊第
一位)上的數(shù)字變化時向前的進(jìn)位或退位忽略。
例如:
00000 的第 5 位減 1 變?yōu)?99999 ;
99999 的第 5 位減 1 變?yōu)?99998 ;
00000 的第 4 位減 1 變?yōu)?99990 ;
97993 的第 4 位加 1 變?yōu)?98003 ;
99909 的第 3 位加 1 變?yōu)?00009 。
保險箱上一開始有一個數(shù)字 x,小藍(lán)希望把它變成 y,這樣才能打開它,問
小藍(lán)最少需要操作的次數(shù)。
【輸入格式】
輸入的第一行包含一個整數(shù) n 。
第二行包含一個 n 位整數(shù) x 。
第三行包含一個 n 位整數(shù) y 。
【輸出格式】
輸出一行包含一個整數(shù)表示答案。
【樣例輸入】
5
12349
54321
【樣例輸出】
11
【評測用例規(guī)模與約定】
思路
比賽的時候看到這題秒想用BFS,但本題的數(shù)據(jù)范圍實在太大,即使跑10s超過10長度的數(shù)據(jù)也跑不出來。這時我們需要挖掘一下題目中的性質(zhì):
- 每一次只能讓一位增加、減少1
- 每一位只會向左邊進(jìn)位、退位,最高位的進(jìn)退位忽略
仔細(xì)思考,根據(jù)已有性質(zhì)可以推出:每一位有三種可能:進(jìn)位、退位、不進(jìn)不退。而且向高位進(jìn)位或者退位次數(shù),不大于1,因為進(jìn)退位的目的只是更接近當(dāng)前位的目標(biāo)數(shù)字,對于高位的第二次改變的花費(fèi)比在高位直接進(jìn)行一次操作花費(fèi)大。
由于前面的操作無后效性,可以考慮一下DP。
狀態(tài)表示
f
[
i
,
0
/
1
/
2
]
f[i, 0/1/2]
f[i,0/1/2], 假設(shè)原字符串和目標(biāo)字符串為
s
,
e
s, e
s,e:
- 集合:分別表示1~i-1位已經(jīng)處理到相應(yīng)位置,第i位進(jìn)位、退位、不進(jìn)不退的最終撥轉(zhuǎn)到目標(biāo)數(shù)花費(fèi)集合
- 屬性:min
狀態(tài)計算:
- 第i位進(jìn)位: f [ i , 0 ] = ( e i + 10 ? s i ) + m i n ( f [ i + 1 , 0 ] ? 1 , f [ i + 1 , 1 ] + 1 , f [ i + 1 , 2 ] ) f[i, 0] = (e_i + 10 - s_i) + min(f[i + 1, 0] - 1, f[i + 1, 1] + 1, f[i + 1, 2]) f[i,0]=(ei?+10?si?)+min(f[i+1,0]?1,f[i+1,1]+1,f[i+1,2])
- 第i位退位: f [ i , 1 ] = ( s i + 10 ? e i ) + m i n ( f [ i + 1 , 0 ] + 1 , f [ i + 1 , 1 ] ? 1 , f [ i + 1 , 2 ] ) f[i, 1] = (s_i + 10 - e_i)+ min(f[i + 1, 0] + 1, f[i + 1, 1] - 1, f[i + 1, 2]) f[i,1]=(si?+10?ei?)+min(f[i+1,0]+1,f[i+1,1]?1,f[i+1,2])
- 第i位不進(jìn)不退: f [ i , 2 ] = ∣ s i ? e i ∣ + m i n ( f [ i + 1 , 0 ] + 1 , f [ i + 1 , 1 ] + 1 , f [ i + 1 , 2 ] ) f[i, 2] = |s_i - e_i| + min(f[i + 1, 0] + 1, f[i + 1, 1] + 1, f[i + 1, 2]) f[i,2]=∣si??ei?∣+min(f[i+1,0]+1,f[i+1,1]+1,f[i+1,2])
n = int(input())
f = [[0, 0, 0] for _ in range(n + 5)]
st = input()
ed = input()
for i in range(n, 0, -1) :
if i == n :
f[i][0] = int(ed[i - 1]) + 10 - int(st[i - 1])
f[i][1] = int(st[i - 1]) + 10 - int(ed[i - 1])
f[i][2] = abs(int(st[i - 1]) - int(ed[i - 1]))
else :
f[i][0] = int(ed[i - 1]) + 10 - int(st[i - 1]) + min(f[i + 1][0] - 1, f[i + 1][1] + 1, f[i + 1][2])
f[i][1] = int(st[i - 1]) + 10 - int(ed[i - 1]) + min(f[i + 1][0] + 1, f[i + 1][1] - 1, f[i + 1][2])
f[i][2] = abs(int(st[i - 1]) - int(ed[i - 1])) + min(f[i + 1][0] + 1, f[i + 1][1] + 1, f[i + 1][2])
print(min(f[1][0], f[1][1], f[1][2]))
思路感覺沒毛病,但在dotcpp上只能過一個點(diǎn),家人們誰懂啊
試題 F: 樹上選點(diǎn)
時間限制: 10.0s 內(nèi)存限制: 512.0MB 本題總分:15 分
【問題描述】
給定一棵樹,樹根為 1,每個點(diǎn)的點(diǎn)權(quán)為
V
i
V_i
Vi? 。
你需要找出若干個點(diǎn)
P
i
P_i
Pi?,使得:
- 每兩個點(diǎn) P x P y P_x P_y Px?Py? 互不相鄰;
- 每兩個點(diǎn) P x P y P_x P_y Px?Py? 與樹根的距離互不相同;
- 找出的點(diǎn)的點(diǎn)權(quán)之和盡可能大。
請輸出找到的這些點(diǎn)的點(diǎn)權(quán)和的最大值。
【輸入格式】
輸入的第一行包含一個整數(shù) n 。
第二行包含 n ? 1 個整數(shù)
F
i
F_i
Fi? ,相鄰整數(shù)之間使用一個空格分隔,分別表示
第 2 至 n 個結(jié)點(diǎn)的父結(jié)點(diǎn)編號。
第三行包含 n 個整數(shù)
V
i
V_i
Vi?,相鄰整數(shù)之間使用一個空格分隔,分別表示每個
結(jié)點(diǎn)的點(diǎn)權(quán)。
【輸出格式】
輸出一行包含一個整數(shù)表示答案。
【樣例輸入】
5
1 2 3 2
2 1 9 3 5
【樣例輸出】
11
【評測用例規(guī)模與約定】
思路
題目大意是,選的節(jié)點(diǎn)不具有父子關(guān)系,且不可以深度相同,最終使選擇的點(diǎn)價值最大。
明顯的狀態(tài)機(jī)樹形DP。
對于一個確定的節(jié)點(diǎn)
i
i
i,要么取要么不取。
分情況討論:
- 取 : 則子節(jié)點(diǎn)一定不能取
- 不?。簞t可以取一個子節(jié)點(diǎn),也可以不取
靠寫不出來了,感覺又BFS又DFS好煩,過了過了
試題 G: T 字消除
時間限制: 10.0s 內(nèi)存限制: 512.0MB 本題總分:20 分
【問題描述】
小藍(lán)正在玩一款游戲,游戲中有一個 n × n 大小的 01 矩陣
A
i
,
j
A_{i, j}
Ai,j? 。
小藍(lán)每次需要選擇一個 T 字型的區(qū)域,且這個區(qū)域內(nèi)至少要有一個 1 。選
中后,這個區(qū)域內(nèi)所有的元素都會變成 0 。
給定游戲目前的矩陣,小藍(lán)想知道他最多可以進(jìn)行多少次上述操作。
T 字型區(qū)域是指形如
(
x
?
1
,
y
)
(
x
,
y
)
(
x
+
1
,
y
)
(
x
,
y
+
1
)
(x ? 1, y) (x, y) (x + 1, y) (x, y + 1)
(x?1,y)(x,y)(x+1,y)(x,y+1) 的四個點(diǎn)所形成的區(qū)
域。其旋轉(zhuǎn) 90, 180, 270 度的形式同樣也視作 T 字形區(qū)域。
【輸入格式】
輸入包含多組數(shù)據(jù)。
輸入的第一行包含一個整數(shù) D 表示數(shù)據(jù)組數(shù)。
對于每組數(shù)據(jù),第一行包含一個整數(shù) n 。
接下來 n 行每行包含 n 個 0 或 1,表示矩陣
A
i
,
j
A_{i, j}
Ai,j? 的每個位置的值。
【輸出格式】
輸出 D 行,每行包含一個整數(shù)表示小藍(lán)最多可以對當(dāng)前詢問中的矩陣操作
的次數(shù)。
【樣例輸入】
1
3
001
011
111
【樣例輸出】
5
【樣例說明】
我們用 X 表示某次操作選中的 T 字形,以下給出一種可行方案:
【評測用例規(guī)模與約定】
思路
麻了,題目看懂了想dfs做但無從下手,感覺是個貪心的題,去你的。
試題 H: 獨(dú)一無二
時間限制: 30.0s 內(nèi)存限制: 512.0MB 本題總分:20 分
【問題描述】
有一個包含 n 個點(diǎn),m 條邊的無向圖,第 i 條邊的邊權(quán)為
c
i
c_i
ci?,沒有重邊和
自環(huán)。設(shè)
s
i
s_i
si? 表示從結(jié)點(diǎn) 1 出發(fā)到達(dá)結(jié)點(diǎn) i 的最短路的不同路徑數(shù) ( i ∈ [1, n] ),
顯然可以通過刪除若干條邊使得
s
i
=
1
s_i = 1
si?=1,也就是有且僅有一條從 1 到 i 的最短
路,且保持最短路的路徑長度不變,對于每個 i ,求出刪除邊數(shù)的最小值。
【輸入格式】
輸入的第一行包含兩個正整數(shù) n, m。
接下來 m 行,每行包含三個正整數(shù)
u
i
,
v
i
,
c
i
u_i, v_i, c_i
ui?,vi?,ci? 表示第 i 條邊連接的兩個點(diǎn)的
編號和邊權(quán)。
【輸出格式】
輸出 n 行,第 i 行包含一個正整數(shù)表示對于結(jié)點(diǎn) i ,刪除邊數(shù)的最小值,
如果 1 和 i 不連通,輸出 ?1 。
【樣例輸入】
4 4
1 2 1
1 3 2
2 4 2
3 4 1
【樣例輸出】
0
0
0
1
【樣例說明】
在給定的圖中,只有 s4 一開始為 2,因為有兩條最短路:1 → 2 → 4, 1 →
3 → 4,任意刪掉一條邊后,就可以只剩一條最短路。
【評測用例規(guī)模與約定】
思路
聽說是什么最短路+dp轉(zhuǎn)移,聽都沒聽過,以后有緣再見吧!
試題 I: 異或和
時間限制: 15.0s 內(nèi)存限制: 512.0MB 本題總分:25 分
【問題描述】
給一棵含有 n 個結(jié)點(diǎn)的有根樹,根結(jié)點(diǎn)為 1 ,編號為 i 的點(diǎn)有點(diǎn)權(quán)
a
i
a_i
ai?
(
i
∈
[
1
,
n
]
)
(i ∈ [1, n])
(i∈[1,n])?,F(xiàn)在有兩種操作,格式如下:
? 1 x y 該操作表示將點(diǎn) x 的點(diǎn)權(quán)改為 y 。
? 2 x 該操作表示查詢以結(jié)點(diǎn) x 為根的子樹內(nèi)的所有點(diǎn)的點(diǎn)權(quán)異或和。
現(xiàn)有長度為 m 的操作序列,請對于每個第二類操作給出正確的結(jié)果。
【輸入格式】
輸入的第一行包含兩個正整數(shù) n, m ,用一個空格分隔。
第二行包含 n 個整數(shù)
a
1
,
a
2
,
.
.
.
,
a
n
a_1, a_2, ..., a_n
a1?,a2?,...,an? ,相鄰整數(shù)之間使用一個空格分隔。
接下來 n ? 1 行,每行包含兩個正整數(shù)
u
i
,
v
i
u_i, v_i
ui?,vi? ,表示結(jié)點(diǎn)
u
i
u_i
ui? 和
v
i
v_i
vi? 之間有一條
邊。
接下來 m 行,每行包含一個操作。
【輸出格式】
輸出若干行,每行對應(yīng)一個查詢操作的答案。
【樣例輸入】
4 4
1 2 3 4
1 2
1 3
2 4
2 1
1 1 0
2 1
2 2
【樣例輸出】
4
5
6
【評測用例規(guī)模與約定】
思路
一個dfs序模板
首先要知道異或和的一些性質(zhì) :
0異或任何數(shù)都是這個數(shù)本身
任何數(shù)異或本身等于0
所以異或中加減操作都集中在異或運(yùn)算上
具體來說,先處理出樹的dfs序列,然后初始化樹狀數(shù)組。dfs序列易于處理一個以u為根的子樹,在序列中表示一個區(qū)間。用樹狀數(shù)組處理區(qū)間和單點(diǎn)操作。
import sys
sys.setrecursionlimit(60000)
n, m = map(int, input().split())
id = [0] # 表示dfs序
inn = [0] * (n + 1) #以i節(jié)點(diǎn)為根的子樹在dfs序開始位置
out = [0] * (n + 1) #以i節(jié)點(diǎn)為根的子樹在dfs序末尾位置
h = [-1] * (2 * n + 7)
e = [0] * (2 * n + 7)
ne = [-1] * (2 * n + 7)
idx = 0
tr = [0] * (n + 7) # 樹狀數(shù)組,存儲(x - lowbit(x), x]區(qū)間內(nèi)的異或和
def lowbit(x) :
return x & -x
def sum(x, c) : # 修改操作
i = x
while i <= n :
tr[i] ^= c
i += lowbit(i)
def ask(x) : # 查詢操作
res = 0
i = x
while i :
res ^= tr[i]
i -= lowbit(i)
return res
def add(a, b) :
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1
time = 0 # 標(biāo)記dfs序位置
def dfs(u, fa) : # 構(gòu)建dfs序,同時記錄每個節(jié)點(diǎn)為根的子樹在dfs序的位置
global time
time += 1
inn[u] = time
id.append(u)
i = h[u]
while ~ i :
j = e[i]
if j != fa :
dfs(j, u)
i = ne[i]
out[u] = time
def init() : # 依據(jù)dfs序?qū)?yīng)樹上的權(quán)值初始化樹狀數(shù)組
for i in range(1, n + 1) :
sum(i, a[id[i]])
a = [0] + list(map(int, input().split()))
for i in range(n - 1) :
aa, b = map(int, input().split())
add(aa, b)
add(b, aa)
dfs(1, -1)
# print(id, inn, out, a)
init()
for _ in range(m) :
cmd = list(map(int, input().split()))
op = cmd[0]
if op == 2 :
l, r = inn[cmd[1]], out[cmd[1]] # 表示該子樹在dfs序中位于[l, r]
res = ask(r) ^ ask(l - 1) # 查詢[l, r]的異或和情況
print(res)
else :
index, t = inn[cmd[1]], cmd[2]
sum(index, a[id[index]]) # 減操作
a[id[index]] = t
sum(index, a[id[index]]) # 加操作
試題 J: 混亂的數(shù)組
時間限制: 10.0s 內(nèi)存限制: 512.0MB 本題總分:25 分
【問題描述】
給定一個正整數(shù) x,請找出一個盡可能短的僅含正整數(shù)的數(shù)組 A 使得 A 中
恰好有 x 對 i, j 滿足
A
i
>
A
j
A_i > A_j
Ai?>Aj? 。
如果存在多個這樣的數(shù)組,請輸出字典序最小的那個。
【輸入格式】
輸入一行包含一個整數(shù)表示 x 。
【輸出格式】
輸出兩行。
第一行包含一個整數(shù) n ,表示所求出的數(shù)組長度。
第二行包含 n 個整數(shù)
A
i
A_i
Ai?,相鄰整數(shù)之間使用一個空格分隔,依次表示數(shù)組
中的每個數(shù)。
【樣例輸入】
3
【樣例輸出】
3
3 2 1
【評測用例規(guī)模與約定】
思路
對于這題,我決定直接打表得分,蚊子肉也是肉啊文章來源:http://www.zghlxwxcb.cn/news/detail-434280.html
x = int(input())
if x == 1:
print(2)
print(2, 1)
if x == 2:
print(3)
print(2, 1, 1)
if x == 3:
print(3)
print(3, 2, 1)
if x == 4:
print(4)
print(2, 2, 1, 1)
if x == 5:
print(4)
print(3, 2, 1, 1)
if x == 6:
print(4)
print(4, 3, 2, 1)
if x == 7:
print(5)
print(3, 2, 2, 2, 1)
if x == 8:
print(5)
print(3, 3, 2, 1, 1)
if x == 9:
print(5)
print(4, 3, 2, 1, 1)
if x == 10:
print(5)
print(5, 4, 3, 2, 1)
總結(jié)
麻了,做這B樣也能省一,還挺開心。感覺還差挺多的,很多讀題失誤,很多題沒好好體會導(dǎo)致無謂失分,很可惜。繼續(xù)加油努力吧,沖刺國賽。文章來源地址http://www.zghlxwxcb.cn/news/detail-434280.html
到了這里,關(guān)于第十四屆藍(lán)橋杯Python B組省賽復(fù)盤的文章就介紹完了。如果您還想了解更多內(nèi)容,請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!