2016-E51-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ 2017/04/16 16:40-21:40 · Siunaus · Akalm/JTJL/sfiction │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│G [0:33]│ 1 OOOOO.ooo.. 2 .OOOo Oo# │
│J [0:01]│ 1#23 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│B6[1:36]│ 1 .OOOOOOOOOo oOOOOOOoooooooo.oo oo..oooooOo! !o.# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│A [0:22]│ 1 oOOOOOOo# 2 3 │
│C [0:14]│ 1 .OOoo.o#2 3 │
│D [0:47]│ 1 OOoOOOOooooo.o! .oooo#2 3│
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [3:34]│ o. oOOOOOOoo. .OOoo.oo OOOOO.ooo.OOoOOOOooooo.ooOOOOOOOOOooooooOOOOOOoooooooo.ooOOOOo..oooooOoOoooo.o. │
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│E [0:00]│ 1 2 .. │
│F3[0:00]│ 1 │
│H [0:00]│ 1 2 │
│I1[0:00]│ 1 │
│K8[0:00]│ 1 │
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}
||Submission time||ID||Problem||Compiler||Verdict||Time||Memory||Test||
||16 Apr 2017, 16:31:29||4427784||B||GNU c++ 11 4.9||OK||285ms||2.05Mb||-||
||16 Apr 2017, 16:24:13||4427710||B||GNU c++ 11 4.9||RE||359ms||103.03Mb||5||
||16 Apr 2017, 16:22:14||4427688||G||GNU c++ 11 4.9||OK||3.401s||162.21Mb||-||
||16 Apr 2017, 16:15:36||4427643||B||GNU c++ 11 4.9||ML||5.557s||512.44Mb||5||
||16 Apr 2017, 14:56:20||4426858||D||GNU c++ 11 4.9||OK||0.601s||46.88Mb||-||
||16 Apr 2017, 14:19:33||4425925||D||GNU c++ 11 4.9||TL||3.073s||19.75Mb||10||
||16 Apr 2017, 13:01:49||4425341||C||GNU c++ 11 4.9||OK||285ms||1.96Mb||-||
||16 Apr 2017, 12:17:51||4425074||A||GNU c++ 11 4.9||OK||37ms||1.00Mb||-||
||16 Apr 2017, 11:45:51||4424862||J||GNU c++ 11 4.9||OK||3ms||388.00Kb||-||
比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4398
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>
}}}
=== H. Maximum Color Clique [Akalm] ===
数学归纳法可推得满足题意的图至少有一个点，所有出边颜色一样。于是就能得出一个序列 {a_i}, 对于 u < v < w, C[a_u, a_v] == C[a_u, a_w]。
枚举子集中在 {a_i} 位置最靠后的元素即可算出答案。┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│ 2017/04/16 16:40-21:40 · Siunaus · Akalm/JTJL/sfiction │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│G [0:33]│ 1 OOOOO.ooo.. 2 .OOOo Oo# ││J [0:01]│ 1#23 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│B6[1:36]│ 1 .OOOOOOOOOo oOOOOOOoooooooo.oo oo..oooooOo! !o.# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│A [0:22]│ 1 oOOOOOOo# 2 3 ││C [0:14]│ 1 .OOoo.o#2 3 ││D [0:47]│ 1 OOoOOOOooooo.o! .oooo#2 3│├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [3:34]│ o. oOOOOOOoo. .OOoo.oo OOOOO.ooo.OOoOOOOooooo.ooOOOOOOOOOooooooOOOOOOoooooooo.ooOOOOo..oooooOoOoooo.o. │├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│E [0:00]│ 1 2 .. ││F3[0:00]│ 1 ││H [0:00]│ 1 2 ││I1[0:00]│ 1 ││K8[0:00]│ 1 │└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
| Submission time | ID | Problem | Compiler | Verdict | Time | Memory | Test |
| 16 Apr 2017, 16:31:29 | 4427784 | B | GNU c++ 11 4.9 | OK | 285ms | 2.05Mb | - |
| 16 Apr 2017, 16:24:13 | 4427710 | B | GNU c++ 11 4.9 | RE | 359ms | 103.03Mb | 5 |
| 16 Apr 2017, 16:22:14 | 4427688 | G | GNU c++ 11 4.9 | OK | 3.401s | 162.21Mb | - |
| 16 Apr 2017, 16:15:36 | 4427643 | B | GNU c++ 11 4.9 | ML | 5.557s | 512.44Mb | 5 |
| 16 Apr 2017, 14:56:20 | 4426858 | D | GNU c++ 11 4.9 | OK | 0.601s | 46.88Mb | - |
| 16 Apr 2017, 14:19:33 | 4425925 | D | GNU c++ 11 4.9 | TL | 3.073s | 19.75Mb | 10 |
| 16 Apr 2017, 13:01:49 | 4425341 | C | GNU c++ 11 4.9 | OK | 285ms | 1.96Mb | - |
| 16 Apr 2017, 12:17:51 | 4425074 | A | GNU c++ 11 4.9 | OK | 37ms | 1.00Mb | - |
| 16 Apr 2017, 11:45:51 | 4424862 | J | GNU c++ 11 4.9 | OK | 3ms | 388.00Kb | - |
比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4398
start at 16:40
流水账
总结
题解
H. Maximum Color Clique [Akalm]
数学归纳法可推得满足题意的图至少有一个点，所有出边颜色一样。于是就能得出一个序列 {a_i}, 对于 u < v < w, C[a_u, a_v] == C[a_u, a_w]。
枚举子集中在 {a_i} 位置最靠后的元素即可算出答案。