2016-E30-team1

从 Trac 迁移的文章

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

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||Failed test||
||357||4:55:35||4322||H||g++0x||Wrong answer||4||
||356||4:47:49||4288||H||g++0x||Wrong answer||2||
||355||4:10:00||2097||F||g++0x||OK||N/A||
||354||3:28:20||3359||J||g++0x||OK||N/A||
||353||3:13:27||2796||J||g++0x||Time-limit exceeded||1||
||352||2:33:20||1672||G||g++0x||OK||N/A||
||351||2:20:56||2931||D||g++0x||OK||N/A||
||350||1:46:13||2946||I||g++0x||OK||N/A||
||349||1:17:23||1618||I||g++0x||Wrong answer||2||
||348||1:10:38||1288||A||g++0x||OK||N/A||
||347||1:05:54||1218||A||g++0x||Wrong answer||5||

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

start at 14:25

== 流水账 ==

== 总结 ==

== 题解 ==

=== A. Defense of the Ancients [sfiction] ===

乘积规划。将解的两个和视为坐标，考虑整个点集的凸包，在最小化的目标下，只有凸包的左下边界有意义。通过分别最小化sum(ai)和sum(bi)，可以确定凸包的左边界A和下边界B。然后求出靠近原点方向离其连线最远的点，这个点必定在左下边界上。由叉积得出要最大化(Bx-Cx)(Ay-Cy)-(By-Cy)(Ax-Cx)=Cx(By-Ay)-Cy(Bx-Ax)+BxAy-ByAx。于是设w=Cx(By-Ay)-Cy(Bx-Ax)，然后取最大k项组成解即可。复杂度为O(n^3^logn)，但是比较虚。（当前的代码没有处理三点共线，复杂度不对）

复杂度证明的参考：https://www.zhihu.com/question/26086333。

同类题目：bzoj2395, hdu5697, 2014-Asia-Tokyo-J

=== C. Combinations Strike Back [sfiction] ===

只有元素的数量有意义，并且最多只有n^0.5^种不同数量。考虑用生成函数计算多重集子集数。则可以将每种数量对应的多项式转为点值表示然后相乘。数量i多次出现只需用快速幂处理即可。DFT的复杂度为O(n^1.5^logn)。点值乘法的复杂度则可证明一个更紧的界O(n^1.5^)。因为多项式形式特殊，可以考虑直接计算点值表示，如果对所有长度排序，每次len(i)对应的点值表示从len(i-1)转移过来，则单步需要O(nlog(len(i)-len(i-1)))，总的复杂度也是O(n^1.5^)。询问相当于将一个数量i变为i+1，因此同样只有n^0.5^种。每种询问可以除以一个表达式再乘上一个表达式，~~前者通过求逆完成~~可以通过维护第一步中的前缀&后缀和来完成。所得点值表示做IDFT之后即可解决所有同类询问。复杂度同样为O(n^1.5^logn)。

经过试验，O(n^1.5^logn)无法通过。处理询问必须使用标程的解法，前半部分的O(n^1.5^)在opentrains的数据上比O(nlog^2^n)要快一点，可能是因为只需要调用一次ntt。

标程解法：按照多项式数量分治后相乘，容易证明复杂度为O(nlog^2^n)（分治下层的复杂度不会超过顶层，顶层是nlogn）。处理询问同样是考虑最多n^0.5^类。由于(1+..+x^k+1^)/(1+...+x^k^)=(x^k+2^-1)/(x^k+1^-1)，每个询问可以用暴力的多项式乘/除法处理。复杂度是O((n+m)k)，nm为两式最高次数，k为乘/除多项式的非零项数。O(nlog^2^n+n^1.5^)。

=== D. DFT for Dummies [sfiction] ===

通过推导可以发现序列a[]做两次DFT后，a0保持不变，剩余部分翻转。并且DFT前后二范数保持不变。因此只需用splay维护序列的平方和并支持翻转。O(nlogn)。

=== F. Passing Finals [sfiction, JTJL] ===

考虑先将所有位置填0。枚举第一个空，只要其余子式非零就可以构造出解，如果为零则递归处理余子式。假设某一层递归的余子式非零，则其中的空都为0，递归返回时需要构造非零余子式，显然0/1中必然有一个可行。因此实际上只需枚举每个位置填0/1计算共2^K^个det即可。之后枚举第一个空，根据所求出的det检查余子式是否为零即可。O(2^K^n^3^+K*2^K-1^)。

=== G. Important Guests [Akalm] ===

对左边的点，根据deg与sqrt(n)的大小关系分为黑(>=)和白(<)点，黑与黑之间、黑与白之间的方案书可以通过枚举黑点，再枚举所有边进行计算；白与白之间则可通过对每个点枚举所有与之相连的边对来计算。

