2016-E49-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ 1985/08/05 14:13-19:13 · Siunaus · Akalm/JTJL/sfiction │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│C [1:10]│ 1 2 3 oOOo oOOO. OOooooo ..ooo. oooOoooooooo# │
│J [0:29]│ 1 oOOo! 2 oOOOoo. 3 o!..# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│H [0:41]│ 1 o.OOOOOOOoOOooOo.. o.# 2 3 │
│M [0:27]│ 1 oOOo2OooOoO# 3 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│B [0:09]│ oO1# 2 3 │
│E [0:25]│ 1 OOOOOooo.oo! # 2 3 │
│G [1:01]│ 1 OOOOOOOo2oo. o .ooOooo oOo! .oooo# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [4:34]│ .OOo oOOooOOooOOooOooOoOoOOOooOOOOOooo.ooooooOOOOOOOoOOooOo.oOOO.oOOOOOOOOOOooooOOoooooooOooo.ooooOooooOooooooooooooooO│
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│A6[0:11]│ .OOo . . 1 oO│
│D2[0:00]│ 1 │
│F [0:00]│ 1 2 │
│I5[0:00]│ 1 │
│K [0:00]│ 1 2 │
│L4[0:00]│ 1 │
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}
||Submission time||ID||Problem||Compiler||Verdict||Time||Memory||Test||
||13 Apr 2017, 15:55:10||4409220||G||GNU c++ 11 4.9||OK||-||0.947s||68.89Mb||-||
||13 Apr 2017, 15:43:02||4409174||C||GNU c++ 11 4.9||OK||-||0.638s||4.56Mb||-||
||13 Apr 2017, 15:13:00||4408436||G||GNU c++ 11 4.9||WA||-||1.122s||79.92Mb||2||
||13 Apr 2017, 13:45:11||4407907||H||GNU c++ 11 4.9||OK||-||73ms||14.82Mb||-||
||13 Apr 2017, 12:55:02||4407655||J||GNU c++ 11 4.9||OK||-||60ms||836.00Kb||-||
||13 Apr 2017, 12:54:20||4407652||E||GNU c++ 11 4.9||OK||-||74ms||1.83Mb||-||
||13 Apr 2017, 12:49:50||4407626||J||GNU c++ 11 4.9||WA||-||4ms||512.00Kb||2||
||13 Apr 2017, 12:45:18||4407601||E||GNU c++ 11 4.9||PE||-||66ms||1.59Mb||2||
||13 Apr 2017, 12:03:02||4407403||M||GNU c++ 11 4.9||OK||-||278ms||37.70Mb||-||
||13 Apr 2017, 11:35:39||4407300||J||GNU c++ 11 4.9||WA||-||4ms||512.00Kb||2||
||13 Apr 2017, 11:24:46||4407255||B||GNU c++ 11 4.9||OK||-||32ms||380.00Kb||-||
比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4384
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>
}}}
=== I. Industrial Cookie Production [Akalm] ===
阅读理解题。枚举所有机器的状态，再枚举在某个状态下所有最接近G的子集来进行转移，使用矩阵乘法优化。排序后等价的状态可以合并。
=== L. Longest Racing Track [Akalm] ===
考虑欧拉回路的存在性，题目即为删掉尽量少的PlainRoad使得所有点的deg都是偶数，也就是在PlainRoad子图上找总长度尽量小的不相交路径把初始deg为奇数的点两两连起来。
注意到题目中点数较少，可以多次随机染色求二分图最小权匹配来解决。┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│ 1985/08/05 14:13-19:13 · Siunaus · Akalm/JTJL/sfiction │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│C [1:10]│ 1 2 3 oOOo oOOO. OOooooo ..ooo. oooOoooooooo# ││J [0:29]│ 1 oOOo! 2 oOOOoo. 3 o!..# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│H [0:41]│ 1 o.OOOOOOOoOOooOo.. o.# 2 3 ││M [0:27]│ 1 oOOo2OooOoO# 3 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│B [0:09]│ oO1# 2 3 ││E [0:25]│ 1 OOOOOooo.oo! # 2 3 ││G [1:01]│ 1 OOOOOOOo2oo. o .ooOooo oOo! .oooo# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [4:34]│ .OOo oOOooOOooOOooOooOoOoOOOooOOOOOooo.ooooooOOOOOOOoOOooOo.oOOO.oOOOOOOOOOOooooOOoooooooOooo.ooooOooooOooooooooooooooO│├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│A6[0:11]│ .OOo . . 1 oO││D2[0:00]│ 1 ││F [0:00]│ 1 2 ││I5[0:00]│ 1 ││K [0:00]│ 1 2 ││L4[0:00]│ 1 │└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
| Submission time | ID | Problem | Compiler | Verdict | Time | Memory | Test | |
| 13 Apr 2017, 15:55:10 | 4409220 | G | GNU c++ 11 4.9 | OK | - | 0.947s | 68.89Mb | - |
| 13 Apr 2017, 15:43:02 | 4409174 | C | GNU c++ 11 4.9 | OK | - | 0.638s | 4.56Mb | - |
| 13 Apr 2017, 15:13:00 | 4408436 | G | GNU c++ 11 4.9 | WA | - | 1.122s | 79.92Mb | 2 |
| 13 Apr 2017, 13:45:11 | 4407907 | H | GNU c++ 11 4.9 | OK | - | 73ms | 14.82Mb | - |
| 13 Apr 2017, 12:55:02 | 4407655 | J | GNU c++ 11 4.9 | OK | - | 60ms | 836.00Kb | - |
| 13 Apr 2017, 12:54:20 | 4407652 | E | GNU c++ 11 4.9 | OK | - | 74ms | 1.83Mb | - |
| 13 Apr 2017, 12:49:50 | 4407626 | J | GNU c++ 11 4.9 | WA | - | 4ms | 512.00Kb | 2 |
| 13 Apr 2017, 12:45:18 | 4407601 | E | GNU c++ 11 4.9 | PE | - | 66ms | 1.59Mb | 2 |
| 13 Apr 2017, 12:03:02 | 4407403 | M | GNU c++ 11 4.9 | OK | - | 278ms | 37.70Mb | - |
| 13 Apr 2017, 11:35:39 | 4407300 | J | GNU c++ 11 4.9 | WA | - | 4ms | 512.00Kb | 2 |
| 13 Apr 2017, 11:24:46 | 4407255 | B | GNU c++ 11 4.9 | OK | - | 32ms | 380.00Kb | - |
比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4384
start at 16:00
流水账
总结
题解
I. Industrial Cookie Production [Akalm]
阅读理解题。枚举所有机器的状态，再枚举在某个状态下所有最接近G的子集来进行转移，使用矩阵乘法优化。排序后等价的状态可以合并。
L. Longest Racing Track [Akalm]
考虑欧拉回路的存在性，题目即为删掉尽量少的PlainRoad使得所有点的deg都是偶数，也就是在PlainRoad子图上找总长度尽量小的不相交路径把初始deg为奇数的点两两连起来。
注意到题目中点数较少，可以多次随机染色求二分图最小权匹配来解决。