Kevin5307的博客

博客

ROI 2023 简要题解

2024-07-12 11:13:29 By Kevin090228

Day 1

A

行列分别处理,随便枚举一下哪个坐标转完之后最小即可。

B

一种构造方案是:将 1 看成 (0 看成 ),然后跑一个循环的括号匹配,把匹配上的右括号传过去。

第二遍把 1 看成 )0 看成 ( 做一个对称的操作即可。

杜老师告诉我,这个模型是一个 Hypercube,然后做 Hypercube 的 symmetric decomposition,找到输入集合的补集在链上的对称点即可。

C

考虑分的两个子序列,它们值域有交的第一个位置,容易发现之后一定可以取到理论上界,也就是答案为:该位置前的答案 + 满足所有元素小于子序列 1min 的最长下降子序列长度 + 满足所有元素大于子序列 2\max 的最长上升子序列长度。

在这个位置之前,两部分值域不交,一定只有 O(n) 种情况,用线段树维护转移,每次将一个状态分裂成两个状态。对于最长上升子序列和最长下降子序列,倒着用线段树做一遍这个过程,把修改看做一些区间加,然后正着做的时候倒过来模拟这些区间加即可。

时间复杂度 O(n\log n)

D

把集合放到 Trie 上考虑 mex-极限。不妨设当前子树中有数不存在于集合中,分类讨论:

  1. 左儿子没有满:mex-极限和左儿子的 mex-极限相等;
  2. 左儿子满了,右儿子中最小的数 2^k 存在:mex-极限和右儿子的 mex-极限相等;
  3. 左儿子满了,右儿子中最小的数 2^k 不存在,最大的数 2^{k+1}-1 不存在:mex-极限是 2^k
  4. 左儿子满了,右儿子中最小的数 2^k 不存在,最大的数 2^{k+1}-1 存在:此时一次操作后会将整个子树翻转,且翻转后的左子树不满,所以 mex-极限和右子树翻转之后的 mex-极限相等。

于是容易写出 DP 状态,使用 NTT 转移。

时间复杂度 O(2^k k^2)

Day 2

A

没咋看,看上去就是简单题。

B

跑一遍 DP,保留所有起点 DP 值为奇数或偶数(选择个数较多那个奇偶性)的区间,注意在最优方案中的区间需要保留,不能让答案小于 \frac{m}{2}。正确性显然。

C

将答案转化为 n(n-1)m 减去每个人到达终点之后其他人走到检查点的次数求和。注意到检查点坐标的和不大,所以可以将其按照前缀长度 \max 分成若干段,每一段贡献其实相同。

然后随便做一下,复杂度 O(n\sqrt x)

D

给一个点点权增加 1,答案最多增加 1。于是可以从全 l_i 慢慢增加到全 r_i。每个点增加的过程中一定是一段前缀对答案没影响,剩下来的后缀每次给答案 +1。用全局平衡二叉树做修改点权,查询全局最大独立集,然后容易找出这个前缀和后缀的分界点。

时间复杂度 O(n\log n)

评论

[+1]
  • 2024-07-12 16:21:24
  • Reply
徐启文,你好牛
  • 2024-07-15 08:56:37
  • Reply
[0]
/duide
  • 2024-08-17 12:50:01
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。