题解:CF283D Cows and Cool Sequences

SFlyer

2024-11-15 15:11:32

Solution

口胡的。这里 x,y 是下标。

首先充要条件是 x=\frac{y(y-1)}{2}+kyk 是整数。反解 k,解出 2k=\frac{2x-y^2+y}{y},即 \frac{2x}{y}-y+1 是偶数,即 y\mid 2x\frac{2x}{y}y 奇偶性不同。

这个奇偶性不同启发我们,把数表示成 2^{a(x)}\times b(x),其中 b(x) 是一个奇数。整理一下我们的条件:(x,y) 是好的当且仅当:

第三个有点难表达,分类讨论一下:

考虑 dp。遇见「最少操作数」平常有两个着手点:dp_{i,j} 表示前 i 个最后一个是 j 的最小次数,这个显然不可做;dp_{i} 表示 i 一定不改变,最小次数,枚举上一个不改变的 j 即可。这个很好做啊!

现在就是要 \mathcal{O}(1) 判断 [j+1,i-1] 可不可以任意操作变成 [j,i] 好的。显然有充要条件: