题解 | #计数器#

题目链接

计数器

题目描述

一个计数器的工作方式如下：

在 $t=1$ 时，显示数字 $3$ 。
在接下来的每个时刻，数字减 $1$ ，直到变为 $1$ 。
当数字变为 $1$ 后，在下一个时刻，计数器会重置，新显示的数字是上一个计数周期初始值的两倍。然后重复第2步。

例如：

$t=1, 2, 3$ ，值分别为 $3, 2, 1$ 。（周期1，初始值为3）
$t=4$ ，值重置为 $3 \cdot 2 = 6$ 。
$t=4, 5, ..., 9$ ，值分别为 $6, 5, ..., 1$ 。（周期2，初始值为6）
$t=10$ ，值重置为 $6 \cdot 2 = 12$ 。

给定一个时刻 $t$ ，求出该时刻计数器显示的值。

解题思路

这是一个规律探索问题。由于 $t$ 的范围非常大（可达 $10^{12}$ ），我们不能通过模拟来求解，必须找出其中的数学规律。

1. 分析计数周期

我们来分析每个周期的初始值和起始时刻：

周期	初始值 ( $v$ )	周期长度 ( $len$ )	起始时刻 ( $t_{start}$ )
1	3	3	1
2	6	6	4 = 1 + 3
3	12	12	10 = 4 + 6
4	24	24	22 = 10 + 12
...	...	...	...

可以观察到以下规律：

初始值 $v$ 的序列是 $3, 6, 12, 24, ...$ ，通项公式为 $v_i = 3 \cdot 2^{i-1}$ (其中 $i$ 是周期序号)。
周期长度 $len$ 总是等于该周期的初始值 $v$ 。
起始时刻 $t_{start}$ 满足 $t_{start, i} = t_{start, i-1} + v_{i-1}$ 。

2. 寻找 $t$ 所在的周期

我们可以推导出第 $i$ 个周期的起始时刻 $t_{start}$ 与其初始值 $v$ 之间的直接关系： $t_{start, i} = 1 + \sum_{j=1}^{i-1} v_j = 1 + \sum_{j=1}^{i-1} 3 \cdot 2^{j-1} = 1 + 3 \cdot (2^{i-1} - 1) = v_i - 2$ 。

所以，一个初始值为 $v$ 的周期，它的起始时刻是 $v - 2$ 。

现在，问题转化为：给定一个时刻 $t$ ，我们需要找到它所属的那个周期。这意味着，我们需要找到一个 $v$ （ $v$ 必须是 $3 \cdot 2^n$ 的形式），使得 $t$ 位于该周期的 $[t_{start}, t_{end}]$ 区间内，即： $v - 2 \le t$ 为了确定是哪个周期，我们应该寻找满足这个条件的最大的 $v$ 。

3. 数学求解

我们要求解的是：找到最大的 $v = 3 \cdot 2^n$ ，使得 $3 \cdot 2^n - 2 \le t$ 。

整理不等式： $3 \cdot 2^n \le t + 2$ $2^n \le (t + 2) / 3$

这表明，我们需要的 $2^n$ 就是不大于 $(t + 2) / 3$ 的最大的2的幂次方。

这个值可以通过位运算高效地求出。

4. 计算最终结果

一旦我们通过上述方法找到了 $t$ 所在周期的初始值 $v$ ，该周期的起始时刻就是 $t_{start} = v - 2$ 。

在 $t_{start}$ 时刻，值为 $v$ 。在 $t$ 时刻，值已经减少了 $t - t_{start}$ 。

所以，最终的计数值为： $Result = v - (t - t_{start}) = v - (t - (v - 2)) = 2v - t - 2$

算法步骤总结

给定 $t$ ，计算 $rem = t + 2$ 。
计算 $p = rem / 3$ 。
找到不大于 $p$ 的最大的2的幂次方，记为 $pow2$ 。（例如，通过 highestOneBit 或 bit_length 等方法）
计算周期的初始值 $v = 3 \cdot pow2$ 。
计算最终结果 $ans = 2v - t - 2$ 。

代码

c++
java
python

#include <iostream>

// 函数找到不大于 n 的最大2的幂次方
long long largest_power_of_two(long long n) {
    if (n == 0) return 0;
    long long p = 1;
    while ((p << 1) <= n) {
        p <<= 1;
    }
    return p;
}

// C++20 中有 std::bit_floor
// 或者使用内置函数 __builtin_clzll for GCC/Clang for O(1)
long long largest_power_of_two_fast(long long n) {
    if (n == 0) return 0;
    return 1LL << (63 - __builtin_clzll(n));
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long t;
    std::cin >> t;

    long long rem = t + 2;
    long long p = rem / 3;
    
    long long pow2 = largest_power_of_two_fast(p);
    
    long long v = 3 * pow2;
    
    long long result = 2 * v - t - 2;
    
    std::cout << result << std::endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long t = sc.nextLong();

        long rem = t + 2;
        long p = rem / 3;

        // Long.highestOneBit(p) 找到不大于p的最大2的幂次方
        long pow2 = Long.highestOneBit(p);

        long v = 3 * pow2;

        long result = 2 * v - t - 2;

        System.out.println(result);
    }
}

import sys

def solve():
    try:
        t_str = sys.stdin.readline()
        if not t_str:
            return
        t = int(t_str)
        
        rem = t + 2
        p = rem // 3
        
        # 找到不大于 p 的最大2的幂次方
        # (p.bit_length() - 1) 得到的是该幂的指数
        if p == 0:
            pow2 = 0 # Should not happen based on constraints
        else:
            pow2 = 1 << (p.bit_length() - 1)
        
        v = 3 * pow2
        
        result = 2 * v - t - 2
        
        print(result)

    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法：数学、位运算
时间复杂度: $\mathcal{O}(1)$ 。整个计算过程只涉及几次算术运算和一次位运算，与输入 $t$ 的大小无关。
空间复杂度: $\mathcal{O}(1)$ 。