CodeForces 1312C Adding Powers

题目链接

题目比较好理解不解释了

题解

对数组中的每个数都转换成k进制，统计每位上的个数和，若存在某一位上的和大于1，假设此位为第t位（从低位算起），那么这就说明只用一个k^t是不能够构成此数组的，输出NO。 ———————————————— 思路秒出，因为比较简单。但是我居然卡在如何实现k进制转化上了。。。。 最后想了个歪门邪道实现的。

代码1是实现k进制转化的标准方法； 代码2是我的方法。

代码1

#include
using namespace std;
typedef long long ll;

ll a;
int cnt[105], n, k, T;

int main() {
	cin>>T;
	while(T--) {
		memset(cnt, 0, sizeof cnt);
		cin>>n>>k;
		for(int i = 1;i >a;
			int j = 0;
			while(a) {
				cnt[j] += a%k;
				a /= k;
				j ++;
			}
		}
		int flag = 0;
		for(int i = 0;i  1) {
				flag = 1;
				break;
			}
			
		if(flag) puts("NO");
		else puts("YES"); 
	}
}

代码2

#include
using namespace std;
typedef long long ll;

ll a;
int cnt[100], T, n, k;

int main() {
	cin>>T;
	while(T--) {
		int flag = 0;
		cin>>n>>k;
		memset(cnt, 0, sizeof cnt); // memset也wa了一发
		for(int i = 1;i >a;
			for(int j = 66;j >= 0;j --) {
				ll po = pow(k, j);
				if(po = po) a -= po, cnt[j] ++, flag?:flag = (cnt[j]>1);
				if(a == 0) break;
			}
			if(a) flag = 1; // 看cf数据才知道的
		}
		if(flag) puts("NO");
		else puts("YES");
	}
}