[ARC128D] Neq Neq 题解

不难考虑设 \(f_i\) 表示现在处理了前 \(i\) 个数，第 \(i\) 个数必选得到的方案数。由于 \(a_n\) 不可能被删掉（需要一个 \(a_{n+1}\)），所以答案即为 \(f_n\)。

对 \(f_i\)，我们考虑前一个被保留的数 \(j\)，问题转化成被 \(i,j\) 夹住的一段连续的数可不可以全部删掉，分类讨论：

1. \(j=i-1\)：啥都没夹，当然能全删了。
2. 有两个相同颜色的数相邻：肯定不行，因为这两个数互相锁死了。
3. 相邻数互不相等：
   1. 有两种颜色：那么只可能形如 b|abababab|a，这种情况能够全删只可能是 a|b|a。因为只要中间那段长度大于 \(1\) 后，随便删掉哪个数都会变成第二种情况。
   2. 有三种及以上颜色：那么最坏情况下也肯定形如 a|babacabab|a，我们单独把 c 拿出来，可以发现，我们只要以 c 为中心，不断地消除左边和右边的数即可。

我们现在就能判断一段数能不能被删了，现在只剩下一个问题：怎么快速寻找 \(j\)？

由于不能有两个相同颜色的数相邻，所以在扫描序列的过程中，只要出现了 \(a_{i-1}=a_i\)，那么之后的数就不能扫描到 \(i-1\)，因为扫到那里就会出现相邻同颜色，于是我们解决了这个问题。

至于判断颜色种数，你直接双指针不就完了。/cf/cf/cf。