ACWing藍(lán)橋杯每日一題

一直沒時(shí)間去總結(jié)算法，終于有空可以總結(jié)一下刷的acwing了，因?yàn)闆]時(shí)間所以最近只刷了ACWING的藍(lán)橋杯每日一題。。。真是該死

1.截?cái)鄶?shù)組

首先我們要知道，如果sum(a)不能被3整除或者len(a) < 3 ，那么他肯定沒法讓截?cái)嗟娜齻€(gè)子數(shù)組和都一樣
然后我們只要把平均值算出來，從前往后遍歷，我們會得到1average截?cái)帱c(diǎn)，也會得到2average截?cái)帱c(diǎn)，意思就是說在1average截?cái)帱c(diǎn)前的子數(shù)組加和為average ，那么其實(shí)答案就是 2average截?cái)帱c(diǎn)的個(gè)數(shù) + 在2average截?cái)帱c(diǎn)之前的 1average截?cái)帱c(diǎn)的個(gè)數(shù)，，所以我們只要讓當(dāng)tot = 2average時(shí)，答案 += 當(dāng)時(shí)的1average 截?cái)帱c(diǎn)的個(gè)數(shù)就好了

注意！在判斷tot = average 還是 2average 時(shí)，要先判斷是否等于2average，因?yàn)楫?dāng)tot等于0時(shí)，1average == 2average，你如果先判斷了2*average，就會把1級截?cái)帱c(diǎn)和二級截?cái)帱c(diǎn)在同一個(gè)地方。。

同時(shí)考慮到數(shù)組全為0的情況，那么這種情況我們就C（len-1,2）就行了

具體代碼如下

n = int(input())
a = [int(x) for x in input().split()]
def c(a,b):res = 1while b:res = res * a / ba -= 1b -= 1return int(res)
if sum(a) % 3 != 0 or len(a) < 3:print(0)
elif a == [0]*len(a):print(c(len(a)-1,2))
else:average = sum(a) // 3one = 0res = 0tot = 0for i in range(n-1): # 最后一個(gè)點(diǎn)不能考慮進(jìn)去，要留下一個(gè)做第三部分tot += a[i]if tot == 2*average: res += oneif tot == average:one += 1print(res)

2.改變數(shù)組元素

初始化一個(gè)V 數(shù)組，大小為（n+1）初始化都是0
只需要去通過i去遍歷a[i],遍歷到第i次時(shí)，我們就把 i - a[i] + 1 到 i 全部加1，
i就可以代表V數(shù)組實(shí)際的長度應(yīng)該是多少，例如當(dāng)i = 5 ，那么其實(shí)V數(shù)組實(shí)際上長度是5，因?yàn)槟┪仓槐患恿?個(gè)0 ，然后假設(shè)a[5] = 2 ，那就是V[4] 和 V[5] + 1 ，這里為什么可以+ 1 不用讓他等于1？因?yàn)檎麄€(gè)流程沒有減過，所以只要這個(gè)位置不等于0，就代表他被改變過，一定等于1
然后這種從i - a[i] + 1 到 i 全部加1的實(shí)現(xiàn)通過差分就很好實(shí)現(xiàn)了

具體代碼如下

def add(l,r):  # 差分,最后前綴和后L到R + 1V[l] += 1V[r+1] -= 1 t = int(input())
for _ in range(t):## 第i次就等于從i- a[i] + 1到i 全變?yōu)?## 利用差分，從 i - a[i] + 1 到 i 全部加1 ，因?yàn)椴粫p，所以最后只要前綴和不是0就代表他被換過n = int(input())a = [int(x) for x in input().split()]V = [0]*(n+1) #直接開一個(gè)這么大的數(shù)組,直接開N  TLE了for i in range(1,n+1):  # i要從1開始，i等于1表示數(shù)組中末尾添加了一個(gè)0if a[i-1] == 0:continueif (a[i-1] >= i):add(0,i-1)else:add(i - a[i-1],i-1)for i in range(n):V[i+1] += V[i]for i in range(n):if V[i] != 0 :print(1,end = ' ')else: print(0,end = ' ')print()

3.我在哪？

