2016-S05-team1

从 Trac 迁移的文章

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

原文章内容如下：

||Run Id||Problem||Time||Status||Language||
||136||A||8||Yes||GNU C++11||
||344||L||15||Yes||GNU C++11||
||628||D||36||RE||GNU C++11||
||653||D||37||Yes||GNU C++11||
||778||H||46||Yes||GNU C++11||
||1229||E||81||WA||Java||
||1285||E||86||WA||Java||
||1576||C||115||WA||GNU C++11||
||1742||C||132||Yes||GNU C++11||
||1774||E||135||Yes||Java||
||2557||B||212||WA||GNU C++11||
||2727||B||225||Yes||GNU C++11||
||3120||G||254||TLE||GNU C++11||
||3282||G||263||Yes||GNU C++11||
||3396||F||269||WA||GNU C++11||
||3585||F||278||Yes||GNU C++11||
||4697||K||299||WA||GNU C++11||
||4831||K||299||WA||GNU C++11||

比赛链接: http://10.71.10.90/sfiction/ranklist/2016_Asia_China-Final_Shanghai/ranklist.htm

== 流水账 ==

[http://www.cc98.org/dispbbs.asp?boardID=329&ID=4673136 2016 China-Final 小结 by sfiction @Siunaus]

== 总结 ==

== 题解 ==

{{{
#!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>
}}}

AL略去不表。

=== B. Hemi Palindrome [JTJL] ===

从前往后枚举每位，计数确定填0或1。计数时根据两串是否回文确定有多少自由元，根据是否跨过中心自由元数量有所不同。

=== C. Mr. Panda and Strips [Akalm, sfiction] ===

枚举左侧区间[l,r]，其中出现过的数字都不可选，序列右侧被划分为多个连续区间。单个连续区间的最优解可以O(n^2^)预处理。如果令r=l->n，则需要用set维护区间划分和所有区间最优解。反过来做则只需要处理区间的合并和维护最大值（最大值单调递增），容易想到用并查集维护。实际上因为对于新加入的合法点p，只会检查p-1和p+1的所属区间，而这两个点要么非法，要么是已有区间的端点，因此只需要在端点处维护区间信息。O(n^2+n^2)。

=== D. Ice Cream Tower [JTJL, sfiction] ===

必然存在解，每层的size都小于等于下一层的size。因此二分答案K，一层层填入合法值即可。O(nlogn+nlogn)。

=== E. Bet [all] ===

每个赌局在仅自己获利时总体获利，必须保证投注比例大于a/(a+b)，因此求出每个赌局的投注比例，尽可能取最小。

=== F. Mr. Panda and Fantastic Beats [Akalm && sfiction] ===

将所有字符串拼在一起，并维护好每个位置在原串中最大后缀长度。跑一遍SA，然后枚举sa数组中所有属于一号串的位置，向前向后算算它与非第一个串位置的lcp并与最大后缀长度比较下判断合法性，更新答案即可。

=== G. Pandaria [sfiction] ===

容易证明可达点集间只有包含和相离关系，没有相交。因此最多只有2n-1个不同点集，按边从小到大排序，对点集合并即可。对每个询问，在根据集合包含关系所建的树上倍增即可确定可达点集。树上的出现最多次数数字可以用线段树合并或者启发式合并来做。线段树合并O(nlogn)，启发式合并用dsu或map分别是O(nlogn)和O(nlog^2^n)。O(mlogm+(n+q)logn)。

=== H. Great Cells [sfiction] ===

{{{
#!html
<p>分解答案的表示为$\sum{g(A_g)}$和$\sum{A_g}$，前者是所有方案中特殊点数量之和，后者为方案数。前者通过计算每个位置贡献即可。O(Klogn)。可能可以把公式优化到O(logn)？</p>
}}}
Run IdProblemTimeStatusLanguage
136A8YesGNU C++11
344L15YesGNU C++11
628D36REGNU C++11
653D37YesGNU C++11
778H46YesGNU C++11
1229E81WAJava
1285E86WAJava
1576C115WAGNU C++11
1742C132YesGNU C++11
1774E135YesJava
2557B212WAGNU C++11
2727B225YesGNU C++11
3120G254TLEGNU C++11
3282G263YesGNU C++11
3396F269WAGNU C++11
3585F278YesGNU C++11
4697K299WAGNU C++11
4831K299WAGNU C++11

比赛链接: http://10.71.10.90/sfiction/ranklist/2016_Asia_China-Final_Shanghai/ranklist.htm

流水账

2016 China-Final 小结 by sfiction @Siunaus

总结

题解

AL略去不表。

B. Hemi Palindrome [JTJL]

从前往后枚举每位，计数确定填0或1。计数时根据两串是否回文确定有多少自由元，根据是否跨过中心自由元数量有所不同。

C. Mr. Panda and Strips [Akalm, sfiction]

枚举左侧区间[l,r]，其中出现过的数字都不可选，序列右侧被划分为多个连续区间。单个连续区间的最优解可以O(n2)预处理。如果令r=l->n，则需要用set维护区间划分和所有区间最优解。反过来做则只需要处理区间的合并和维护最大值（最大值单调递增），容易想到用并查集维护。实际上因为对于新加入的合法点p，只会检查p-1和p+1的所属区间，而这两个点要么非法，要么是已有区间的端点，因此只需要在端点处维护区间信息。O(n2+n2)。

D. Ice Cream Tower [JTJL, sfiction]

必然存在解，每层的size都小于等于下一层的size。因此二分答案K，一层层填入合法值即可。O(nlogn+nlogn)。

E. Bet [all]

每个赌局在仅自己获利时总体获利，必须保证投注比例大于a/(a+b)，因此求出每个赌局的投注比例，尽可能取最小。

F. Mr. Panda and Fantastic Beats [Akalm && sfiction]

将所有字符串拼在一起，并维护好每个位置在原串中最大后缀长度。跑一遍SA，然后枚举sa数组中所有属于一号串的位置，向前向后算算它与非第一个串位置的lcp并与最大后缀长度比较下判断合法性，更新答案即可。

G. Pandaria [sfiction]

容易证明可达点集间只有包含和相离关系，没有相交。因此最多只有2n-1个不同点集，按边从小到大排序，对点集合并即可。对每个询问，在根据集合包含关系所建的树上倍增即可确定可达点集。树上的出现最多次数数字可以用线段树合并或者启发式合并来做。线段树合并O(nlogn)，启发式合并用dsu或map分别是O(nlogn)和O(nlog2n)。O(mlogm+(n+q)logn)。

H. Great Cells [sfiction]

分解答案的表示为$\sum{g(A_g)}$和$\sum{A_g}$，前者是所有方案中特殊点数量之和，后者为方案数。前者通过计算每个位置贡献即可。O(Klogn)。可能可以把公式优化到O(logn)？

附加文件