CF1082-div1 / Contest 2201

Div 2

Problem A

Problem B

有趣的签到题。

题解利用的是两两分组的性质。

我的是类似走格的思路，当前状态为可用 $a$ 与 $b$ 数量的差值 $(-1,0,1)$，根据奇偶判断是否可以转移到下一个非 $?$ 的位置。

Div 1

Problem A1

栈

Problem A2

考虑什么时候其产生代价

Problem B

构造

Problem C

实际上的 $\text{DP}$ 策略并没有那么复杂。 /ee

对于末尾为 $($ 的子序列一定是可行的。

如果末尾为 $)$，分情况考虑让每个位置保持非负。

对于选中的某点 $S_i$，考虑 $[S_i,S_{i+1})$ 这段区间内，值的变化量为加入的 $)$ 和被踢出的 $S_i$。如果为 $)$ 则无限制，如果为 $($ 则需要这段的总和不小于 $2$。

Problem D

关键性质：$k_{max}=\text{max}{|i-j|}(a_i=a_j)$

且如果存在 $(i,i+1,k),(i+1,i+2,k),…,(i+x-1,i+x,k)$，等价关系可以传递，产生数对总数为 $\binom{x}{2}$。

因此可以从分别从每个值的集合中选出最远的一对，按照长度在若干个 $\text{set}$ 中合并区间，取最大的计算答案。

---

E,F1,F2,G