看上去很复杂的一个题. 然而数据范围 ( n \leq 50 ) 基础知识0: python 里面 list 可以做 dict 的 key. 基础知识1: python 里面 list 可以直接比较大小, 比较方式就是元素的字典序. 做法是先按照 username 对记录进行归类 (dict of list). 然后把每个 username 对应的所有记录按 timestamp 进行排序. (sorted(…, key=lambda …)) 然后枚举每个用户的所有访问页面三元组并扔进 list 里面. 因为要求一个用户只算一次, 所以要去除 list 里面重复的元素. 所以把 list 转换成 set (集合) 就好了. 也可以直接用 set. 然后把 set 里面的元素都用一个 dict 做一下记数. 最后从记数的 dict 里面挑出次数最多且字典序最小的就可以了. 代码链接

首先弄清楚中序遍历是什么意思. 中序遍历是一个序列 (list). 不存在的节点的中序遍历是空序 ([]). 以 u 为根的二叉树的中序遍历 = u 的左儿子的中序遍历 + u + u 的右儿子的中序遍历 其中加号就是连接两个序列的意思. 题目里说只考虑叶子节点的中序遍历, 就是把所有非叶子从中序里扔掉就好了. 然后考虑从随便一个序列构造一个满足条件的二叉树. 其实这个二叉树上的任意一个点会对应原序列中的连续一段, 而这个点的值就是这一段的所有数的最大值. 我们考虑自底向上的建树. 也就是说最开始是 n 个单独的点, 然后每次建一个新点, 它的两个儿子分别是原来的两个点. 然后用这个新点代替原来的两个点. 重复 “挑选, 替代” 的过程直到只剩一个点, 就建成了一棵完整的树. 每次挑选的两个点一定代表原数组上相邻的两个区间. 合并后建成这棵树的 最小 代价为 左儿子的最小代价 + 右儿子的最小代价 + 左边最大值 * 右边最大值. 而我们的最小化目标是根的 最小 代价. 自然想到用 f[l][i] 代表以 i 为第一个数的长度为 l 的区间所代表的点为根的树 的 最小 代价. 首先 f[1][i] == a[i], 而我们的目标是 f[n][0]. 进一步想, 最小化 f[l][i] 就是在所有该点的左右儿子分配方式 (就是各有多长, 总之加起来是 l) 中挑一个最小的....

很基础的 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[正无穷] 中的最大值....

状压动态规划. 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]...

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....

我的愿望真的很简单 如果有一天我变成骨灰了的话 我不想被装进盒子里

看了一篇文章叫 “北大毕业生去送外卖” 以前北大毕业生好像还有去卖猪肉的. 这篇就是, 很真实噢 我们活成了什么样? 我们自己希望活成什么样? 我们被别人希望活成什么样? 我们凭什么要活成别人希望的那样? 再问下去就应该问 “我们为什么要活着” 了 怎么活着不是活着? 人生苦短, 为什么要干这么多不喜欢干的事? 所谓 “幸福” 的 “未来”, “前途”, 谁知道是不是扯淡? 我大胆猜想, 都是一个更大的坑 因为投入多 期待有收益 但现在没有得到应有的收益 出于愚蠢/拖延 只能天真地期望未来的收益/下一代带来收益 切 还不如活得洒脱一点呢 Historical Comments AInoob at 2019-07-18T13:36:31 活得快乐就不错吧。虽然我还没想好搞什么。 laekov at 2019-07-24T04:49:21 @Alnoob 快乐也没有那么简单吧..