2016-E47-team1

从 Trac 迁移的文章

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

原文章内容如下：

{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                     2017/04/11 14:50-19:50 · Siunaus · Akalm/JTJL/sfiction                                      │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│J [0:04]│ 1oo# 2 3                                                                                                               │
│K [0:20]│    1            2oOOOooo.  3o! o#                                                                                      │
│L [0:25]│                 1                      oOOOoooO2o#               3                                                     │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│G [1:04]│                 1                                 2      o.ooO.o.OOOoooooo..oo.oooooooo!          .o!.  . ..ooooo#     │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│B [0:09]│     .O1O#           2          3                                                                                       │
│D [0:12]│            1oOoOo.#                 2              3                                                                   │
│E [0:27]│                   1                                                               2              o.  oO!oo!!!    oo!o# │
│F [0:37]│             1                o  OOoOOoo!           oooOo.2o...o!#                3                                     │
│H [0:17]│        1               oOOOo.oo!2 #                                     3                                              │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [4:01]│  ooOoOOOoo  oOoOooOOOooOOOOoooooOOoOOoooOOOoooOoo. oooOo.ooooOoooOOOoooooo..oo.oooooooooOOoo.oOooo.o.OOoooo.ooooooo.ooo│
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│A [0:00]│                      1                                                                                                2│
│C [0:27]│  1 O!  2oo  .                                                                3         oOOoo.oOoo.                    o│
│I [0:00]│            1                                                                                                      2    │
│M [0:00]│                                                  1                                                                   2 │
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}

||Submission time||ID||Problem||Compiler||Verdict||Time||Memory||Test||
||11 Apr 2017, 14:47:24||4397932||E||GNU c++ 11 4.9||OK||8ms||388.00Kb||-||
||11 Apr 2017, 14:41:05||4397926||E||GNU c++ 11 4.9||WA||8ms||384.00Kb||43||
||11 Apr 2017, 14:35:48||4397915||G||GNU c++ 11 4.9||OK||3ms||512.00Kb||-||
||11 Apr 2017, 14:23:16||4397074||E||GNU c++ 11 4.9||WA||9ms||388.00Kb||42||
||11 Apr 2017, 14:21:31||4397063||E||GNU c++ 11 4.9||WA||2ms||380.00Kb||1||
||11 Apr 2017, 14:19:28||4397049||E||GNU c++ 11 4.9||WA||8ms||388.00Kb||42||
||11 Apr 2017, 14:12:51||4397000||E||GNU c++ 11 4.9||WA||8ms||388.00Kb||43||
||11 Apr 2017, 14:03:26||4396961||G||GNU c++ 11 4.9||WA||3ms||512.00Kb||2||
||11 Apr 2017, 13:31:01||4396819||G||GNU c++ 11 4.9||WA||3ms||508.00Kb||2||
||11 Apr 2017, 12:34:54||4396479||F||GNU c++ 11 4.9||OK||2ms||380.00Kb||-||
||11 Apr 2017, 12:30:00||4396449||F||GNU c++ 11 4.9||WA||2ms||380.00Kb||4||
||11 Apr 2017, 11:56:27||4396264||L||GNU c++ 11 4.9||OK||0.769s||17.99Mb||-||
||11 Apr 2017, 11:31:03||4396101||F||GNU c++ 11 4.9||WA||2ms||380.00Kb||2||
||11 Apr 2017, 11:19:51||4396037||H||GNU c++ 11 4.9||OK||214ms||14.00Mb||-||
||11 Apr 2017, 11:13:16||4395995||K||GNU c++ 11 4.9||OK||14ms||380.00Kb||-||
||11 Apr 2017, 11:12:02||4395984||H||GNU c++ 11 4.9||WA||56ms||7.82Mb||8||
||11 Apr 2017, 11:06:15||4395950||K||GNU c++ 11 4.9||ML||422ms||536.63Mb||2||
||11 Apr 2017, 10:38:20||4395808||D||GNU c++ 11 4.9||OK||0.554s||380.00Kb||-||
||11 Apr 2017, 10:14:24||4395699||B||GNU c++ 11 4.9||OK||76ms||9.32Mb||-||
||11 Apr 2017, 10:04:01||4395647||C||GNU c++ 11 4.9||WA||3ms||380.00Kb||1||
||11 Apr 2017, 10:00:12||4395631||J||GNU c++ 11 4.9||OK||4ms||384.00Kb||-||


比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4368

start at 14:50

== 流水账 ==

== 总结 ==

== 题解 ==

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

}}}

BDJK略去不表。

=== E. E-commerce [JTJL, sfiction] ===

选定一个方案后以无限小区间重复操作。每个方案必定是依赖关系连续的一组股票。容易得出合并后收益率为2\sum{c_i}/{g_root+\sum{g_i}}。枚举链求收益率即可。注意本金购入一只股票所达收益率即达到目标时，答案为0。O(n^2)。

=== F. Floor [JTJL, sfiction] ===

等价于矩形扩大0.5后盖住的正方形中心，题目所求值可以看成一个大矩形减去一个小矩形。小矩形应该是大矩形收缩1.05。O(1)。

=== H. Hacker City [sfiction] ===

求出图中所有环，每条路径走到环再走回来不影响结果，因此可以用环调整代价。高斯消元求环的线性基。O((m+q)logA)。

=== I. Intelligen Vaccuum Cleaner [sfiction] ===

环形走必定比其中某两步走对角线更优。

有多条路径共点时必定不是最优解，因此枚举哪条路径占据公共部分。O(4*2^4^n^2^)。

=== L. Large Table [Akalm] ===

