2016-E29-team1

从 Trac 迁移的文章

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

原文章内容如下：

||#||When||Problem||Lang||Verdict||Time||Memory||
||24285833||2017-01-31 12:19:55||K - Kiwi Trees||GNU C++11||Accepted||78 ms||2100 KB||
||24285585||2017-01-31 12:08:49||D - Driving in Optimistan||GNU C++11||Accepted||46 ms||11000 KB||
||24285387||2017-01-31 12:00:21||D - Driving in Optimistan||GNU C++11||Wrong answer on test 1||15 ms||10200 KB||
||24284005||2017-01-31 10:35:49||J - Jupiter Orbiter||GNU C++11||Accepted||15 ms||2200 KB||
||24283841||2017-01-31 10:24:13||B - British Menu||GNU C++11||Accepted||857 ms||46200 KB||
||24283581||2017-01-31 10:06:09||B - British Menu||GNU C++11||Wrong answer on test 1||15 ms||28600 KB||
||24283284||2017-01-31 09:44:00||J - Jupiter Orbiter||GNU C++11||Wrong answer on test 30||15 ms||25500 KB||
||24283145||2017-01-31 09:32:58||A - Arranging Hat||GNU C++11||Accepted||155 ms||58700 KB||
||24283051||2017-01-31 09:24:45||A - Arranging Hat||GNU C++11||Accepted||140 ms||58700 KB||
||24282725||2017-01-31 08:56:46||I - Iron and Coal||GNU C++11||Accepted||265 ms||30300 KB||
||24282605||2017-01-31 08:44:41||F - Free Weights||GNU C++11||Accepted||1560 ms||49300 KB||
||24282459||2017-01-31 08:32:59||C - Careful Ascent||GNU C++11||Accepted||15 ms||1800 KB||
||24282391||2017-01-31 08:26:57||H - Hamiltonian Hypercube||GNU C++11||Accepted||15 ms||2000 KB||
||24282252||2017-01-31 08:16:46||E - Exam Redistribution||GNU C++11||Accepted||31 ms||17700 KB||

比赛链接: http://codeforces.com/gym/101170

start at 13:01

== 流水账 ==

== 总结 ==

== 题解 ==

CEFH 略去不表。

=== A. Arranging Hat [sfiction] ===

解的最高位要有序，每个连续段对应的m-1位数也要有序。容易想到从最低位向上处理，由于共有10种数字，因此用f[k][i][j][d]表示[i,j]内数的最低k位有序，且j的第k位<=d的最小代价，转移时只需用到状态f[k-1][][][9]，复杂度为O(n)。O(10mn^3^)。


=== B. British Menu [Akalm] ===
SCC缩点后按逆拓扑序DP，同一个SCC内暴力枚举，不同的调用DP结果

=== D. Driving in Optimistan [sfiction] ===

首先要根据给出的距离建树。之后的部分只是稍微复杂一些的树形DP。因为链长被所给距离确定，因此从链入手建树。build(u,v,lst)表示当前处理以u为根的子树，子树中元素为u,v,lst。对于lst中的点w，根据所处子树根在链u-v上的位置（通过a[u][v],a[u][w],a[v][w]计算）进行分类，然后递归处理。注意距离和会爆ll，需要用double。O(n^2^logn)。

=== I. Iron and Coal [Akalm] ===
两次BFS，然后枚举中（分叉）点

=== J. Jupiter Orbiter [JTJL] ===

贪心。首先传感器是无效的，直接合并为队列的数据即可。在每次传送窗口，观察每个队列的状态。如果数据溢出，则寻找最早的还没使用完的窗口k和不晚于k收集到的该队列的数据，依次传送，直到队列恰好能装下为止。最后的时候强制再收集Ci的虚数据用来清空队列即可。一旦中间出现不合法的情况即为无解。直接暴力处理的复杂度是O(n^3^q)，足够通过，还有充分的优化余地。

另解：网络流(自然的构图即可。sf补充：首先将传感器合并为queue的每轮数据量a[i][j]。用最大流解决。表示阶段i的队列j的点要拆分成a[i][j]和b[i][j]。源点到a[i][j]连容量为a[i][j]的边。d[i]到汇连容量为d[i]的边。a[i][j]到d[i]连容量无穷大的边，表示数据传送。a[i][j]到b[i][j]连容量为c[j]的边，限制队列容量。b[i][j]到a[i+1][j]连容量无穷大的边，表示剩余数据。满流即表示可行。)

=== K. Kiwi Trees [JTJL, Akalm] ===

