2016-E45-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ 2017/04/02 16:00-21:00 · Siunaus · Akalm/JTJL/sfiction │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│I [0:36]│ 1 2 .o.o3OooOOOooO!..o# │
│L [0:35]│ 1 o2Oo .3 oOOOOOo! o! oo!o# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│B [0:14]│ 1 2 oOOOOo 3 │
│F [0:19]│ 1 .OOo! .OO2# 3 │
│H [0:29]│ 1 oOOOOo2ooo! 3 ..o# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│A [0:13]│ o1OOo# 3 │
│C [0:42]│ 1 2 oOOOooo .OOOoO3oooo!│
│D [0:12]│ 1 2 3 oOo.Oo# │
│E [0:26]│ 1 2 3 oOOOooO!ooo ! . !! ! ! │
│J [0:10]│ 1 2 3 oOo!o# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [3:56]│ oOOOooOOooOOOOOOOOo.OooOOOOOooOOOOooooooOOoOooo...o. . .. .. oOOOooOooooo.oOOooOOOooOo..o. oOOOooOOOOOoOOOoOOoooo.│
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│G7[0:00]│ 1 . │
│K [0:00]│ 1 2 3 │
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}
||Submission time||ID||Problem||Compiler||Verdict||Time||Memory||Test||
||2 Apr 2017, 15:58:56||4346719||C||GNU c++ 11 4.9||WA||44ms||396.00Kb||4||
||2 Apr 2017, 15:51:12||4346572||E||GNU c++ 11 4.9||WA||2ms||380.00Kb||7||
||2 Apr 2017, 15:37:10||4346407||E||GNU c++ 11 4.9||WA||2ms||380.00Kb||22||
||2 Apr 2017, 15:32:47||4346365||E||GNU c++ 11 4.9||WA||2ms||380.00Kb||28||
||2 Apr 2017, 15:28:54||4346320||E||GNU c++ 11 4.9||WA||2ms||380.00Kb||19||
||2 Apr 2017, 14:55:27||4345926||I||GNU c++ 11 4.9||OK||2.311s||18.28Mb||-||
||2 Apr 2017, 14:46:52||4345808||I||GNU c++ 11 4.9||WA||5ms||2.00Mb||3||
||2 Apr 2017, 14:20:05||4345447||E||GNU c++ 11 4.9||WA||2ms||380.00Kb||7||
||2 Apr 2017, 14:03:55||4345257||E||GNU c++ 11 4.9||WA||2ms||380.00Kb||7||
||2 Apr 2017, 13:11:12||4344689||H||GNU c++ 11 4.9||OK||5ms||508.00Kb||-||
||2 Apr 2017, 13:01:14||4344595||L||GNU c++ 11 4.9||OK||0.759s||168.73Mb||-||
||2 Apr 2017, 12:57:00||4344553||L||GNU c++ 11 4.9||ML||1.159s||278.39Mb||30||
||2 Apr 2017, 12:55:43||4344540||J||GNU c++ 11 4.9||OK||328ms||584.00Kb||-||
||2 Apr 2017, 12:50:43||4344490||J||GNU c++ 11 4.9||WA||2ms||380.00Kb||5||
||2 Apr 2017, 12:44:16||4344406||L||GNU c++ 11 4.9||ML||0.805s||265.53Mb||28||
||2 Apr 2017, 12:41:33||4344384||H||GNU c++ 11 4.9||WA||3ms||380.00Kb||11||
||2 Apr 2017, 12:16:46||4344124||L||GNU c++ 11 4.9||ML||1.103s||280.21Mb||28||
||2 Apr 2017, 11:59:13||4343929||D||GNU c++ 11 4.9||OK||190ms||56.58Mb||-||
||2 Apr 2017, 11:44:00||4343760||F||GNU c++ 11 4.9||OK||481ms||380.00Kb||-||
||2 Apr 2017, 11:25:39||4343563||F||GNU c++ 11 4.9||WA||2ms||380.00Kb||2||
||2 Apr 2017, 11:17:33||4343491||A||GNU c++ 11 4.9||OK||2ms||380.00Kb||-||
Start at 16:00(UTC+8)
比赛链接: http://official.contest.yandex.ru/opencupXVII/contest/4296/enter
opentrains: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=10374 Div.2: 10384
== 流水账 ==
== 总结 ==
== 题解 ==
=== A. Arithmetical Derivative [sfiction] ===
n'=n*\sum{1/p}，p包括重复质因数。因此要求n'/n为整数的数只需以p^p^作为约数。数量不多，可以全部求出。
=== C. New Street [sfiction] ===
将有限制的段取出，用多项式幂计算生成函数，然后再求所有生成函数的积。处理询问时枚举分配到自由位置的楼层数即可。询问部分为O(Am)。每个1类询问最多只会新增一个限制段，另外会覆盖已有的限制段，最多导致另外两个新段的产生。另外段数最多增加2。因此可以复用未修改段的计算结果。这样每次就只需要做最多60+3log(n/3)次ntt。合并D-C相同的段还可以进一步优化。因此生成函数计算部分复杂度为O(5*30^2^AlogA)。
=== D. Clones and Treasures [Akalm, sfiction] ===
设H为1，K为-1求出前缀和s[i]。如果出发点i是gold，那么行走极限是i右侧第一个小于s[i]的值。如果出发点是药水会有所不同，为了统一处理可以在所有H前加入一个A，表示空地。右侧首个小于s[i]的值可以根据s[i]的大小排序，用set或者双端链表维护。O(nlogn)。
=== E. Space Tourists [sfiction] ===
首先dd形式的数是必选的，其次n>k时必然有重复数位，因此答案为k。对于剩下的情况，首先考虑令边成对出现，这样可以将序列转化为集合。可以视为有一个k个点的无向图，要求加尽可能少的边，使得每个n元子集都包含至少一条边。可以将k分为n-1组，每组为完全图。
=== J. Terminal [sfiction] ===
枚举第一艘离开的时间，应该尽量让更多人上去。按照每个group到齐时间的先后顺序做背包。O(mk)。手写bitset可以优化到O(mk/bitset)。┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│ 2017/04/02 16:00-21:00 · Siunaus · Akalm/JTJL/sfiction │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│I [0:36]│ 1 2 .o.o3OooOOOooO!..o# ││L [0:35]│ 1 o2Oo .3 oOOOOOo! o! oo!o# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│B [0:14]│ 1 2 oOOOOo 3 ││F [0:19]│ 1 .OOo! .OO2# 3 ││H [0:29]│ 1 oOOOOo2ooo! 3 ..o# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│A [0:13]│ o1OOo# 3 ││C [0:42]│ 1 2 oOOOooo .OOOoO3oooo!││D [0:12]│ 1 2 3 oOo.Oo# ││E [0:26]│ 1 2 3 oOOOooO!ooo ! . !! ! ! ││J [0:10]│ 1 2 3 oOo!o# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [3:56]│ oOOOooOOooOOOOOOOOo.OooOOOOOooOOOOooooooOOoOooo...o. . .. .. oOOOooOooooo.oOOooOOOooOo..o. oOOOooOOOOOoOOOoOOoooo.│├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│G7[0:00]│ 1 . ││K [0:00]│ 1 2 3 │└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
| Submission time | ID | Problem | Compiler | Verdict | Time | Memory | Test |
| 2 Apr 2017, 15:58:56 | 4346719 | C | GNU c++ 11 4.9 | WA | 44ms | 396.00Kb | 4 |
| 2 Apr 2017, 15:51:12 | 4346572 | E | GNU c++ 11 4.9 | WA | 2ms | 380.00Kb | 7 |
| 2 Apr 2017, 15:37:10 | 4346407 | E | GNU c++ 11 4.9 | WA | 2ms | 380.00Kb | 22 |
| 2 Apr 2017, 15:32:47 | 4346365 | E | GNU c++ 11 4.9 | WA | 2ms | 380.00Kb | 28 |
| 2 Apr 2017, 15:28:54 | 4346320 | E | GNU c++ 11 4.9 | WA | 2ms | 380.00Kb | 19 |
| 2 Apr 2017, 14:55:27 | 4345926 | I | GNU c++ 11 4.9 | OK | 2.311s | 18.28Mb | - |
| 2 Apr 2017, 14:46:52 | 4345808 | I | GNU c++ 11 4.9 | WA | 5ms | 2.00Mb | 3 |
| 2 Apr 2017, 14:20:05 | 4345447 | E | GNU c++ 11 4.9 | WA | 2ms | 380.00Kb | 7 |
| 2 Apr 2017, 14:03:55 | 4345257 | E | GNU c++ 11 4.9 | WA | 2ms | 380.00Kb | 7 |
| 2 Apr 2017, 13:11:12 | 4344689 | H | GNU c++ 11 4.9 | OK | 5ms | 508.00Kb | - |
| 2 Apr 2017, 13:01:14 | 4344595 | L | GNU c++ 11 4.9 | OK | 0.759s | 168.73Mb | - |
| 2 Apr 2017, 12:57:00 | 4344553 | L | GNU c++ 11 4.9 | ML | 1.159s | 278.39Mb | 30 |
| 2 Apr 2017, 12:55:43 | 4344540 | J | GNU c++ 11 4.9 | OK | 328ms | 584.00Kb | - |
| 2 Apr 2017, 12:50:43 | 4344490 | J | GNU c++ 11 4.9 | WA | 2ms | 380.00Kb | 5 |
| 2 Apr 2017, 12:44:16 | 4344406 | L | GNU c++ 11 4.9 | ML | 0.805s | 265.53Mb | 28 |
| 2 Apr 2017, 12:41:33 | 4344384 | H | GNU c++ 11 4.9 | WA | 3ms | 380.00Kb | 11 |
| 2 Apr 2017, 12:16:46 | 4344124 | L | GNU c++ 11 4.9 | ML | 1.103s | 280.21Mb | 28 |
| 2 Apr 2017, 11:59:13 | 4343929 | D | GNU c++ 11 4.9 | OK | 190ms | 56.58Mb | - |
| 2 Apr 2017, 11:44:00 | 4343760 | F | GNU c++ 11 4.9 | OK | 481ms | 380.00Kb | - |
| 2 Apr 2017, 11:25:39 | 4343563 | F | GNU c++ 11 4.9 | WA | 2ms | 380.00Kb | 2 |
| 2 Apr 2017, 11:17:33 | 4343491 | A | GNU c++ 11 4.9 | OK | 2ms | 380.00Kb | - |
Start at 16:00(UTC+8)
比赛链接: http://official.contest.yandex.ru/opencupXVII/contest/4296/enter
opentrains: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=10374 Div.2: 10384
流水账
总结
题解
A. Arithmetical Derivative [sfiction]
n'=n*\sum{1/p}，p包括重复质因数。因此要求n'/n为整数的数只需以pp作为约数。数量不多，可以全部求出。
C. New Street [sfiction]
将有限制的段取出，用多项式幂计算生成函数，然后再求所有生成函数的积。处理询问时枚举分配到自由位置的楼层数即可。询问部分为O(Am)。每个1类询问最多只会新增一个限制段，另外会覆盖已有的限制段，最多导致另外两个新段的产生。另外段数最多增加2。因此可以复用未修改段的计算结果。这样每次就只需要做最多60+3log(n/3)次ntt。合并D-C相同的段还可以进一步优化。因此生成函数计算部分复杂度为O(5*302AlogA)。
D. Clones and Treasures [Akalm, sfiction]
设H为1，K为-1求出前缀和s[i]。如果出发点i是gold，那么行走极限是i右侧第一个小于s[i]的值。如果出发点是药水会有所不同，为了统一处理可以在所有H前加入一个A，表示空地。右侧首个小于s[i]的值可以根据s[i]的大小排序，用set或者双端链表维护。O(nlogn)。
E. Space Tourists [sfiction]
首先dd形式的数是必选的，其次n>k时必然有重复数位，因此答案为k。对于剩下的情况，首先考虑令边成对出现，这样可以将序列转化为集合。可以视为有一个k个点的无向图，要求加尽可能少的边，使得每个n元子集都包含至少一条边。可以将k分为n-1组，每组为完全图。
J. Terminal [sfiction]
枚举第一艘离开的时间，应该尽量让更多人上去。按照每个group到齐时间的先后顺序做背包。O(mk)。手写bitset可以优化到O(mk/bitset)。