2016-E26-team1

从 Trac 迁移的文章

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

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||Failed test||
||410||3:35:14||1236||E||g++0x||OK||N/A||
||409||2:52:11||2743||J||g++||OK||N/A||
||408||1:54:14||1580||F||g++||OK||N/A||
||407||1:36:16||1561||F||g++||Wrong answer||10||
||406||1:35:01||1539||F||g++||Compilation error||N/A||
||405||0:46:39||1986||A||g++||OK||N/A||
||404||0:40:09||1989||A||g++||Time-limit exceeded||17||
||403||0:18:47||300||D||g++||OK||N/A||

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

start at 16:30

== 流水账 ==

== 总结 ==

== 题解 ==

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
}}}

=== A. MEX-Query [sfiction] ===

与E23-H类似。以位置为下标建线段树，从右往左扫一遍，过程中维护所有值最后（右）出现的位置，其他位置置为inf。对于询问[l,i]，求出[1,l-1]的最小值，其他已出现的更小的值应当都在[l,i]中。与E23-H不同的时，所有已经出现的值不一定是连续的，也就是说可能有比[1,l-1]更小的值根本没有在[1,i]中出现，可以用一个set或者双端链表维护这个全局未出现最小值。

标程的做法：以值为下标建线段树，从左往右扫一遍，过程中维护所有值最后（左）一次出现的位置，未出现值置为inf。线段树结点维护最大值，处理询问[i,r]时根据r在线段树上二分。某个结点的值大于r表明这段区间中有数没有在[i,r]中出现。

还有很多其他做法，似乎都是O(nlogn)。

=== B. Beer Quadrilaterls [JTJL] ===

