2017-Sp251-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]

== 流水账 ==
签完到后sub和周任飞单挑几何，不幸败北。
=== chenjb ===
今天前期没什么问题，做K不做B也是根据榜和几何选手想法合理的选择。周任飞的说法：当时两个几何题，电脑上dp还没写完，感觉B题虽然难，但是不占机时，所以做他更应当。周任飞的说法我觉得可以记下来，这是个很经典的封榜战略选择。
=== oipotato ===

=== subconscious  ===

== 题解 == 
 * A：每次拿一行或一列除了问号之外只有一种字母的，把这行或列直接变成问号，把操作过程反着输出即可。

 * B：sub

 * C：枚举公比，暴力判定。

 * D：暴力枚举，O(1)取区间max。

 * E：显然后一半的人两两不能相邻，由于有k+1个这样的数，所以只能放在奇数位，f[i][mask]表示大的数字的前i个放好了，位置是mask的方案数。转移的时候把mask解码，暴力进行判断和系数计算。

 * F：分治求出挖掉一个点的图的floyd结果，每个答案枚举两个出度，更新。

 * G：

 * H：大力用stl库模拟。

 * I：把所有可能的初始情况都存下来，每次根据结果看哪些初始情况对应的符合，如果某一次可以判定必胜，则all-in，log级别。

 * J：背包求出第一种体系下和为k时第二种体系最大值，用bitset存方案，之后反过来再做一次。

 * K：结论是只需要考虑不与初始边交叉的边，直接最小生成树。找边的方法对每个点极角排序，扫的过程中维护线段到点的距离，这里注意方法和常数。

 * L：a偶数变成bc，再变回a，a奇数的时候变成cb，然后变回a，注意long long。

 * M：f[i][mask]代表目前在第i个位置，mask 3进制代表每一列目前1的状态，倒过来dp，每次查询的时候用dp值来断定即可。

 * [https://icpc.camp/twsf/XVI%20Open%20Cup%20named%20after%20E.V.%20Pankratiev%20Grand%20Prix%20of%20Bashkortostan TheWaySoFar]

 * [https://icpc.camp/dreadnought/XVI%20Open%20Cup%20named%20after%20E.V.%20Pankratiev.%20Grand%20Prix%20of%20Bashkortostan Dreadnought]

流水账

签完到后sub和周任飞单挑几何，不幸败北。

chenjb

今天前期没什么问题，做K不做B也是根据榜和几何选手想法合理的选择。周任飞的说法：当时两个几何题，电脑上dp还没写完，感觉B题虽然难，但是不占机时，所以做他更应当。周任飞的说法我觉得可以记下来，这是个很经典的封榜战略选择。

oipotato

subconscious

题解

• A：每次拿一行或一列除了问号之外只有一种字母的，把这行或列直接变成问号，把操作过程反着输出即可。
• B：sub
• C：枚举公比，暴力判定。
• D：暴力枚举，O(1)取区间max。
• E：显然后一半的人两两不能相邻，由于有k+1个这样的数，所以只能放在奇数位，f[i][mask]表示大的数字的前i个放好了，位置是mask的方案数。转移的时候把mask解码，暴力进行判断和系数计算。
• F：分治求出挖掉一个点的图的floyd结果，每个答案枚举两个出度，更新。
• G：
• H：大力用stl库模拟。
• I：把所有可能的初始情况都存下来，每次根据结果看哪些初始情况对应的符合，如果某一次可以判定必胜，则all-in，log级别。
• J：背包求出第一种体系下和为k时第二种体系最大值，用bitset存方案，之后反过来再做一次。
• K：结论是只需要考虑不与初始边交叉的边，直接最小生成树。找边的方法对每个点极角排序，扫的过程中维护线段到点的距离，这里注意方法和常数。
• L：a偶数变成bc，再变回a，a奇数的时候变成cb，然后变回a，注意long long。
• M：f[i][mask]代表目前在第i个位置，mask 3进制代表每一列目前1的状态，倒过来dp，每次查询的时候用dp值来断定即可。
• TheWaySoFar
• Dreadnought

附加文件

• 1.png by chenjb