2016-E21-team1

从 Trac 迁移的文章

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

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||Failed test||
||15||4:59:47||3165||C||g++0x||Wrong answer||1||
||14||4:55:55||2924||C||g++0x||Time-limit exceeded||25||
||13||4:32:25||2798||C||g++0x||Wrong answer||6||
||12||3:07:19||2070||E||g++0x||OK||N/A||
||11||2:36:19||1869||J||g++0x||OK||N/A||
||10||2:04:00||1145||B||g++0x||OK||N/A||
||9||2:00:30||674||G||g++0x||OK||N/A||
||8||1:45:44||1243||B||g++0x||Wrong answer||14||
||7||1:28:41||1248||H||g++0x||OK||N/A||
||6||1:02:32||1170||D||g++0x||OK||N/A||
||5||0:57:54||1084||D||g++0x||Wrong answer||12||
||4||0:33:20||177||K||g++0x||OK||N/A||
||3||0:31:52||935||F||g++0x||OK||N/A||
||2||0:19:49||866||A||g++0x||OK||N/A||
||1||0:17:28||866||A||g++0x||Time-limit exceeded||31||

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

start at 16:15

== 流水账 ==

=== sfiction ===

AD各看错一次题，宛如智障……

== 总结 ==

== 题解 ==

=== A. Array Factory [sfiction] ===

对n+1个前缀和（包括0）排序后从大到小求固定区间尾部的最优解。O(nlogn)。

=== B. Purchases and Bonuses [sfiction] ===

首先将每步的策略分为四种：1.全额现金 2.全额积分 3. 用尽积分 4. 不用尽积分。易见123都是唯一的，而4中存在变量。

一定存在没有4的最优解。证明：考虑4第一次出现的位置为i。如果i+1..n中存在3/4，则可以将本次所用积分保留到那些位置使用，解不会更劣。然后便归约到i+1..n中不存在3/4的情形。此时可以在本次使用更多积分，即使导致i+1..n中有些位置积分不足，解也不会更劣。

由于p很小，积分不会超过1e5，可以DP。dp[i][j]表示购买了前i件，当前积分为j的最少支付。按上述三种操作转移即可。注意要保证转移意义的正确性，当j=0时只能全额现金，不能转移到dp[i+1][0]。O(n^2^P/100)。

=== C. Number of Solutions [JTJL, Akalm] ===

像2-sat那样建图，然后遍历一次算出每个点确定状态后，能推导出多少其它点的状态。接下来做一遍度数优先的记忆化搜索就好了。

=== D. Cutting Potatoes [sfiction] ===

枚举上限，令其他物品都恰好小于等于上限即可。n很小，暴力n^2^k应该也可以过。我的实现是用分数类+大根堆，每次令最大值的划分次数+1，手动维护最小值。顶部元素划分次数=k时即终止。O(nklogn)。

=== E. Divide and Conquer [JTJL] ===

DFS枚举每一位，DP计数。

=== F. Doubling [JTJL] ===

奇数-1，偶数/2（小范围区间打牌，不知道有没有必要）

=== G. New Collection [JTJL] ===

统计有多少不同的数出现了，分段~~人肉~~学习

=== H. Path or Coloring [Akalm] ===

先做染色问题，每个点从相邻颜色中取mex作为自身颜色；如果这种方法失败，就能从第一个染色失败的点开始找一条简单路径。

=== J. Timer [sfiction] ===

题意比较难懂，标记位于0&1两行。数字位于3-10，只有5的倍数。两者均表示分钟数。秒数需要通过标记的位置来确定。比较简单的做法是先将整个圆柱侧面的图形绘制出来，然后暴力匹配，注意顶部和底部三行要忽略首尾部分。

=== K. Ultraprime Numbers [Akalm] ===

U-Prime只有9个。

== 补题 ==

CI
Run IDTimeSizeProblemLanguageResultFailed test
154:59:473165Cg++0xWrong answer1
144:55:552924Cg++0xTime-limit exceeded25
134:32:252798Cg++0xWrong answer6
123:07:192070Eg++0xOKN/A
112:36:191869Jg++0xOKN/A
102:04:001145Bg++0xOKN/A
92:00:30674Gg++0xOKN/A
81:45:441243Bg++0xWrong answer14
71:28:411248Hg++0xOKN/A
61:02:321170Dg++0xOKN/A
50:57:541084Dg++0xWrong answer12
40:33:20177Kg++0xOKN/A
30:31:52935Fg++0xOKN/A
20:19:49866Ag++0xOKN/A
10:17:28866Ag++0xTime-limit exceeded31

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

start at 16:15

流水账

sfiction

AD各看错一次题，宛如智障……

总结

题解

A. Array Factory [sfiction]

对n+1个前缀和（包括0）排序后从大到小求固定区间尾部的最优解。O(nlogn)。

B. Purchases and Bonuses [sfiction]

首先将每步的策略分为四种：1.全额现金 2.全额积分 3. 用尽积分 4. 不用尽积分。易见123都是唯一的，而4中存在变量。

一定存在没有4的最优解。证明：考虑4第一次出现的位置为i。如果i+1..n中存在3/4，则可以将本次所用积分保留到那些位置使用，解不会更劣。然后便归约到i+1..n中不存在3/4的情形。此时可以在本次使用更多积分，即使导致i+1..n中有些位置积分不足，解也不会更劣。

由于p很小，积分不会超过1e5，可以DP。dp[i][j]表示购买了前i件，当前积分为j的最少支付。按上述三种操作转移即可。注意要保证转移意义的正确性，当j=0时只能全额现金，不能转移到dp[i+1][0]。O(n2P/100)。

C. Number of Solutions [JTJL, Akalm]

像2-sat那样建图，然后遍历一次算出每个点确定状态后，能推导出多少其它点的状态。接下来做一遍度数优先的记忆化搜索就好了。

D. Cutting Potatoes [sfiction]

枚举上限，令其他物品都恰好小于等于上限即可。n很小，暴力n2k应该也可以过。我的实现是用分数类+大根堆，每次令最大值的划分次数+1，手动维护最小值。顶部元素划分次数=k时即终止。O(nklogn)。

E. Divide and Conquer [JTJL]

DFS枚举每一位，DP计数。

F. Doubling [JTJL]

奇数-1，偶数/2（小范围区间打牌，不知道有没有必要）

G. New Collection [JTJL]

统计有多少不同的数出现了，分段人肉学习

H. Path or Coloring [Akalm]

先做染色问题，每个点从相邻颜色中取mex作为自身颜色；如果这种方法失败，就能从第一个染色失败的点开始找一条简单路径。

J. Timer [sfiction]

题意比较难懂，标记位于0&1两行。数字位于3-10，只有5的倍数。两者均表示分钟数。秒数需要通过标记的位置来确定。比较简单的做法是先将整个圆柱侧面的图形绘制出来，然后暴力匹配，注意顶部和底部三行要忽略首尾部分。

K. Ultraprime Numbers [Akalm]

U-Prime只有9个。

补题

CI