dsa加训

refs: OI Wiki - OI Wiki (oi-wiki.org)

1. 枚举

POJ 2811 熄灯问题

refs : OpenJudge - 2811:熄灯问题

如果要枚举每个灯开或者不开的情况，总计2^30种情况，显然T。

不过我们可以发现：若第i行的某个灯亮了，那么有且仅有第i行和第i+1行的同一列的灯可以影响到它（把它关掉）。

如果某一行的操作已经结束，那么就只有下一行能影响到它了。因此我们可以仅仅枚举第一行的所有操作序列。接下来的每行都会尝试去“填补”上一行产生的问题（也即上一行的没有熄灭的灯）。

在枚举第一行的操作序列时，我们可以发现这是一个长度为6的0-1串，因此转换为十进制后，范围在0-63，我们可以用一个range(64)的列表以及位运算来实现这个操作。

from typing import Listgrid = []m,n = 5,6for _ in range(m):grid.append(list(map(int,input().split())))# 仅枚举第一行，检查剩余行 操作从全0到全1
f_ops = [x for x in range(64)]directions = [(0,0),(-1,0),(0,1),(1,0),(0,-1)
]def mat_clone(g:List[List[int]])->List[List[int]]:r,c = len(g),len(g[0])ans = [[0 for _ in range(c)] for _ in range(r)]for i in range(r):for j in range(c):ans[i][j] = g[i][j]return ansdef all_down(g:List[List[int]])->bool:return sum([sum(g[i]) for i in range(len(grid))])==0def is_valid(x:int,y:int)->bool:return 0<=x<m and 0<=y<ndef flip(x:int,y:int,puz:List[List[int]]):for direction in directions:nx,ny = x+direction[0],y+direction[1]if is_valid(nx,ny):puz[nx][ny] = 1-puz[nx][ny]def check(fop:int)->bool:ops = [[0 for _ in range(n)] for _ in range(m)]for i in range(n-1,-1,-1):ops[0][i] = fop&1fop >>= 1puz = mat_clone(grid)for i,op in enumerate(ops[0]):if op==1:flip(0,i,puz)for i in range(1,m):for j in range(n):if puz[i-1][j]==1:ops[i][j] = 1flip(i,j,puz)if all_down(puz):for row in ops:print(' '.join(list(map(str,row))))return Truereturn Falsefor f_op in f_ops:if check(f_op):break

我觉得这道题我写的已经比较优雅了，仅仅60行。

假设行数为m，列数为n，则时间复杂度O(mn*2^n)

3. 递归

LC 437 路径总和Ⅲ

refs: 437. 路径总和 III - 力扣（LeetCode）

向下深搜，维护任意一个子链的路径和到哈希表里，key是路径和，v是出现次数。每次把当前节点加到其下的子链的路径和上去，如果发现为targetSum，则根据v更新答案。

class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:ans = 0def check(d:dict,tmp:dict,curr:int):nonlocal ansfor k,v in d.items():if k+curr == targetSum:ans += vif k+curr in tmp:tmp[k+curr] += velse:tmp[k+curr] = vdef dfs(node:TreeNode)->dict:if node is None:return {}nonlocal ansld = dfs(node.left)rd = dfs(node.right)if node.val == targetSum:ans += 1res = {}res[node.val] = 1check(ld,res,node.val)check(rd,res,node.val)return resdfs(root)return ans

还有种写法更加简洁，运行时间也更短的：维护任一子链前缀和并置入哈希表，key是前缀和，v是出现次数。查询去掉多少个前缀和可以将当前节点和剩余前缀和加起来等于targetSum即可。

class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:m = defaultdict(int)m[0] = 1def dfs(node:TreeNode,prefix:int)->int:if node is None:return 0cnt = 0prefix += node.valif prefix - targetSum in m:cnt += m[prefix-targetSum]m[prefix] += 1cnt += dfs(node.left,prefix)cnt += dfs(node.right,prefix)m[prefix]-=1return cntreturn dfs(root,0)

注意维护哈希表时记得回溯时去掉当前prefix，不然可能导致a链上的前缀和被b链上的节点所用。也即

