2016-E28-team1

从 Trac 迁移的文章

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

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||Failed test||
||498||4:50:12||2421||I||g++0x||OK||N/A||
||497||4:36:09||2167||I||g++0x||Wrong answer||15||
||496||4:22:08||1597||I||g++0x||Wrong answer||8||
||495||4:09:09||1544||I||g++0x||Time-limit exceeded||8||
||494||4:03:44||2148||I||g++0x||Time-limit exceeded||8||
||493||3:52:28||1534||I||g++0x||Wrong answer||3||
||492||3:44:12||3071||J||g++0x||OK||N/A||
||491||3:13:31||915||A||g++0x||OK||N/A||
||490||3:06:20||910||A||g++0x||Time-limit exceeded||6||
||489||2:21:47||385||B||g++0x||OK||N/A||
||488||1:54:33||839||E||g++0x||OK||N/A||
||487||1:51:02||839||E||g++0x||Wrong answer||16||
||486||1:47:34||837||E||g++0x||Run-time error||10||
||485||1:43:44||5356||J||javac||Time-limit exceeded||9||
||484||1:12:05||1368||F||g++0x||OK||N/A||
||483||0:59:47||1231||F||g++0x||Time-limit exceeded||11||
||482||0:56:10||1447||C||g++0x||OK||N/A||
||481||0:34:09||1338||F||g++0x||Wrong answer||4||
||480||0:33:04||899||G||g++0x||OK||N/A||

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

start at 14:35

== 流水账 ==

=== sfiction ===

这场写了 CEBA。C 是个细节题，不应该在一开始抢机时，写了 30+min 也有点久，还是要提升一下细节题的速度。E 写得比较快但写错数组大小和一处判断条件 WA 了两次。B 代码很短，比较顺利。A 虽然写得巧妙但还是比较慢，而且又写挂了一个地方。

== 总结 ==

== 题解 ==

=== A. Morse Code [JTJL, sfiction] ===

考虑将单个询问划分为log段。注意到M可以通过复制自身并取反来构造，对于任意t，M序列的[t*2^k^,(t+1)*2^k^)都是和[0,2^k^)相同或者是取反的结果（取反与否只需快速检查A_{t*2^k^}）。可以将询问划分为符合这一性质的段。段的大小在划分过程前半部分受到y的最低非0位的限制，在后半部分则受到k的大小的限制。使用倍增方法在O(nlogn)时间内预处理出f(i,j)=\sum_{k=0}!^{2^k^-1}(A_{i+k}*M_{k})。O(nlogn+qlogn)。

=== B. Deadly Sin [sfiction] ===

显然应该利用sin的周期性，可以令大周期为小周期的偶数倍，这样两者就可以独立调整。因此取xi=(2k)^i^，这样第i个不等式就依赖于a*(2k)^i^%2和1的大小关系。注意a应该加一个极小量以避免不等式左边为0。取k=5可以方便实现。O(n^2^+nq)。

=== C. Supermutations [sfiction] ===

按照下标模5分为5个序列，维护每个序列各自的段偏移量和段内位置，询问也拆分为5个。O(q)。

=== D. Serpentine [JTJL] ===

自然的考虑到可以分治。对于一个正方形，只要把九个小正方形的答案相加乘上(1/3)^p^即可。(Sierpinski地毯的边缘为白色，所以小正方形之间不会相互影响)。同时注意到a和b表示的斜率在整个过程中一直保持不变，c的变换也是在[1,a+b-1]之间的整数。所以我们倒着迭代若干次即可。

=== E. Best Student [wxj, sfiction] ===

首先只需考虑<=A_1的人。其次如果有和A_1完全一样的人则必然无解。根据每个分量<=或<可以得到2^n^条规则，这些规则将所有人划分为2^n^类。显然全部为=的规则必须为10，其他规则按照<的数量依次计算出应赋值即可。O(mn+n^2^)。

=== F. Snyrk’s Prediction [JTJL] ===

题意是给定两个排列，问是否存在一个逆序对同时出现在两个排列中(感觉日本人出过这个题)。考虑i本身、i在两个排列中的位置三个量，则可以得到三维空间中的n个点，问题转化为求是否存在一个点对，在三维上都满足<关系。考虑一维排序当作时间，剩下两维维护平面上的一条凸链。对于新的点判断是否和后一个点合法，同时动态更新另一侧的凸链即可。每个点只会出入数据结构一次，额外再做两次比较。用set来维护可以做到O(nlogn)。


=== G. Accordion [Akalm] ===
N奇和N偶K奇都是必胜态，N偶K偶时先手也只能选偶数个，所以策略是和N/2, K/2时是一样的

=== I. Polynomials [JTJL] ===

暴力Hash即可。(开场挂了一片以为卡Hash，结果好像都是T了)。
需要long long范围的(膜)数，同时需要注意自乘和0多项式的情况。