根据题目给定的角度限制，任何一个小于180度的角以及相邻两条边构成的三角形都能放下一棵树。所以我们枚举所有顶点，找出所有这样卡在角落的圆，并且和所有边判交（~~存在三角形内被异物插入特殊情况~~）。最后对所有的圆两两~~圆交~~一遍看是否存在一对合法解即可。O(n^2^)~~感受出来是对的，不知道如何严格证明~~
#WhenProblemLangVerdictTimeMemory
242858332017-01-31 12:19:55K - Kiwi TreesGNU C++11Accepted78 ms2100 KB
242855852017-01-31 12:08:49D - Driving in OptimistanGNU C++11Accepted46 ms11000 KB
242853872017-01-31 12:00:21D - Driving in OptimistanGNU C++11Wrong answer on test 115 ms10200 KB
242840052017-01-31 10:35:49J - Jupiter OrbiterGNU C++11Accepted15 ms2200 KB
242838412017-01-31 10:24:13B - British MenuGNU C++11Accepted857 ms46200 KB
242835812017-01-31 10:06:09B - British MenuGNU C++11Wrong answer on test 115 ms28600 KB
242832842017-01-31 09:44:00J - Jupiter OrbiterGNU C++11Wrong answer on test 3015 ms25500 KB
242831452017-01-31 09:32:58A - Arranging HatGNU C++11Accepted155 ms58700 KB
242830512017-01-31 09:24:45A - Arranging HatGNU C++11Accepted140 ms58700 KB
242827252017-01-31 08:56:46I - Iron and CoalGNU C++11Accepted265 ms30300 KB
242826052017-01-31 08:44:41F - Free WeightsGNU C++11Accepted1560 ms49300 KB
242824592017-01-31 08:32:59C - Careful AscentGNU C++11Accepted15 ms1800 KB
242823912017-01-31 08:26:57H - Hamiltonian HypercubeGNU C++11Accepted15 ms2000 KB
242822522017-01-31 08:16:46E - Exam RedistributionGNU C++11Accepted31 ms17700 KB

比赛链接: http://codeforces.com/gym/101170

start at 13:01

流水账

总结

题解

CEFH 略去不表。

A. Arranging Hat [sfiction]

解的最高位要有序，每个连续段对应的m-1位数也要有序。容易想到从最低位向上处理，由于共有10种数字，因此用f[k][i][j][d]表示[i,j]内数的最低k位有序，且j的第k位<=d的最小代价，转移时只需用到状态f[k-1][][][9]，复杂度为O(n)。O(10mn3)。

B. British Menu [Akalm]

SCC缩点后按逆拓扑序DP，同一个SCC内暴力枚举，不同的调用DP结果

D. Driving in Optimistan [sfiction]

首先要根据给出的距离建树。之后的部分只是稍微复杂一些的树形DP。因为链长被所给距离确定，因此从链入手建树。build(u,v,lst)表示当前处理以u为根的子树，子树中元素为u,v,lst。对于lst中的点w，根据所处子树根在链u-v上的位置（通过a[u][v],a[u][w],a[v][w]计算）进行分类，然后递归处理。注意距离和会爆ll，需要用double。O(n2logn)。

I. Iron and Coal [Akalm]

两次BFS，然后枚举中（分叉）点

J. Jupiter Orbiter [JTJL]

贪心。首先传感器是无效的，直接合并为队列的数据即可。在每次传送窗口，观察每个队列的状态。如果数据溢出，则寻找最早的还没使用完的窗口k和不晚于k收集到的该队列的数据，依次传送，直到队列恰好能装下为止。最后的时候强制再收集Ci的虚数据用来清空队列即可。一旦中间出现不合法的情况即为无解。直接暴力处理的复杂度是O(n3q)，足够通过，还有充分的优化余地。

另解：网络流(自然的构图即可。sf补充：首先将传感器合并为queue的每轮数据量a[i][j]。用最大流解决。表示阶段i的队列j的点要拆分成a[i][j]和b[i][j]。源点到a[i][j]连容量为a[i][j]的边。d[i]到汇连容量为d[i]的边。a[i][j]到d[i]连容量无穷大的边，表示数据传送。a[i][j]到b[i][j]连容量为c[j]的边，限制队列容量。b[i][j]到a[i+1][j]连容量无穷大的边，表示剩余数据。满流即表示可行。)

K. Kiwi Trees [JTJL, Akalm]

根据题目给定的角度限制，任何一个小于180度的角以及相邻两条边构成的三角形都能放下一棵树。所以我们枚举所有顶点，找出所有这样卡在角落的圆，并且和所有边判交（存在三角形内被异物插入特殊情况）。最后对所有的圆两两圆交一遍看是否存在一对合法解即可。O(n2)感受出来是对的，不知道如何严格证明