=== J. For Fun and Lulz [Akalm] ===

lct。由于数据保证随机，实际上维护暴力版即可通过。

Run ID	Time	Size	Problem	Language	Result	Failed test
357	4:55:35	4322	H	g++0x	Wrong answer	4
356	4:47:49	4288	H	g++0x	Wrong answer	2
355	4:10:00	2097	F	g++0x	OK	N/A
354	3:28:20	3359	J	g++0x	OK	N/A
353	3:13:27	2796	J	g++0x	Time-limit exceeded	1
352	2:33:20	1672	G	g++0x	OK	N/A
351	2:20:56	2931	D	g++0x	OK	N/A
350	1:46:13	2946	I	g++0x	OK	N/A
349	1:17:23	1618	I	g++0x	Wrong answer	2
348	1:10:38	1288	A	g++0x	OK	N/A
347	1:05:54	1218	A	g++0x	Wrong answer	5

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

start at 14:25

流水账

总结

题解

A. Defense of the Ancients [sfiction]

乘积规划。将解的两个和视为坐标，考虑整个点集的凸包，在最小化的目标下，只有凸包的左下边界有意义。通过分别最小化sum(ai)和sum(bi)，可以确定凸包的左边界A和下边界B。然后求出靠近原点方向离其连线最远的点，这个点必定在左下边界上。由叉积得出要最大化(Bx-Cx)(Ay-Cy)-(By-Cy)(Ax-Cx)=Cx(By-Ay)-Cy(Bx-Ax)+BxAy-ByAx。于是设w=Cx(By-Ay)-Cy(Bx-Ax)，然后取最大k项组成解即可。复杂度为O(n³logn)，但是比较虚。（当前的代码没有处理三点共线，复杂度不对）

复杂度证明的参考：https://www.zhihu.com/question/26086333。

同类题目：bzoj2395, hdu5697, 2014-Asia-Tokyo-J

C. Combinations Strike Back [sfiction]

只有元素的数量有意义，并且最多只有n^0.5种不同数量。考虑用生成函数计算多重集子集数。则可以将每种数量对应的多项式转为点值表示然后相乘。数量i多次出现只需用快速幂处理即可。DFT的复杂度为O(n^1.5logn)。点值乘法的复杂度则可证明一个更紧的界O(n^1.5)。因为多项式形式特殊，可以考虑直接计算点值表示，如果对所有长度排序，每次len(i)对应的点值表示从len(i-1)转移过来，则单步需要O(nlog(len(i)-len(i-1)))，总的复杂度也是O(n^1.5)。询问相当于将一个数量i变为i+1，因此同样只有n^0.5种。每种询问可以除以一个表达式再乘上一个表达式，前者通过求逆完成可以通过维护第一步中的前缀&后缀和来完成。所得点值表示做IDFT之后即可解决所有同类询问。复杂度同样为O(n^1.5logn)。

经过试验，O(n^1.5logn)无法通过。处理询问必须使用标程的解法，前半部分的O(n^1.5)在opentrains的数据上比O(nlog²n)要快一点，可能是因为只需要调用一次ntt。

标程解法：按照多项式数量分治后相乘，容易证明复杂度为O(nlog²n)（分治下层的复杂度不会超过顶层，顶层是nlogn）。处理询问同样是考虑最多n^0.5类。由于(1+..+x^k+1)/(1+...+x^k)=(x^k+2-1)/(x^k+1-1)，每个询问可以用暴力的多项式乘/除法处理。复杂度是O((n+m)k)，nm为两式最高次数，k为乘/除多项式的非零项数。O(nlog²n+n^1.5)。

D. DFT for Dummies [sfiction]

通过推导可以发现序列a[]做两次DFT后，a0保持不变，剩余部分翻转。并且DFT前后二范数保持不变。因此只需用splay维护序列的平方和并支持翻转。O(nlogn)。

F. Passing Finals [sfiction, JTJL]

考虑先将所有位置填0。枚举第一个空，只要其余子式非零就可以构造出解，如果为零则递归处理余子式。假设某一层递归的余子式非零，则其中的空都为0，递归返回时需要构造非零余子式，显然0/1中必然有一个可行。因此实际上只需枚举每个位置填0/1计算共2^K个det即可。之后枚举第一个空，根据所求出的det检查余子式是否为零即可。O(2^Kn³+K*2^K-1)。

G. Important Guests [Akalm]

对左边的点，根据deg与sqrt(n)的大小关系分为黑(>=)和白(<)点，黑与黑之间、黑与白之间的方案书可以通过枚举黑点，再枚举所有边进行计算；白与白之间则可通过对每个点枚举所有与之相连的边对来计算。

J. For Fun and Lulz [Akalm]

lct。由于数据保证随机，实际上维护暴力版即可通过。