=== J. Foreign Currency Exchange [JTJL, Akalm] ===
hash维护一下分子分母，并对它们分别开一个数组来动态记录质因子次数来处理约分

Run ID	Time	Size	Problem	Language	Result	Failed test
498	4:50:12	2421	I	g++0x	OK	N/A
497	4:36:09	2167	I	g++0x	Wrong answer	15
496	4:22:08	1597	I	g++0x	Wrong answer	8
495	4:09:09	1544	I	g++0x	Time-limit exceeded	8
494	4:03:44	2148	I	g++0x	Time-limit exceeded	8
493	3:52:28	1534	I	g++0x	Wrong answer	3
492	3:44:12	3071	J	g++0x	OK	N/A
491	3:13:31	915	A	g++0x	OK	N/A
490	3:06:20	910	A	g++0x	Time-limit exceeded	6
489	2:21:47	385	B	g++0x	OK	N/A
488	1:54:33	839	E	g++0x	OK	N/A
487	1:51:02	839	E	g++0x	Wrong answer	16
486	1:47:34	837	E	g++0x	Run-time error	10
485	1:43:44	5356	J	javac	Time-limit exceeded	9
484	1:12:05	1368	F	g++0x	OK	N/A
483	0:59:47	1231	F	g++0x	Time-limit exceeded	11
482	0:56:10	1447	C	g++0x	OK	N/A
481	0:34:09	1338	F	g++0x	Wrong answer	4
480	0:33:04	899	G	g++0x	OK	N/A

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

start at 14:35

流水账

sfiction

这场写了 CEBA。C 是个细节题，不应该在一开始抢机时，写了 30+min 也有点久，还是要提升一下细节题的速度。E 写得比较快但写错数组大小和一处判断条件 WA 了两次。B 代码很短，比较顺利。A 虽然写得巧妙但还是比较慢，而且又写挂了一个地方。

总结

题解

A. Morse Code [JTJL, sfiction]

考虑将单个询问划分为log段。注意到M可以通过复制自身并取反来构造，对于任意t，M序列的[t*2^k,(t+1)*2^k)都是和[0,2^k)相同或者是取反的结果（取反与否只需快速检查A_{t*2^k}）。可以将询问划分为符合这一性质的段。段的大小在划分过程前半部分受到y的最低非0位的限制，在后半部分则受到k的大小的限制。使用倍增方法在O(nlogn)时间内预处理出f(i,j)=\sum_{k=0}!^{2k^-1}(A_{i+k}*M_{k})。O(nlogn+qlogn)。

B. Deadly Sin [sfiction]

显然应该利用sin的周期性，可以令大周期为小周期的偶数倍，这样两者就可以独立调整。因此取xi=(2k)ⁱ，这样第i个不等式就依赖于a*(2k)ⁱ%2和1的大小关系。注意a应该加一个极小量以避免不等式左边为0。取k=5可以方便实现。O(n²+nq)。

C. Supermutations [sfiction]

按照下标模5分为5个序列，维护每个序列各自的段偏移量和段内位置，询问也拆分为5个。O(q)。

D. Serpentine [JTJL]

自然的考虑到可以分治。对于一个正方形，只要把九个小正方形的答案相加乘上(1/3)^p即可。(Sierpinski地毯的边缘为白色，所以小正方形之间不会相互影响)。同时注意到a和b表示的斜率在整个过程中一直保持不变，c的变换也是在[1,a+b-1]之间的整数。所以我们倒着迭代若干次即可。

E. Best Student [wxj, sfiction]

首先只需考虑<=A_1的人。其次如果有和A_1完全一样的人则必然无解。根据每个分量<=或<可以得到2ⁿ条规则，这些规则将所有人划分为2ⁿ类。显然全部为=的规则必须为10，其他规则按照<的数量依次计算出应赋值即可。O(mn+n²)。

F. Snyrk’s Prediction [JTJL]

题意是给定两个排列，问是否存在一个逆序对同时出现在两个排列中(感觉日本人出过这个题)。考虑i本身、i在两个排列中的位置三个量，则可以得到三维空间中的n个点，问题转化为求是否存在一个点对，在三维上都满足<关系。考虑一维排序当作时间，剩下两维维护平面上的一条凸链。对于新的点判断是否和后一个点合法，同时动态更新另一侧的凸链即可。每个点只会出入数据结构一次，额外再做两次比较。用set来维护可以做到O(nlogn)。

G. Accordion [Akalm]

N奇和N偶K奇都是必胜态，N偶K偶时先手也只能选偶数个，所以策略是和N/2, K/2时是一样的

I. Polynomials [JTJL]

暴力Hash即可。(开场挂了一片以为卡Hash，结果好像都是T了)。

需要long long范围的(膜)数，同时需要注意自乘和0多项式的情况。

J. Foreign Currency Exchange [JTJL, Akalm]

hash维护一下分子分母，并对它们分别开一个数组来动态记录质因子次数来处理约分