The 2nd Universal Cup Semifinals 部分题解
大约 3 分钟
注意
题解写得可能非常抽象。
「如果一个题解你看不懂,那是题解垃圾而不是你垃圾。」
比赛链接:UCup
A. Records in Chichén Itzá
题意
给定一个度数序列,问是否存在两颗不同构的树都满足这个度数序列。
题解
存在当且仅当:
- 度数序列中存在至少 个大于 的数;或
- 度数序列中存在至少 个大于等于 的数,且不完全相同。
C. Space Station
题意
有 次攻击,已知 ,每次的强度为 的一个 shuffle( 种)。每次攻击来之前,你可以决定是用 的代价拦住这次攻击还是用 的代价在攻击之后处理;来之后你就知道这次攻击的 。求最优策略下的最小期望代价。
题解
每次决策选择 和剩余 平均值中较小的一个。即答案为 。DP 为 个数和为 的方案数,答案为
G. CNOI Knowledge
题意
交互题。有一个长为 的串 ,内容未知。你可以询问 次,给出 ,返回 的不同子串的个数。给出一个可能的 。。
题解
一个一个字符加。每次二分当前字符上次出现的位置,靠比较询问 和求 的结果来判断。
K. Game: Battle of Menjis
题意
有一个长为 的非负整数序列,Alice 和 Bob 轮流操作,共 轮:
- Alice 找一个位置,将其加一
- Bob 找一个大于零的位置,将其减一 Alice 希望结果的异或和最大,Bob 希望结果的异或和最小。求最优策略下结果的异或和。。
题解
无论 等于多少,结果都和 一样:
- Bob 可以保证结果小于等于它:前 轮操作,Bob 都把 Alice 的操作抵消掉,从而只在最后一轮用自己的最优策略
- Alice 可以保证结果大于等于它:Alice 在第一次操作,用 时的最优策略,之后每次 Bob 的操作都抵消掉,最后 Bob 会进行一次操作。
枚举 Alice 的操作,Bob 的操作相当于将结果异或一个 0...01...1
,可行的操作取决于数的 ctz
、只有 种,简单维护一下所有数的 ctz
的集合即可。
M. Puzzle: Summon
题意
有一个 的矩阵,每 为一宫。一个合法的填数方案满足:
- 里面只有 、 和空格子
- 每一宫恰有一个 和一个
- 相同的数不相邻(八连通) 一个填数方案的分数为第一行从左往右读,所有数的和(中间没有空格子的数字可以连成一个多位数)。给出一个已经填入一些数的矩阵,求最大的分数,或输出无解。
题解
先不考虑每一个数在第一行还是第二行,整个矩阵分为三个阶段:
- 宫里的两个数都在左边
- 宫里的两个数一左一右
- 宫里的两个数都在右边
枚举中间阶段是 12
交替还是 21
交替,让中间阶段尽可能长、然后所有数尽可能放在第一行,即可得到最大的分数。
Python 似乎会因为整数 +=
复杂度是两个整数长度较大值而 TLE。