2016-E24-team1

从 Trac 迁移的文章

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

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||Failed test||
||24||5:16:57||2800||L||g++0x||OK||N/A||
||23||5:03:29||2776||L||g++0x||Wrong answer||29||
||22||4:29:15||2507||J||g++0x||Wrong answer||5||
||21||3:10:37||3631||H||g++0x||OK||N/A||
||20||2:02:57||3528||H||g++0x||Wrong answer||5||
||19||1:35:25||1005||K||g++0x||OK||N/A||
||18||1:30:32||1001||K||g++0x||Run-time error||14||
||17||1:12:42||1151||C||g++0x||OK||N/A||
||16||0:46:08||503||F||g++0x||OK||N/A||
||15||0:26:59||1116||A||g++0x||OK||N/A||

比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010358

start at 19:00

== 流水账 ==

== 总结 ==

== 题解 ==

A略去不表。
=== B. Bipartite Blanket [Akalm] ===
本题有一个重要结论。设S是某个仅包含左侧点的点集，T是仅包含右侧点的点集；如果S和T都是某个匹配的子集，那么他们的并也是某个匹配的子集。

证明：记X是覆盖S的匹配，Y是覆盖T的匹配。对于边 (u, v) \in X，连一条u到v的有向边；对于 (u, v) \in Y，连一条v到u的有向边，于是现在构造出一个出度、入度都为0或者1的图，这张图里只有简单路径或者长度为偶数的简单环，然后选中环或路径中顺序为奇数的边（长度为奇数的路径中最后条边不选，最后一个点出度为0，本身不属于S或T）。将选择的边映射回原图，就构成了一个覆盖S和T的匹配。

利用这个结论，分别计算两边点集的合法性和权重，再two-pointers算一下答案即可。计算合法性可以使用Hall定理。

=== C. Convex Contour [JTJL] ===

特判全是三角形的情况，否则，如果对于三角形在两侧的情况，找到两边第一个非三角形的图案连接即可。

=== D. Dancing Disks [sfiction] ===

考虑n*m矩阵所能处理的乱序序列长度下界。显然f(1,1)=1，f(1,2)=f(2,1)=2。对于更大的情形，考虑将整个序列按照值的大小分为，每个连续段放置到一个可达格子中，即可将(n,m)拆分为nm-1个子问题，而且这些子问题间互不干扰。因此有f(n,m)=\sum_{i=1..n,j=1..m}[i<n \cup j<m]f(i,j)。据此递归构造即可。O((n+m)S)（S为初始序列长度）。

=== E. Easy Equation [Akalm] ===
考虑当前已有解 (a, b, c)，固定b, c，利用方程的性质可以迅速找到另外一组解 (kc + kb - a, b, c)，于是可以枚举一些简单解（例如(0, 1, k)）作为起点不断bfs新的解。 

=== F. Free Figurines [sfiction] ===

将所有套娃按由内到外的顺序视为链。注意到一条边当且仅当包含其的前缀不变时才能保留。因此枚举变换前后都为链首的点，计算最长公共前缀，除此之外的部分都需断开。O(n)。

=== H. Hangar Hurdles [JTJL] ===

预处理以每个点为中心的最大正方形，然后把格子间的边从大到小排序之后依次加入并查集建树。询问时在树上查询LCA即可。

=== J. Jazz Journey [sfiction] ===

不同城市对之间相互独立。对于城市对(x,y)，设有R(x,y)<=R(y,x)，则存在三种不同大小关系，对三种大小关系分别贪心即可。O(nlogn)。

另外一种做法：考虑枚举R(x,y)的购买次数，则应当取尽可能靠前的x和尽可能靠后的y以减小对R(y,x)的影响。可以二分计算出R(x,y)最大张数和R(y,x)最大张数，枚举R(x,y)数量即可快速计算最优解。O(nlogn)。

=== K. Key Knocking [Akalm] ===
设原串为A，B[i] = A[i] xor A[i+1]，答案实际为B[i]之和+1。考虑通过修改使得每三个B[i]至少有两个为1，分类讨论一下四种情况即可。

=== L. Lost Logic [JTJL] ===

