https://acm.ecnu.edu.cn/index.php?title=XVIII_Open_Cup_named_after_E.V._Pankratiev._Grand_Prix_of_Korea&feed=atom&action=history
XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Korea - Revision history
2024-03-19T04:40:59Z
Revision history for this page on the wiki
MediaWiki 1.35.2
https://acm.ecnu.edu.cn/wiki/index.php?title=XVIII_Open_Cup_named_after_E.V._Pankratiev._Grand_Prix_of_Korea&diff=4618&oldid=prev
Kilo: /* Problem C */
2019-09-09T07:15:18Z
<p><span dir="auto"><span class="autocomment">Problem C</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 07:15, 9 September 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l70" >Line 70:</td>
<td colspan="2" class="diff-lineno">Line 70:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题意:有 $n$ 条路径,每条路径上有 $m$ 条不共用的边。现在每条边有 $p_i$ 的概率损坏,现在每一次可以查询一条边是否损坏,问在采取最优策略的情况下,期望多少次查询能找到一条完整的路径,或者判断不存在一条完整的路径。</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题意:有 $n$ 条路径,每条路径上有 $m$ 条不共用的边。现在每条边有 $p_i$ 的概率损坏,现在每一次可以查询一条边是否损坏,问在采取最优策略的情况下,期望多少次查询能找到一条完整的路径,或者判断不存在一条完整的路径。</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>题解:对于每一个路径,优先查找最可能坏掉的边。计算出第 $i$ 条路径的期望查找次数 $t_i$ 和联通概率 $p_i$。之后,我们发现如果当前检查的路径的顺序是 $a_1,a_2,a_3,...,a_n$,那么总共的期望查询次数是 $t_{a_1}+p_{a_1} \times (t_{a_2}+p_{a_2}\times(\dots \times (t_{a_{n-1}} + p_{a_{n-1}} t_{a_n})\dots))$。我们发现,交换前后两项是可以直接算出来情况是否变得更优的。因此,用冒泡排序尝试找到最优的 {$a_n$}<del class="diffchange diffchange-inline">,并计算出答案。结果说明这么做是对的。</del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>题解:对于每一个路径,优先查找最可能坏掉的边。计算出第 $i$ 条路径的期望查找次数 $t_i$ 和联通概率 $p_i$。之后,我们发现如果当前检查的路径的顺序是 $a_1,a_2,a_3,...,a_n$,那么总共的期望查询次数是 $t_{a_1}+p_{a_1} \times (t_{a_2}+p_{a_2}\times(\dots \times (t_{a_{n-1}} + p_{a_{n-1}} t_{a_n})\dots))$。我们发现,交换前后两项是可以直接算出来情况是否变得更优的。因此,用冒泡排序尝试找到最优的 {$a_n$}<ins class="diffchange diffchange-inline">并计算出答案。</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Problem D ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Problem D ==</div></td></tr>
</table>
Kilo
https://acm.ecnu.edu.cn/wiki/index.php?title=XVIII_Open_Cup_named_after_E.V._Pankratiev._Grand_Prix_of_Korea&diff=3615&oldid=prev
Xiejiadong: /* Problem L */
2019-05-09T03:26:15Z
<p><span dir="auto"><span class="autocomment">Problem L</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 03:26, 9 May 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l92" >Line 92:</td>
<td colspan="2" class="diff-lineno">Line 92:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Solved by Kilo_5723.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Solved by Kilo_5723.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>题意:给定一个循环序列 {<del class="diffchange diffchange-inline">$</del>a_n$<del class="diffchange diffchange-inline">}</del>,每一次把 $a_i$ 替换成 $a_i$ ~ $a_{i+m-1}$ 的异或和,求操作 $t$ 次之后序列的值。</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>题意:给定一个循环序列 <ins class="diffchange diffchange-inline">$\</ins>{a_n<ins class="diffchange diffchange-inline">\}</ins>$,每一次把 $a_i$ 替换成 $a_i$ ~ $a_{i+m-1}$ 的异或和,求操作 $t$ 次之后序列的值。</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题解:通过找规律发现,在操作 $2^k$ 次之后,$a_i$ 有贡献的位置是 $a_i$ 开始,间隔为 $2^k-1$ 的连续 $m$ 个位置。</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题解:通过找规律发现,在操作 $2^k$ 次之后,$a_i$ 有贡献的位置是 $a_i$ 开始,间隔为 $2^k-1$ 的连续 $m$ 个位置。</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>根据这个规律,找出一次性操作 $2^k$ 次的方法:对于每一个 $i$,不停的找其对应 $+2^k-1$ 的下一个位置,找到一个长度为 $len$ 的循环节,那么可以通过求 $m+len$ 个前缀异或和一次性处理掉这个循环节里所有数的末态。但如果 $m>>len$,此时前 $k$ 个数的前缀异或和和前 $k \mod 2\times len$ 的前缀异或和是相同的,因为循环节中长度等于 $2 \times len$ 的部分异或和会相抵消。因此可以在 $O(len)$ 的时间里处理掉每个循环节,就也能在 $O(n)$ 的时间里处理掉每次一次性操作 $2^k$ 的末态。总共的操作次数是 $O(log(t))$,总复杂度是 $O(n*log(t))$ 的。</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>根据这个规律,找出一次性操作 $2^k$ 次的方法:对于每一个 $i$,不停的找其对应 $+2^k-1$ 的下一个位置,找到一个长度为 $len$ 的循环节,那么可以通过求 $m+len$ 个前缀异或和一次性处理掉这个循环节里所有数的末态。但如果 $m>>len$,此时前 $k$ 个数的前缀异或和和前 $k \mod 2\times len$ 的前缀异或和是相同的,因为循环节中长度等于 $2 \times len$ 的部分异或和会相抵消。因此可以在 $O(len)$ 的时间里处理掉每个循环节,就也能在 $O(n)$ 的时间里处理掉每次一次性操作 $2^k$ 的末态。总共的操作次数是 $O(log(t))$,总复杂度是 $O(n*log(t))$ 的。</div></td></tr>
</table>
Xiejiadong
https://acm.ecnu.edu.cn/wiki/index.php?title=XVIII_Open_Cup_named_after_E.V._Pankratiev._Grand_Prix_of_Korea&diff=3598&oldid=prev
Xiejiadong: /* Problem L */
2019-05-08T18:19:22Z
<p><span dir="auto"><span class="autocomment">Problem L</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 18:19, 8 May 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l96" >Line 96:</td>
<td colspan="2" class="diff-lineno">Line 96:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题解:通过找规律发现,在操作 $2^k$ 次之后,$a_i$ 有贡献的位置是 $a_i$ 开始,间隔为 $2^k-1$ 的连续 $m$ 个位置。</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题解:通过找规律发现,在操作 $2^k$ 次之后,$a_i$ 有贡献的位置是 $a_i$ 开始,间隔为 $2^k-1$ 的连续 $m$ 个位置。</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>根据这个规律,找出一次性操作 $2^k$ 次的方法:对于每一个 $i$,不停的找其对应 $+2^k-1$ 的下一个位置,找到一个长度为 $len$ 的循环节,那么可以通过求 $m+len$ 个前缀异或和一次性处理掉这个循环节里所有数的末态。但如果 $m>>len$,此时前 $k$ 个数的前缀异或和和前 $k \mod 2\times len$ 的前缀异或和是相同的,因为循环节中长度等于 $2<del class="diffchange diffchange-inline">\times k </del>\times len$ 的部分异或和会相抵消。因此可以在 $O(len)$ 的时间里处理掉每个循环节,就也能在 $O(n)$ 的时间里处理掉每次一次性操作 $2^k$ 的末态。总共的操作次数是 $O(log(t))$,总复杂度是 $O(n*log(t))$ 的。</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>根据这个规律,找出一次性操作 $2^k$ 次的方法:对于每一个 $i$,不停的找其对应 $+2^k-1$ 的下一个位置,找到一个长度为 $len$ 的循环节,那么可以通过求 $m+len$ 个前缀异或和一次性处理掉这个循环节里所有数的末态。但如果 $m>>len$,此时前 $k$ 个数的前缀异或和和前 $k \mod 2\times len$ 的前缀异或和是相同的,因为循环节中长度等于 $2 \times len$ 的部分异或和会相抵消。因此可以在 $O(len)$ 的时间里处理掉每个循环节,就也能在 $O(n)$ 的时间里处理掉每次一次性操作 $2^k$ 的末态。总共的操作次数是 $O(log(t))$,总复杂度是 $O(n*log(t))$ 的。</div></td></tr>
</table>
Xiejiadong
https://acm.ecnu.edu.cn/wiki/index.php?title=XVIII_Open_Cup_named_after_E.V._Pankratiev._Grand_Prix_of_Korea&diff=3597&oldid=prev
Xiejiadong: /* Problem L */
2019-05-08T18:19:11Z
<p><span dir="auto"><span class="autocomment">Problem L</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 18:19, 8 May 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l96" >Line 96:</td>
<td colspan="2" class="diff-lineno">Line 96:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题解:通过找规律发现,在操作 $2^k$ 次之后,$a_i$ 有贡献的位置是 $a_i$ 开始,间隔为 $2^k-1$ 的连续 $m$ 个位置。</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题解:通过找规律发现,在操作 $2^k$ 次之后,$a_i$ 有贡献的位置是 $a_i$ 开始,间隔为 $2^k-1$ 的连续 $m$ 个位置。</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>根据这个规律,找出一次性操作 $2^k$ 次的方法:对于每一个 $i$,不停的找其对应 $+2^k-1$ 的下一个位置,找到一个长度为 $len$ 的循环节,那么可以通过求 $m+len$ 个前缀异或和一次性处理掉这个循环节里所有数的末态。但如果 $m>>len$,此时前 $k$ 个数的前缀异或和和前 $k<del class="diffchange diffchange-inline">%(</del>2<del class="diffchange diffchange-inline">*</del>len<del class="diffchange diffchange-inline">)</del>$ 的前缀异或和是相同的,因为循环节中长度等于 $2\times k \times len$ 的部分异或和会相抵消。因此可以在 $O(len)$ 的时间里处理掉每个循环节,就也能在 $O(n)$ 的时间里处理掉每次一次性操作 $2^k$ 的末态。总共的操作次数是 $O(log(t))$,总复杂度是 $O(n*log(t))$ 的。</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>根据这个规律,找出一次性操作 $2^k$ 次的方法:对于每一个 $i$,不停的找其对应 $+2^k-1$ 的下一个位置,找到一个长度为 $len$ 的循环节,那么可以通过求 $m+len$ 个前缀异或和一次性处理掉这个循环节里所有数的末态。但如果 $m>>len$,此时前 $k$ 个数的前缀异或和和前 $k <ins class="diffchange diffchange-inline">\mod </ins>2<ins class="diffchange diffchange-inline">\times </ins>len$ 的前缀异或和是相同的,因为循环节中长度等于 $2\times k \times len$ 的部分异或和会相抵消。因此可以在 $O(len)$ 的时间里处理掉每个循环节,就也能在 $O(n)$ 的时间里处理掉每次一次性操作 $2^k$ 的末态。总共的操作次数是 $O(log(t))$,总复杂度是 $O(n*log(t))$ 的。</div></td></tr>
</table>
Xiejiadong
https://acm.ecnu.edu.cn/wiki/index.php?title=XVIII_Open_Cup_named_after_E.V._Pankratiev._Grand_Prix_of_Korea&diff=3596&oldid=prev
Xiejiadong: /* Problem L */
2019-05-08T18:18:41Z
<p><span dir="auto"><span class="autocomment">Problem L</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 18:18, 8 May 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l91" >Line 91:</td>
<td colspan="2" class="diff-lineno">Line 91:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Solved by Kilo_5723.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Solved by Kilo_5723.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">题意:给定一个循环序列 {$a_n$},每一次把 $a_i$ 替换成 $a_i$ ~ $a_{i+m-1}$ 的异或和,求操作 $t$ 次之后序列的值。</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">题解:通过找规律发现,在操作 $2^k$ 次之后,$a_i$ 有贡献的位置是 $a_i$ 开始,间隔为 $2^k-1$ 的连续 $m$ 个位置。</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">根据这个规律,找出一次性操作 $2^k$ 次的方法:对于每一个 $i$,不停的找其对应 $+2^k-1$ 的下一个位置,找到一个长度为 $len$ 的循环节,那么可以通过求 $m+len$ 个前缀异或和一次性处理掉这个循环节里所有数的末态。但如果 $m>>len$,此时前 $k$ 个数的前缀异或和和前 $k%(2*len)$ 的前缀异或和是相同的,因为循环节中长度等于 $2\times k \times len$ 的部分异或和会相抵消。因此可以在 $O(len)$ 的时间里处理掉每个循环节,就也能在 $O(n)$ 的时间里处理掉每次一次性操作 $2^k$ 的末态。总共的操作次数是 $O(log(t))$,总复杂度是 $O(n*log(t))$ 的。</ins></div></td></tr>
</table>
Xiejiadong
https://acm.ecnu.edu.cn/wiki/index.php?title=XVIII_Open_Cup_named_after_E.V._Pankratiev._Grand_Prix_of_Korea&diff=3595&oldid=prev
Xiejiadong: /* Problem E */
2019-05-08T18:06:26Z
<p><span dir="auto"><span class="autocomment">Problem E</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 18:06, 8 May 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l79" >Line 79:</td>
<td colspan="2" class="diff-lineno">Line 79:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Upsolved by Kilo_5723.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Upsolved by Kilo_5723.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">题意:给定一个圆环上的点,有删点和加点操作,要维护环上最远距离。</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">题解:把每一个点的对点也加入到环上,就变成了维护环上两种颜色的点的最近距离。把所有的点都加到一个环上,显然我们只对相邻异色点的距离感兴趣。set 维护即可。</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Problem F ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Problem F ==</div></td></tr>
</table>
Xiejiadong
https://acm.ecnu.edu.cn/wiki/index.php?title=XVIII_Open_Cup_named_after_E.V._Pankratiev._Grand_Prix_of_Korea&diff=3594&oldid=prev
Xiejiadong: /* Problem C */
2019-05-08T17:19:03Z
<p><span dir="auto"><span class="autocomment">Problem C</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 17:19, 8 May 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l70" >Line 70:</td>
<td colspan="2" class="diff-lineno">Line 70:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题意:有 $n$ 条路径,每条路径上有 $m$ 条不共用的边。现在每条边有 $p_i$ 的概率损坏,现在每一次可以查询一条边是否损坏,问在采取最优策略的情况下,期望多少次查询能找到一条完整的路径,或者判断不存在一条完整的路径。</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题意:有 $n$ 条路径,每条路径上有 $m$ 条不共用的边。现在每条边有 $p_i$ 的概率损坏,现在每一次可以查询一条边是否损坏,问在采取最优策略的情况下,期望多少次查询能找到一条完整的路径,或者判断不存在一条完整的路径。</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>题解:对于每一个路径,优先查找最可能坏掉的边。计算出第 $i$ 条路径的期望查找次数 $t_i$ 和联通概率 $p_i$。之后,我们发现如果当前检查的路径的顺序是 $a_1,a_2,a_3,...,a_n$,那么总共的期望查询次数是 $t_{a_1}+p_{a_1} \times (t_{a_2}+p_{a_2}\times(\dots \times (t_{a_{n-1}} + p_{a_{n-1}} t_{a_n})\dots))$。我们发现,交换前后两项是可以直接算出来情况是否变得更优的。因此,用冒泡排序尝试找到最优的 {$a_n$}<del class="diffchange diffchange-inline">,并计算出答案。过了说明这么做是对的。</del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>题解:对于每一个路径,优先查找最可能坏掉的边。计算出第 $i$ 条路径的期望查找次数 $t_i$ 和联通概率 $p_i$。之后,我们发现如果当前检查的路径的顺序是 $a_1,a_2,a_3,...,a_n$,那么总共的期望查询次数是 $t_{a_1}+p_{a_1} \times (t_{a_2}+p_{a_2}\times(\dots \times (t_{a_{n-1}} + p_{a_{n-1}} t_{a_n})\dots))$。我们发现,交换前后两项是可以直接算出来情况是否变得更优的。因此,用冒泡排序尝试找到最优的 {$a_n$}<ins class="diffchange diffchange-inline">,并计算出答案。结果说明这么做是对的。</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Problem D ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Problem D ==</div></td></tr>
</table>
Xiejiadong
https://acm.ecnu.edu.cn/wiki/index.php?title=XVIII_Open_Cup_named_after_E.V._Pankratiev._Grand_Prix_of_Korea&diff=3593&oldid=prev
Xiejiadong: /* Problem C */
2019-05-08T17:18:37Z
<p><span dir="auto"><span class="autocomment">Problem C</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 17:18, 8 May 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l70" >Line 70:</td>
<td colspan="2" class="diff-lineno">Line 70:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题意:有 $n$ 条路径,每条路径上有 $m$ 条不共用的边。现在每条边有 $p_i$ 的概率损坏,现在每一次可以查询一条边是否损坏,问在采取最优策略的情况下,期望多少次查询能找到一条完整的路径,或者判断不存在一条完整的路径。</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题意:有 $n$ 条路径,每条路径上有 $m$ 条不共用的边。现在每条边有 $p_i$ 的概率损坏,现在每一次可以查询一条边是否损坏,问在采取最优策略的情况下,期望多少次查询能找到一条完整的路径,或者判断不存在一条完整的路径。</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>题解:对于每一个路径,优先查找最可能坏掉的边。计算出第 $i$ 条路径的期望查找次数 $t_i$ 和联通概率 $p_i$。之后,我们发现如果当前检查的路径的顺序是 $a_1,a_2,a_3,...,a_n$,那么总共的期望查询次数是 $t_{a_1}+p_{a_1} \times (t_{a_2}+p_{a_2}\times(\dots \times (t_{a_{n-1}} + p_{a_{n-1}} t_{a_n}<del class="diffchange diffchange-inline">)</del>)\dots)$<del class="diffchange diffchange-inline">。</del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>题解:对于每一个路径,优先查找最可能坏掉的边。计算出第 $i$ 条路径的期望查找次数 $t_i$ 和联通概率 $p_i$。之后,我们发现如果当前检查的路径的顺序是 $a_1,a_2,a_3,...,a_n$,那么总共的期望查询次数是 $t_{a_1}+p_{a_1} \times (t_{a_2}+p_{a_2}\times(\dots \times (t_{a_{n-1}} + p_{a_{n-1}} t_{a_n})\dots)<ins class="diffchange diffchange-inline">)$。我们发现,交换前后两项是可以直接算出来情况是否变得更优的。因此,用冒泡排序尝试找到最优的 {$a_n</ins>$<ins class="diffchange diffchange-inline">},并计算出答案。过了说明这么做是对的。</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Problem D ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Problem D ==</div></td></tr>
</table>
Xiejiadong
https://acm.ecnu.edu.cn/wiki/index.php?title=XVIII_Open_Cup_named_after_E.V._Pankratiev._Grand_Prix_of_Korea&diff=3592&oldid=prev
Xiejiadong: /* Problem C */
2019-05-08T17:15:01Z
<p><span dir="auto"><span class="autocomment">Problem C</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 17:15, 8 May 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l70" >Line 70:</td>
<td colspan="2" class="diff-lineno">Line 70:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题意:有 $n$ 条路径,每条路径上有 $m$ 条不共用的边。现在每条边有 $p_i$ 的概率损坏,现在每一次可以查询一条边是否损坏,问在采取最优策略的情况下,期望多少次查询能找到一条完整的路径,或者判断不存在一条完整的路径。</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题意:有 $n$ 条路径,每条路径上有 $m$ 条不共用的边。现在每条边有 $p_i$ 的概率损坏,现在每一次可以查询一条边是否损坏,问在采取最优策略的情况下,期望多少次查询能找到一条完整的路径,或者判断不存在一条完整的路径。</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>题解:对于每一个路径,优先查找最可能坏掉的边。计算出第 $i$ 条路径的期望查找次数 $t_i$ 和联通概率 $p_i$。之后,我们发现如果当前检查的路径的顺序是 $a_1,a_2,a_3,...,a_n$,那么总共的期望查询次数是 $t_{a_1}+p_{a_1} \times (t_{a_2}+p_{a_2}\times(\dots \times p_{a_{n-1}} <del class="diffchange diffchange-inline">\times </del>t_{a_n}))\dots)$。</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>题解:对于每一个路径,优先查找最可能坏掉的边。计算出第 $i$ 条路径的期望查找次数 $t_i$ 和联通概率 $p_i$。之后,我们发现如果当前检查的路径的顺序是 $a_1,a_2,a_3,...,a_n$,那么总共的期望查询次数是 $t_{a_1}+p_{a_1} \times (t_{a_2}+p_{a_2}\times(\dots \times <ins class="diffchange diffchange-inline">(t_{a_{n-1}} + </ins>p_{a_{n-1}} <ins class="diffchange diffchange-inline"> </ins>t_{a_n}))\dots)$。</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Problem D ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Problem D ==</div></td></tr>
</table>
Xiejiadong
https://acm.ecnu.edu.cn/wiki/index.php?title=XVIII_Open_Cup_named_after_E.V._Pankratiev._Grand_Prix_of_Korea&diff=3591&oldid=prev
Xiejiadong: /* Problem C */
2019-05-08T17:14:05Z
<p><span dir="auto"><span class="autocomment">Problem C</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 17:14, 8 May 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l70" >Line 70:</td>
<td colspan="2" class="diff-lineno">Line 70:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题意:有 $n$ 条路径,每条路径上有 $m$ 条不共用的边。现在每条边有 $p_i$ 的概率损坏,现在每一次可以查询一条边是否损坏,问在采取最优策略的情况下,期望多少次查询能找到一条完整的路径,或者判断不存在一条完整的路径。</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>题意:有 $n$ 条路径,每条路径上有 $m$ 条不共用的边。现在每条边有 $p_i$ 的概率损坏,现在每一次可以查询一条边是否损坏,问在采取最优策略的情况下,期望多少次查询能找到一条完整的路径,或者判断不存在一条完整的路径。</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>题解:对于每一个路径,优先查找最可能坏掉的边。计算出第 $i$ 条路径的期望查找次数 $t_i$ 和联通概率 $p_i$。之后,我们发现如果当前检查的路径的顺序是 $a_1,a_2,a_3,...,a_n$,那么总共的期望查询次数是 $t_{a_1}+p_{a_1} \times (t_{a_2}+p_{a_2}\times \dots \times p_{a_{n-1}} \times t_{a_n}))\dots)$。</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>题解:对于每一个路径,优先查找最可能坏掉的边。计算出第 $i$ 条路径的期望查找次数 $t_i$ 和联通概率 $p_i$。之后,我们发现如果当前检查的路径的顺序是 $a_1,a_2,a_3,...,a_n$,那么总共的期望查询次数是 $t_{a_1}+p_{a_1} \times (t_{a_2}+p_{a_2}\times<ins class="diffchange diffchange-inline">(</ins>\dots \times p_{a_{n-1}} \times t_{a_n}))\dots)$。</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Problem D ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Problem D ==</div></td></tr>
</table>
Xiejiadong