2016-E44-team1

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                     2017/03/31 18:14-23:14 · Siunaus · Akalm/JTJL/sfiction                                      │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│H [0:48]│      1              OooO          oOOOOoooooOOo.2! .oOoo#                 3                                            │
│I [0:12]│          1OOO#                                             2                                                           │
│L [0:18]│                   1                                        2            oOOo.o..o.o3  o! !   . .     #                 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│F [0:16]│   oO1OOo#  3                                                                                                           │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│A [0:24]│                 1      oOOoooooo.o#             2              3                                                       │
│B [0:10]│      1        OOo#2     3                                                                                              │
│D [0:03]│ 1o#                                                                                                                    │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [3:30]│  oOOOOOooOOOOoOOo...OooOOOoooooo.ooOOOOoooooOOo.o. .oOoo.oOOooOOOooo.oOooOOo.o..o.oo  oOOOooO. oo.o o .    oOOo..oooooO│
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│C3[0:00]│                                                                                           1                            │
│E0[0:00]│                                                                                                                        │
│G3[0:32]│                                                          1OOooOOOooo.oOo.                                              │
│J5[0:00]│                                1                                                                                       │
│K [0:47]│                      1                                                            2    oOOooO. oo.o o .    3OOo..oooooO│
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}

||#||When||Problem||Lang||Verdict||Time||Memory||
||463||4:15:42||1345||L||g++0x||OK||N/A||
||462||3:45:41||1001||L||g++0x||Wrong answer||12||
||461||3:40:36||1000||L||g++0x||Wrong answer||12||
||460||2:24:41||2392||H||g++0x||OK||N/A||
||459||2:06:08||2180||H||g++0x||Memory limit exceeded||1||
||458||1:28:12||1720||A||g++0x||OK||N/A||
||457||0:47:35||981||B||g++0x||OK||N/A||
||456||0:46:41||980||B||g++0x||Compilation error||N/A||
||455||0:37:24||1957||I||g++0x||OK||N/A||
||454||0:24:24||1229||F||g++0x||OK||N/A||
||453||0:09:29||499||D||g++0x||OK||N/A||

比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006275

start at 18:15

== 流水账 ==

== 总结 ==

== 题解 ==

{{{
#!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>
}}}


=== A. Album of Numbers [sfiction] ===

{{{
#!html
$ans=\sum{(a_i-a_{i-1})/\prod_{j=1}^{i-1}{(b_j+1)}}$，其中ai是从小到大排序的数字，bi是其出现次数。另外要除去空集。注意到分母增长很快，因此每次只需暴力计算前50项。O(nlogn+50q)。
}}}

比赛时的做法是用线段树维护结果，用对数形式保存分母，过大时当成inf。

=== B. Well Off [sfiction] ===

将每个未知量的正负视为点，对每种情况连边判环。O(n+m)。

=== C. Accurate Shots (8M ML!) [sfiction] ===

考虑折半搜索。由于空间限制，不能存下所有的数。可以枚举高位部分模为x的所有值，统计最少修改、数量和最小值。然后枚举低位部分模为m-x的所有值，求出相应量组合即可。O(n^0.5^)，空间为O(1)。

本题折半的特殊之处在于两部分各自划分为数个集合，两侧集合一一对应。而且最优解的构成是分别从两个集合中取出最优解合并。限制很多。

=== G. Board Game ===

对颜色分治；计算两边颜色答案时，可以通过先将一边取负，然后求两边凸包的Minkowski和来找最大值。

=== H. Scouts [JTJL, Akalm] ===

写出n^3^的dp表达式后，可以发现在某个位置之后一定取左边（右边同理）。于是可以把结果算出来后拿数据结构维护区间最小值。

赛后仔细想想发现是可以用树状数组维护的……

=== I. Insects [Akalm] ===

最大权闭合子图。

=== J. Cave [Akalm] ===

不难想到用f[st][i]表示当前走过的集合为st，位于i，还需多久找到物品的期望，分两种（直接走、重新随机选点）情况转移。但第二种转移:

