Day 1
A
行列分别处理,随便枚举一下哪个坐标转完之后最小即可。
B
一种构造方案是:将 1
看成 (
,0
看成 )
,然后跑一个循环的括号匹配,把匹配上的右括号传过去。
第二遍把 1
看成 )
,0
看成 (
做一个对称的操作即可。
杜老师告诉我,这个模型是一个 Hypercube,然后做 Hypercube 的 symmetric decomposition,找到输入集合的补集在链上的对称点即可。
C
考虑分的两个子序列,它们值域有交的第一个位置,容易发现之后一定可以取到理论上界,也就是答案为:该位置前的答案 + 满足所有元素小于子序列 1 的 min 的最长下降子序列长度 + 满足所有元素大于子序列 2 的 \max 的最长上升子序列长度。
在这个位置之前,两部分值域不交,一定只有 O(n) 种情况,用线段树维护转移,每次将一个状态分裂成两个状态。对于最长上升子序列和最长下降子序列,倒着用线段树做一遍这个过程,把修改看做一些区间加,然后正着做的时候倒过来模拟这些区间加即可。
时间复杂度 O(n\log n)。
D
把集合放到 Trie 上考虑 mex-极限。不妨设当前子树中有数不存在于集合中,分类讨论:
- 左儿子没有满:mex-极限和左儿子的 mex-极限相等;
- 左儿子满了,右儿子中最小的数 2^k 存在:mex-极限和右儿子的 mex-极限相等;
- 左儿子满了,右儿子中最小的数 2^k 不存在,最大的数 2^{k+1}-1 不存在:mex-极限是 2^k;
- 左儿子满了,右儿子中最小的数 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)。