不妨设对角线交点为E，考虑△ABE，对于固定的 ∠AEB 和 ∠BAE ，AE/BE为定值。同样，固定 ∠BEC 和 ∠BCE 后，CE/BE也固定了。那我们枚举 ∠AEB 。此时对于所有的pair<∠BAC, ∠BCA>, 我们可以求出 AE/CE。而 ∠CED = ∠AEB ，同样的pair<∠DAC, ∠DCA> 也对应着相同的 CE/AE。所以我们只要求出在这k^2^个pair对应的比例中有多少对的积为1即可。复杂度为O(k^3^)或者O(k^3^logk)。也可以O(k^4^)暴力打表(XD。 需要注意一下精度问题。

=== C. The Palindrome Extraction [sfiction] ===

假设|B|>=|D|，即连续回文部分P是B的后缀。考虑枚举P的中心，P一定越长越好。用manacher算法确定P=s[l,r]之后，就是询问前缀的[1,l-1]的反串在后缀[r+1,n]中的最长匹配。这可以用后缀数组来处理。处理出s$rev(s)的后缀信息，确定rev(s[1,l-1])在sa[]中的位置后，向前找到第一个sa[i]>r的位置，向后找到第一个sa[i]>r的位置更新答案即可。查找部分可以用倍增解决。O(n+n+nlogn)。

为了简化代码，可以通过处理s的反串解决|D|>=|B|的情况，还可以通过对所有字符取负合并向前向后查找的情况。

=== D. Short Enough Task [sfiction] ===

{{{
#!html
<p>枚举每个子串成为回文串的概率后求和，$ans=\sum_{i=1}^{n}(n-i+1)k^{-\lfloor i/2 \rfloor}$。可以发现几十项后就小于所要求精度了，因此算前几百项就可以了。特判$k=1$的情况。$O(1)$。</p>

<p>合并指数相同项后应该可以推出公式。</p>
</script>
}}}

=== E. Another Short Problem [JTJL, sfiction] ===

枚举点判断是否在凸包上比较困难。考虑到没有四点共面，凸包表面都是三角形，用v/e/f分别表示点线面的个数，则应该有2e/3=f，代入欧拉公式v+f=e+2即有v=2+f/2。而一个面在凸包上概率是很好计算的。要注意有0/1/2个点的情况的面数也要考虑，根据公式分别是-4/-2/0。

=== F. Just Another Sequence Problem [Akalm, sfiction] ===

因为段数无限制，状态表示可以不考虑。dp(i,j)表示最后一段为(i,j]的最优解。则显然有dp(j,k)=max(dp(i,j)+(sum[j]-sum[i])*(sum[k]-sum[j]))，是一个斜率优化的形式。这个式子还有一些特殊性，对于一个固定的j，更新状态是固定的，不随k变化而变化，因此只要求一个凸线就能用来更新所有k。O(n^2^logn)。

=== H. Cyclic String [sfiction] ===

考虑二分答案，将问题分为排序和判定两部分。排序部分很容易解决，最暴力的就是把所有循环表示接在一起求SA。用dp(len,i)表示从i开始，长度为len的串在所有长为len的子串中的rank，可以按len从小到大递推。对所有串一起排序的时候，先用dp(len,i)中的信息比较两串中较短串的长度，如果一样就是更长的串更大。

判定部分可以用贪心方法解决。将一个小于等于mid的子串(i,j)视为i->j的一条边，问题就是能否恰好K步走一圈。这个问题有一个特殊性，即从i出发的可达位置是从i+1开始连续的一段，设最远到len[i]。如果我们能求出从i出发走K步距离最远的一个方案，走过长度>=n，那其中必然有一个时刻，我们在位置u，还剩下k步可以走，u+k<=i且len[u]<=i-k-1，下一步我们可以跳到i-k-1，之后一步步走就可以到达出发点。这要求后面的所有位置都是至少能往后走一步的，因此我们把所有没有可达位置的点删掉，包括删掉这些点后失去所有可达位置的。在新的图上做上述算法。还有一个问题就是如何走得最远。以u的所有可达点v中v+len[v]最大的点作为后继nex[u]，因为这个点包含了最多的决策方法，当然最后一步是选择len[u]而不是nex[u]。

O(n^2^logn+n^2^logn)。

=== I. Circle Clique [Akalm] ===

比赛中读错题，两点间能否连线判断条件是直线而不是线段，对解法影响较大，值得检讨。

算出每个点到圆的两个切点的位置，构成一个区间，两个点可以连边即对应的两个区间相交但不包含（后面描述中相交关系不包括包含关系）。注意到 A 与 B 相交，则 A 与 B补 也相交； A 与 B 相离，则 A 被 B补 包含（反之亦然）。所以就可以枚举基准区间 I ，挑出所有与 I 相交的区间 J ，并且在 J和 J补 中留下相对 I 而言是左侧的一个，记为 J‘ ；然后 J' 的左右端点分别对 I 的左右端点作差，跑一遍二维LIS即可。

=== J. Dividing Area [JTJL, sfiction] ===

按时间顺序从后往前处理，添加线段视为合并两个区域。最终状态中的封闭区域求解和左手侧区域确定用farmland处理。O(qlogn)。

Farmland例题：zoj1030, zoj2361(ASC3A)(http://blog.watashi.ws/970/andrew-stankevich-3-solution/)
Run IDTimeSizeProblemLanguageResultFailed test
4103:35:141236Eg++0xOKN/A
4092:52:112743Jg++OKN/A
4081:54:141580Fg++OKN/A
4071:36:161561Fg++Wrong answer10
4061:35:011539Fg++Compilation errorN/A
4050:46:391986Ag++OKN/A
4040:40:091989Ag++Time-limit exceeded17
4030:18:47300Dg++OKN/A

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

start at 16:30

流水账

总结

题解

A. MEX-Query [sfiction]

与E23-H类似。以位置为下标建线段树，从右往左扫一遍，过程中维护所有值最后（右）出现的位置，其他位置置为inf。对于询问[l,i]，求出[1,l-1]的最小值，其他已出现的更小的值应当都在[l,i]中。与E23-H不同的时，所有已经出现的值不一定是连续的，也就是说可能有比[1,l-1]更小的值根本没有在[1,i]中出现，可以用一个set或者双端链表维护这个全局未出现最小值。

标程的做法：以值为下标建线段树，从左往右扫一遍，过程中维护所有值最后（左）一次出现的位置，未出现值置为inf。线段树结点维护最大值，处理询问[i,r]时根据r在线段树上二分。某个结点的值大于r表明这段区间中有数没有在[i,r]中出现。

还有很多其他做法，似乎都是O(nlogn)。

B. Beer Quadrilaterls [JTJL]

不妨设对角线交点为E，考虑△ABE，对于固定的 ∠AEB 和 ∠BAE ，AE/BE为定值。同样，固定 ∠BEC 和 ∠BCE 后，CE/BE也固定了。那我们枚举 ∠AEB 。此时对于所有的pair<∠BAC, ∠BCA>, 我们可以求出 AE/CE。而 ∠CED = ∠AEB ，同样的pair<∠DAC, ∠DCA> 也对应着相同的 CE/AE。所以我们只要求出在这k2个pair对应的比例中有多少对的积为1即可。复杂度为O(k3)或者O(k3logk)。也可以O(k4)暴力打表(XD。 需要注意一下精度问题。

C. The Palindrome Extraction [sfiction]

假设|B|>=|D|，即连续回文部分P是B的后缀。考虑枚举P的中心，P一定越长越好。用manacher算法确定P=s[l,r]之后，就是询问前缀的[1,l-1]的反串在后缀[r+1,n]中的最长匹配。这可以用后缀数组来处理。处理出s$rev(s)的后缀信息，确定rev(s[1,l-1])在sa[]中的位置后，向前找到第一个sa[i]>r的位置，向后找到第一个sa[i]>r的位置更新答案即可。查找部分可以用倍增解决。O(n+n+nlogn)。

为了简化代码，可以通过处理s的反串解决|D|>=|B|的情况，还可以通过对所有字符取负合并向前向后查找的情况。

D. Short Enough Task [sfiction]

枚举每个子串成为回文串的概率后求和，$ans=\sum_{i=1}^{n}(n-i+1)k^{-\lfloor i/2 \rfloor}$。可以发现几十项后就小于所要求精度了，因此算前几百项就可以了。特判$k=1$的情况。$O(1)$。

合并指数相同项后应该可以推出公式。

E. Another Short Problem [JTJL, sfiction]

枚举点判断是否在凸包上比较困难。考虑到没有四点共面，凸包表面都是三角形，用v/e/f分别表示点线面的个数，则应该有2e/3=f，代入欧拉公式v+f=e+2即有v=2+f/2。而一个面在凸包上概率是很好计算的。要注意有0/1/2个点的情况的面数也要考虑，根据公式分别是-4/-2/0。

F. Just Another Sequence Problem [Akalm, sfiction]

因为段数无限制，状态表示可以不考虑。dp(i,j)表示最后一段为(i,j]的最优解。则显然有dp(j,k)=max(dp(i,j)+(sum[j]-sum[i])*(sum[k]-sum[j]))，是一个斜率优化的形式。这个式子还有一些特殊性，对于一个固定的j，更新状态是固定的，不随k变化而变化，因此只要求一个凸线就能用来更新所有k。O(n2logn)。

H. Cyclic String [sfiction]

考虑二分答案，将问题分为排序和判定两部分。排序部分很容易解决，最暴力的就是把所有循环表示接在一起求SA。用dp(len,i)表示从i开始，长度为len的串在所有长为len的子串中的rank，可以按len从小到大递推。对所有串一起排序的时候，先用dp(len,i)中的信息比较两串中较短串的长度，如果一样就是更长的串更大。

判定部分可以用贪心方法解决。将一个小于等于mid的子串(i,j)视为i->j的一条边，问题就是能否恰好K步走一圈。这个问题有一个特殊性，即从i出发的可达位置是从i+1开始连续的一段，设最远到len[i]。如果我们能求出从i出发走K步距离最远的一个方案，走过长度>=n，那其中必然有一个时刻，我们在位置u，还剩下k步可以走，u+k<=i且len[u]<=i-k-1，下一步我们可以跳到i-k-1，之后一步步走就可以到达出发点。这要求后面的所有位置都是至少能往后走一步的，因此我们把所有没有可达位置的点删掉，包括删掉这些点后失去所有可达位置的。在新的图上做上述算法。还有一个问题就是如何走得最远。以u的所有可达点v中v+len[v]最大的点作为后继nex[u]，因为这个点包含了最多的决策方法，当然最后一步是选择len[u]而不是nex[u]。

O(n2logn+n2logn)。

I. Circle Clique [Akalm]

比赛中读错题，两点间能否连线判断条件是直线而不是线段，对解法影响较大，值得检讨。

算出每个点到圆的两个切点的位置，构成一个区间，两个点可以连边即对应的两个区间相交但不包含（后面描述中相交关系不包括包含关系）。注意到 A 与 B 相交，则 A 与 B补 也相交； A 与 B 相离，则 A 被 B补 包含（反之亦然）。所以就可以枚举基准区间 I ，挑出所有与 I 相交的区间 J ，并且在 J和 J补 中留下相对 I 而言是左侧的一个，记为 J‘ ；然后 J' 的左右端点分别对 I 的左右端点作差，跑一遍二维LIS即可。

J. Dividing Area [JTJL, sfiction]

按时间顺序从后往前处理，添加线段视为合并两个区域。最终状态中的封闭区域求解和左手侧区域确定用farmland处理。O(qlogn)。

Farmland例题：zoj1030, zoj2361(ASC3A)(http://blog.watashi.ws/970/andrew-stankevich-3-solution/)