Codeforces 1312C Adding Powers

本文主要是介绍Codeforces 1312C Adding Powers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

题目描述
设有一个长度为 $n$ 的 $V$ 。初始时，所有的元素都为 0。
现在可以对数组 $V$ 进行若干次操作，对于第 $i$ 次操作如下( $i$ 从0 开始)：

任选一个位置 $p o s$ ， $p o s \in [1, n]$ ，然后执行 $V_{pos} = V_{pos} + k^i$ 。
跳过该次操作，什么也不做。

另有一个长度为 $n$ 的数组 $A$ ，问是否存在一种方案使得对 $V$ 经过若干次操作后有 $V = A$ 。

数据范围
$1 <= n <= 30, 2 <= k <= 100，对于任意 i ∈ [1, n] ，有 0 <= A[i] <= 10^{16}$

样例

n = 3 k = 9
A = [0, 59049, 810]

跳过第0步，第1步；
第2步，第3步选择 pos = 3， $V_3 = 9^2 + 9^3 = 810$ ；
第4步，第5步选择 pos = 2， $V_2 = 9^4 + 9^5 = 59049$ ；

题目类型：构造，暴力枚举

解题思路
如果有解，那么数组 $A$ 应该满足下述两个条件：

对于 $A$ 中的所有元素都能拆解成 $k^a + k^b + k^c + ...$ 形式的累加和。
对于 $A$ 中所有元素的累加向的指数两两不相等。因为每一步操作只能选一个位置。

那么解题的关键就变成了如何判断元素是否满足条件一，以及如何将其拆解。
判断及拆解方法如下：

当 $x = 0$ 时， $x$ 显然满足条件一，算法结束。
当 $x > 0$ 时：
2.1 如果存在 $p$ 满足 $k^p <= x 且 x< k^{p+1}$ ，那么 $k^p$ 有可能是累加项的其中一项，执行 $x = x - k^p$ ，跳转步骤一。
2.2 如果不存在上述 $p$ ，则 $x$ 显然不满足条件一，算法结束。

代码

#include <bits/stdc++.h>using namespace std;bool check(int64_t x, int k, unordered_set<int> &mark) {if (x == 0) {return true;}for(int i = 0; i < 64; i++) {for(int64_t j = 0, mul = 1; ; j++, mul *= k) {if(mul > x) {auto tmp = j-1;if(mark.find(tmp) != mark.end()) {return false;}mark.insert(tmp);x -= mul/k;if(x == 0) {return true;}break;}}}return true;
}int main() {cin.sync_with_stdio(false);int T;cin >> T;while(T--) {int n, k;cin >> n >> k;unordered_set<int> mark;bool flag = true;while (n--) {int64_t x; cin >> x;if (check(x, k, mark) == false) {flag = false;} }if (flag) {cout << "YES" << endl;} else {cout << "NO" << endl;}}return 0;
}