偶尔碰到的问题

[Draymonders]

• 给定一个数组，找到两个不相交且连续的子数组A和B，A中的数字和为sum(A), B中的元素和为sum(B), 求sum(A) - sum(B) 绝对值的最大值。

  • solution

    
    left1[i] 表示以i为结尾的最大字段和，left2[i] 表示以i为结尾的最小字段和
    right1[i] 表示以i为首的最大字段和，right2[i] 表示以i为首的最小字段和

然后就 4种组合求差的绝对值

[Draymonders]

智力题 给定一个上帝函数G，能够以x的概率返回1，1-x概率返回0，0 < x < 1求一个函数 F(p),能够以p概率返回1，1-p概率返回0，不得使用其他库函数，只能使用上帝函数G。

思路: x的概率返回1,1-x概率返回0， 那么是可以等概率生成0和1的，即 先0后1和先1后0的概率是相等的.

然后这个题就等价成了 有一个rand(0, 1)可以生成等概率的0和1，求生成[0,100]的概率， 那么生成的数 > p*100,就返回 0, 否则返回1

可以枚举二进制位的0和1？