這題我覺得主要的就是需要考慮到字符串的哈希存儲，因?yàn)樽址疀]法像數(shù)組那樣去用下標(biāo)來找到第幾個(gè)字母，所以得先將字符串進(jìn)行哈希存儲，然后再遍歷遍歷列表，例如k = 4 ，就字符串前四個(gè)的值放入集合中，然后字符串2-5的哈希值看看在不在集合中，如果在，就返回False
然后要找K的話其實(shí)從1開始遍歷就好了，只不過那樣時(shí)間復(fù)雜度是O（n）很可能會被卡，最好用二分

具體代碼如下

字符串哈希

## 核心思想：將字符串看成P進(jìn)制數(shù)，P的經(jīng)驗(yàn)值是131或13331，取這兩個(gè)值的沖突概率低
##  小技巧：取模的數(shù)用2^64，溢出的結(jié)果就是取模的結(jié)果
## h[k]存儲字符串前k個(gè)字母的哈希值, p[k]存儲 P^k mod 2^64
N = 10**5 +10
P = 131
M = 91815541
h = [0] * N
p = [0] * N
p[0] = 1
n = int(input())
s = " " + input()
for i in range(1,n+1):h[i] = h[i-1]*P + ord(s[i]) % M
def get(l,r):return (h[r] - h[l-1] * P**(r-l+1)) % M
def check(k):a = set()for i in range(1,n - k + 2):if get(i,i + k -1) in a:return Falseelse:a.add(get(i,i+k-1))return Trueif __name__ == '__main__':l,r = 1,nwhile l < r:mid = (l + r) >> 1if check(mid): r = midelse: l = mid + 1print(r)

4.字符串刪減

這個(gè)相對于Python來說就很好做吧，別的我不知道，就是記錄一下連續(xù)x的長度，然后最后計(jì)算一下就好了，直接看代碼吧

具體代碼如下

n = int(input())
s = input()
lens = 0
lenshuzu = [] # 記錄每一段連續(xù)的數(shù)組
for i in s:if i == 'x':lens += 1else:lenshuzu.append(lens)lens = 0
lenshuzu.append(lens)
res = 0
for i in lenshuzu:if i >= 3:res += i - 2
print(res)

5.磚塊

這題我選擇算是用貪心的方法去做吧，分為兩種，全變黑和全變白
如果是全變白，那么就當(dāng)看到黑的磚塊，就把他變白就好了
后面的輸入操作的我可能是寫的有點(diǎn)麻煩了。。有大佬有更簡便的可以指導(dǎo)一下

具體代碼如下

T = int(input())
for _ in range(T):k = int(input())p = input()p2 = p #記錄一下p = list(p)caozuo1 = []ans1 = 0flag1 = Falseflag2 = False# 全變白色for i in range(k-1):if p[i] == 'B':p[i] = 'W'if p[i+1] == 'B':p[i+1] = 'W'else: p[i+1] = 'B'caozuo1.append(i+1)ans1 += 1if p == ['W']*k :flag1 = True# 全變黑色p2 = list(p2)caozuo2 = []ans2 = 0for i in range(k-1):if p2[i] == 'W':p2[i] = 'B'if p2[i+1] == 'W':p2[i+1] = 'B'else: p2[i+1] = 'W'caozuo2.append(i+1)ans2 += 1if p2 == ['B']*k:flag2 = Trueif flag1 and flag2:if ans1 < ans2:print(ans1)if caozuo1:for i in caozuo1:print(i,end = ' ')print()continueelse:print(ans2)if caozuo2:for i in caozuo2:print(i,end = ' ')print()continueif flag1:print(ans1)if caozuo1:for i in caozuo1:print(i,end = ' ')print()continueif flag2:print(ans2)if caozuo2:for i in caozuo2:print(i,end = ' ')print()continueprint(-1)

6.樹的遍歷

這題就遞歸做，可以通過中序和后序找到根節(jié)點(diǎn)的左右子樹的中序和后序，然后遞歸往下建立

建立完一棵樹之后就用Dfs去搜索就好了

具體代碼如下