显然本质不同的变量只有八种。对于同种变量可以相互推出。所有互补的变量其实也可以相互推出，所以只剩下了000，001，010，100四种。000可以通过!x->x来得到。剩下三种在只有两种的时候可以轻松根据样例构造，剩下三种同时出现的时候可以证明无解。

Run ID	Time	Size	Problem	Language	Result	Failed test
24	5:16:57	2800	L	g++0x	OK	N/A
23	5:03:29	2776	L	g++0x	Wrong answer	29
22	4:29:15	2507	J	g++0x	Wrong answer	5
21	3:10:37	3631	H	g++0x	OK	N/A
20	2:02:57	3528	H	g++0x	Wrong answer	5
19	1:35:25	1005	K	g++0x	OK	N/A
18	1:30:32	1001	K	g++0x	Run-time error	14
17	1:12:42	1151	C	g++0x	OK	N/A
16	0:46:08	503	F	g++0x	OK	N/A
15	0:26:59	1116	A	g++0x	OK	N/A

比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010358

start at 19:00

流水账

总结

题解

A略去不表。

B. Bipartite Blanket [Akalm]

本题有一个重要结论。设S是某个仅包含左侧点的点集，T是仅包含右侧点的点集；如果S和T都是某个匹配的子集，那么他们的并也是某个匹配的子集。

证明：记X是覆盖S的匹配，Y是覆盖T的匹配。对于边 (u, v) \in X，连一条u到v的有向边；对于 (u, v) \in Y，连一条v到u的有向边，于是现在构造出一个出度、入度都为0或者1的图，这张图里只有简单路径或者长度为偶数的简单环，然后选中环或路径中顺序为奇数的边（长度为奇数的路径中最后条边不选，最后一个点出度为0，本身不属于S或T）。将选择的边映射回原图，就构成了一个覆盖S和T的匹配。

利用这个结论，分别计算两边点集的合法性和权重，再two-pointers算一下答案即可。计算合法性可以使用Hall定理。

C. Convex Contour [JTJL]

特判全是三角形的情况，否则，如果对于三角形在两侧的情况，找到两边第一个非三角形的图案连接即可。

D. Dancing Disks [sfiction]

考虑n*m矩阵所能处理的乱序序列长度下界。显然f(1,1)=1，f(1,2)=f(2,1)=2。对于更大的情形，考虑将整个序列按照值的大小分为，每个连续段放置到一个可达格子中，即可将(n,m)拆分为nm-1个子问题，而且这些子问题间互不干扰。因此有f(n,m)=\sum_{i=1..n,j=1..m}[i

E. Easy Equation [Akalm]

考虑当前已有解 (a, b, c)，固定b, c，利用方程的性质可以迅速找到另外一组解 (kc + kb - a, b, c)，于是可以枚举一些简单解（例如(0, 1, k)）作为起点不断bfs新的解。

F. Free Figurines [sfiction]

将所有套娃按由内到外的顺序视为链。注意到一条边当且仅当包含其的前缀不变时才能保留。因此枚举变换前后都为链首的点，计算最长公共前缀，除此之外的部分都需断开。O(n)。

H. Hangar Hurdles [JTJL]

预处理以每个点为中心的最大正方形，然后把格子间的边从大到小排序之后依次加入并查集建树。询问时在树上查询LCA即可。

J. Jazz Journey [sfiction]

不同城市对之间相互独立。对于城市对(x,y)，设有R(x,y)<=R(y,x)，则存在三种不同大小关系，对三种大小关系分别贪心即可。O(nlogn)。

另外一种做法：考虑枚举R(x,y)的购买次数，则应当取尽可能靠前的x和尽可能靠后的y以减小对R(y,x)的影响。可以二分计算出R(x,y)最大张数和R(y,x)最大张数，枚举R(x,y)数量即可快速计算最优解。O(nlogn)。

K. Key Knocking [Akalm]

设原串为A，B[i] = A[i] xor A[i+1]，答案实际为B[i]之和+1。考虑通过修改使得每三个B[i]至少有两个为1，分类讨论一下四种情况即可。

L. Lost Logic [JTJL]

显然本质不同的变量只有八种。对于同种变量可以相互推出。所有互补的变量其实也可以相互推出，所以只剩下了000，001，010，100四种。000可以通过!x->x来得到。剩下三种在只有两种的时候可以轻松根据样例构造，剩下三种同时出现的时候可以证明无解。