Day 31 (2022.2.12)
# acwing 1224. 交换瓶子
if __name__ == '__main__':
n = int(input())
arr = [0]+[int(x) for x in input().split()]
st, cnt = [0]*(n+1), 0
for i in range(1,n+1):
if not st[i]:
cnt += 1
while not st[i]:
st[i] = 1
i = arr[i]
print(n-cnt)
Day 32 (2022.2.13)
今天复习了下树状数组和线段树，然后油漆面积和三体攻击就没有认真研究了，感觉很有难度，可以先放一放。
# acwing 1228. 油漆面积
if __name__ == '__main__':
n = int(input())
arr, x_max, y_max = [], 0, 0
for _ in range(n):
square = [int(x) for x in input().split()]
x_max, y_max = max(x_max, square[2]), max(y_max, square[3])
arr.append(square)
squares = [[0]*y_max for _ in range(x_max)]
for i in range(n):
x1,y1,x2,y2 = arr[i]
for x in range(x1,x2):
for y in range(y1,y2):
squares[x][y] = 1
res = 0
for i in range(x_max):
for j in range(y_max):
if squares[i][j]!=0: res+=1
print(res)
Day 33 (2022.2.14)
# acwing 1240. 完全二叉树的权值
if __name__ == '__main__':
n = int(input())
arr = [0] + [int(x) for x in input().split()]
depth, v_max, depth_max = 0, -float('inf'), 1
width, i = 1, 1
while i <= n:
tmp_v, depth = 0, depth+1
for j in range(width):
if i+j <= n: tmp_v += arr[i+j]
if tmp_v > v_max:
depth_max = depth
v_max = tmp_v
i += width
width *= 2
print(depth_max)
完全二叉树的性质：1. 每一层节点编号从 2^(n-1) - 2^n-1
2. 每一层节点数 2^(n-1)
3. 树的深度 floor(log2(n))+1
