题解：P13591 [NWRRC 2023] Kitchen Timer

前言

蒟蒻心血来潮做的一道题，因为还没有通过一道题号数字有五位数的题。

翻译（参考机翻）

题目描述

Kenny 的厨房里有一个微波炉，配有一个奇怪的单按钮计时器界面。当把食物放入微波炉并想开始加热时，你需要按下按钮一次或多次。第一次按下按钮时，计时器设置为

1

分钟。如果立即再次按下按钮，计时器会增加

2

分钟（总计

3

分钟）。紧接着再按一次，会增加

4

分钟，以此类推。如果连续按下按钮第

k

次，它会增加

2^{k-1}

分钟。

仅通过连续按按钮无法设置某些时间（例如

2

分钟）。幸运的是，你可以通过暂停一秒钟来重置按钮计数器。例如：按一次、暂停一秒、再按一次，可以设置 2 分钟。另一个例子：按两次（

1+2

）、暂停、再按三次（

1+2+4

），总时间为

1+2+1+2+4=10

分钟。

Kenny 需要加热食物恰好

x

分钟。请帮助他找到设置计时器所需的最少暂停次数（假设只有暂停消耗时间，按按钮的时间忽略）。

输入格式

第一行包含测试用例数 $t$ （ $1 \le t \le 10^4$ )。
接下来 $t$ 行，每行一个整数 $x$ （ $1 \le x \le 10^{18}$ ），表示需要加热的分钟数。

输出格式

对于每个测试用例，输出一个整数，表示最少暂停次数。

样例

略

说明/提示

$x=1$ ：按一次，无需暂停。
$x=2$ ：按、暂停、按，暂停 $1$ 次。
$x=3$ ：按两次，无需暂停。
$x=4$ ：按两次、暂停、按一次，暂停 $1$ 次。

思路

分析

~~As we all know，~~ 连续按

k

次按钮，增加的分钟数为

1+2+4+…+2^{k−1}=2^k−1

。所以我们可以将

x

看为

n

个

2^k-1

的和（

n\ge1

)。问题就转化为使

n

最小化，所求的暂停数就等于

n-1

。

数学推导

~~蒟蒻数学不好，凑合看吧 QaQ~~

已知最少分段数为

n

，则暂停次数为

n−1

。每段对应一连续按钮序列，其和为

2^{k_i}−1

则：

x=\sum_{i=1}^n(2^{k_i}-1)=(\sum_{i=1}^n2^{k_i})-n

移项得：

x+m=\sum_{i=1}^n2^{k_i}

其中

k_i\ge1

（即

2^{k_i}\ge2

）。

条件：

$x+n$ 必须能表示为 $m$ 个 $2$ 的幂次（指数 $\ge1$ ) 之和。
由于每个幂次至少为 $2$ ，有 $x+m\ge2m$ （即 $x\ge m$ ）。
$x+m$ 的二进制表示中 $1$ 的个数（记为 $cnt$ ）必须满足 $cnt\le m$ （因为重复幂次可通过拆分合并，例如 $2^k+2^k=2^{k+1}$ ，拆分操作可增加项数）。

算法

枚举即可。可以使用 GCC 内部函数快速统计 __builtin_popcountll() 一个二进制数

1

的个数。

复杂度

x

最大

10^{18}

，二进制最多不超过

64

位，所以枚举到

70

完全可以。

代码

CPP

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
int t;
int main()
{
    scanf("%d",&t);
    while (t--)
   {
        ll x;
        scanf("%lld",&x);
        // 枚举分段数 m (从 1 到 70)
        for (int n = 1; n <= 70; n++)
       {
            if (x < n) continue;  // 不满足基本条件 x ≥ m
            ll num = x + n;
            int cnt = __builtin_popcountll(num);  // 使用内置函数计算 1 的个数
            if (cnt <= n)
            {
                printf("%d\n",n-1);  // 暂停次数 = 分段数 -1
                break;
            }
        }
    }
    return 0;
}

AC 记录 QAQ

题解：P13591 [NWRRC 2023] Kitchen Timer

文章操作

前言

题目描述

输入格式

输出格式

样例

说明/提示

思路

分析

数学推导

条件：

算法

复杂度

代码

相关推荐

评论

题解：P13591 [NWRRC 2023] Kitchen Timer