2016-E37-team1

从 Trac 迁移的文章

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

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||Failed test||
||482||3:12:07||1833||I||g++0x||OK||N/A||
||481||2:59:05||4155||H||g++0x||OK||N/A||
||480||2:55:30||4152||H||g++0x||Run-time error||20||
||479||2:35:07||1175||D||g++0x||OK||N/A||
||478||2:19:04||1132||D||g++0x||Wrong answer||2||
||477||1:36:14||1400||B||g++0x||OK||N/A||
||476||1:19:37||772||J||g++0x||OK||N/A||
||475||1:10:04||1401||F||g++0x||OK||N/A||
||474||0:20:32||889||A||g++0x||OK||N/A||

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

start at 17:55

== 流水账 ==

== 总结 ==

== 题解 ==

=== A. As Easy As Possible [sfiction] ===

a[i][chr]表示位置i及右边首个出现的chr。借助a[i][]可以计算出p[i][0]，表示位置i及右边首个出现的子序列easy。然后对p[i]倍增即可。O(nlogn+mlogn)。

=== B. Be Friends [sfiction] ===

考虑根据最高位为0/1将所有数分为两类，如果两类均不为空，那么两类之间至少有一条边。由于两类之间的任意边的权值都大于类内的边权，可以递归处理两类，然后再求类间的最小值使其连通。类间的最小值可以用二进制Trie计算。O(nlog^2^P)。

=== C. Coprime Heaven ===

TBA

=== D. Drawing Hell [JTJL] ===

所有点共线时边数为2n-1。存在凸包时，最后结果必定是一个三角剖分，由平面图欧拉公式可得边数为3n-c-3。于是判共线后求凸包即可。O(nlogn)。

=== E. Easiest Game [sfiction] ===

暴力求小数据可以得出对于s>=t，n>=m，当且仅当gcd(s,t)=1、2s<=n、s+t<=m、s+t为奇数时，能够走遍整个棋盘。给定n和m，后三个条件可以O(1)求出，因此可以对gcd容斥，借助反演和分段可以做到O(n^0.5^+m^0.5^)。注意n=m=1的特例。

=== F. Fibonacci of Fibonacci [JTJL] ===

找循环节。

=== G. Global Warming ===

TBA

=== H. Hash Collision [Sfiction, Akalm] ===

用类似快速幂的方法倍增求n下的方案数， ntt+crt 转移

用a[i]表示哈希值为i的字符串数，则n+1可以暴力在O(SIGMA*m)内完成，n*2则可以用卷积处理，结果的范围过大，需要使用ntt+crt，复杂度为O(mlogm+mlogLL)。总得复杂度为O(mlogn(SIGMA+logm+logLL))。


=== I. Increasing or Decreasing [sfiction] ===

确定最高最低值和长度的不严格单调序列数可以用组合数计算。因此用类似数位DP的方法逐位统计即可。O(10logn)。

=== J. Just Convolution [Akalm] ===

枚举最大的 100N 对a_i+b_j，再暴力处理c[]中没被更新过的位置

Run ID	Time	Size	Problem	Language	Result	Failed test
482	3:12:07	1833	I	g++0x	OK	N/A
481	2:59:05	4155	H	g++0x	OK	N/A
480	2:55:30	4152	H	g++0x	Run-time error	20
479	2:35:07	1175	D	g++0x	OK	N/A
478	2:19:04	1132	D	g++0x	Wrong answer	2
477	1:36:14	1400	B	g++0x	OK	N/A
476	1:19:37	772	J	g++0x	OK	N/A
475	1:10:04	1401	F	g++0x	OK	N/A
474	0:20:32	889	A	g++0x	OK	N/A

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

start at 17:55

流水账

总结

题解

A. As Easy As Possible [sfiction]

a[i][chr]表示位置i及右边首个出现的chr。借助a[i][]可以计算出p[i][0]，表示位置i及右边首个出现的子序列easy。然后对p[i]倍增即可。O(nlogn+mlogn)。

B. Be Friends [sfiction]

考虑根据最高位为0/1将所有数分为两类，如果两类均不为空，那么两类之间至少有一条边。由于两类之间的任意边的权值都大于类内的边权，可以递归处理两类，然后再求类间的最小值使其连通。类间的最小值可以用二进制Trie计算。O(nlog²P)。

C. Coprime Heaven

TBA

D. Drawing Hell [JTJL]

所有点共线时边数为2n-1。存在凸包时，最后结果必定是一个三角剖分，由平面图欧拉公式可得边数为3n-c-3。于是判共线后求凸包即可。O(nlogn)。

E. Easiest Game [sfiction]

暴力求小数据可以得出对于s>=t，n>=m，当且仅当gcd(s,t)=1、2s<=n、s+t<=m、s+t为奇数时，能够走遍整个棋盘。给定n和m，后三个条件可以O(1)求出，因此可以对gcd容斥，借助反演和分段可以做到O(n^0.5+m^0.5)。注意n=m=1的特例。

F. Fibonacci of Fibonacci [JTJL]

找循环节。

G. Global Warming

TBA

H. Hash Collision [Sfiction, Akalm]

用类似快速幂的方法倍增求n下的方案数， ntt+crt 转移

用a[i]表示哈希值为i的字符串数，则n+1可以暴力在O(SIGMA*m)内完成，n*2则可以用卷积处理，结果的范围过大，需要使用ntt+crt，复杂度为O(mlogm+mlogLL)。总得复杂度为O(mlogn(SIGMA+logm+logLL))。

I. Increasing or Decreasing [sfiction]

确定最高最低值和长度的不严格单调序列数可以用组合数计算。因此用类似数位DP的方法逐位统计即可。O(10logn)。

J. Just Convolution [Akalm]

枚举最大的 100N 对a_i+b_j，再暴力处理c[]中没被更新过的位置