class TreeNode(object):def __init__(self,x):self.val = xself.left = Noneself.right = Noneclass Solution(object):def buildTree(self,inorder,postorder):  # inorder是中序，postorder是后序if not postorder:return Noneroot = TreeNode(postorder[-1])root_index = inorder.index(postorder[-1]) # 根節(jié)點(diǎn)在中序中的坐標(biāo)left_i = inorder[:root_index] # 根據(jù)中序確定左右子樹right_i = inorder[root_index + 1:]len_li = len(left_i)  # 左子樹長度left_p = postorder[:len_li]  # 確定后序遍歷的左右子樹right_p = postorder[len_li:-1]root.left = self.buildTree(left_i,left_p)root.right = self.buildTree(right_i,right_p)return root
def bfs(root):  #廣搜進(jìn)行層序遍歷if root == None:returnq = []q.append(root)head = 0while len(q)!=0:print(q[head].val,end=' ')if q[head].left != None:q.append(q[head].left)if q[head].right != None:q.append(q[head].right)q.pop(0)n = int(input())posto = [int(x) for x in input().split()]
inord = [int(x) for x in input().split()]solution = Solution()
root = solution.buildTree(inord,posto)
bfs(root)

7.親戚

啊這題典型的并查集，讓同樣是親戚的有同一個(gè)祖先就好了，不用管祖先是誰
簡單說一下并查集吧
就是有一個(gè)p數(shù)組，代表自己的父親是誰，然后就是每次遍歷兩個(gè)a,b，如果a和b沒有同一個(gè)祖先，我們就讓a的祖先 去 變成b的祖先的兒子，這樣a和b就有同一個(gè)祖先了吧？
然后怎么找a和b的祖先呢，這也是并查集的精髓所在，一個(gè)find函數(shù)

def find(x):if p[x] != x:p[x] = find(p[x])return p[x]

如果x的父親不是自己，就代表x不是這個(gè)家族的祖先對吧，那么讓p[x]等于find(p[x])，find(p[x])就是找到p[x]的祖先，一層一層網(wǎng)上找，這個(gè)find函數(shù)的精髓在于，他會讓p[x] = find(p[x]) 就是如果你現(xiàn)在他這個(gè)找到祖先的一條線的P[x]都會直接變?yōu)樗麄兊淖嫦?#xff0c;而不是他們的父親
然后就很好做了，看看他們的祖先是否一樣就能代表是不是一個(gè)群體了

具體完整代碼如下

import sys
# 不知道為什么用map(int,input().split())會被卡。。
N, M = map(int, sys.stdin.readline().strip().split())
p = [i for i in range(N + 1)]def find(x):if p[x] != x:p[x] = find(p[x])return p[x]for i in range(M):a, b = map(int, sys.stdin.readline().strip().split())pa, pb = find(a), find(b)if pa != pb:p[pa] = pb
q = int(input())
for i in range(q):a, b = map(int, sys.stdin.readline().strip().split())if find(a) == find(b):print('Yes')else:print('No')

8.笨拙的手指

這題我的想法是，把二進(jìn)制的每一位都變一下，就是把可能的正確答案都存在一個(gè)列表中，然后去對比二進(jìn)制和三進(jìn)制的列表，找到相同的，二進(jìn)制的好做，0和1之間變換只要用^就可以了，三進(jìn)制就需要在遍歷一下1-3 ，如果與當(dāng)前位不同再去變，看代碼吧，蠻容易看懂的，比我寫清晰多了

具體代碼如下

import copy
er = input()
three = input()
erjinzhi = []
sanjinzhi = []
for i in range(len(er)):erjinzhi.append(int(er[i]))
for j in range(len(three)):sanjinzhi.append(int(three[j]))
res_2 = []
res_3 = []
copy_erjinzhi = copy.deepcopy(erjinzhi)
for i in range(len(erjinzhi)):  #勉強(qiáng)算20erjinzhi = copy.deepcopy(copy_erjinzhi)erjinzhi[i] = erjinzhi[i] ^ 1lenlen = 2**(len(erjinzhi)-1)res = 0for j in erjinzhi:res += j*lenlenlenlen >>= 1res_2.append(res)copy_sanjinzhi = copy.deepcopy(sanjinzhi)
for i in range(len(sanjinzhi)):  #勉強(qiáng)算20for j in range(3):sanjinzhi = copy.deepcopy(copy_sanjinzhi)if sanjinzhi[i] != j:sanjinzhi[i] = jlenlen = 3**(len(sanjinzhi) - 1)res = 0for k in sanjinzhi:res += k*lenlenlenlen //= 3res_3.append(res)
res = 0
for i in res_2:for j in res_3:if i == j:res = max(res,i)
print(res)

