10.01 ~ 10.03 做题记录

· · 个人记录

由于神秘原因,之前的 blog 被覆盖了,2w 字的做题记录全没了 /ll

只留下这么点东西 /fn

【1+】XXS0103 局部函数

一个基本的刻画是,考虑相邻项 u,v,若 x_u 的更新时刻早于 x_v 则连边 u \to v,建图是有向链。

取任意拓扑序均可得到唯一的 x_1 \sim x_n。考虑 O(4^n) 枚举 x_1 \sim x_n,根据上述刻画设计内层 DP:

只要记录 (x_{i-1},x_i,f_{0,i-1}, f_{1,i-1}) 四元组,内层 DP 就能建模为 DFA,状态信息量 4^2 \times 2^2=64。考虑外层 DP:

复杂度 O(k^3 n),其中 k=4。代码。

:::::error[为啥不会做] 一个主要问题是,没想到有向链的刻画。

赛时略想一下先判定后计数,觉得不可做就否掉了,一直在区间 dp,自然是不可能会做的 /ll

【1+】XXS0104 rplrprq

只有 +\text{lowbit} 的操作,可以势能线段树直接维护。本题不能直接做的原因是,+1 会破坏势能。

可以用线段树套 01-Trie 维护,使用子树 +v 的 trick,时间 O(n \log n \log V+q \log^2 n\log V),空间 O(n \log n \log V) 没有通过的风险。

考虑分析性质。对区间 [l,r],取最大的 k 使得 i \in [l,r], a_i \bmod 2^k 全相等,二进制下即为低 k 位相同。任取 a_x \in [l,r] 作为代表元,整体 +\text{lowbit} 时:

用线段树维护区间和,区间代表元,区间的 k 值,这些信息构成交换半群,再打标记处理区间加法。

将所有节点的 \log V-k 相加作为势能进行分析,可以均摊到 O(n \log V+q \log n \log V) 的复杂度,容易通过本题。代码。

:::::error[为啥不会做] 赛时被 l=1,r=n 和全局 +1 误导了,一直在 01-trie,并且我见过子树 +v 这个 trick,胡出来 2log 以后就在尝试套线段树,最后发现只开 trie 都开不下。这个时候没时间了,拼好分去了。 :::::

【1+】QOJ12180 Point Divide and Conquer

正着做删点不好维护。不妨时光倒流,倒着扫 p 序列改为加点。加点会合并若干连通块,将这些块的根标记为当前 p_i,用并查集维护即可。代码。

【1+】P17215 [ICPC 2017 Nanning R] The Champion

不妨设 p \ge \frac{1}{2},称 1 \sim k-1 为强者,k+1 \sim 2^r 为弱者,同类之间没有区分。打强者的获胜概率为 1-p,打弱者的获胜概率为 p。

贪心策略是,令 k 尽量与弱者打,同类内部消耗。记 x 个强者 y 个弱者的答案为 f(x,y),考虑递推:

注意到每轮递归 x,y 折半,直接记搜下去,复杂度 O(\log r) 可以通过。

【1+】QOJ12102 Hedgehog Daniyar and Algorithms

观察 可以排序,当且仅当任意逆序对和 \le k,形式化地 \forall i,j \in [l,r] ,i < j\land a_i>a_j, a_i+a_j \le k。

证明 每个逆序对必须被邻项交换,必然性易得。冒泡排序的过程只交换逆序对,充分性可证。

将问题强化为,区间查询 \max\limits_{i<j\land a_i>a_j} (a_i+a_j) 与 k 比较。离线对 r 扫描线,令 j=r 更新每个 i 的答案

f_i \gets a_r+\max_{a_i>a_r} a_i

用单调栈维护 a_i 的前缀 \max,加入 r 时先弹掉栈顶,注意到只更新 \max 的答案不劣,只对栈顶更新 f 值即可。

用线段树维护 f 数组,支持前缀 chkmax 单点查询,视 n,q 同阶复杂度 O(n \log n)。代码。

【1】CF1485F Copy or Prefix Sum

容易列得朴素 DP:

对 f 滚动数组,考察上述转移:

用哈希表维护 f 数组,记录偏移量与 \sum f 即可。复杂度 O(n \log n)。代码。

【2】CF626F Group Projects

将 a_i 升序排序后逐个加点。可以列得延迟钦定 DP:

第三维 S \in [-nV, k],故复杂度 O(n^3 V) 无法通过。

考虑微元贡献法 a_r-a_l=\sum\limits_{i=l+1}^r (a_i-a_{i-1}),令 i 决策后立刻计算微元 a_i-a_{i-1} 的贡献。

令 S'=S+x(a_i-a_{i-1}),再转移到 f_{i,x',S'} 只需保留 S' \ge 0 的部分即可。

复杂度 O(n^2 k) 足以通过。代码。

:::::error[为啥不会做] 延迟钦定 dp 很快做明白了,但是不会做优化,一直在尝试搞前缀和,没见过这个差分 trick。 :::::