P8918 『MdOI R5』Jump

Kubic · 2022-12-31 20:29:44 · 题解

只有第一秒走的长度为奇数，后面每一秒走的长度都为偶数，因此所有除 0 外的偶数点都是不可达的。

当 n 为奇数时，设 d 为满足 \sum\limits_{i=1}^d 2^{i-1}\ge n 的最小值。可以证明答案为 d。

证明：

初始令每一秒都是往右走的，我们需要将某一些秒调整为往左走使得最终恰好走到 n。

设 m=\sum\limits_{i=1}^d 2^{i-1}-n。显然 m 为偶数。

我们需要找到一些秒，使得这些秒中走的距离之和恰好为 \dfrac{m}{2}，并将这些秒调整为往左走。

只需要找出 \dfrac{m}{2} 的二进制表示，将它分解为若干个互不相同的 2 的幂之和，这样就一定可以得到一组方案。

时间复杂度 O(T) 或 O(T\log n)。

参考代码：

#include <bits/stdc++.h>
using namespace std;
int T,n;
void slv()
{
    scanf("%d",&n);
    if(n&1) printf("%d\n",32-__builtin_clz(n));
    else printf("-1\n");
}
int main()
{
    scanf("%d",&T);
    while(T--) slv();return 0;
}