很基础的 BFS 题目. BFS 和 DFS 是相对应的两种算法. 其区别在于对于新发现的可能性, BFS 将其放入队列末尾, 稍后进行探索, 而 DFS 立即探索这种新情况, 等探索完之后再回到之前的状态继续枚举. 对于这道题目来说, 具体来讲, 状况可以用 (位置, 距离, 颜色) 这么一个 tuple 来表示. 最开始的时候, 有 (0, 0, blue) 和 (0, 0, red) 这两种情况. 假设 0到1 有一条蓝边, 0到2 有一条红边, 那么新的情况是 (1, 1, red) 和 (2, 1, blue). 如果我们使用 DFS, 那么当新发现 (1, 1, red) 这个状态的时候, 我会立即以 (1, 1, red) 为起点, 继续探索 1 号点的邻居, 比如找到了 (3, 2, blue) … 直到找完所有通过 (1, 1, red) 可以达到的状态之后, 再继续以 (2, 1, blue) 为基础进行枚举....
先预处理一下, 把 >8h 的变成 +1, <=8h 的变成 -1 现在问题就变成了: 找最长的连续一段使其和 >0 使用前缀和数组, 要求 i~j 的和, 公式是 sum[j] - sum[i - 1]. 枚举左端点 i. 对于某个确定的 i, 要找以 i 为左端点的最长一段符合要求的区间, 即找满足条件 sum[j] > sum[i - 1] 的最大的 j 注意到 sum 数组的取值为 [-n, n], 故使用值域数组 values. value[k] 表示 sum[j] == k 的最大的 j. 该数组可以在求 sum 数组时一并求出. 满足条件 sum[j] > sum[i - 1] 的最大 j 即求 values[sum[i - 1] + 1], values[sum[i - 1] + 2], values[sum[i - 1] + 3], …, values[正无穷] 中的最大值....
class Solution: def longestWPI(self, hours: List[int]) -> int: for i, h in enumerate(hours): hours[i] = 1 if h > 8 else -1 s = [0] n = len(hours) values = [0] * (n * 2 + 2) for i, h in enumerate(hours): s.append(s[-1] + h) values[s[-1] + n] = i + 1 for i in range(n * 2 - 1, -1, -1): values[i] = max(values[i], values[i + 1]) answer = 0 for i in range(n): answer = max(answer, values[s[i] + n + 1] - i) return answer
状压动态规划. dp[x] 表示 x 状态下的最少人数. 其中 x 是二进制数, 第 i 位表示第 i 项技能是否有人已经拥有. 例如 ( x = (10010)_2 ) 从右往左第 1, 4 位是 1, 表示技能 1, 4 已有人掌握, 而 0, 2, 3 无人掌握. 假设一个人的技巧是 p, 现在的状态是 x, 则加入后的状态是 x|p. 其中 | 即 python/cpp 中的 | 运算符, 意义是取二进制或. 运算过程为最初时只有 dp[0] = 0. 对于每个人的技能集合 p, 可以更新 dp 数组 dp[x | p] = min(dp[x | p], dp[x] + 1) 最后的答案是 dp[((111\dots 1)_2)] 即 dp[(1 « len(skills)) - 1]...
class Solution: def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]: m = len(req_skills) dp = [99999] * (1 « m) fr = [None] * (1 « m) dp[0] = 0 for pi, p in enumerate(people): skills = 0 for s in p: try: idx = req_skills.index(s) skills |= 1 « idx except Exception: continue for i in range(1 « m): if dp[i | skills] > dp[i] + 1: dp[i | skills] = dp[i] + 1 fr[i | skills] = (i, pi) result = [] stat = (1 « m) - 1 while stat > 0: result....
ISC'19. 一场大概是退役失败的超算比赛. 我负责的 part 是 AI, 还有万年大锅 HPL, 以及神秘应用. 还有就是订保险订酒店联系赞助商blabla. 本来想帮忙搞 HPCC 的但是没有精力搞不动 ovo AI AI 题是去年的 GB 论文 + 精调模型. 在解决了组委会提供的脚本里的一些性能上的 bug 之后顺利地训了起来. 而且按照原文里在上千个节点上并行训还能收敛来讲, 是可以在现有机器条件下随便数据并行的. (事实证明直接把整个训练集切成 10 个batch 也没有问题) 因为最终要求是精度, 所以请教了一些人, 得到的思路是 数据增强, ensemble. 数据增强不太写得动, 于是改脚本做了 ensemble 的 inference, 效果还不错. 比原文高了几个点. 但也没有特别闪亮的突破性进展. 唯一发现是 bn 用的是 training mode. (原因应该是 tf 的 bn 一直自带 bug, 如果用推理模式精度就是会炸掉) 于是推理的时候也应该 bs 越大越好. 于是就有了 dummy sample inference + unique 的一个脚本. 然后因为没有处理好 “//” 于是组委会还怀疑了半天为什么我的脚本有锅. 哭. 然后就是现场出了一个锅: unseen dataset 发下来一看居然是事前给出的 test set....
前段时间遇到 mac 微信出了一个锅. 部分微信群和联系人在电脑上收不到消息, 可以发消息, 但发出去一直显示转圈圈 (其实对方已经收到了), 切换窗口再切回来就连之前自己发的消息都不见了ovo 然而因为不太影响使用(可以在手机上看消息, 电脑盲回) 所以没太管. 但是作为一个强迫症还是不太能忍, 于是过了好久还是决定动手修一下. mac下微信的本地数据文件在 /Users/laekov/Library/Containers/com.tencent.xinWeChat/Data/Library/Application Support/com.tencent.xinWeChat/2.0b4.0.9. 初步估计是本地文件出锅了, 于是对它动手. 首先在mac端不上线的情况下手机拉了一个不影响别人的群, 然后用mac登录, 果然这个群属于bug群. 把 Message 目录移动为 Message_bak, 重新登录, 失去了所有聊天记录. 再次尝试使用上面那个群, 发现可以正常使用. 定位到问题文件在 Message 目录里. 发现 Message 目录下有 msg_[0-9]十种前缀的文件, 估计是对聊天记录进行了分桶. 大胆猜测是某个桶坏了. 于是等了一分钟后在群里发了一条消息, 发现只有 msg_6 开头文件被更新了. 大胆猜想是 msg_6 这个桶炸了. 另有有一个 MessageTemp 目录较大, 目测是数据文件. (比如消息, 图片, 视频) 猜想这里放的是元数据. 于是把旧的 MessageTemp 先拷回来. 然后恢复了 msg_1 开头的几个文件, 发现果然聊天记录回来了一部分. 挨个恢复除了 msg_6 以外的所有 msg_x 文件, 于是除了之前炸掉的记录以外, 聊天记录都回来了. 坏掉的文件就确实没法修了. 鬼知道.data格式是啥玩意. 完结撒花....
许久没写过博客了. 看到 harry 写了赛记才想起我还有个博客. 随便写一点东西吧. ASC19. 拿了 “大满贯” 之后第一场比赛, 拿了个亚军. @大连理工 Sec 0 赛前给自己的定位大概就是, 学学配机器和benchmark这种看上去比较底层的东西. 应用上就划划水好好干别的事. 于是初赛成为了写 proposal 选手 + 装机器选手. 最初装机器闹了很多笑话 比如在R730上把 V100 的挡板拆了然后导致显卡悬空. 感谢戴尔和 NVIDIA 的 PCIe 槽足够结实没有直接坏掉让我赔20万的机器的卡. 然后 proposal 也是写到崩溃 ovo. 然后跑 HPL 发现各种玄学, 以及 32G 的 V100 性能和 16G 的不太一样. 单卡跑不上去, 多卡也有各种问题. 然后 P, Q, NB 有很多玄妙的组合. (后来知道 N 也有很多玄学). 以及连续跑和单独跑是不一样的. 这还是不考虑功耗在四台 R730 上插上 8 张卡裸跑的情况. HPCG 单卡不压功率也只有 125 的样子. 另一个神奇的情况是直接跑HPL会报 MPI Error: Illegal address. 解决它的方法是, 跑一次HPCG....
我的愿望真的很简单 如果有一天我变成骨灰了的话 我不想被装进盒子里
看了一篇文章叫 “北大毕业生去送外卖” 以前北大毕业生好像还有去卖猪肉的. 这篇就是, 很真实噢 我们活成了什么样? 我们自己希望活成什么样? 我们被别人希望活成什么样? 我们凭什么要活成别人希望的那样? 再问下去就应该问 “我们为什么要活着” 了 怎么活着不是活着? 人生苦短, 为什么要干这么多不喜欢干的事? 所谓 “幸福” 的 “未来”, “前途”, 谁知道是不是扯淡? 我大胆猜想, 都是一个更大的坑 因为投入多 期待有收益 但现在没有得到应有的收益 出于愚蠢/拖延 只能天真地期望未来的收益/下一代带来收益 切 还不如活得洒脱一点呢