P11499 题解

· · 题解

与现有两篇题解的思路不同，我使用了分块思维，没有写大型分讨，自认为代码和思路比较清新。

声明：此做法不卡常，其时间复杂度为 O(1)。记录。

思路

把整个添加功率的过程几何化，相当与把一个在数轴上的点从 a 移动到 b。其中 c 的倍数的点不能到达。

所有不可到达的点把数轴分成了若干段，定义其中第 k 段对应点坐标 [kc+1, kc+(c-1)]。那么点 q 所在区间编号为 \cfrac{q}{c}。

这样从 a 走到 b 可以分为三个阶段：

  1. 从 a 走到它所在区间的末尾。
  2. 从 a 所在区间的下一个区间走到 b 所在区间的上一个区间。
  3. 从 b 所在区间的开头走到 b。

当然，如果 a,b 在同一个区间，要进行特判，因为三个阶段会有重叠部分。

通过简单推导可以得出，第一段的区间为 [a, \lceil \cfrac{a}{c}\rceil \times c -1]，第三段的区间为 [\lfloor \cfrac{b}{c}\rfloor \times c+1,b]。这两段都是畅通无阻的，没有 c 的倍数的障碍，可以贪心地走。每次尽量往右走 2 格，贪心可以 O(1)，写法见代码中的 calc 函数。calc(i,j) 可以计算从点 i 走到点 j，没有障碍的情况下，最少需要多少次操作。显然将 i 和 j 同时加上或者减去一个值不影响函数值。

第二段是最麻烦的，首先得出：

然后开始暴力走。我们的目标是从 p 区间第一个位置走到 q 区间第一个位置，具体坐标在代码注释中有所呈现。这样的话，我们可以把这个过程继续拆解：

  1. 从 p 区间第一个位置走到 p 区间最后一个位置，花费 calc(1, c-1) 步。
  2. 进行一次 Y 操作，从 p 区间最后一个位置走到 p+1 区间第一个位置。
  3. 从 p+1 区间第一个位置走到 p+1 区间最后一个位置，花费 calc(1, c-1) 步。
  4. 进行一次 Y 操作，从 p+1 区间最后一个位置走到 p+2 区间第一个位置。
  5. 从 p+2 区间第一个位置走到 p+2 区间最后一个位置，花费 calc(1, c-1) 步。
  6. 进行一次 Y 操作，从 p+2 区间最后一个位置走到 p+3 区间第一个位置。
  7. ......

看到规律了吗？每两次操作为一个周期，共有 q-p 个周期，每个周期。这就是阶段二的答案。

最后把三个阶段的答案加在一起，这个题就做完了。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll a, b, c;
ll calc(ll l, ll r) {
    ll dt = r - l;
    if (dt % 2 == 0) return dt / 2;
    return dt / 2 + 1;
}
int main() {
    cin >> a >> b >> c;
    if (a / c == b / c) {
        cout << calc(a, b) << "\n";
        return 0;
    }
    ll ans = 0;
    // a -> (a / c + 1) * c - 1
    ans += calc(a, (a / c + 1) * c - 1) + 1;
    // now pos: (a / c + 1) * c + 1;
    ans += (calc(1, c-1) + 1) * ((b / c) - (a / c + 1));
    // now pos: (b / c) * c + 1
    ans += calc((b / c) * c + 1, b);
    cout << ans << "\n";
    return 0;
}