2016-E40-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ 2017/03/18 14:00-19:00 · Siunaus · Akalm/JTJL/sfiction │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│B [0:30]│ oOOoo1. 2oooo.3o# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│C [0:06]│ 1 oO.2 # 3 │
│D [0:27]│ 1 2 3 oO oOOOOOo.ooo# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│A [0:06]│o2# │
│E [0:34]│ 1 .oOOoOOoOOoooo# 2 3 │
│G [0:18]│ 1 2 .OO3oo!o# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [3:59]│oOooOOooooO.OoooooOoOoOOOOOo.oooOOOoo.o. .oOOoOOoOOoooooooOoo oOOoOooOooooooOOOOOoooooooOOOooOooOOOOOOooOoooo│
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│F [0:52]│ 1 oOOoOo. oOOOOOoooooo!. 2! ! 3!. │
│H [0:15]│ 1 2 3 OOoooO.o. ! │
│I [0:24]│ 1 oooOoo . oOooo2o. │
│J9[0:27]│ 1 OOOOOO Ooo!o│
│K4[0:00]│ 1 │
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}
||Run ID||When||Size||Problem||Lang||Verdict||Time||
||27||4:56:05||2425||J||g++0x||Wrong answer||4||
||26||4:55:51||2425||J||g++0x||Wrong answer||4||
||25||4:53:03||3385||H||g++0x||Wrong answer||1||
||24||4:47:42||2742||F||g++0x||Time-limit exceeded||13||
||23||4:24:03||2664||F||g++0x||Time-limit exceeded||13||
||22||4:16:12||2646||F||g++0x||Wrong answer||7||
||21||4:07:38||2579||F||g++0x||Wrong answer||7||
||20||2:18:29||2048||E||g++0x||OK||N/A||
||19||1:38:04||930||G||g++0x||OK||N/A||
||18||1:34:14||930||G||g++0x||Wrong answer||6||
||17||1:20:19||2039||D||g++0x||OK||N/A||
||16||0:52:54||924||B||g++0x||OK||N/A||
||15||0:35:26||554||C||g++0x||OK||N/A||
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001498
start at 14:00
== 流水账 ==
== 总结 ==
== 题解 ==
=== C. Distribution Center [JTJL] ===
显然，可以到达同一位置的出发点是一段连续的区间。按照x排序之后，每个arm可以把相邻的两个区间合并，for一遍即可
=== D. Hidden Anagrams [JTJL, sfiction] ===
从大到小枚举k，hash每种字符数即可。
=== F. Three Kingdoms of Bourdelot [sfiction] ===
设祖先关系的集合为S。如果一个文档与S交为空，则将其置为negative即可。于是维护集合S。扩展方式有两种，第一种是新加入边之后，检查有这条边的文档。第二种是新加入边之后，保持S的闭包性质。前者为O(nk^2^)，后者可以做到O(k^3^)。新加入边(u,v)，对所有(x,u)更新(x,v)，对所有(v,y)更新(u,y)，然后对更新所得边迭代。对所有通过(u,v)扩展得到的边(x,y)，都可以通过(u,v)->(x,v)->(x,y)的路径被更新。
=== G. Placing Medals on Binary Tree [sfiction] ===
视为一个二进制数的位置。相应位为0时可以加入。相应位为1时，如果更高位存在0，则可以进位，如果低位全为0，也可以进位，且和变为1。对于位数过多的问题，由于每个位置最多往前进位18位，对每个位置l，取[l-19,l]的并进行离散化即可。对原先互不影响的区域，离散化后至少有一个0分隔。对于高位是否为0的检查可以维护从最高位开始的连续1的长度。O(nlogn(nlogn))。
=== H. Animal Companion in Maze [Akalm] ===
判环分两步：第一步只看双向边，如果成环则inf；然后将前一步形成的森林中的树缩成点，把原先的单向边加回来跑一遍scc找环。
剩下的图就是一个DAG，按逆拓扑序进行dp，遇到一个树缩成的点就在树里做换根树dp。
=== I. Skinny Polygon [JTJL, Akalm] ===
考虑在对角线附近找点，根据 gcd(x,y) 的大小以及 exgcd 出来的一组 ax+by=gcd(x, y) 进行构造┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│ 2017/03/18 14:00-19:00 · Siunaus · Akalm/JTJL/sfiction │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│B [0:30]│ oOOoo1. 2oooo.3o# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│C [0:06]│ 1 oO.2 # 3 ││D [0:27]│ 1 2 3 oO oOOOOOo.ooo# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│A [0:06]│o2# ││E [0:34]│ 1 .oOOoOOoOOoooo# 2 3 ││G [0:18]│ 1 2 .OO3oo!o# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [3:59]│oOooOOooooO.OoooooOoOoOOOOOo.oooOOOoo.o. .oOOoOOoOOoooooooOoo oOOoOooOooooooOOOOOoooooooOOOooOooOOOOOOooOoooo│├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│F [0:52]│ 1 oOOoOo. oOOOOOoooooo!. 2! ! 3!. ││H [0:15]│ 1 2 3 OOoooO.o. ! ││I [0:24]│ 1 oooOoo . oOooo2o. ││J9[0:27]│ 1 OOOOOO Ooo!o││K4[0:00]│ 1 │└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
| Run ID | When | Size | Problem | Lang | Verdict | Time |
| 27 | 4:56:05 | 2425 | J | g++0x | Wrong answer | 4 |
| 26 | 4:55:51 | 2425 | J | g++0x | Wrong answer | 4 |
| 25 | 4:53:03 | 3385 | H | g++0x | Wrong answer | 1 |
| 24 | 4:47:42 | 2742 | F | g++0x | Time-limit exceeded | 13 |
| 23 | 4:24:03 | 2664 | F | g++0x | Time-limit exceeded | 13 |
| 22 | 4:16:12 | 2646 | F | g++0x | Wrong answer | 7 |
| 21 | 4:07:38 | 2579 | F | g++0x | Wrong answer | 7 |
| 20 | 2:18:29 | 2048 | E | g++0x | OK | N/A |
| 19 | 1:38:04 | 930 | G | g++0x | OK | N/A |
| 18 | 1:34:14 | 930 | G | g++0x | Wrong answer | 6 |
| 17 | 1:20:19 | 2039 | D | g++0x | OK | N/A |
| 16 | 0:52:54 | 924 | B | g++0x | OK | N/A |
| 15 | 0:35:26 | 554 | C | g++0x | OK | N/A |
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001498
start at 14:00
流水账
总结
题解
C. Distribution Center [JTJL]
显然，可以到达同一位置的出发点是一段连续的区间。按照x排序之后，每个arm可以把相邻的两个区间合并，for一遍即可
D. Hidden Anagrams [JTJL, sfiction]
从大到小枚举k，hash每种字符数即可。
F. Three Kingdoms of Bourdelot [sfiction]
设祖先关系的集合为S。如果一个文档与S交为空，则将其置为negative即可。于是维护集合S。扩展方式有两种，第一种是新加入边之后，检查有这条边的文档。第二种是新加入边之后，保持S的闭包性质。前者为O(nk2)，后者可以做到O(k3)。新加入边(u,v)，对所有(x,u)更新(x,v)，对所有(v,y)更新(u,y)，然后对更新所得边迭代。对所有通过(u,v)扩展得到的边(x,y)，都可以通过(u,v)->(x,v)->(x,y)的路径被更新。
G. Placing Medals on Binary Tree [sfiction]
视为一个二进制数的位置。相应位为0时可以加入。相应位为1时，如果更高位存在0，则可以进位，如果低位全为0，也可以进位，且和变为1。对于位数过多的问题，由于每个位置最多往前进位18位，对每个位置l，取[l-19,l]的并进行离散化即可。对原先互不影响的区域，离散化后至少有一个0分隔。对于高位是否为0的检查可以维护从最高位开始的连续1的长度。O(nlogn(nlogn))。
H. Animal Companion in Maze [Akalm]
判环分两步：第一步只看双向边，如果成环则inf；然后将前一步形成的森林中的树缩成点，把原先的单向边加回来跑一遍scc找环。
剩下的图就是一个DAG，按逆拓扑序进行dp，遇到一个树缩成的点就在树里做换根树dp。
I. Skinny Polygon [JTJL, Akalm]
考虑在对角线附近找点，根据 gcd(x,y) 的大小以及 exgcd 出来的一组 ax+by=gcd(x, y) 进行构造