专栏文章

题解：CF2091G Gleb and Boating

沉沉石鱼惊旋山有木兮
CF2091G题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mipt4qoi
此快照首次捕获于
2025/12/03 17:31
3 个月前
此快照最后确认于
2025/12/03 17:31
3 个月前
查看原文

题意

你需要在 [0,s][0,s] 的数轴上移动。不能超出这个范围。初始步长是 kk。初始默认方向是 0→s0\to s。即 pp 走一步走到 p+kp+k。转弯一次会令 k←max⁡{k−1,1}k\gets \max\{k-1,1\}。转弯一次是从 pp 走一步走到 p−kp-k，以此类推。
问到达 ss 时最后的 kk 最大是几。
多测，1≤t≤1001\leq t\leq 100，1≤s≤1091\leq s\leq 10^9，1≤k≤10001\leq k\leq 1000，1≤∑k≤20001\leq \sum k\leq 2000。

做法

ss 很大的时候显然有通解。s≥k2s\geq k^2 的时候若 k∣sk\mid s 则答案就是 kk。否则答案是 max⁡{k−2,1}\max\{k-2,1\}。
考虑直接走到 k⌊s/k⌋k\lfloor s/k \rfloor 的位置。即最后一个 kk 的倍数。此时剩下的距离设为 r=s mod kr=s\bmod k。
r=0r=0 直接判掉答案为 kk。
对于 r≠0r\neq 0 的情况分讨如下。
若 r<k−2r\lt k-2，考虑到我们往后一步往前一步相当于后退一步，往后 pp 步往前 pp 步就是后退 pp 步。我们总能找到一个 pp 满足 r+p=k−2r+p=k-2，且由于 s≥k2s\geq k^2 所以 p(k−1)≤k⌊s/k⌋<k2p(k-1)\leq k\lfloor s/k \rfloor\lt k^2。
若 r=k−2r=k-2，我们往后退 k−2k-2 步然后往前就是一个解。显然有 k−2∣(k−2)(k−1)+(k−2)k-2 \mid (k-2)(k-1)+(k-2)。
若 r=k−1r=k-1，我们往后退 k−3k-3 步然后往前就是一个解。显然有 k−2∣(k−3)(k−1)+(k−1)k-2 \mid (k-3)(k-1)+(k-1)。
所以 s≥k2s\geq k^2 总能找到 kk 或 k−2k-2 作为答案。
若 s<k2s\lt k^2 则在数据范围下有 s<106s\lt 10^6。而我们有显然的状态设计 fi,jf_{i,j} 表示步长为 ii 时是否可以走到 jj。转移就枚举走几个 ii，直接做难以通过。
但是可以直接 bitset 优化。其实跑得很快。
wuxigk在这篇题解底下的回复（经过格式修复）：
复杂度算错了吧，外层调和级数是 s+s/2+⋯+s/ks+s/2+\dots +s/k，乘上单次 bitset 的 s/ws/w，是 s2log⁡k/ws^2\log k/w，正确的 bitset 优化应该是移 1 次 2 次 4 次 8 次这样吧。
我先阐述一下为什么我这个 DP 跑的很快。
考虑到 s≥k2s\geq k^2 的时候答案是不小于 k−2k-2，所以答案是 s\sqrt s 量级的。
这个 DP 实际运算量是 O(∑sks2/i/w)\mathcal O(\sum\limits_{\sqrt s}^k s^2/i/w) 的，打个表跑一下其实大概是 2×1010/w2\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，但是这个题我本地拍了十万组没拍出来有锅），或者说开若干个大小为 22 的幂的 bitset 每次选一个刚好够的用一下，或者直接手写一个。

代码

感谢 wuxigk指出的复杂度分析问题以及更优的 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;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...