2016-E03-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||789||4:46:45||3651||7||g++0x||OK||
||788||4:42:30||3613||7||g++0x||Run-time error||
||787||4:38:56||3576||7||g++0x||Wrong answer||
||786||2:53:36||3144||5||g++0x||OK||
||785||2:46:34||1855||4||g++0x||OK||
||784||2:31:59||2605||5||g++0x||Time-limit exceeded||
||783||2:00:51||1640||3||g++0x||OK||
||782||1:59:16||1638||3||g++0x||Run-time error||
||781||1:57:58||2096||3||g++0x||Wrong answer||
||780||1:47:36||1497||8||g++0x||OK||
||779||0:57:29||752||10||g++0x||OK||
||778||0:26:29||1013||2||g++0x||OK||
||777||0:09:31||803||12||g++0x||OK||
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010272
== 流水账 ==
== 总结 ==
== 题解 ==
B L 略去不表。
=== C. String [Akalm] ===
扩展Kmp求每个点和起点的最长公共前缀，从小到大枚举K暴力判即可。
=== D. Books [Akalm] ===
又是裸FWT.
=== E. Big Bed [JTJL] ===
SPFA预处理。
=== G. The weasel in the hen coop [Akalm] ===
一定要注意到输入中保证同字母的点坐标奇偶性是一样的。[[BR]]
不考虑字母的情况下，只需要对棋盘黑白染色，源向黑点连边，黑点向四边白点连边，白点向汇连边跑最大流即可；对于字母约束，每种字母建一个点用于限制流量。
=== H. Colonization [sfiction] ===
有n(<=2000)个细菌，给出两两之间距离。两群细菌距离定义为所有对细菌距离的算术平均，每轮合并一对，相近时合并任意一对，求一个可能的合并过程。
维护每 群到其他群的距离，并用优先队列维护最小值。每次从中O(n)时间取出最小进行合并。合并后的群可以根据原先两群的信息在O(n)时间内计算出新的距离。之后更新其他群的优先队列。O(n!^2logn)。
=== J. Swimming [JTJL] ===
等角螺线。特判圆和共线即可。
== 补题 ==
AFIK| 789 | 4:46:45 | 3651 | 7 | g++0x | OK |
| 788 | 4:42:30 | 3613 | 7 | g++0x | Run-time error |
| 787 | 4:38:56 | 3576 | 7 | g++0x | Wrong answer |
| 786 | 2:53:36 | 3144 | 5 | g++0x | OK |
| 785 | 2:46:34 | 1855 | 4 | g++0x | OK |
| 784 | 2:31:59 | 2605 | 5 | g++0x | Time-limit exceeded |
| 783 | 2:00:51 | 1640 | 3 | g++0x | OK |
| 782 | 1:59:16 | 1638 | 3 | g++0x | Run-time error |
| 781 | 1:57:58 | 2096 | 3 | g++0x | Wrong answer |
| 780 | 1:47:36 | 1497 | 8 | g++0x | OK |
| 779 | 0:57:29 | 752 | 10 | g++0x | OK |
| 778 | 0:26:29 | 1013 | 2 | g++0x | OK |
| 777 | 0:09:31 | 803 | 12 | g++0x | OK |
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010272
流水账
总结
题解
B L 略去不表。
C. String [Akalm]
扩展Kmp求每个点和起点的最长公共前缀，从小到大枚举K暴力判即可。
D. Books [Akalm]
又是裸FWT.
E. Big Bed [JTJL]
SPFA预处理。
G. The weasel in the hen coop [Akalm]
一定要注意到输入中保证同字母的点坐标奇偶性是一样的。
不考虑字母的情况下，只需要对棋盘黑白染色，源向黑点连边，黑点向四边白点连边，白点向汇连边跑最大流即可；对于字母约束，每种字母建一个点用于限制流量。
H. Colonization [sfiction]
有n(<=2000)个细菌，给出两两之间距离。两群细菌距离定义为所有对细菌距离的算术平均，每轮合并一对，相近时合并任意一对，求一个可能的合并过程。
维护每 群到其他群的距离，并用优先队列维护最小值。每次从中O(n)时间取出最小进行合并。合并后的群可以根据原先两群的信息在O(n)时间内计算出新的距离。之后更新其他群的优先队列。O(n!^2logn)。
J. Swimming [JTJL]
等角螺线。特判圆和共线即可。
补题
AFIK