自动搬运

查看原文

来自洛谷，原作者为

	Kubic Go straight ahead 'til we've lost it all.

搬运于2025-08-24 22:43:44，当前版本为作者最后更新于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;
}