结果与总结
这里是式酱～(∠・ω< )⌒☆
很遗憾没能AK混个牌子，只做了4道题，T5感觉是知识盲区了，可能是个带优化的回溯？，疯狂TLE，好在前面四题都没WA，拿了81名，能进前百就满足了，赛后去把T5补一下。
1. 补给马车
数据范围很小，按照题意，直接写个暴力进行模拟即可。
class Solution:
def supplyWagon(self, supplies: List[int]) -> List[int]:
n = len(supplies)
while True:
min_i = -1
min_val = 10**9
for i in range(1,len(supplies)):
d = supplies[i] + supplies[i-1]
if d < min_val:
min_val = d
min_i = i
if len(supplies) == n//2:
return supplies
supplies = supplies[:min_i - 1] + [min_val] + supplies[min_i+1:]2. 探险营地
同样的，根据题意进行暴力即可，python的字符串处理起来确实很方便，写的很快，记得先把空字符串加入set中，空字符串无法表示新区域。
class Solution:
def adventureCamp(self, expeditions: List[str]) -> int:
d = set()
d.add('')
x = expeditions[0].split('->')
for s in x:
d.add(s)
ans = -1
max_count = 0
for i in range(1,len(expeditions)):
x = expeditions[i].split('->')
count = 0
for s in x:
if s not in d:
count += 1
d.add(s)
if count > max_count:
max_count = count
ans = i
return ans3. 最强祝福力场
第一眼看见以为是一个比较复杂的扫描线问题（可以参考一下主站内的矩阵面积这道题），但是数据范围很小，那么直接暴力O(n^3)的写法也是可以过的，可以这样思考：
1.多个矩阵重叠的区域，他一定也是一块矩形。
2.这个区域内有无数个点，有没有什么点是特殊的呢？
选择最边角上的点，一定有点(x,y)满足x在某个矩形的边缘，y在某个矩形的边缘,因为数据范围很小，直接先验（x，y），然后根据矩形反推多少矩形包含这个点即可。
class Solution:
def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:
x_index = set()
y_index = set()
for x,y,size in forceField:
x_index.add(x - size/2)
x_index.add(x + size/2)
y_index.add(y - size/2)
y_index.add(y + size/2)
ans = 0
for x in x_index:
for y in y_index:
count = 0
for dx,dy,size in forceField:
if abs(x - dx) <= size/2 and abs(y - dy) <= size/2:
count += 1
ans = max(ans,count)
return ans4. 传送卷轴
思路比较复杂，需要慢慢盘点其中的细节。
首先需要从终点end走一个最短路，把终点能到达的点的最短时间都算出来，无法到达则记为inf.
然后对maze这个图进行预处理，得到的change数组表示在当前这个位置如果魔法师改变了小扣的位置，那么他到达终点的距离此时是多少？（这里有部分细节，如果传送后的位置是块石头，那么是不可传送的，此时无法附加负面效果，相当于代价为0，否则这两个镜像位置的代价取一个max，代价为之前预处理的end到达镜像点的距离）。
得到change数组之后，我们知道每个位置魔法师对小扣施加魔法之后，小扣应该付出多少代价，那么此时小扣往终点走，他的最优策略是什么呢？当然是在往终点走的同时避开传送后代价最大的点，才可以让最终的答案最小。
这就回到了经典原题，在图中走一个路径，路径上最小化点权的最大值，可以用二分也可以用并查集。
经典模板题 1631. 最小体力消耗路径
class Solution:
def challengeOfTheKeeper(self, maze: List[str]) -> int:
# 守护者可以不使用卷轴； --> 从起点出发直接无法到达
# 传送后的镜像位置可能与原位置相同。
m = len(maze)
n = len(maze[0])
for i in range(m):
for j in range(n):
if maze[i][j] == 'T':
end = (i, j)
if maze[i][j] == 'S':
start = (i, j)
# 从终点跑一次bfs，记录每个点到终点的距离
dist = [[inf] * n for _ in range(m)]
dist[end[0]][end[1]] = 0
q = deque([end])
while q:
x, y = q.popleft()
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] != '#' and dist[nx][ny] == inf:
dist[nx][ny] = dist[x][y] + 1
q.append((nx, ny))
change = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
# 是石头不可以传送
if maze[m - 1 - i][j] == '#' and maze[i][n - 1 - j] == '#':
continue
elif maze[m - 1 - i][j] == '#':
change[i][j] = dist[i][n - 1 - j]
elif maze[i][n - 1 - j] == '#':
change[i][j] = dist[m - 1 - i][j]
else:
change[i][j] = max(dist[i][n - 1 - j], dist[m - 1 - i][j])
change[end[0]][end[1]] = 0
# print(change)
# 二分沿途最大值
def check(k):
q = deque([start])
visit = [[False] * n for _ in range(m)]
while q:
x,y = q.popleft()
if x == end[0] and y == end[1]:
return True
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] != '#' and not visit[nx][ny] and change[nx][ny] <= k:
visit[nx][ny] = True
q.append((nx, ny))
return False
l = 0
r = 4*m*n
while l <= r:
mid = (l + r) // 2
if check(mid):
r = mid - 1
else:
l = mid + 1
return l if l <= 4*m*n else -1LCP 76. 魔法棋盘
这题的难度很大，数据范围刚好卡的死死的，时间复杂度O(m*21^n)(严格保证n<=5,约为2e8，实践上有很多状态是无用的，大概最终跑的数据约为1e7) 加上lc特立独行的总时间判定机制，如果每次都去重新处理的话，肯定无法通过。需要在大量地方做预处理节省时间。
1.两颗异色棋子在同一行或者同一列且两颗异色棋子之间恰好只有一颗棋子，等价于每行每列要么全是一种颜色，要么就是每种颜色交替出现（中间可以填空位，但不能出现两个相同棋子连一起出现）
2.由于指数的复杂度很大，一旦我们发现m < n的时候（极端情况下m == 1，n == 30），此时状压时间复杂度直接爆表，我们就对行列进行互换，这样不影响我们最后的答案，但是把指数的复杂度往下降。
3.把取空当成0，取红当成1，取蓝当成2，我们先对行进行预处理，通过check函数把每个行不互斥的情况统计出来，也就是代码最开头的部分。然后对当前方阵每行能够取到的mask进行预处理（有k个"?"就有3**k种可能）。至此，预处理部分完成。
4.每一列当前的颜色，能否取得，只与上一行以及上上一行的颜色有关，因此可以对上一列以及上上列的颜色做一个状压，状态会有7种：无/单红/单蓝/红红/红蓝/蓝红/蓝蓝，分别对应0,1,2,4,5,7,8。出现冲突的情况有且仅有红碰上蓝蓝,蓝碰上红红，红碰上红蓝，蓝碰上蓝红这四种。用ok函数判断mask和pre_mask是否冲突。
5.往新行转移时，设该列前两种颜色是c1，c2，如果此行颜色c取空，那么颜色依然为c1，c2，否则则变为c，c1。
6.至此用dfs(i,pre_mask)进行记忆化搜索，转移过程的条件判定以及转移过程的mask变化都已经完成。对update和ok放在外面进行记忆化是因为重复的运算过多，如果放在里面和不做记忆化会TLE，合并与矩阵无关.
ok 总状态数 (< 21^n)
update 总状态数(< 21 ^ n)
dfs 总状态数 (m*7^n)
# 预处理行内不会出现共鸣的情况 保证每行不互斥
def check(mask):
li = []
while mask:
if mask % 3:
li.append(mask % 3)
mask //= 3
# 只有一种
if len(set(li)) <= 1:
return True
# 交替出现
for i in range(1, len(li)):
if li[i] == li[i - 1]:
return False
return True
# 预处理行不互斥的情况，n=5的时候最多只有115种情况
col_mask = [set() for _ in range(6)]
for n in range(1, 6):
for i in range(3 ** n):
if check(i):
col_mask[n].add(i)
@cache
def ok(mask, pre_mask):
# 本身行自身冲突
for _ in range(n):
# 红碰上蓝蓝
if mask % 3 == 1 and pre_mask % 10 == 8:
return False
# 蓝碰上红红
if mask % 3 == 2 and pre_mask % 10 == 4:
return False
# 红碰上红蓝
if mask % 3 == 1 and pre_mask % 10 == 5:
return False
# 蓝碰上蓝红
if mask % 3 == 2 and pre_mask % 10 == 7:
return False
mask //= 3
pre_mask //= 10
return True
@cache
def update(mask, pre_mask):
new = 0
for i in range(n):
cur = mask % 3
# 这列目前有颜色 不是空
if cur != 0:
pre = (pre_mask % 10) // 3
new += 10 ** i * (3 * cur + pre)
else:
new += 10 ** i * (pre_mask % 10)
mask //= 3
pre_mask //= 10
return new
class Solution:
def getSchemeCount(self, n: int, m: int, chessboard: List[str]) -> int:
# 每行每列黑红黑红黑排列
# 或者要么就全红 要么就全黑
# 只需要维护行的上一个状态和上上一个状态即可
m = len(chessboard)
n = len(chessboard[0])
# 三进制枚举 由于指数的关系，所以三进制表示的部分尽量小,m < n就交换行列
# 对于每一列来说，状态会有7种：无 / 单红 / 单蓝 / 红蓝 / 红红 / 蓝蓝 / 蓝红。
# 分别对应0,1,2,4,5,7,8
# 为了方便 列就采用10进制表示，但是实际只有7种状态
if m < n:
m, n = n, m
chessboard = list(zip(*chessboard))
# 预处理每行可选的mask
ms = []
for index in range(m):
mask = 0
for j in range(n):
if chessboard[index][j] == 'R':
mask += 3 ** j
elif chessboard[index][j] == 'B':
mask += 2 * 3 ** j
temp = [mask]
for j in range(n):
if chessboard[index][j] == '?':
temp += [x + 3 ** j for x in temp] + [x + 2 * 3 ** j for x in temp]
ms.append([x for x in temp if x in col_mask[n]])
# 0代表空 1代表红 2代表黑
@cache
def dfs(index, pre_mask):
if index == m:
return 1
# 有初始放置的棋子，不能与他们冲突
ans = 0
for mask in ms[index]:
if ok(mask, pre_mask):
ans += dfs(index + 1, update(mask, pre_mask))
return ans
return dfs(0, 0)写在最后
