{"trustable":true,"prependHtml":"\u003cstyle\u003e.statText pre { font-size: 12px; }\ntable {display:block !important; width:100%; }\ntable tbody {display:block !important; width:100%; }\ntable tbody tr { width:100% !important;display: block;}\ntable tbody tr td.statText { margin-left: 5px; display: inline-block; width: fit-content; }\ntable tbody tr td.statText br { display: block; content: \" \";line-height: 12px;margin: 12px 0;}\ntable tbody tr td.statText table table pre {\n white-space: pre-wrap;\n text-overflow: ellipsis;\n word-break: break-all;\n}\ntd { padding: 0 !important; border: none !important; }\npre { line-height: normal; margin: 0; }\n\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\n\u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\n \u003ch3\u003e问题陈述\u003c/h3\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cp\u003e你得到了一个有N行M列的棋盘。我们用(i,j)来表示第i行的第j个格子(0-based indices)。每个格子初始都是白色的。你的目标是让棋盘上每一行和每一列都至少有一个黑色的格子。\u003c/p\u003e\n \u003cp\u003e你将轮流把格子涂成黑色。每一轮,你选择一个格子(选择的方式如下所述)并把它涂成黑色。一旦达到你的目标,你就停止。\u003c/p\u003e\n \u003cp\u003e你得到了一个由N个元素组成的字符串数组\u003cb\u003eprob\u003c/b\u003e,每个元素都有M个字符。在\u003cb\u003eprob\u003c/b\u003e中的所有字符都是数字(\u00270\u0027-\u00279\u0027)。第i行的第j个字符(0-based indices)表示的数字将被记为p[i][j]。这个数字是每一轮选择格子(i,j)的相对概率。\u003c/p\u003e\n \u003cp\u003e正式地说,让s是所有p[i][j]的和。那么每一轮选择格子(i,j)的概率是p[i][j]/s。注意同一个格子可能被选择多次:我们有时可能选择一个已经是黑色的格子。\u003c/p\u003e\n \u003cp\u003e约束条件保证你可以达到你的目标。返回达到你的目标所需要的预期轮数。\u003c/p\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\n \u003ch3\u003e定义\u003c/h3\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e类:\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003eRandomPaintingOnABoard\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e方法:\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003eexpectedSteps\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e参数:\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003eString[]\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e返回:\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003edouble\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e方法签名:\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003edouble expectedSteps(String[] prob)\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e(确保你的方法是公开的)\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\n \u003ch3\u003e注释\u003c/h3\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e你的返回值必须有小于1e-9的相对或绝对误差。\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\n \u003ch3\u003e约束条件\u003c/h3\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003cb\u003eprob\u003c/b\u003e将包含1到21个元素,包含端点。\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003cb\u003eprob\u003c/b\u003e的每个元素将有1到21个字符,包含端点。\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003cb\u003eprob\u003c/b\u003e的元素将有相同的长度。\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003cb\u003eprob\u003c/b\u003e的每个元素将只包含数字(\u00270\u0027-\u00279\u0027)。\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003cb\u003eprob\u003c/b\u003e中的格子总数(即\u003cb\u003eprob\u003c/b\u003e中的数字总数)将在1到150之间,包含端点。\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e每一行将至少有一个非零数字。\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e每一列将至少有一个非零数字。\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\n \u003ch3\u003e示例\u003c/h3\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e0)\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{\"10\",\n \"01\"}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003eReturns: 3.0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\n \u003cp\u003e格子(0,0)和(1,1)每一轮被选择的概率都是1/2。其中一个格子将在第一轮被涂黑。\u003c/p\u003e\n \u003cp\u003e然后还会有一些轮数,直到另一个格子被选择。由于这个事件的概率是1/2,所以预期的额外轮数是2。\u003c/p\u003e\n \u003cp\u003e因此,总的预期轮数是1+2 \u003d 3。\u003c/p\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e1)\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{\"11\",\n \"11\"}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003eReturns: 3.6666666666666665\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\n \u003cp\u003e这个棋盘是对称的,所以我们可以假设格子(0,0)在第一轮被选择。\u003c/p\u003e\n \u003cp\u003e然后还会有一些轮数,直到有一个不同的格子被首次选择。选择一个不同的格子的概率是3/4,因此这些额外轮数的预期数是4/3。\u003c/p\u003e\n \u003cp\u003e现在,哪个格子会被第二次涂黑呢?\u003c/p\u003e\n \u003cul\u003e\n \u003cli\u003e以1/3的概率,格子(1,1)会被涂黑,我们就完成了。\u003c/li\u003e\n \u003cli\u003e以2/3的概率,其他两个格子中的一个会被涂黑。在这两种情况中,我们仍然需要把另外两个白色的格子中的一个涂黑,直到那个事件发生的预期轮数是2。\u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003e因此,答案是1 + 4/3 + (2/3 * 2) \u003d 11/3。\u003c/p\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e2)\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{\"11\",\n \"12\"}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003eReturns: 3.9166666666666665\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e3)\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{\"0976\",\n \"1701\",\n \"7119\"}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003eReturns: 11.214334077031307\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e4)\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{\"000000000000001000000\",\n \"888999988889890999988\",\n \"988889988899980889999\",\n \"889898998889980999898\",\n \"988889999989880899999\",\n \"998888998988990989998\",\n \"998988999898990889899\"}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003eReturns: 1028.7662876159634\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n\u003c/table\u003e\n\u003chr\u003e\n\u003cp\u003e这个问题陈述是TopCoder, Inc的专有和专利财产。未经TopCoder, Inc的事先书面同意,任何未经授权的使用或复制这些信息都严格禁止。 (c)2023, TopCoder, Inc. 保留所有权利。\u003c/p\u003e"}}]}