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\)
构造方法:
- 写下序列 \([a_1,a_2,a_3,....,a_k]\)
- 在序列前添上,\([1个a_2,1个a_2-1,.....,1个a_1+1]\)
- 在序列前添上,\([2个a_3,2个a_3-1,.....,2个a_2+1]\)
- 在序列前添上,\([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