广州专门做网站,目前网站开发状况,wordpress 文章静态,网站首页设计代码refs: OI Wiki - OI Wiki (oi-wiki.org) 1. 枚举
POJ 2811 熄灯问题 refs : OpenJudge - 2811:熄灯问题 如果要枚举每个灯开或者不开的情况#xff0c;总计2^30种情况#xff0c;显然T。
不过我们可以发现#xff1a;若第i行的某个灯亮了#xff0c;那么有且仅有第i行和第… refs: OI Wiki - OI Wiki (oi-wiki.org) 1. 枚举
POJ 2811 熄灯问题 refs : OpenJudge - 2811:熄灯问题 如果要枚举每个灯开或者不开的情况总计2^30种情况显然T。
不过我们可以发现若第i行的某个灯亮了那么有且仅有第i行和第i1行的同一列的灯可以影响到它把它关掉。
如果某一行的操作已经结束那么就只有下一行能影响到它了。因此我们可以仅仅枚举第一行的所有操作序列。接下来的每行都会尝试去“填补”上一行产生的问题也即上一行的没有熄灭的灯。
在枚举第一行的操作序列时我们可以发现这是一个长度为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 0xm and 0yndef flip(x:int,y:int,puz:List[List[int]]):for direction in directions:nx,ny xdirection[0],ydirection[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] fop1fop 1puz mat_clone(grid)for i,op in enumerate(ops[0]):if op1: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 kcurr targetSum:ans vif kcurr in tmp:tmp[kcurr] velse:tmp[kcurr] 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,i1)设第i个大臣前的左手数字的乘积为s。金币最大数有以下两种情况
(i,i1) (i1,i) 若前者站位方式更优于后者则 等价于通分约分 也就是说对于任意相邻的两个大臣计算上式如果前者更大那么这两个大臣应该互换位置。
注意这个过程是递归的如果(i,i1)换了位置那么还得检查(i-1,i1)要不要换位置……直到不需要换位置为止。核心思想是每次交换都把相邻两人之间的最大金币数削减到更小的值。
那么这个一直交换的过程相当于什么呢显然是冒泡排序。
所以在具体实现时我们可以把每个大臣手里的数封装为一个类实例然后覆写比较类实例的函数直接对实例列表排序即可冒泡排序本身是排序的一种实现方式既然我们要对整个列表排序为什么不用更快的排序方式呢比如py提供的内置快排
n int(input())a,b tuple(map(int,input().split()))from functools import total_orderingtotal_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的题解但没人说过传递律的问题。可以想见一些贪心算法的证明中到底遗漏掉了多少细节和重要的地方。
