计数题乱做

标签：le argmax text 计数 3n max 题乱

计数水平下滑非常严重，于是来练计数题了。

[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)\) 的。

做法好像没有任何启发性呢

标签：le,argmax,text,计数,3n,max,题乱
From： https://www.cnblogs.com/ducati/p/17083790.html