题解：CF2091G Gleb and Boating
沉石鱼惊旋
·
·
题解
题意
你需要在 [0,s] 的数轴上移动。不能超出这个范围。初始步长是 k。初始默认方向是 0\to s。即 p 走一步走到 p+k。转弯一次会令 k\gets \max\{k-1,1\}。转弯一次是从 p 走一步走到 p-k，以此类推。
问到达 s 时最后的 k 最大是几。
多测，1\leq t\leq 100，1\leq s\leq 10^9，1\leq k\leq 1000，1\leq \sum k\leq 2000。
做法
考虑直接走到 $k\lfloor s/k \rfloor$ 的位置。即最后一个 $k$ 的倍数。此时剩下的距离设为 $r=s\bmod k$。
$r=0$ 直接判掉答案为 $k$。
对于 $r\neq 0$ 的情况分讨如下。
若 $r\lt k-2$，考虑到我们往后一步往前一步相当于后退一步，往后 $p$ 步往前 $p$ 步就是后退 $p$ 步。我们总能找到一个 $p$ 满足 $r+p=k-2$，且由于 $s\geq k^2$ 所以 $p(k-1)\leq k\lfloor s/k \rfloor\lt k^2$。
若 $r=k-2$，我们往后退 $k-2$ 步然后往前就是一个解。显然有 $k-2 \mid (k-2)(k-1)+(k-2)$。
若 $r=k-1$，我们往后退 $k-3$ 步然后往前就是一个解。显然有 $k-2 \mid (k-3)(k-1)+(k-1)$。
所以 $s\geq k^2$ 总能找到 $k$ 或 $k-2$ 作为答案。
若 $s\lt k^2$ 则在数据范围下有 $s\lt 10^6$。而我们有显然的状态设计 $f_{i,j}$ 表示步长为 $i$ 时是否可以走到 $j$。转移就枚举走几个 $i$，直接做难以通过。
但是可以直接 bitset 优化。其实跑得很快。
---
@[wuxigk](https://www.luogu.com.cn/user/287029) 在这篇题解底下的回复（经过格式修复）：
>复杂度算错了吧，外层调和级数是 $s+s/2+\dots +s/k$，乘上单次 bitset 的 $s/w$，是 $s^2\log k/w$，正确的 bitset 优化应该是移 1 次 2 次 4 次 8 次这样吧。
我先阐述一下为什么我这个 DP 跑的很快。
考虑到 $s\geq k^2$ 的时候答案是不小于 $k-2$，所以答案是 $\sqrt s$ 量级的。
这个 DP 实际运算量是 $\mathcal O(\sum\limits_{\sqrt s}^k s^2/i/w)$ 的，打个表跑一下其实大概是 $2\times 10^{10}/w$ 的，可以轻松通过。
wuxigk 指出的做法，正如本文章代码部分所说，我尝试写了一个然后 WA 了一个很大的点，应该是这个做法下使用 `std::tr2::dynamic_bitset` 被叉了。我的这个 DP 能过只是因为本题答案的特性。如果真的想要学习正常的 bitset 优化，还是得写这个做法。另外这里也征求一份写了这个做法的代码 qaq。
---
多测可以用 `std::tr2::dynamic_bitset`（这个东西大概是唯一一个 OI 赛场上能直接用的动态 bitset，但是有 bug，参考 <https://codeforces.com/blog/entry/129454>，但是这个题我本地拍了十万组没拍出来有锅），或者说开若干个大小为 $2$ 的幂的 bitset 每次选一个刚好够的用一下，或者直接手写一个。
# 代码
感谢 @[wuxigk](https://www.luogu.com.cn/user/287029) 指出的复杂度分析问题以及更优的 bitset 优化。但是我写挂了（流汗。WA 了一个很后的点，大抵是 `dynamic_bitset` 的 bug 在这种做法下体现出来被叉掉了。这份代码还是文中的暴力转移。
<https://codeforces.com/contest/2091/submission/312735736>
```cpp
#include <bits/stdc++.h>
#include <tr2/dynamic_bitset>
using namespace std;
using namespace tr2;
void solve()
{
int s, k;
cin >> s >> k;
if (s >= k * k)
return cout << (s % k ? max(1, k - 2) : k) << '\n', void();
vector<dynamic_bitset<>> f(k + 1);
for (int i = 0; i <= k; i++)
f[i].resize(s + 1);
for (int i = 0; i <= s; i += k)
f[k][i] = 1;
for (int i = k; i >= 2; i--)
{
if (f[i][s])
return cout << i << '\n', void();
if (k - i & 1)
{
for (int j = 0; j <= s; j += i - 1)
f[i - 1] |= (f[i] <<= i - 1);
}
else
{
for (int j = 0; j <= s; j += i - 1)
f[i - 1] |= (f[i] >>= i - 1);
}
// cout << i - 1 << '\n';
// for (int j = 0; j <= s; j++)
// cout << f[i - 1][j] << ' ';
// cout << '\n';
}
cout << 1 << '\n';
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
```