题解：P15046 [UOI 2022 II Stage] 魔法鞋

ycy25 · 2026-01-26 10:35:32 · 题解

思路

阅读题目，我们发现从速度为 1 米每秒推到速度为 k 米每秒不太容易，这时我们可以考虑倒推——从速度为 k 米每秒推到速度为 1 米每秒。

现在，我们将原问题转化成了以下问题：
如果穿着魔法鞋的人当前速度为 a 米每秒，那么她可以施展以下两种咒语之一：

• 将自身速度变为 a/2 米每秒。
• 将自身速度变为 (a-1)/2 米每秒。

穿着这双鞋的人初始速度为 k 米每秒，问至少需念动几次咒语才能使速度降为 1 米每秒。

在原问题中，显然在任意时刻速度都是正整数。因此无论施展哪种咒语，都必须保证施展咒语后速度是整数。那么，显然当当前速度 a 为奇数时，只能施展第二种咒语，否则只能施展第一种咒语。

根据以上思路模拟即可。

代码

#include<cstdio>
int main()
{
    long long k;
    scanf("%lld",&k);
    int ans=0;
    while(k>1)
    {
        if(k%2)k=(k-1)/2;
        else k/=2;
        ans++;
    }
    printf("%d",ans);
    return 0;
}