yhz012

女人唱歌.jpg 让我看看这题 最暴力的做法就是直接求团长到车上的时间和追兵到车上时间就可以了吧？ 问题见下面回复 跑路时间是 (c - a) / s1， (c - b) / s2 障碍时间追兵的很好算，直接n * t2就完了，团长的需要处理下，不过直接线性扫过去就好了吧，大于a的就计入

其实就是线性规划但是要求解只能是0和1里面选 某种意义上你可以理解为扫雷其实就是01规划问题，顺带一提这问题是NP完全问题，所以会有很多相关的问题

自己实现需要一些知识点 为了方便我们以这道题考虑，每个石头的魔力是0~M/3，为了方便我就用u = M/3来写了，我们一共打算开n个空位来保存这些石头。这里u大概是10^17，n大概是10^4 第一个就是universal hash family 作为大前提，任何确定的hash函数都会在某些特定的输入上出现严重的冲突。因为很显然我们要把10^17映射到10^4里，那至少有一个格子要对应至少10^13个不同的石头。在这种情况下，如果你先给我个确定的函数来映射，那我一定能找到这个格子，然后挑这堆格子的对应的石头给你，结果就是所有石头全跑一个格子里去了，打表大失败 所以我们需要的是反过来，我有一组hash函数，你先给我石头，然后我随机挑一个函数来映射。如果映射的结果好，那万事大吉。如果映射的结果不好，退一万步说最坏情况下我可以重选一个，然后再映射。 只要我映射的结果好的概率足够大，那就不是问题。 更数学一点的说法就是，我现在有一组函数。我任意拿出两块石头，我都能保证在我这一组函数中，我随便拿出来一个，让这俩石头映射到一个格子里的概率只有1/n 再换一个表述方式就是，假设我们一共有H个函数，对于任意两块石头，最多有H/n个函数把这两块石头放到一起 而满足这个定义的这一组函数的集合，称为universal hash family 之所以需要这个集合，是因为我们核心目的是希望平均来说，每个格子尽可能少的石头 具体来讲比如我们现在需要一个x的石头，这时候如果同一个格子里有个y石头，那我们就需要再花时间来判断哪个是x哪个是y，如果更多，我就需要花费更多的时间。 根据上面的universal hash family定义，和x映射到同一个格子的概率是1/n，我一共有n块石头，所以期望是1块。换句话说平均来说，每个格子里只会有2块石头，分辨2块石头的时间是O(1)的级别，所以问题不大。 接下来的问题就是我们需要找到一个这样的universal hash family 这里开始会涉及一点数论的知识了。另外构造方法不唯一，我只是拿一个我习惯的例子 我们目标是开至少n个格子，为了方便一点，我能找到一个刚好比n大一点的素数p，我直接开p个格子 每个石头的魔力量我都可以写成p进制的形式，举例来说p = 3的情况下，5魔力我就可以写成(0, 0, 0, ..., 0, 1, 2)，一共log_3 (u) 个分量 因此任意的一个石头x，我都能写成(x_r, x_{r-1}, ..., x_2, x_1, x_0)的形式。这里r = log_p (u) 同时我构造这样一个数组，a = (a_r, a_{r-1}, ..., a_2, a_1, a_0)，每一位也都是在[0, p-1]里面随机选 我的hash函数就是 a 和 x 对应位相乘后对p取余，然后求和，即 sum_i (a_i * x_i) % p 因此整个universal hash family 就是所有可能取到的a 接下来我需要证明这个确实是个universal hash family 那我们考虑两个不同的石头x和y 因此我写成p进制之后至少存在一个分量 x_k != y_k 我们把这一个分量单独拿出来，选择随机的一个hash函数h： h(x) = (x' + a_k * x_k) % p，其中x'是其他分量的求和 h(y) = (y' + a_k * y_k) % p 如果相等，意味着 a_k (x_k - y_k) % p = (x' - y') %p 这里我需要两个数论的定理了 定理1： 给定非零整数 i < p，那么有 ix %p = iy %p 当且仅当 x %p = y %p 定理2： 给定整数 b, c < p，且b != 0，有且仅有一个整数a < p，使得 a * b %p = c 根据这两个定理，我们回到上面的 a_k (x_k - y_k) % p = (x' - y') %p 意味着有且仅有一个a_k使得上述等式成立 而a_k我们是在0~p-1里面随机选的。所以h(x) = h(y)的概率就只有1/p。证明完毕。 给定以上情况，我们已经找到了一个universal hash family，用这个就可以构造hashmap了 接下来是性能分析的问题 平均来说，映射到一起的概率是1/n，所以平均查找速度是O(1 + n * 1/n) = O(1) 但是上面只是平均结果，我们会存在一些格子有更多的石头，可以计算得到最满的格子里的石头个数的期望是O(log n / log(log n) )，如果你不是很在意这一丁点的性能差异的话，几乎和O(1)没啥问题，直接用也可以了 如果很在意，我们有以下解决方案 1. 之前我们考虑的是放到n个格子里，现在如果我们用放到n^2个格子里，经过计算是可以保证时间复杂度的（可以用马尔科夫不等式证明不产生冲突的概率至少是1/2），不过问题是我们需要n^2空间，有的时候还是挺肉疼的 2. 之前我们是用类似链表的形式处理放在同一个格子里的石头的，实际上我们可以再进一步在这个格子里继续构造一个二级的hashmap，经过计算也是可以保证时间复杂度和空间复杂度的。（假设每个格子里的石头数是S_i，可以证明sum (S_i)^2的期望是O(n)级别的）

C我记得可以用开源的uthash来着好像，我找找 在这http://troydhanson.github.io/uthash/

C啊……我记得C甚至不自带hash相关库吧……会很痛苦…………

打哈希表的话，长度只有N，问题不大，尤其在最难的情况下数量级差太多了

暴力一点的处理方法就是规约到3SUM了吧 经典方案就是 A = 10 * A + 1 B = 10 * B + 2 C = (10 * C - 3) - 10 * M S = A + B + C 然后用3sum的伪多项式求法就可以了吧？等下，3sum有更快的伪多项式算法么

数学一点的描述可以是 给定数组ABC，求系数abc，使得abc各分量都是01，且 sum a = sum b = sum c = 1，sum aA+bB+cC = M 所以这个是个01规划问题……，如果求精确解估计最好也只能伪多项式级别了 什么我以为连easy都会有问题的（x 因为真的太暴力了（ 退一万步说sort一下之后也可以拉到O(n^2)的（ 先把ABC 花O(nlogn)sort出来 for a in A: tempC = C[-1] for b in B: while a + b + tempC > M: tempC = tempC.prev if a + b + tempC == M: count = count + 1 这样BC实际上是一起跑的，所以事实上只有2个循环，能拉到O(n^2) 嗯这里我假定了ABC所有元素都不同，如果相同稍微改一下上面的代码问题应该也不大 或者舍得空间复杂度的话直接写哈希表 for a in A: dict = dict + {M - a: a} for b in B: for c in C: if b + c in dict: count = count + 1 这个改相同元素很简单 for a in A: dict[M - a] = dict[M - a] + 1 for b in B: for c in C: if b + c in dict: count = count + dict[b + c] 避免误解，这里的dict始终都是hashmap，key存在的时候返回value，key不存在的时候返回0，所以前面打表A的时候我手懒判断M-a存不存在了（理解意思就好（x

那最暴力方案O(n^3)肯定能跑了（ 顺带是不是应该用maxM +1，不然如果M刚好取最大值也可以直接说没方法了（x

等下是我理解错了么？M/3侧是开区间，所以三个加一起怎么也小于M？

现实来说倒是确实这样 当然真要现实考虑的话真的会有不得不用这种方法做排序的情况么？ 我记得好像有哪个模型是单带图灵机+栈来着？

时间复杂度倒是没问题，空间复杂度直接开栈最坏可以是O(n)的吧，逻辑算的话只需要O(1)

居然直接写栈么 实际上不用实际的空间来开栈也可以做吧 stackFlag = False next = 0 prev = 0 temp = 0 usedFlag = False for x in A: if stackFlag: if x != temp: return 2 else: temp = temp - 1 if temp == next: stackFlag = False next = prev + 1 else: if x != next: usedFlag = True prev = x stackFlag = True temp = prev - 1 else: next = next + 1 return 1 if usedFlag else 0

传送门其实还是能做的 首先如果所有传送门之间没有交叉情况（可以真包含），那么必然是单向的，用单向带走就可以了 麻烦的是传送门之间有交叉 但是这个情况也可以用马尔科夫决策过程来做，暴力policy iteration或者value iteration肯定能converge的，这样每个传送门的选择也就确定单向了 所以说昨天那问题是真的我的老本行了（笑 等我有时间可以写着玩玩

等下我昨天的传送门还稍微有点问题呢（x 感觉是组合数学的问题 最平凡解是你有多少数字我用多少栈，然后一个数字一个栈 但是很显然的是，对于数字1我们不需要栈，因为直接把1丢出来就好了 同样地，我们因此可以发现，跟在1后面的+1序列全都不需要栈，直接丢出来就可以了

这部分以我的理解是玩家自己选择的，所以肯定对于玩家来说是主动选择最优解法

有必要的，举例来说我现在一共100格子，有通道1-51，48-52，49-100

艹这就突然变成我老本行了（x 我拿particle filter做可以不，暴力模拟的（ 等我刷完牙开始写好了，已经有想法了 为了方便我就把格子从0开始编号了，所以会和题目中的编号差1，不过不影响大局。 首先需要一个概率论非常重要的性质，即期望的线性性 —— 定理1 可以表述为E( sum_i (k_i X_i) ) = sum_i ( k_i E(X_i))，其中的k为常数X为随机变量 我们考虑最简单的情况，终点在1 有期望 = 1 * 1 = 1，即1的概率走至少1格，花费1步 终点在2时，我们有 1/6的概率走到1，花费1步，然后变成剩下1格的情况，即期望1。以及5/6的情况花费一步直接到位。即期望 1/6 * (1 + 1) + 5/6 = 7/6 终点在3时，我们有 1/6走到1，花费1，变成剩下2格。1/6走到2，花费1，变成剩下1格，4/6的情况一步到位。即期望1/6 * (1 + 7/6) + 1/6 * (1 + 1) + 4/6 * 1 = 49/36 终点4同理，有 1/6 * (1 + 49/36) + 1/6 * (1 + 7/6) + 1/6 * (1 + 1) + 3/6 * 1 = 343/216 终点5同理，有 1/6 * (1 + 343/216) + ... = 2401/1296 终点6同理有 16807/7776 ok，现在初始表格填完了，接下来考虑递推，因为显然终点在至少是7的时候不存在1步到位的情况了，所以是通项公式 终点在k的时候我们有花1步把问题变为 1/6概率终点在k-1 1/6概率终点在k-2 1/6概率终点在k-3 1/6概率终点在k-4 1/6概率终点在k-5 1/6概率终点在k-6 利用定理1，得到K = 1 + 1/6 (K-1 + K-2 + K-3 + K-4 + K-5 + K-6)，其中大写K为终点在K时的期望步数，K-x同理。 至此，如果无传送门，得解。（注：这里可以用类似斐波那契数列的矩阵求法类似的方式直接得到通项公式） —— 公式1 为了解决传送门问题，首先我们需要准确知道到各传送门的概率。 类似的方法，初始化-5~-1号格子为0， 0号格子为1，对格子k有 K = 1/6 (K-1 + K-2 + K-3 + K-4 + K-5 + K-6)，其中大写K为走到格子K的概率，K-x同理。 —— 公式2 需要注意的是，对于传送门实际上我需要精确的刚好走到这一格的期望，因为错过了就凉了，所以需要求的期望和上面的终点期望稍微有一些不同 举例来说1是(1 * 1/6) / 1/6 = 1，2是(2 * 1/36 + 1 * 1/6) / (1/36 + 1/6)，3是(3 * 1/6^3 + 2 * 1/6^2 * 2 + 1 * 1/6) / (1/6^3 + 1/6^2 * 2 + 1/6)…… 不过同样的对于7及以上可以得到和公式1一样的递推公式 —— 公式3 实际上这里我们已经得到了精确地走到每个格子的期望，为了转化成最终结果，只需要对最后6个格子的递推公式改一下，把置零的部分变成置一就可以了 然后传送门可以理解为将a端的期望直接复制给b端即可（ab可互换）（当然是选择留小的就是了这句有很大问题 想了下基本上已经可以做了 公式3依然可以暴力做成矩阵的通项公式的形式，然后对于传送门两侧update一下之后继续用递推公式暴力打表就好了，最后用最后6个格子的期望稍微处理一下就完了

你要拿c的速度来判python，尤其还不是科学计算这种本身可以依靠numpy这种c优化的，那肯定慢就是了 我个人角度来说其实我只关心O(n)还是O(exp(n))，至于后面的常数问题至少从我这边来说其实并不是很在意 当然你说为了在工业界找工作那确实是另一回事了

haskell没用过，不过我用过spark 至于内存管理这事，python如果只是为了科学计算其实你可以用nump这种第三方包的屏蔽掉内存管理问题，写着一点都不疼

那我下次尽量晚点答好了（x 说起来要不要考虑出project euler的题？我觉得可以靠题号控制难度，比较有渐进的过程，然后也更关注算法而不是底层细节 （没错我是py党我就是要屏蔽掉内存管理（

py我说实话我一般都是拿sublime text写，然后命令行跑 只要不是逻辑太扭曲的代码，调试靠print就够了，IDE我是觉得比较重 顺带一提，只要我写的够快，那就算跑慢点也会比写得慢的先跑完

为什么不来python呢（x 直接用命令行都可以写（

py党就安利一下python的一个第三方包——sympy好了 化简公式什么的有奇效

艹今天居然是隐藏在数字中的邪神（x 艹难怪写代码写久了我觉得san值下降 太艹了（ 艹是01背包？不过每个算法的价值都是1的话，那直接升序从小的开始拿就好了吧…… 或者直接求最小S个元素，用快排的分割部分就好，然后拿这最小S个sort一遍就好了 或者更精确地可以先扫一遍，拿到最小值min_i san，然后求最小(S / min)个元素 当然如果X比(S / min)小的话那就直接sort就好了 当然我这里是假定第二行全都是正整数的，也就是不存在没有代价就能学会的算法！（逃