计数水平下滑非常严重,于是来练计数题了。
[AGC056B] Range Argmax
AGC 的 B 题要花这么久,我是普及组选手。
先考虑判定性问题,即 \(\{x_1,x_2,\cdots,x_m\}\) 何时合法。考虑先确定 \(\text{argmax}[1,n]\)。显然,\(x_p\) 能够成为 \(\text{argmax}[1,n]\),当且仅当所有包含 \(p\) 的区间的 \(\text{argmax}\) 均为 \(p\)。不妨令 \(x\) 为满足条件的 \(p\) 中最小的一个。此时 \([1,x),(x,n]\) 是独立的子问题,递归地构造即可。
再考虑计数。考虑区间 \(\text{dp}\)。令 \(f_{l,r}\) 表示 \([l,r]\) 的答案,枚举 \(x \in [l,r]\) 并钦定 \(\text{argmax}[l,r]=x\) 并从 \(f_{l,x-1},f_{x+1,r}\) 两边转移过来。但需要注意,\([l,x)\) 中不得存在满足要求的 \(p\),这要求必须存在 \([l_i,r_i]\) 同时包含 \(\text{argmax}[l,x)\) 及 \(x\)。也就是说,我们可能对 \(\text{argmax}[l,r]\) 进行了限定,从而要再加一维 \(u\) 表示要求 \(\text{argmax}[l,r] \ge u\),然后就能正常转移了。
时间复杂度 \(O(n^3)\)。
[AGC055D] ABC Ultimatum
Lemma. 有解当且仅当
\[\max_{1 \le p \le 3n} \{[1,p,B]-[1,p,A]\}+\max_{1 \le p \le 3n}\{[1,p,C]-[1,p,B]\}+\max_{1 \le p \le 3n}\{[1,p,A]-[1,p,C]\} \le n \]其中 \([l,r,c]\) 表示 \([l,r]\) 中字符 \(c\) 的出现次数。
必要性显然。充分性不管。
那么直接 \(O(n^6)\) 地 \(\text{dp}\) 就好了,维护前缀中三种字符的出现次数以及三个值,转移是 \(O(1)\) 的。
做法好像没有任何启发性呢