2018 Petrozavodsk Winter Camp, Yandex Cup


A. Ability Draft

solved by RDC 60min start, 148 min AC, 1Y

题意:两只 Dota 队伍,每队 \(n\) 个英雄,英雄一开始无技能,他们需要按照给定的顺序在技能池中选技能,每个英雄需要恰选择 \(s\) 个普通技能 和 1 个终极技能,每个技能有强度值,双方都想最大化己方和对方强度值之差,双方都是明智的。

做法:注意到,每个英雄,要么选择最强的终极技能要么选择最强普通技能。考虑 DP,用 \(f[x][mask_1][mask_2]\) 表示,还有 \(x\) 个人没选技能,队伍 A 中 \(mask_1\) 中的人获得了终极技能,队伍 B 中 \(mask_2\) 中的人获得了终极技能,在此情况下队伍 A 和队伍 B 的极大分差。考虑到 \(f[x][mask_1][mask_2]\) 的转移,我们对拿终极技能还是普通技能进行决策,即可转移到 \(f[x+1][?][?]\)


C. Block, Stock and Two Smoking Galaxy Notes

solved by F0_0H 20min start, 57 min AC, 1Y


F. Shuffle

solved by sdcgvhgj 267min AC, +4


G. Piecewise Linearity

solved by sdcgvhgj 117min AC, +1


H. Sketch

solved by RDC 213min start, 256 min AC, +4

题意 构造长度为 \(n\) 的序列 \(b[]\), \(1\leq b_i \leq m\),LIS 为 \(k\),对于 \(1\leq i \leq k\)\(a_i \neq -1\),长度为 \(i\) 的不降子序列结尾元素极小值为 \(a_i\)

做法 考虑没有 -1 的 case,有解的一个必要条件是 \(a_i\) 不降,先不考虑长度为 \(n\) 的限制,那么有

  • 我们可以构造长度为 \(k\) 的序列,且 \(k\) 是下界。
  • 在序列中,\([a_k,m+1)\) 中的每个元素至多出现 \(k\) 次,\([a_{k-1},a_k)\) 中的每个元素至多出现 \(k-1\) 次 ..... \([a_1,a_2)\) 中的每个元素至多出现 1 次,根据这个性质,序列长度存在一个上界 \((a_2-a_1)+2*(a_3-a_2)+....+k*(m+1-a_k)\) = \(k*(m+1) - \sum_{i=1}^{k}a_i\)

构造方法:

  1. 写下序列 \([a_1,a_2,a_3,....,a_k]\)
  2. 在序列前添上,\([1个a_2,1个a_2-1,.....,1个a_1+1]\)
  3. 在序列前添上,\([2个a_3,2个a_3-1,.....,2个a_2+1]\)
  4. 在序列前添上,\([3个a_4,3个a_4-1,.....,3个a_3+1]\)

以此类推,因此我们证明了,下界到上界中的每个长度都是可以构造出来的。【介值定理既视感】

考虑有 -1 的 Cas,我们贪心地给 \(a_i=-1\) 的位置赋值使得上界极大即可。


K. Hiding a Tree

solved by sdcgvhgj 40min start, 64min AC, +2


2018 Petrozavodsk Winter Camp, Yandex Cup

上一篇:谈谈call(), apply(), bind()的异同


下一篇:node 基础API(Buffer)