Kevin and Combination Lock 题解

题意简述

给定一个整数 $x$，你可以执行以下两种操作任意次：

1. 若 $x\neq 33$，可以删除 $x$ 中连续的两个数字 $3$。
2. 若 $x\ge 33$，可以令 $x=x-33$。

问能否通过若干次操作使得 $x$ 变为 $0$。

核心观察

两种操作本质上都在做同一件事： 让 $x$ 减少 $33$ 的整数倍。

• 操作 2 是直接减 $33$，显然是 $33$ 的倍数。
• 操作 1 删除数字串中的 "33"，等价于原数减去形如 $\underbrace{33}_{k个0}\cdots00$ 的数，也一定是 $33$ 的倍数。

因此： 能把 $x$ 变成 $0$，当且仅当 $x$ 是 $33$ 的倍数。

结论

对每个 $x$：

• 若 $x \bmod 33 = 0$，输出 YES
• 否则输出 NO

完整 AC 代码

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        long long x;
        cin >> x;
        cout << (x % 33 == 0 ? "YES" : "NO") << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(t)$，每组数据 $O(1)$ 判断。
• 空间复杂度：$O(1)$。
• 数据范围 $t\le 10^4, x\le 10^9$，完全满足时限要求。