2016-E50-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ 2017/04/15 16:00-21:00 · Siunaus · Akalm/JTJL/sfiction │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│D [0:14]│ 1 oOOOoo# 2 3 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│C [0:34]│ 1 2OOOoOOooooo!. o# │
│K [0:50]│ 1 oOOoooOoo...oOooooo!. 2! oo# 3 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│B [0:15]│ OOO1o!# 2 3 │
│J9[1:17]│ 1 ooOoooooooooooo. oOOoooooo. Oo.oo!! oo..#│
│L [0:12]│ 1 OOoo.#2 3 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [3:48]│ OOOOoo.. OOoo.oOOOooo.. .. ..oOOoooOoo...oOooooo.. .. ooooOoooooooooooo.OOOOOOOoOOoooooooOOOo.oo.OOOOoOOooooo.ooooo│
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│A0[0:00]│ │
│E6[0:26]│ 1 .OOOOOOOo oOO! o│
│F3[0:00]│ 1 │
│G0[0:00]│ │
│H0[0:00]│ │
│I1[0:00]│ 1 │
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}
||Submission time||ID||Problem||Compiler||Verdict||Time||Memory||Test||
||15 Apr 2017, 15:59:40||4420446||J||GNU c++ 11 4.9||WA||211ms||4.57Mb||2||
||15 Apr 2017, 15:58:46||4420432||J||GNU c++ 11 4.9||OK||192ms||8.20Mb||-||
||15 Apr 2017, 15:56:38||4420420||C||GNU c++ 11 4.9||OK||29ms||2.54Mb||-||
||15 Apr 2017, 15:47:23||4420352||C||GNU c++ 11 4.9||WA||29ms||3.23Mb||17||
||15 Apr 2017, 15:15:12||4420142||J||GNU c++ 11 4.9||WA||211ms||4.57Mb||2||
||15 Apr 2017, 15:13:54||4420130||J||GNU c++ 11 4.9||RE||4ms||380.00Kb||2||
||15 Apr 2017, 15:00:19||4420049||E||GNU c++ 11 4.9||WA||162ms||145.16Mb||2||
||15 Apr 2017, 13:33:37||4418809||K||GNU c++ 11 4.9||OK||462ms||41.62Mb||-||
||15 Apr 2017, 13:23:52||4418728||K||GNU c++ 11 4.9||WA||4ms||640.00Kb||18||
||15 Apr 2017, 13:13:21||4418649||K||GNU c++ 11 4.9||WA||4ms||640.00Kb||18||
||15 Apr 2017, 12:01:19||4418075||D||GNU c++ 11 4.9||OK||2.796s||35.23Mb||-||
||15 Apr 2017, 11:46:41||4417957||L||GNU c++ 11 4.9||OK||54ms||9.14Mb||-||
||15 Apr 2017, 11:23:48||4417779||B||GNU c++ 11 4.9||OK||42ms||24.99Mb||-||
||15 Apr 2017, 11:22:03||4417765||B||GNU c++ 11 4.9||RE||4ms||788.00Kb||3||
比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4394
start at 16:00
== 流水账 ==
== 总结 ==
== 题解 ==
{{{
#!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>
}}}
=== H. Hippos [Akalm] ===
先随机给边定向。
一通欧拉定理组合拳后可证得任一deg[u] > 3的点一定能连到某个 deg[v] <= 2的点，翻转他们路径上的所有边就可以让deg[u]-1。
有点像网络流的过程。初始局面贪心定向后直接流过去了……┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│ 2017/04/15 16:00-21:00 · Siunaus · Akalm/JTJL/sfiction │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│D [0:14]│ 1 oOOOoo# 2 3 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│C [0:34]│ 1 2OOOoOOooooo!. o# ││K [0:50]│ 1 oOOoooOoo...oOooooo!. 2! oo# 3 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│B [0:15]│ OOO1o!# 2 3 ││J9[1:17]│ 1 ooOoooooooooooo. oOOoooooo. Oo.oo!! oo..#││L [0:12]│ 1 OOoo.#2 3 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [3:48]│ OOOOoo.. OOoo.oOOOooo.. .. ..oOOoooOoo...oOooooo.. .. ooooOoooooooooooo.OOOOOOOoOOoooooooOOOo.oo.OOOOoOOooooo.ooooo│├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│A0[0:00]│ ││E6[0:26]│ 1 .OOOOOOOo oOO! o││F3[0:00]│ 1 ││G0[0:00]│ ││H0[0:00]│ ││I1[0:00]│ 1 │└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
| Submission time | ID | Problem | Compiler | Verdict | Time | Memory | Test |
| 15 Apr 2017, 15:59:40 | 4420446 | J | GNU c++ 11 4.9 | WA | 211ms | 4.57Mb | 2 |
| 15 Apr 2017, 15:58:46 | 4420432 | J | GNU c++ 11 4.9 | OK | 192ms | 8.20Mb | - |
| 15 Apr 2017, 15:56:38 | 4420420 | C | GNU c++ 11 4.9 | OK | 29ms | 2.54Mb | - |
| 15 Apr 2017, 15:47:23 | 4420352 | C | GNU c++ 11 4.9 | WA | 29ms | 3.23Mb | 17 |
| 15 Apr 2017, 15:15:12 | 4420142 | J | GNU c++ 11 4.9 | WA | 211ms | 4.57Mb | 2 |
| 15 Apr 2017, 15:13:54 | 4420130 | J | GNU c++ 11 4.9 | RE | 4ms | 380.00Kb | 2 |
| 15 Apr 2017, 15:00:19 | 4420049 | E | GNU c++ 11 4.9 | WA | 162ms | 145.16Mb | 2 |
| 15 Apr 2017, 13:33:37 | 4418809 | K | GNU c++ 11 4.9 | OK | 462ms | 41.62Mb | - |
| 15 Apr 2017, 13:23:52 | 4418728 | K | GNU c++ 11 4.9 | WA | 4ms | 640.00Kb | 18 |
| 15 Apr 2017, 13:13:21 | 4418649 | K | GNU c++ 11 4.9 | WA | 4ms | 640.00Kb | 18 |
| 15 Apr 2017, 12:01:19 | 4418075 | D | GNU c++ 11 4.9 | OK | 2.796s | 35.23Mb | - |
| 15 Apr 2017, 11:46:41 | 4417957 | L | GNU c++ 11 4.9 | OK | 54ms | 9.14Mb | - |
| 15 Apr 2017, 11:23:48 | 4417779 | B | GNU c++ 11 4.9 | OK | 42ms | 24.99Mb | - |
| 15 Apr 2017, 11:22:03 | 4417765 | B | GNU c++ 11 4.9 | RE | 4ms | 788.00Kb | 3 |
比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4394
start at 16:00
流水账
总结
题解
H. Hippos [Akalm]
先随机给边定向。
一通欧拉定理组合拳后可证得任一deg[u] > 3的点一定能连到某个 deg[v] <= 2的点，翻转他们路径上的所有边就可以让deg[u]-1。
有点像网络流的过程。初始局面贪心定向后直接流过去了……