{{{
#!html
$E_st = t + \frac{1}{n}(\sum_{i \notin st}f[st | 1 << i][i] + \sum_{i \in st}f[st][i])$ <br>

是有环的。

记$f'[st][i]$为仅做第一种转移后的结果，显然有

$f[st][t] = min(f'[st][t], E_st)$ <br>

代入得

$E_st = t + \frac{1}{n}(\sum_{i \notin st}f[st | 1 << i][i] + \sum_{i \in st}min(f'[st][i], E_st)$ <br>

而$f'[st][i]$的计算不依赖于$E_st$，于是可以求出$f'[st][i]$，排序后枚举$E_st$所处的区间来破掉min()即可进行转移。

}}}

=== K. Blocks [JTJL, sfiction] ===

根据最小块的放置位置可以得到递推式f(n,p,l)=f(n-1,p,l)*(n-1)+f(n-1,p-1,l)+f(n-1,p,l-1)。暴力做O(npl)。

{{{
#!html
根据递推式可以直接得出固定n的生成函数$\prod_{i=0}^{n-1}{(x+y+i)}$，将$x+y$视为整体展开，可以$O(n(p+l))$计算确定x和y总次数的项的系数，然后再乘上$\binom{p-1}{p+l-2}$。对系数的直观的解释，可以考虑将两个相邻可见块中间的部分视为一段，例如21534视为[2,1],[5],[3,4]，容易发现两侧段的交换是合法的。
}}}

=== L. Postman [Akalm] ===

试着写出确定顺序后的树dp表达式，就可以发现转移并不依赖于子树访问顺序，于是可以做换根树dp。
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│                                     2017/03/31 18:14-23:14 · Siunaus · Akalm/JTJL/sfiction                                      │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│H [0:48]│      1              OooO          oOOOOoooooOOo.2! .oOoo#                 3                                            ││I [0:12]│          1OOO#                                             2                                                           ││L [0:18]│                   1                                        2            oOOo.o..o.o3  o! !   . .     #                 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│F [0:16]│   oO1OOo#  3                                                                                                           │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│A [0:24]│                 1      oOOoooooo.o#             2              3                                                       ││B [0:10]│      1        OOo#2     3                                                                                              ││D [0:03]│ 1o#                                                                                                                    │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [3:30]│  oOOOOOooOOOOoOOo...OooOOOoooooo.ooOOOOoooooOOo.o. .oOoo.oOOooOOOooo.oOooOOo.o..o.oo  oOOOooO. oo.o o .    oOOo..oooooO│├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│C3[0:00]│                                                                                           1                            ││E0[0:00]│                                                                                                                        ││G3[0:32]│                                                          1OOooOOOooo.oOo.                                              ││J5[0:00]│                                1                                                                                       ││K [0:47]│                      1                                                            2    oOOooO. oo.o o .    3OOo..oooooO│└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
#WhenProblemLangVerdictTimeMemory
4634:15:421345Lg++0xOKN/A
4623:45:411001Lg++0xWrong answer12
4613:40:361000Lg++0xWrong answer12
4602:24:412392Hg++0xOKN/A
4592:06:082180Hg++0xMemory limit exceeded1
4581:28:121720Ag++0xOKN/A
4570:47:35981Bg++0xOKN/A
4560:46:41980Bg++0xCompilation errorN/A
4550:37:241957Ig++0xOKN/A
4540:24:241229Fg++0xOKN/A
4530:09:29499Dg++0xOKN/A

比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006275

start at 18:15

流水账

总结

题解

A. Album of Numbers [sfiction]

$ans=\sum{(a_i-a_{i-1})/\prod_{j=1}^{i-1}{(b_j+1)}}$，其中ai是从小到大排序的数字，bi是其出现次数。另外要除去空集。注意到分母增长很快，因此每次只需暴力计算前50项。O(nlogn+50q)。

比赛时的做法是用线段树维护结果，用对数形式保存分母，过大时当成inf。

B. Well Off [sfiction]

将每个未知量的正负视为点，对每种情况连边判环。O(n+m)。

C. Accurate Shots (8M ML!) [sfiction]

考虑折半搜索。由于空间限制，不能存下所有的数。可以枚举高位部分模为x的所有值，统计最少修改、数量和最小值。然后枚举低位部分模为m-x的所有值，求出相应量组合即可。O(n0.5)，空间为O(1)。

本题折半的特殊之处在于两部分各自划分为数个集合，两侧集合一一对应。而且最优解的构成是分别从两个集合中取出最优解合并。限制很多。

G. Board Game

对颜色分治；计算两边颜色答案时，可以通过先将一边取负，然后求两边凸包的Minkowski和来找最大值。

H. Scouts [JTJL, Akalm]

写出n3的dp表达式后，可以发现在某个位置之后一定取左边（右边同理）。于是可以把结果算出来后拿数据结构维护区间最小值。

赛后仔细想想发现是可以用树状数组维护的……

I. Insects [Akalm]

最大权闭合子图。

J. Cave [Akalm]

不难想到用f[st][i]表示当前走过的集合为st，位于i，还需多久找到物品的期望，分两种（直接走、重新随机选点）情况转移。但第二种转移:

$E_st = t + \frac{1}{n}(\sum_{i \notin st}f[st | 1 << i][i] + \sum_{i \in st}f[st][i])$
是有环的。记$f'[st][i]$为仅做第一种转移后的结果，显然有$f[st][t] = min(f'[st][t], E_st)$
代入得$E_st = t + \frac{1}{n}(\sum_{i \notin st}f[st | 1 << i][i] + \sum_{i \in st}min(f'[st][i], E_st)$
而$f'[st][i]$的计算不依赖于$E_st$，于是可以求出$f'[st][i]$，排序后枚举$E_st$所处的区间来破掉min()即可进行转移。

K. Blocks [JTJL, sfiction]

根据最小块的放置位置可以得到递推式f(n,p,l)=f(n-1,p,l)*(n-1)+f(n-1,p-1,l)+f(n-1,p,l-1)。暴力做O(npl)。

根据递推式可以直接得出固定n的生成函数$\prod_{i=0}^{n-1}{(x+y+i)}$，将$x+y$视为整体展开，可以$O(n(p+l))$计算确定x和y总次数的项的系数，然后再乘上$\binom{p-1}{p+l-2}$。对系数的直观的解释，可以考虑将两个相邻可见块中间的部分视为一段，例如21534视为[2,1],[5],[3,4]，容易发现两侧段的交换是合法的。

L. Postman [Akalm]

试着写出确定顺序后的树dp表达式，就可以发现转移并不依赖于子树访问顺序，于是可以做换根树dp。