UCUP 5. Stage 1: Nizhny Novgorod
VP。
| ID | Diff | Description | Solution | Penalty | Review |
|---|---|---|---|---|---|
| B | Hard | (1) 对非负序列 ,重复操作:选择 ,若 为奇数则停止,否则将 同时变为 。:停止前操作次数的最小值。 (2) 长序列 ,求 。 | (1) 若 ,答案为 ,其中设 。 | 182+3 | |
| 长非负序列 ,重复操作:选择排列 ,同时更新 ,然后任选一个元素删除,将其余元素拼接。最大化 次操作后剩余的元素。 | |||||
| E | Easy | 长初始全为 的序列 。重复操作:等概率随机选择未锁定的下标 ,令 增加 ,随后永久锁定任意下标。当序列严格递增时终止。求最优策略下最小期望轮数。 | 没有几何分布。若第一步选中 ,则需要 ;否则需要 。。 | 15 | |
| G | Expert | 长序列 ,值域 ,均匀随机生成。选手参与 轮游戏,初始得分 ,每轮实时决定是否令 。已知选手策略:认为 均匀分布,选择能最大化期望得分的操作,若期望得分相同则选择异或。求排列 最小化选手期望得分。 | (1) 由于 均匀分布,那么 也均匀分布,因此当 时选手策略是操作。 (2) 答案大概率为 。最优时,highbit 不降,每个 highbit 恰有第一个数被操作。 (3) 问题化为:每个 highbit 取一个数,异或和最小。分组 FWT。 | * | |
| K | Easy | 长非负序列 ,构造 ,满足从 的非空子集中均匀随机取一个 ,则 。 | 若存在 0,取 ;若序列全为 1,取 ;否则,反复删去 1(比例考虑空集时,删去 1 不影响 的比例),得到只能是 或 。 | 25 | |
| L | Expert | 点图。 个三元点对,每个点出现恰好 次。删除一个点对,再从剩余每个点对中各删除一个点,得到 个二元点对,连边后构成一棵树。 | (1) 考虑有向树,树上每个非根点需要一条入边。需要给每个点 分配一个点对 ,再指定父节点 形成生成树,特别地,被删去的点对作为根,不需要分配父节点。 (2) 对于前者,以原图点 为左部点,点对下标 为右部点建立二分图。这是 正则二分图,有完美匹配。 (3) 对于后者,将可选的父子关系画成有向边,对于点对 匹配节点 ,父节点可以是 或 ,连接 及 ,得到一个入度等于出度的弱连通有向图,这必然强连通,可以定根并找到外向生成树。 | * | |
本部落格所有文章除特別聲明外,均採用CC BY-NC-SA 4.0 授權協議。轉載請註明來源 小明の雜貨屋!
評論