跳至主要內容

The 2nd Universal Cup Semifinals 部分题解

Wallbreaker5th大约 3 分钟OI×ICPCOI×ICPC - 题解OI×ICPC - DPOI×ICPC - 交互题OI×ICPC - 二分OI×ICPC - 博弈论OI×ICPC - 位运算OI×ICPC - 贪心OI×ICPC - 高精度

注意

题解写得可能非常抽象。

「如果一个题解你看不懂,那是题解垃圾而不是你垃圾。」

比赛链接:UCupopen in new window

A. Records in Chichén Itzá

题意

给定一个度数序列,问是否存在两颗不同构的树都满足这个度数序列。n105n\leq 10^5

题解

存在当且仅当:

  • 度数序列中存在至少 44 个大于 22 的数;或
  • 度数序列中存在至少 33 个大于等于 22 的数,且不完全相同。

C. Space Station

题意

nn 次攻击,已知 aia_i,每次的强度为 aia_i 的一个 shuffle(n!n! 种)bib_i。每次攻击来之前,你可以决定是用 mm 的代价拦住这次攻击还是用 bib_i 的代价在攻击之后处理;来之后你就知道这次攻击的 bib_i。求最优策略下的最小期望代价。n,m100,ai200n,m\leq 100, a_i\leq 200

题解

每次决策选择 mm 和剩余 bib_i 平均值中较小的一个。即答案为 1n!bi=1nmin(m,j=1ibji)\frac{1}{n!} \sum_{b} \sum_{i=1}^{n} \min \left(m, \frac{\sum_{j=1}^{i} b_j}{i} \right)。DP f[i,j]f[i,j]ii 个数和为 jj 的方案数,答案为

1n!i=1nj=1Vmin(m,ji)f[i,j]i!(ni)! \frac{1}{n!} \sum_{i=1}^{n} \sum_{j=1}^{V} \min \left(m, \frac{j}{i} \right) f[i,j] i! (n-i)!

G. CNOI Knowledge

题意

交互题。有一个长为 nn 的串 ss,内容未知。你可以询问 1000010000 次,给出 l,rl,r,返回 s[l..r]s[l..r] 的不同子串的个数。给出一个可能的 ssn1000n\leq 1000

题解

一个一个字符加。每次二分当前字符上次出现的位置,靠比较询问 (m,i)(m, i) 和求 (m,i1)(m,i-1) 的结果来判断。

K. Game: Battle of Menjis

题意

有一个长为 nn 的非负整数序列,Alice 和 Bob 轮流操作,共 kk 轮:

  • Alice 找一个位置,将其加一
  • Bob 找一个大于零的位置,将其减一 Alice 希望结果的异或和最大,Bob 希望结果的异或和最小。求最优策略下结果的异或和。n105,k109,ai109n\leq 10^5, k\leq 10^9, a_i\leq 10^9

题解

无论 kk 等于多少,结果都和 k=1k=1 一样:

  • Bob 可以保证结果小于等于它:前 k1k-1 轮操作,Bob 都把 Alice 的操作抵消掉,从而只在最后一轮用自己的最优策略
  • Alice 可以保证结果大于等于它:Alice 在第一次操作,用 k=1k=1 时的最优策略,之后每次 Bob 的操作都抵消掉,最后 Bob 会进行一次操作。

枚举 Alice 的操作,Bob 的操作相当于将结果异或一个 0...01...1,可行的操作取决于数的 ctz、只有 log\log 种,简单维护一下所有数的 ctz 的集合即可。

M. Puzzle: Summon

题意

有一个 2×2n2\times 2n 的矩阵,每 2×22\times 2 为一宫。一个合法的填数方案满足:

  • 里面只有 1122 和空格子
  • 每一宫恰有一个 11 和一个 22
  • 相同的数不相邻(八连通) 一个填数方案的分数为第一行从左往右读,所有数的和(中间没有空格子的数字可以连成一个多位数)。给出一个已经填入一些数的矩阵,求最大的分数,或输出无解。n105n\leq 10^5

题解

先不考虑每一个数在第一行还是第二行,整个矩阵分为三个阶段:

  • 宫里的两个数都在左边
  • 宫里的两个数一左一右
  • 宫里的两个数都在右边

枚举中间阶段是 12 交替还是 21 交替,让中间阶段尽可能长、然后所有数尽可能放在第一行,即可得到最大的分数。

Python 似乎会因为整数 += 复杂度是两个整数长度较大值而 TLE。