2016-E14-team1

从 Trac 迁移的文章

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

原文章内容如下：

||User||Problem||Result||Memory||Time||Language||Length||Submit Time||
||Siunaus||K||WA||  ||  ||G++||3024||2016-09-21 23:05:17||
||Siunaus||C||AC||5416||124||G++||1490||2016-09-21 22:42:23||
||Siunaus||C||WA||  ||  ||G++||1467||2016-09-21 22:37:01||
||Siunaus||C||WA||  ||  ||G++||1466||2016-09-21 22:32:07||
||Siunaus||C||TLE|| ||  ||G++||1383||2016-09-21 22:21:15||
||Siunaus||D||AC||138144||1372||G++||2968||2016-09-21 22:04:14||
||Siunaus||L||AC||48044||1388||G++||2009||2016-09-21 21:15:50||
||Siunaus||H||AC||4580||15||G++||1392||2016-09-21 19:53:36||
||Siunaus||E||AC||14104||1825||G++||2038||2016-09-21 19:11:31||
||Siunaus||J||AC||11384||1575||G++||3282||2016-09-21 19:09:41||
||Siunaus||E||TLE|| ||  ||G++||1988||2016-09-21 18:47:30||
||Siunaus||E||TLE|| ||  ||G++||1412||2016-09-21 18:32:54||
||Siunaus||B||AC||1416||249||G++||272||2016-09-21 18:17:51||

start at 18:05:00

比赛链接: http://vjudge.net/contest/133209

== 流水账 ==

== 总结 ==

== 题解 ==

official: http://bestcoder.hdu.edu.cn/blog/2016-multi-university-training-contest-7-solutions-by-sysu/

== 补题 ==

AFGIK

=== A. Ants [Akalm] ===
所有蚂蚁到最后都会变为在两个点之间徘徊。

KD树寻找任意点的最近点，连边，用并查集判断是否在同一连通块内。

=== G. Golden Week [Akalm] ===
树dp。dp[i][j]表示以i为根节点，到i的总费用为j，整个子树的最大收益。实际上j取B_i  才有意义，离散化后直接可以dp。

=== K. Knights [Akalm] ===
概率dp。dp[i][j]表示前i个人有j个最后向右的概率，不难推出O(n^3^)的式子，观察一下加加减减就能得到O(n^2^)的递推式。

User	Problem	Result	Memory	Time	Language	Length	Submit Time
Siunaus	K	WA			G++	3024	2016-09-21 23:05:17
Siunaus	C	AC	5416	124	G++	1490	2016-09-21 22:42:23
Siunaus	C	WA			G++	1467	2016-09-21 22:37:01
Siunaus	C	WA			G++	1466	2016-09-21 22:32:07
Siunaus	C	TLE			G++	1383	2016-09-21 22:21:15
Siunaus	D	AC	138144	1372	G++	2968	2016-09-21 22:04:14
Siunaus	L	AC	48044	1388	G++	2009	2016-09-21 21:15:50
Siunaus	H	AC	4580	15	G++	1392	2016-09-21 19:53:36
Siunaus	E	AC	14104	1825	G++	2038	2016-09-21 19:11:31
Siunaus	J	AC	11384	1575	G++	3282	2016-09-21 19:09:41
Siunaus	E	TLE			G++	1988	2016-09-21 18:47:30
Siunaus	E	TLE			G++	1412	2016-09-21 18:32:54
Siunaus	B	AC	1416	249	G++	272	2016-09-21 18:17:51

start at 18:05:00

比赛链接: http://vjudge.net/contest/133209

流水账

总结

题解

official: http://bestcoder.hdu.edu.cn/blog/2016-multi-university-training-contest-7-solutions-by-sysu/

补题

AFGIK

A. Ants [Akalm]

所有蚂蚁到最后都会变为在两个点之间徘徊。

KD树寻找任意点的最近点，连边，用并查集判断是否在同一连通块内。

G. Golden Week [Akalm]

树dp。dp[i][j]表示以i为根节点，到i的总费用为j，整个子树的最大收益。实际上j取B_i 才有意义，离散化后直接可以dp。

K. Knights [Akalm]

概率dp。dp[i][j]表示前i个人有j个最后向右的概率，不难推出O(n³)的式子，观察一下加加减减就能得到O(n²)的递推式。