2016-E53-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ 2017/04/21 16:30-21:30 · Siunaus · Akalm/JTJL/sfiction │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│D [0:23]│ 1 oOOOOoo2.....o.3o .o# │
│E [0:28]│ 1 2 .OoO!o.o! . .ooOO..3o # │
│I [0:08]│ 1 2 3 OOo# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│F [1:12]│ 1 oO 2 ooo . oo oOOOooooooo3...oooo.oooooOoo!!# │
│G [0:13]│ 1 2 oOOOO# 3 │
│H [0:18]│ OOO1Ooo .# 2 3 │
│K [0:04]│ 1 O#3 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│A [0:39]│ oOO1OoOOo .OOOoO.oo# 2 │
│C [0:16]│ 1 .OOOoooo# 3 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [3:41]│ Oo.OOOOOooOOOooooOOoOOOOOoo......o.oo oOOOOoOOoOOOOoOOOoO.oo.oOOoOoo.o. oooooOOoOOoOOOoooooooo...oooo.oooooOooooo │
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│B6[0:00]│ 1 │
│J3[0:00]│ 1 │
│L [0:00]│ 1 2 3 │
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}
||Submission time||ID||Problem||Compiler||Verdict||Time||Memory||Test||
||21 Apr 2017, 16:24:13||4454838||F||GNU c++ 11 4.9||OK||79ms||380.00Kb||-||
||21 Apr 2017, 16:22:15||4454829||F||GNU c++ 11 4.9||WA||5ms||380.00Kb||5||
||21 Apr 2017, 16:18:26||4454816||F||GNU c++ 11 4.9||WA||4ms||380.00Kb||4||
||21 Apr 2017, 15:54:12||4454710||A||GNU c++ 11 4.9||TL||5.056s||168.00Kb||1||
||21 Apr 2017, 15:53:48||4454709||A||GNU c++ 11 4.9||WA||2.803s||164.00Kb||1||
||21 Apr 2017, 15:21:17||4454634||A||GNU c++ 11 4.9||WA||3.003s||176.00Kb||1||
||21 Apr 2017, 15:13:07||4454620||E||GNU c++ 11 4.9||OK||1.502s||304.94Mb||-||
||21 Apr 2017, 14:56:34||4454586||A||GNU c++ 11 4.9||WA||3.18s||164.00Kb||1||
||21 Apr 2017, 14:53:00||4454558||A||GNU c++ 11 4.9||CE||0ms||0B||-||
||21 Apr 2017, 14:35:56||4454477||E||GNU c++ 11 4.9||WA||3ms||636.00Kb||2||
||21 Apr 2017, 14:27:32||4454396||E||GNU c++ 11 4.9||WA||3ms||636.00Kb||2||
||21 Apr 2017, 14:10:41||4454123||A||GNU c++ 11 4.9||OK||2.155s||227.81Mb||-||
||21 Apr 2017, 13:49:21||4453694||G||GNU c++ 11 4.9||OK||0.585s||494.34Mb||-||
||21 Apr 2017, 13:20:21||4453387||D||GNU c++ 11 4.9||OK||145ms||17.54Mb||-||
||21 Apr 2017, 12:31:13||4453242||I||GNU c++ 11 4.9||OK||403ms||61.40Mb||-||
||21 Apr 2017, 12:23:16||4453213||C||GNU c++ 11 4.9||OK||7ms||512.00Kb||-||
||21 Apr 2017, 12:10:35||4453115||H||GNU c++ 11 4.9||OK||118ms||648.00Kb||-||
||21 Apr 2017, 11:44:28||4452582||K||GNU c++ 11 4.9||OK||3ms||380.00Kb||-||
||21 Apr 2017, 11:43:57||4452561||K||Free Basic 1.04||CE||0ms||0B||-||
比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4360
start at 16:30
== 流水账 ==
== 总结 ==
== 题解 ==
{{{
#!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>
}}}
=== J. Jackpot [Akalm] ===
f[u][k]表示从u出发到dfn更大的结点、长度为k的路径数，做一下简单的仙人掌dp……
=== L. Longest repeating substring [Akalm] ===
s[l, r]和s[u, v]相等当且仅当所有模 (u-l) 相等的位置字符都相同。维护一下活跃的同余位置上每种字母的数量就能求出修改代价。
枚举两次出现位置的差值diff。记f[diff][l]是最大的r-l+1使得 s[l, r] == s[l+diff, r+diff], 不难发现有f[diff][l] <= f[diff][l+1] + 1, 于是就可以用2pointers去维护答案。┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│ 2017/04/21 16:30-21:30 · Siunaus · Akalm/JTJL/sfiction │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│D [0:23]│ 1 oOOOOoo2.....o.3o .o# ││E [0:28]│ 1 2 .OoO!o.o! . .ooOO..3o # ││I [0:08]│ 1 2 3 OOo# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│F [1:12]│ 1 oO 2 ooo . oo oOOOooooooo3...oooo.oooooOoo!!# ││G [0:13]│ 1 2 oOOOO# 3 ││H [0:18]│ OOO1Ooo .# 2 3 ││K [0:04]│ 1 O#3 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│A [0:39]│ oOO1OoOOo .OOOoO.oo# 2 ││C [0:16]│ 1 .OOOoooo# 3 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [3:41]│ Oo.OOOOOooOOOooooOOoOOOOOoo......o.oo oOOOOoOOoOOOOoOOOoO.oo.oOOoOoo.o. oooooOOoOOoOOOoooooooo...oooo.oooooOooooo │├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│B6[0:00]│ 1 ││J3[0:00]│ 1 ││L [0:00]│ 1 2 3 │└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
| Submission time | ID | Problem | Compiler | Verdict | Time | Memory | Test |
| 21 Apr 2017, 16:24:13 | 4454838 | F | GNU c++ 11 4.9 | OK | 79ms | 380.00Kb | - |
| 21 Apr 2017, 16:22:15 | 4454829 | F | GNU c++ 11 4.9 | WA | 5ms | 380.00Kb | 5 |
| 21 Apr 2017, 16:18:26 | 4454816 | F | GNU c++ 11 4.9 | WA | 4ms | 380.00Kb | 4 |
| 21 Apr 2017, 15:54:12 | 4454710 | A | GNU c++ 11 4.9 | TL | 5.056s | 168.00Kb | 1 |
| 21 Apr 2017, 15:53:48 | 4454709 | A | GNU c++ 11 4.9 | WA | 2.803s | 164.00Kb | 1 |
| 21 Apr 2017, 15:21:17 | 4454634 | A | GNU c++ 11 4.9 | WA | 3.003s | 176.00Kb | 1 |
| 21 Apr 2017, 15:13:07 | 4454620 | E | GNU c++ 11 4.9 | OK | 1.502s | 304.94Mb | - |
| 21 Apr 2017, 14:56:34 | 4454586 | A | GNU c++ 11 4.9 | WA | 3.18s | 164.00Kb | 1 |
| 21 Apr 2017, 14:53:00 | 4454558 | A | GNU c++ 11 4.9 | CE | 0ms | 0B | - |
| 21 Apr 2017, 14:35:56 | 4454477 | E | GNU c++ 11 4.9 | WA | 3ms | 636.00Kb | 2 |
| 21 Apr 2017, 14:27:32 | 4454396 | E | GNU c++ 11 4.9 | WA | 3ms | 636.00Kb | 2 |
| 21 Apr 2017, 14:10:41 | 4454123 | A | GNU c++ 11 4.9 | OK | 2.155s | 227.81Mb | - |
| 21 Apr 2017, 13:49:21 | 4453694 | G | GNU c++ 11 4.9 | OK | 0.585s | 494.34Mb | - |
| 21 Apr 2017, 13:20:21 | 4453387 | D | GNU c++ 11 4.9 | OK | 145ms | 17.54Mb | - |
| 21 Apr 2017, 12:31:13 | 4453242 | I | GNU c++ 11 4.9 | OK | 403ms | 61.40Mb | - |
| 21 Apr 2017, 12:23:16 | 4453213 | C | GNU c++ 11 4.9 | OK | 7ms | 512.00Kb | - |
| 21 Apr 2017, 12:10:35 | 4453115 | H | GNU c++ 11 4.9 | OK | 118ms | 648.00Kb | - |
| 21 Apr 2017, 11:44:28 | 4452582 | K | GNU c++ 11 4.9 | OK | 3ms | 380.00Kb | - |
| 21 Apr 2017, 11:43:57 | 4452561 | K | Free Basic 1.04 | CE | 0ms | 0B | - |
比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4360
start at 16:30
流水账
总结
题解
J. Jackpot [Akalm]
f[u][k]表示从u出发到dfn更大的结点、长度为k的路径数，做一下简单的仙人掌dp……
L. Longest repeating substring [Akalm]
s[l, r]和s[u, v]相等当且仅当所有模 (u-l) 相等的位置字符都相同。维护一下活跃的同余位置上每种字母的数量就能求出修改代价。
枚举两次出现位置的差值diff。记f[diff][l]是最大的r-l+1使得 s[l, r] == s[l+diff, r+diff], 不难发现有f[diff][l] <= f[diff][l+1] + 1, 于是就可以用2pointers去维护答案。