2016-E43-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ 2017/03/28 17:41-22:41 · Siunaus · Akalm/JTJL/sfiction │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│D [0:12]│ 1 oOOoo.#2 3 │
│L [0:08]│ 1 2!oO# 3 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│B [0:22]│ 1 .OO2OoO3o# │
│E [0:09]│ooO# 2 3 │
│F [0:04]│ 1 .O# 3 │
│H [0:12]│ 1 .OOOo# 2 3 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│A [0:01]│2# │
│G [0:49]│ 1 2 3 .OOOOoooooooo!...ooo! o! ! o# │
│I [0:11]│ 1 2 3OOo# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [4:07]│OOOo.Oo o.oOoOOOooOOooOOoOoOOooOOoo.oOoooOoooOo..o.ooooOo. oOOOOooooooooo...ooooOOOoooOooooOOOoooooOoooooooOo.OOOoo│
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│C [1:16]│ 1 2 oOOOo..OooooOOOoooooOoooooo3Oo.OOOoo│
│J0[0:44]│ oOoooOoooOo..o!ooooO!. o │
│K [0:00]│ 1 2 3 │
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}
||#||When||Problem||Lang||Verdict||Time||Memory||
||119||4:13:08||2543||G||g++0x||OK||N/A||
||118||3:56:00||2608||G||g++0x||Wrong answer||32||
||117||3:47:03||2608||G||g++0x||Time-limit exceeded||15||
||116||3:32:06||2396||G||g++0x||Wrong answer||2||
||115||3:30:11||2393||G||g++0x||Wrong answer||2||
||114||3:14:43||2265||G||g++0x||Wrong answer||2||
||113||2:27:21||1621||J||g++0x||Wrong answer||2||
||112||2:11:22||1501||J||g++0x||Time-limit exceeded||2||
||111||1:36:18||1762||D||g++0x||OK||N/A||
||110||1:21:21||1852||B||g++0x||OK||N/A||
||109||0:58:08||960||I||g++0x||OK||N/A||
||108||0:48:25||991||H||g++0x||OK||N/A||
||107||0:36:33||583||L||g++0x||OK||N/A||
||106||0:29:41||245||L||g++0x||Wrong answer||58||
||105||0:15:55||333||F||g++0x||OK||N/A||
||104||0:09:58||1288||E||g++0x||OK||N/A||
||103||0:03:47||56||A||python||OK||N/A||
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010354
start at 17:42
== 流水账 ==
== 总结 ==
== 题解 ==
=== D. Skyscrapers [Akalm] ===
维护一下被摧毁的位置以及a[i]+i与a[i]-i的区间最小值即可。
=== K. GCD on the segments [sfiction, Akalm] ===
枚举左端点l，分别求出右端点r落在哪些区间 [r1,r2] 里 gcd[l..r] 是相同的，记为三元组(l, r1, r2)； 把 gcd 值相同的三元组放在一起排好序后，不难想到一个简单的dp，可以用线段树维护这个dp的区间转移。需要注意线段树重置标记的处理……┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│ 2017/03/28 17:41-22:41 · Siunaus · Akalm/JTJL/sfiction │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│D [0:12]│ 1 oOOoo.#2 3 ││L [0:08]│ 1 2!oO# 3 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│B [0:22]│ 1 .OO2OoO3o# ││E [0:09]│ooO# 2 3 ││F [0:04]│ 1 .O# 3 ││H [0:12]│ 1 .OOOo# 2 3 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│A [0:01]│2# ││G [0:49]│ 1 2 3 .OOOOoooooooo!...ooo! o! ! o# ││I [0:11]│ 1 2 3OOo# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [4:07]│OOOo.Oo o.oOoOOOooOOooOOoOoOOooOOoo.oOoooOoooOo..o.ooooOo. oOOOOooooooooo...ooooOOOoooOooooOOOoooooOoooooooOo.OOOoo│├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│C [1:16]│ 1 2 oOOOo..OooooOOOoooooOoooooo3Oo.OOOoo││J0[0:44]│ oOoooOoooOo..o!ooooO!. o ││K [0:00]│ 1 2 3 │└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
| # | When | Problem | Lang | Verdict | Time | Memory |
| 119 | 4:13:08 | 2543 | G | g++0x | OK | N/A |
| 118 | 3:56:00 | 2608 | G | g++0x | Wrong answer | 32 |
| 117 | 3:47:03 | 2608 | G | g++0x | Time-limit exceeded | 15 |
| 116 | 3:32:06 | 2396 | G | g++0x | Wrong answer | 2 |
| 115 | 3:30:11 | 2393 | G | g++0x | Wrong answer | 2 |
| 114 | 3:14:43 | 2265 | G | g++0x | Wrong answer | 2 |
| 113 | 2:27:21 | 1621 | J | g++0x | Wrong answer | 2 |
| 112 | 2:11:22 | 1501 | J | g++0x | Time-limit exceeded | 2 |
| 111 | 1:36:18 | 1762 | D | g++0x | OK | N/A |
| 110 | 1:21:21 | 1852 | B | g++0x | OK | N/A |
| 109 | 0:58:08 | 960 | I | g++0x | OK | N/A |
| 108 | 0:48:25 | 991 | H | g++0x | OK | N/A |
| 107 | 0:36:33 | 583 | L | g++0x | OK | N/A |
| 106 | 0:29:41 | 245 | L | g++0x | Wrong answer | 58 |
| 105 | 0:15:55 | 333 | F | g++0x | OK | N/A |
| 104 | 0:09:58 | 1288 | E | g++0x | OK | N/A |
| 103 | 0:03:47 | 56 | A | python | OK | N/A |
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010354
start at 17:42
流水账
总结
题解
D. Skyscrapers [Akalm]
维护一下被摧毁的位置以及a[i]+i与a[i]-i的区间最小值即可。
K. GCD on the segments [sfiction, Akalm]
枚举左端点l，分别求出右端点r落在哪些区间 [r1,r2] 里 gcd[l..r] 是相同的，记为三元组(l, r1, r2)； 把 gcd 值相同的三元组放在一起排好序后，不难想到一个简单的dp，可以用线段树维护这个dp的区间转移。需要注意线段树重置标记的处理……