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

原文：https://www.cnblogs.com/FST-stay-night/p/11192416.html