9.裁剪序列

我也沒搞懂。。抱歉

10.周期

首先，我們要知道KMP算法的next數(shù)組是什么用的，他是可以找到后綴和前綴相同的個(gè)數(shù)的一個(gè)數(shù)組，具體求法可以看我的KMP手寫算法那一個(gè)

然后我們只需要從頭到尾掃一遍，只要（i % (i-next[i])）== 0 就代表有重復(fù)節(jié)，并且長度是i // ( i - next[i])
例如 abcabcabcabc 當(dāng)i等于12時(shí)，就是全長了嘛，然后next[i] = 9
滿足條件吧？ 長度為4

具體代碼如下

def find_next(p):next = [0] * (len(p)+1)j,k = 0,-1next[0] = -1  # 防止死循環(huán) k一直等于0 j也不加while(j <= len(p) - 1):if (k == -1 or p[j] == p[k]):j += 1k += 1next[j] = kelse:k = next[k]next[0] = 0return nextif __name__ == '__main__':flag = 1while True:n = int(input())if n == 0: breakprint('Test case #{}'.format(flag))s = input()next = find_next(s)for i in range(2,n+1):if i % (i - next[i]) == 0 and next[i]:print('{} {}'.format(i,i//(i - next[i])))print()flag += 1

11.最大異或和

先求出前i個(gè)數(shù)的異或和sum[i]，再在大小為m的滑動(dòng)窗口內(nèi)進(jìn)行trie.

參考自https://www.acwing.com/solution/content/48648/
用trie樹嘛，每個(gè)數(shù)都被記錄在一個(gè)trie樹中，一個(gè)二分?jǐn)?shù)，每個(gè)節(jié)點(diǎn)都有一個(gè)0，1孩子，我們這邊用了30層，完全夠用了，然后把每個(gè)數(shù)的二進(jìn)制數(shù)給存進(jìn)去
先計(jì)算前綴異或和s[i]
要求異或和a[l]^…a[r] 轉(zhuǎn)化為前綴異或和數(shù)組(s[r]^s[l-1])

具體代碼如下

N = 100010 * 31
M = 100010
son = [[0]*2 for _ in range(N)]  #　son[p][n] n 只有兩個(gè)取值為0和1，
idx = 0
s = [0]*M
cnt = [0]*N # cnt變量表示這個(gè)節(jié)點(diǎn)在構(gòu)建字典樹的時(shí)候保存了幾次
# 遍歷的時(shí)候，如果節(jié)點(diǎn)的cnt>0，就代表可以接著往下走，
def insert(x,v):global idx,son,s,cntp = 0for i in range(30,-1,-1):# 意思就是一棵樹有30層，來代表每個(gè)數(shù)的二進(jìn)制數(shù)u = x >> i & 1if(int(not son[p][u])):  # p的兒子有0和1兩條路徑idx += 1son[p][u] = idxp = son[p][u]            #p變?yōu)閮鹤?#xff0c;如果v是1，那么這條路徑的p的1兒子+1cnt[p] += v              ### 我們遍歷的話肯定是想從最高位開始，走1的分支，因?yàn)槟菢赢惢蚝筒艜?def query(x):# res 初始值為s[i]res = xp = 0for i in range(30,-1,-1):u = x >> i & 1       # x的二進(jìn)制的第i位
## 現(xiàn)在x的第i位是u ，所以我們要走跟u相反的，這樣他們異或才會為1if cnt[son[p][int(not u)]]:  # 就是存在和不存在 p 有兩個(gè)兒子嘛，一個(gè)是0一個(gè)是1，如果u是1，就要看p的0的兒子還有沒有u = int(not u)res ^= u << i  # u << i 因?yàn)橹?u = x >> i & 1 了，現(xiàn)在還回去# print(res)p = son[p][u]  # 接著往下走return resif __name__ == '__main__':n,m = map(int,input().split())a = [int(x) for x in input().split()]for i in range(1,n+1):s[i] = s[i-1]^a[i-1]insert(s[0],1)Res = 0for i in range(1,n+1):if i > m :insert(s[i - m - 1],-1)Res = max(Res,query(s[i]))insert(s[i],1)        # 把s[i]加入到樹中print(Res)