跳至主要內容

ICPC 2024 沈阳区域赛(Shenyang Regional)部分题解:<br>B. Magical Palette<br>D. Dot Product Game<br>G. Guess the Polygon<br>H. Guide Map<br>I. Growing Tree

Wallbreaker5th大约 4 分钟OI×ICPCOI×ICPCOI×ICPC - 题解OI×ICPC - 构造OI×ICPC - 数论OI×ICPC - 博弈论OI×ICPC - 计算几何OI×ICPC - 交互题OI×ICPC - 树状数组OI×ICPC - 树形DPOI×ICPC - 枚举

注意

题解写得可能非常抽象。

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

B. Magical Palette

题意

给定 nnmm,构造 a1,a2,,ana_1,a_2,\ldots,a_nb1,b2,,bmb_1,b_2,\ldots,b_m (0ai,bj<nm)(0\leq a_i,b_j<nm) 使得 aibjmodnma_ib_j\mod nm 互不相同。nm106nm\leq 10^6

题解

n,mn,m 互质时,构造 ai=1+ima_i = 1+imbj=1+jnb_j = 1+jn 即可。大胆猜想不互质时无解。证明就看官方题解吧。

D. Dot Product Game

题意

给两个 11nn 的排列 AABB,Alice 和 Bob 轮流操作,Alice 先操作,Alice 只能操作排列 AA,Bob 只能操作排列 BB,每次操作可以选两个元素交换,使得点积严格变大,不能操作的输,问最优策略下谁赢。

另有 (n1)(n-1) 次修改操作,每次选取其中一个排列的区间 [l,r][l,r]kk 次区间左移。1n5×1051\leq n\leq 5\times 10^5

题解

点积严格变大即交换一个逆序对;一次交换后逆序对的奇偶性一定变化,因此答案只取决于逆序对的奇偶性。一次修改只需要观察 k(rl)k(r-l) 的奇偶性即可得知答案奇偶性的变化。

G. Guess the Polygon

题意

乱序给出一个简单多边形的 nn 个顶点,每次可以询问竖直线 x=p/qx=p/q 与简单多边形的相交部分总长,交互器以分数形式 r/sr/s 返回结果,要在 (n2)(n-2) 次询问内求出简单多边形的面积,以分数形式 u/vu/v 输出。3n10003\leq n\leq 1000,坐标是 [0,1000][0,1000] 内的整数。

题解

我们对“竖线在多边形内的长度”做积分。这是一个分段线性函数。

  • 如果某两点的横坐标相同,这个函数可能在此有一个间断点。我们查询其 ±ϵ\pm \epsilon 处的值
  • 否则,我们查询这个点的值
  • 最左、最右的点,如果是单独的,这个值一定是 00;否则,我们查询其一侧 ±ϵ\pm \epsilon 处的值 这样,我们可以得到每一段的积分结果。

注意到交互库返回的分母可能很大,但由于答案一定是 0.50.5 的整数倍,使用浮点运算或者取模都可以在最后得到准确的结果。

H. Guide Map

题意

给定一张 nn 个点的完全图,给定 (n2)(n-2) 条特殊边,这些特殊边构成两棵树。计算完全图中选取边的子集的方案数,使得从 11 出发按照点编号顺序 DFS 遍历边导出子图时可以经过所有特殊边,同时只经过不多于一条不同的非特殊边。答案对 998244353998244353 取模。n2×105n\leq 2 \times 10^5

题解

先考虑我们如果有 n1n-1 条特殊边组成一棵有根树,我们要额外选哪些边。对于边 uvu\to v,我们 uu 可以选择 vv 里面所有编号大于 vv 的点连过去;即统计除了根以外,每个点的子树内比它大的点的个数的和。设这个和为 ss,那么方案数为 2s2^s

现在考虑两棵树,假设我们选入了一条特殊边 pqp\to q 放进树里,其中 pT1,qT2p\in T_1, q\in T_2。我们考虑有多少边可以放进来:

  • T1T_1 内部的边:考虑方式如上。这一部分为常数
  • T2T_2 内部的边:统计的内容跟上面的类似,但是要对所有根求。这一部分只与 qq 有关
  • T1T_1T2T_2 之间的边:对于 pp 和其所有非 11 祖先 iiii 都可以往 T2T_2 中大于 ii 的点连边。这一部分只与 pp 有关

借助几个树状数组,可以把这三部分都统计出来。答案即为 f1(pf2,p)(qf3,q)f_1 \left(\sum_p f_{2,p}\right) \left(\sum_q f_{3,q}\right)

I. Growing Tree

题意

给出一棵有 nn 层边的满二叉树的所有边的边权,初始这棵树只有根,接下来 nn 天,每天上午会新生长出一层,每天下午可以选择至多一条边将其边权修改为任意正整数,要修改最少的边使得 nn 天后根到每个叶子的简单路径的边权和两两不同,或判定无解。n10n\leq 10

题解

自底向上合并,记录每个子树里、到根路径上没有边被修改的边权集合。当两个子树合并,如果没有冲突则不管他,如果有冲突,则需要在两个子树里面选一个修改,另一个向上传。每向上一层会多一次修改的机会,如果修改的次数不够用了,那么无解。

注意到上面的做法需要决策每次到底取哪个子树向上传,2n2^n 枚举即可。