2016-E48-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ 2017/04/12 16:55-21:55 · Siunaus · Akalm/JTJL/sfiction │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│L [0:42]│ 1 2 oOo oooOoooooooo. .OOoo#3 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│J [0:44]│ 1 2 ooo. oOOooo. ooo! .Oooo! 3 oOO# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│C [0:09]│ 1 oOO# 2 3 │
│E [0:26]│ 1 2OOOoOooo. .! oo# 3 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [2:41]│ oOOo. . ooooOOOoOooooOOoooOoooooOoOooooooOoooooooooOOoOOoo. . ooOOOooooooOooOoo.o│
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│A [0:00]│ 1 2 │
│B0[0:00]│ │
│D3[0:00]│ 1 │
│F6[0:00]│ 1 │
│G0[0:00]│ │
│H5[0:00]│ 1 │
│I [0:40]│ 1 ooOOOooooooOooO2o.o│
│K1[0:00]│ 1 │
│M3[0:00]│ 1 │
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}
||Submission time||ID||Problem||Compiler||Verdict||Time||Memory||Test||
||12 Apr 2017, 15:38:16||4403139||L||GNU c++ 11 4.9||OK||246ms||3.64Mb||-||
||12 Apr 2017, 15:27:47||4403085||J||GNU c++ 11 4.9||OK||0.522s||8.00Mb||-||
||12 Apr 2017, 14:48:38||4402930||J||GNU c++ 11 4.9||WA||205ms||3.99Mb||18||
||12 Apr 2017, 14:32:02||4402826||J||GNU c++ 11 4.9||WA||138ms||3.99Mb||18||
||12 Apr 2017, 14:24:17||4402720||E||GNU c++ 11 4.9||OK||0.511s||492.00Kb||-||
||12 Apr 2017, 14:11:48||4402617||E||GNU c++ 11 4.9||TL||1.045s||900.00Kb||23||
||12 Apr 2017, 12:52:44||4402186||C||GNU c++ 11 4.9||OK||74ms||2.44Mb||-||
比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4379
start at 16:55
== 流水账 ==
== 总结 ==
== 题解 ==
{{{
#!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>
}}}
=== C. Count the Trees [JTJL, sfiction] ===
{{{
#!html
将连通块缩为点，连接到大小为k连通块的点有k种选择。考虑缩点后无根树的prufer编码。因为每个点的度数为prufer编码中出现次数+1，容易得出总方案数为$(\prod{sz[i]})n^{n_0-2}$。n0为缩点后点数。O(nlogn)。
}}}
=== D. Dancing IOI Team [sfiction] ===
考虑枚举final score中top-k和non-top-k之间的分割点，设为X。那么每个a_i的可选c_i都是连续（排序后）的一段。以ai为行，ci为列（均有序）。如果有一列没有任何元素，那么无解。否则必然存在一个数m，使得左上角(n-k)*m区域全可选，右下角k*(n-m)区域均可选。左下角和右上角分别是两个梯形区域，DP求出有i个点落在左下角，j个点落在右上角的方案数，然后用排列组合计算矩形区域中方案数。O(an^2^)。
=== E. Expectation of Damage [sfiction] ===
可以枚举ij，计算打出攻击i，之前有j次尝试的概率之和。如果考虑大小为j的无序集，则是多项式\prod{(1+(1-p[i])x)}的系数。因此将所有一次式相乘，枚举i时除掉i对应的一次式再统计。O(n^2^)。
=== F. Fire Engines [sfiction] ===
设f(x)是x对应的pump坐标，如果有f(x)<=x，那么对于[f(x),x)中的y，必然有f(y)<=y。对于(f(x),x]中的f(y)，必然有f(y)<=y。可以推出所有解必定能够分解为多个极小化的连续段，连续段中pump和engine数量相等，并且都满足f(x)<=x或者f(x)>x。因此对于每个坐标x，有且仅有一个对应的合法极小化连续段。设dp(i)为只考虑前i个坐标，且其中engine全部匹配的最小代价，则只有O(n)个转移。O(nlogn+mlogm)。
=== H. Holes in Aquarium [sfiction] ===
根据底部每段的高度关系建笛卡尔树。每次打穿一个叶子，其到根路径上的水都会流尽。因此就是选k个叶子，使得路径并权值最大。每次贪心取。贪心过程不需要数据结构，可以自底向上求链，每次选最大的一个儿子继续，另一个加入可选集。对可选集做nth_element。O(n)。
=== L. Light Bulbs [sfiction, Akalm] ===
每相邻一个空位（包括外界），都将让一个位置的可选状态减少一半。于是可以在枚举起点终点的朝向后，逐个格子递推状态。
=== M. Medical Services [Akalm] ===
如果只有一个根，两个问题分别可以用排序和二分解决。
现在枚举两个根路径上切掉哪条边，两侧分别当成单根的情况算一算即可。
怀疑这题有毒……直接枚举会T，最小值落在两边可能三分不出来……┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│ 2017/04/12 16:55-21:55 · Siunaus · Akalm/JTJL/sfiction │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│L [0:42]│ 1 2 oOo oooOoooooooo. .OOoo#3 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│J [0:44]│ 1 2 ooo. oOOooo. ooo! .Oooo! 3 oOO# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│C [0:09]│ 1 oOO# 2 3 ││E [0:26]│ 1 2OOOoOooo. .! oo# 3 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [2:41]│ oOOo. . ooooOOOoOooooOOoooOoooooOoOooooooOoooooooooOOoOOoo. . ooOOOooooooOooOoo.o│├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│A [0:00]│ 1 2 ││B0[0:00]│ ││D3[0:00]│ 1 ││F6[0:00]│ 1 ││G0[0:00]│ ││H5[0:00]│ 1 ││I [0:40]│ 1 ooOOOooooooOooO2o.o││K1[0:00]│ 1 ││M3[0:00]│ 1 │└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
| Submission time | ID | Problem | Compiler | Verdict | Time | Memory | Test |
| 12 Apr 2017, 15:38:16 | 4403139 | L | GNU c++ 11 4.9 | OK | 246ms | 3.64Mb | - |
| 12 Apr 2017, 15:27:47 | 4403085 | J | GNU c++ 11 4.9 | OK | 0.522s | 8.00Mb | - |
| 12 Apr 2017, 14:48:38 | 4402930 | J | GNU c++ 11 4.9 | WA | 205ms | 3.99Mb | 18 |
| 12 Apr 2017, 14:32:02 | 4402826 | J | GNU c++ 11 4.9 | WA | 138ms | 3.99Mb | 18 |
| 12 Apr 2017, 14:24:17 | 4402720 | E | GNU c++ 11 4.9 | OK | 0.511s | 492.00Kb | - |
| 12 Apr 2017, 14:11:48 | 4402617 | E | GNU c++ 11 4.9 | TL | 1.045s | 900.00Kb | 23 |
| 12 Apr 2017, 12:52:44 | 4402186 | C | GNU c++ 11 4.9 | OK | 74ms | 2.44Mb | - |
比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4379
start at 16:55
流水账
总结
题解
C. Count the Trees [JTJL, sfiction]
将连通块缩为点，连接到大小为k连通块的点有k种选择。考虑缩点后无根树的prufer编码。因为每个点的度数为prufer编码中出现次数+1，容易得出总方案数为$(\prod{sz[i]})n^{n_0-2}$。n0为缩点后点数。O(nlogn)。D. Dancing IOI Team [sfiction]
考虑枚举final score中top-k和non-top-k之间的分割点，设为X。那么每个a_i的可选c_i都是连续（排序后）的一段。以ai为行，ci为列（均有序）。如果有一列没有任何元素，那么无解。否则必然存在一个数m，使得左上角(n-k)*m区域全可选，右下角k*(n-m)区域均可选。左下角和右上角分别是两个梯形区域，DP求出有i个点落在左下角，j个点落在右上角的方案数，然后用排列组合计算矩形区域中方案数。O(an2)。
E. Expectation of Damage [sfiction]
可以枚举ij，计算打出攻击i，之前有j次尝试的概率之和。如果考虑大小为j的无序集，则是多项式\prod{(1+(1-p[i])x)}的系数。因此将所有一次式相乘，枚举i时除掉i对应的一次式再统计。O(n2)。
F. Fire Engines [sfiction]
设f(x)是x对应的pump坐标，如果有f(x)<=x，那么对于[f(x),x)中的y，必然有f(y)<=y。对于(f(x),x]中的f(y)，必然有f(y)<=y。可以推出所有解必定能够分解为多个极小化的连续段，连续段中pump和engine数量相等，并且都满足f(x)<=x或者f(x)>x。因此对于每个坐标x，有且仅有一个对应的合法极小化连续段。设dp(i)为只考虑前i个坐标，且其中engine全部匹配的最小代价，则只有O(n)个转移。O(nlogn+mlogm)。
H. Holes in Aquarium [sfiction]
根据底部每段的高度关系建笛卡尔树。每次打穿一个叶子，其到根路径上的水都会流尽。因此就是选k个叶子，使得路径并权值最大。每次贪心取。贪心过程不需要数据结构，可以自底向上求链，每次选最大的一个儿子继续，另一个加入可选集。对可选集做nth_element。O(n)。
L. Light Bulbs [sfiction, Akalm]
每相邻一个空位（包括外界），都将让一个位置的可选状态减少一半。于是可以在枚举起点终点的朝向后，逐个格子递推状态。
M. Medical Services [Akalm]
如果只有一个根，两个问题分别可以用排序和二分解决。
现在枚举两个根路径上切掉哪条边，两侧分别当成单根的情况算一算即可。
怀疑这题有毒……直接枚举会T，最小值落在两边可能三分不出来……