m[prefix] -= 1

时间复杂度：瓶颈哈希表，O(n)

5. 贪心

NOIP2012提高组D1T2

refs: 国王游戏 - Vijos

这题挺难的，思维上想不到，不是dsa知识储备的问题。

设第i个大臣手上的数为

对于任意合法的(i,i+1)，设第i个大臣前的左手数字的乘积为s。金币最大数有以下两种情况：

1. (i,i+1)：

1. (i+1,i)：

若前者站位方式更优于后者，则：

等价于（通分+约分）：

也就是说，对于任意相邻的两个大臣，计算上式，如果前者更大，那么这两个大臣应该互换位置。

注意，这个过程是递归的，如果(i,i+1)换了位置，那么还得检查(i-1,i+1)要不要换位置……直到不需要换位置为止。核心思想是每次交换都把相邻两人之间的最大金币数削减到更小的值。

那么这个一直交换的过程相当于什么呢？显然，是冒泡排序。

所以在具体实现时，我们可以把每个大臣手里的数封装为一个类实例，然后覆写比较类实例的函数，直接对实例列表排序即可（冒泡排序本身是排序的一种实现方式，既然我们要对整个列表排序，为什么不用更快的排序方式呢？比如py提供的内置快排）

n = int(input())a,b = tuple(map(int,input().split()))from functools import total_ordering@total_ordering
class nh:def __init__(self,tup:tuple) -> None:self.l = tup[0]self.r = tup[1]def  __lt__(self,x)->bool:if isinstance(x,nh):return max(x.r,self.l*self.r) < max(self.r,x.l*x.r)lrh = [] 
for _ in range(n):lrh.append(nh(tuple(map(int,input().split()))))lrh = sorted(lrh)mx = 0
base = afor nho in lrh:mx = max(mx,base//nho.r)base *= nho.lprint(mx) 

时间复杂度O(nlogn)，瓶颈在排序。

不过这里还有一个问题，我们不妨从归并排序的角度来考虑。

假设我们现在有两个分开的子序列，不妨叫L和R好了，那么在归并时，我们不断从L和R的头部元素中选个最小的放进去。例如，一个归并的结果可能是：

也就是说：

这个不等式拆成两份看都没什么问题，毕竟子序列有序，但问题是，为什么

能推出来

从直观感受上来说，当比较类实例时，我们比较的是相邻元素在上式中的值，当两个元素不相邻，为什么会有传递律？

这个还需要从数学上给出一个数值的证明。我们假设有三个大臣，其手上的数为：

根据上述定义，有：

我们知道，若：

则

于是有：

去掉重复项：

也即(l1,r1)<(l3,r3)的定义。

因此传递律得证，我们可以放心大胆地排序了。

有感

从大二上第一次接触到贪心算法开始，我就觉得这是一个很容易盛产“江湖骗子”的知识点。它不像dp，人家是有严格的状态定义和转移方程的，所以比较令人放心。但是贪心更偏思维和直观感受，或者说就是口胡。说难听点，我觉得除了个别显然且直观的贪心算法的证明（如最短路反证法），其他证明，就算是写在了教科书上，也是“以其昏昏，使人昭昭”，很多时候看到一个证明，我的感受就是：“啊？这就证出来了？”包括我自己写的有关贪心算法的证明，十个里面估计有九个都是在胡扯。这个东西对于我来说几乎无法证明，甚至无法理解别人的证明。

拿这个国王游戏举例，覆写lt然后直接对实例列表进行排序，可以A，而且跑的还很快。可关键在于，如果按照最朴素的邻项交换，那么就会是一个O(n^2)的冒泡排序，虽然跑得慢，但是人家实打实地比较了任意两个元素之间的大小。但如果是归并或者快排，无疑建立在了这个类的实例遵循传递律的基础上，那么传递律又是谁保证的呢？因此我觉得讨论传递律是非常必要的。我在题解区看了一圈，有不少跟我一样直接对实例列表调内置库的sorted的题解，但没人说过传递律的问题。可以想见一些贪心算法的证明中到底遗漏掉了多少细节和重要的地方。