2016-E27-team1

从 Trac 迁移的文章

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

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||Failed test||
||197||4:59:03||3059||H||g++0x||Wrong answer||6||
||196||4:56:56||3066||H||g++0x||Wrong answer||6||
||195||4:48:54||3047||H||g++0x||Wrong answer||6||
||194||4:24:24||1938||F||g++0x||Wrong answer||101||
||193||3:22:29||2009||H||g++0x||Time-limit exceeded||6||
||192||3:16:43||1169||C||g++0x||OK||N/A||
||191||2:50:06||2064||I||g++0x||OK||N/A||
||190||1:21:51||1866||B||g++0x||OK||N/A||
||189||0:56:42||776||J||g++0x||OK||N/A||
||188||0:55:49||771||J||g++0x||Presentation error||12||

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

start at 18:15

== 流水账 ==

== 总结 ==

== 题解 ==


=== B. Divide and Conquer [JTJL] ===

度数最大的点一定在团中，因此可以O(m)求出团。

另解：枚举团的大小。假设团的大小为K，则度数大于K-1的点一定在团中，小于K-1的一定不在团中。此时，对于度数为K-1的点，其K-1个邻居一定在团中。对于某一个点A，如果其邻居中存在度数小于K-1的点，则不符合条件。如果他的邻居的度数都大于K-1，则A和其邻居构成了这个团（答案为A），否则，其邻居中度数为K-1的点B，B和B的K-1个邻居一定构成了这个团（答案为B）。

=== C. Spatial Thinking [sfiction] ===

考虑一个n维超立方体的划分，类比2/3维的划分方法，可以首先取一条对角线A-B，再取与A相连的n条边中的一条作为高，得到一个超棱锥，其底面为n-1维超立方体，可以递归划分。O(n!+n^3^m)。

=== H. Beautiful Pairs [JTJL] ===

首先，观察得到所有的pair是三种形式之一：
 1. (1, n) (n >= 1)
 2. (n, n+1) (n >= 1)
 3. f(1, n) = (n, n * n - 1), f(m, n) = (f(m-1, n).second, (f(m-1, n).second ** 2 - 1) / f(m-1, n).first) （n >= 3, m >= 2）

第一种情况和第二种情况都很容易统计。（第二种情况是第三种情况n=2的特例，第一种情况是m=0的情况（发源！），由于其特殊性所以单独统计……）对于第三种情况，我们可以发现，f(m, n)是关于n的m和m+1次多项式，并且在n >= 3是单调递增。由于n >= 3, 所以m是log级别，最大只能到42。我们可以考虑枚举m。

对于较小的m，我们人工构造多项式，解两个不等式求出n的上下界即可。对于较大的m，此时n的范围很有限，直接枚举n即可。在计算过程中需要注意及时约分，或者使用{{{__int128}}}或者DigInteger或者python。在计算高次方根时，由于精度误差需要在计算完后调整。

=== I. Binary Matrices [sfiction] ===

考虑用位运算实现Mulitply()。对AB=C，考虑每次计算C中的一列，那么只需将B中的一列转置并复制到所有行，再与A，最后合并每行的结果。转置、复制、合并分别可以用三步完成。O(nmlogm)。m为题中矩阵边长。

Run ID	Time	Size	Problem	Language	Result	Failed test
197	4:59:03	3059	H	g++0x	Wrong answer	6
196	4:56:56	3066	H	g++0x	Wrong answer	6
195	4:48:54	3047	H	g++0x	Wrong answer	6
194	4:24:24	1938	F	g++0x	Wrong answer	101
193	3:22:29	2009	H	g++0x	Time-limit exceeded	6
192	3:16:43	1169	C	g++0x	OK	N/A
191	2:50:06	2064	I	g++0x	OK	N/A
190	1:21:51	1866	B	g++0x	OK	N/A
189	0:56:42	776	J	g++0x	OK	N/A
188	0:55:49	771	J	g++0x	Presentation error	12

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

start at 18:15

流水账

总结

题解

B. Divide and Conquer [JTJL]

度数最大的点一定在团中，因此可以O(m)求出团。

另解：枚举团的大小。假设团的大小为K，则度数大于K-1的点一定在团中，小于K-1的一定不在团中。此时，对于度数为K-1的点，其K-1个邻居一定在团中。对于某一个点A，如果其邻居中存在度数小于K-1的点，则不符合条件。如果他的邻居的度数都大于K-1，则A和其邻居构成了这个团（答案为A），否则，其邻居中度数为K-1的点B，B和B的K-1个邻居一定构成了这个团（答案为B）。

C. Spatial Thinking [sfiction]

考虑一个n维超立方体的划分，类比2/3维的划分方法，可以首先取一条对角线A-B，再取与A相连的n条边中的一条作为高，得到一个超棱锥，其底面为n-1维超立方体，可以递归划分。O(n!+n³m)。

H. Beautiful Pairs [JTJL]

首先，观察得到所有的pair是三种形式之一：

1. (1, n) (n >= 1)

2. (n, n+1) (n >= 1)

3. f(1, n) = (n, n * n - 1), f(m, n) = (f(m-1, n).second, (f(m-1, n).second ** 2 - 1) / f(m-1, n).first) （n >= 3, m >= 2）

第一种情况和第二种情况都很容易统计。（第二种情况是第三种情况n=2的特例，第一种情况是m=0的情况（发源！），由于其特殊性所以单独统计……）对于第三种情况，我们可以发现，f(m, n)是关于n的m和m+1次多项式，并且在n >= 3是单调递增。由于n >= 3, 所以m是log级别，最大只能到42。我们可以考虑枚举m。

对于较小的m，我们人工构造多项式，解两个不等式求出n的上下界即可。对于较大的m，此时n的范围很有限，直接枚举n即可。在计算过程中需要注意及时约分，或者使用__int128或者DigInteger或者python。在计算高次方根时，由于精度误差需要在计算完后调整。

I. Binary Matrices [sfiction]

考虑用位运算实现Mulitply()。对AB=C，考虑每次计算C中的一列，那么只需将B中的一列转置并复制到所有行，再与A，最后合并每行的结果。转置、复制、合并分别可以用三步完成。O(nmlogm)。m为题中矩阵边长。