把区间询问改为点询问；离线后按顺序暴力合并相同周期的行即可。

=== M. Matrix Operations [sfiction] ===

每个点需要查询所属的全部矩阵中，比它小的有多少个。如果按照数字从小到大插入，那么只需支持区间加和区间求和。用二维线段树或二维树状数组均可。O(n^2^logn)。
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│                                     2017/04/11 14:50-19:50 · Siunaus · Akalm/JTJL/sfiction                                      │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│J [0:04]│ 1oo# 2 3                                                                                                               ││K [0:20]│    1            2oOOOooo.  3o! o#                                                                                      ││L [0:25]│                 1                      oOOOoooO2o#               3                                                     │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│G [1:04]│                 1                                 2      o.ooO.o.OOOoooooo..oo.oooooooo!          .o!.  . ..ooooo#     │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│B [0:09]│     .O1O#           2          3                                                                                       ││D [0:12]│            1oOoOo.#                 2              3                                                                   ││E [0:27]│                   1                                                               2              o.  oO!oo!!!    oo!o# ││F [0:37]│             1                o  OOoOOoo!           oooOo.2o...o!#                3                                     ││H [0:17]│        1               oOOOo.oo!2 #                                     3                                              │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [4:01]│  ooOoOOOoo  oOoOooOOOooOOOOoooooOOoOOoooOOOoooOoo. oooOo.ooooOoooOOOoooooo..oo.oooooooooOOoo.oOooo.o.OOoooo.ooooooo.ooo│├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│A [0:00]│                      1                                                                                                2││C [0:27]│  1 O!  2oo  .                                                                3         oOOoo.oOoo.                    o││I [0:00]│            1                                                                                                      2    ││M [0:00]│                                                  1                                                                   2 │└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
Submission timeIDProblemCompilerVerdictTimeMemoryTest
11 Apr 2017, 14:47:244397932EGNU c++ 11 4.9OK8ms388.00Kb-
11 Apr 2017, 14:41:054397926EGNU c++ 11 4.9WA8ms384.00Kb43
11 Apr 2017, 14:35:484397915GGNU c++ 11 4.9OK3ms512.00Kb-
11 Apr 2017, 14:23:164397074EGNU c++ 11 4.9WA9ms388.00Kb42
11 Apr 2017, 14:21:314397063EGNU c++ 11 4.9WA2ms380.00Kb1
11 Apr 2017, 14:19:284397049EGNU c++ 11 4.9WA8ms388.00Kb42
11 Apr 2017, 14:12:514397000EGNU c++ 11 4.9WA8ms388.00Kb43
11 Apr 2017, 14:03:264396961GGNU c++ 11 4.9WA3ms512.00Kb2
11 Apr 2017, 13:31:014396819GGNU c++ 11 4.9WA3ms508.00Kb2
11 Apr 2017, 12:34:544396479FGNU c++ 11 4.9OK2ms380.00Kb-
11 Apr 2017, 12:30:004396449FGNU c++ 11 4.9WA2ms380.00Kb4
11 Apr 2017, 11:56:274396264LGNU c++ 11 4.9OK0.769s17.99Mb-
11 Apr 2017, 11:31:034396101FGNU c++ 11 4.9WA2ms380.00Kb2
11 Apr 2017, 11:19:514396037HGNU c++ 11 4.9OK214ms14.00Mb-
11 Apr 2017, 11:13:164395995KGNU c++ 11 4.9OK14ms380.00Kb-
11 Apr 2017, 11:12:024395984HGNU c++ 11 4.9WA56ms7.82Mb8
11 Apr 2017, 11:06:154395950KGNU c++ 11 4.9ML422ms536.63Mb2
11 Apr 2017, 10:38:204395808DGNU c++ 11 4.9OK0.554s380.00Kb-
11 Apr 2017, 10:14:244395699BGNU c++ 11 4.9OK76ms9.32Mb-
11 Apr 2017, 10:04:014395647CGNU c++ 11 4.9WA3ms380.00Kb1
11 Apr 2017, 10:00:124395631JGNU c++ 11 4.9OK4ms384.00Kb-

比赛链接: http://official.contest.yandex.com/mipt2017distant/contest/4368

start at 14:50

流水账

总结

题解

BDJK略去不表。

E. E-commerce [JTJL, sfiction]

选定一个方案后以无限小区间重复操作。每个方案必定是依赖关系连续的一组股票。容易得出合并后收益率为2\sum{c_i}/{g_root+\sum{g_i}}。枚举链求收益率即可。注意本金购入一只股票所达收益率即达到目标时，答案为0。O(n^2)。

F. Floor [JTJL, sfiction]

等价于矩形扩大0.5后盖住的正方形中心，题目所求值可以看成一个大矩形减去一个小矩形。小矩形应该是大矩形收缩1.05。O(1)。

H. Hacker City [sfiction]

求出图中所有环，每条路径走到环再走回来不影响结果，因此可以用环调整代价。高斯消元求环的线性基。O((m+q)logA)。

I. Intelligen Vaccuum Cleaner [sfiction]

环形走必定比其中某两步走对角线更优。

有多条路径共点时必定不是最优解，因此枚举哪条路径占据公共部分。O(4*24n2)。

L. Large Table [Akalm]

把区间询问改为点询问；离线后按顺序暴力合并相同周期的行即可。

M. Matrix Operations [sfiction]

每个点需要查询所属的全部矩阵中，比它小的有多少个。如果按照数字从小到大插入，那么只需支持区间加和区间求和。用二维线段树或二维树状数组均可。O(n2logn)。