2016-E52-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ 2017/04/17 16:34-21:34 · Siunaus · Akalm/JTJL/sfiction │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│D [0:22]│ 1 oOOo OOOOoo# 3 │
│K [0:13]│ 1 OOOOo# 2 3 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│G [0:06]│ 1oo#2 3 │
│I [0:15]│ 1 ooOOo# 2 3 │
│J [0:27]│ 1 Ooo oo. oooo...oooO# 2 3 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│C [0:45]│ 1 oOOoOOOo. .OO. .o . 2 . ooooo. o.o# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [3:46]│ oo.OOOOoo ..ooOOoo. OOooo. OooOOooOOOOooOooo..oOooOo. oOOoOOOooOOOooOO. .oOOOOoO..ooOooooOooOOooooooooooooooooooo│
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│A [1:24]│ 1 oOOOo! 2 OOoOoO!.ooO!oo!OooOOooooo!!! oo.o!.o!│
│B [0:14]│ 1 OOooo. . oo . 2 │
│E8[0:00]│ 1 │
│F3[0:00]│ 1 │
│H9[0:00]│ 1 │
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}
||Submission time||ID||Problem||Compiler||Verdict||Time||Memory||Test||
||17 Apr 2017, 16:33:49||4434858||A||GNU c++ 11 4.9||WA||76ms||384.00Kb||2||
||17 Apr 2017, 16:33:10||4434854||A||GNU c++ 11 4.9||WA||75ms||380.00Kb||2||
||17 Apr 2017, 16:29:30||4434829||C||GNU c++ 11 4.9||OK||315ms||54.29Mb||-||
||17 Apr 2017, 16:29:10||4434825||C||GNU c++ 11 4.9||OK||311ms||54.29Mb||-||
||17 Apr 2017, 16:25:21||4434211||A||GNU c++ 11 4.9||WA||93ms||420.00Kb||6||
||17 Apr 2017, 16:07:37||4433839||A||GNU c++ 11 4.9||WA||65ms||380.00Kb||6||
||17 Apr 2017, 16:03:24||4433812||A||GNU c++ 11 4.9||WA||114ms||388.00Kb||2||
||17 Apr 2017, 16:01:40||4433796||A||GNU c++ 11 4.9||WA||115ms||384.00Kb||2||
||17 Apr 2017, 15:33:42||4433584||A||GNU c++ 11 4.9||WA||91ms||424.00Kb||6||
||17 Apr 2017, 15:25:54||4433544||A||GNU c++ 11 4.9||WA||67ms||384.00Kb||6||
||17 Apr 2017, 15:13:14||4433475||A||GNU c++ 11 4.9||WA||64ms||384.00Kb||5||
||17 Apr 2017, 14:41:48||4433245||A||GNU c++ 11 4.9||WA||100ms||384.00Kb||2||
||17 Apr 2017, 13:57:27||4433023||J||GNU c++ 11 4.9||OK||2ms||380.00Kb||-||
||17 Apr 2017, 13:28:30||4432793||D||GNU c++ 11 4.9||OK||210ms||44.56Mb||-||
||17 Apr 2017, 12:26:47||4432472||I||GNU c++ 11 4.9||OK||1.071s||38.32Mb||-||
||17 Apr 2017, 12:03:32||4432349||K||GNU c++ 11 4.9||OK||230ms||41.92Mb||-||
||17 Apr 2017, 11:49:10||4432263||G||GNU c++ 11 4.9||OK||7ms||1.25Mb||-||
比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4407
start at 16:40
== 流水账 ==
== 总结 ==
== 题解 ==
{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
}}}
=== E. Jumping is Fun [Akalm] ===
用L[k][i]和R[k][i]分别表示从i开始走k步最左最右能到哪里（显然是连续的），不难发现这个可以倍增。
直接二分答案+判定是nlog^3^n的，从答案最高位开始判断每一位是否为1可以降掉一个log.┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│ 2017/04/17 16:34-21:34 · Siunaus · Akalm/JTJL/sfiction │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│D [0:22]│ 1 oOOo OOOOoo# 3 ││K [0:13]│ 1 OOOOo# 2 3 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│G [0:06]│ 1oo#2 3 ││I [0:15]│ 1 ooOOo# 2 3 ││J [0:27]│ 1 Ooo oo. oooo...oooO# 2 3 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│C [0:45]│ 1 oOOoOOOo. .OO. .o . 2 . ooooo. o.o# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [3:46]│ oo.OOOOoo ..ooOOoo. OOooo. OooOOooOOOOooOooo..oOooOo. oOOoOOOooOOOooOO. .oOOOOoO..ooOooooOooOOooooooooooooooooooo│├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│A [1:24]│ 1 oOOOo! 2 OOoOoO!.ooO!oo!OooOOooooo!!! oo.o!.o!││B [0:14]│ 1 OOooo. . oo . 2 ││E8[0:00]│ 1 ││F3[0:00]│ 1 ││H9[0:00]│ 1 │└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
| Submission time | ID | Problem | Compiler | Verdict | Time | Memory | Test |
| 17 Apr 2017, 16:33:49 | 4434858 | A | GNU c++ 11 4.9 | WA | 76ms | 384.00Kb | 2 |
| 17 Apr 2017, 16:33:10 | 4434854 | A | GNU c++ 11 4.9 | WA | 75ms | 380.00Kb | 2 |
| 17 Apr 2017, 16:29:30 | 4434829 | C | GNU c++ 11 4.9 | OK | 315ms | 54.29Mb | - |
| 17 Apr 2017, 16:29:10 | 4434825 | C | GNU c++ 11 4.9 | OK | 311ms | 54.29Mb | - |
| 17 Apr 2017, 16:25:21 | 4434211 | A | GNU c++ 11 4.9 | WA | 93ms | 420.00Kb | 6 |
| 17 Apr 2017, 16:07:37 | 4433839 | A | GNU c++ 11 4.9 | WA | 65ms | 380.00Kb | 6 |
| 17 Apr 2017, 16:03:24 | 4433812 | A | GNU c++ 11 4.9 | WA | 114ms | 388.00Kb | 2 |
| 17 Apr 2017, 16:01:40 | 4433796 | A | GNU c++ 11 4.9 | WA | 115ms | 384.00Kb | 2 |
| 17 Apr 2017, 15:33:42 | 4433584 | A | GNU c++ 11 4.9 | WA | 91ms | 424.00Kb | 6 |
| 17 Apr 2017, 15:25:54 | 4433544 | A | GNU c++ 11 4.9 | WA | 67ms | 384.00Kb | 6 |
| 17 Apr 2017, 15:13:14 | 4433475 | A | GNU c++ 11 4.9 | WA | 64ms | 384.00Kb | 5 |
| 17 Apr 2017, 14:41:48 | 4433245 | A | GNU c++ 11 4.9 | WA | 100ms | 384.00Kb | 2 |
| 17 Apr 2017, 13:57:27 | 4433023 | J | GNU c++ 11 4.9 | OK | 2ms | 380.00Kb | - |
| 17 Apr 2017, 13:28:30 | 4432793 | D | GNU c++ 11 4.9 | OK | 210ms | 44.56Mb | - |
| 17 Apr 2017, 12:26:47 | 4432472 | I | GNU c++ 11 4.9 | OK | 1.071s | 38.32Mb | - |
| 17 Apr 2017, 12:03:32 | 4432349 | K | GNU c++ 11 4.9 | OK | 230ms | 41.92Mb | - |
| 17 Apr 2017, 11:49:10 | 4432263 | G | GNU c++ 11 4.9 | OK | 7ms | 1.25Mb | - |
比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4407
start at 16:40
流水账
总结
题解
E. Jumping is Fun [Akalm]
用L[k][i]和R[k][i]分别表示从i开始走k步最左最右能到哪里（显然是连续的），不难发现这个可以倍增。
直接二分答案+判定是nlog3n的，从答案最高位开始判断每一位是否为1可以降掉一个log.