[codeforces 1312C] Adding Powers 进制转换

Educational Codeforces Round 83 (Rated for Div. 2)   比赛人数8705

[codeforces 1312C]  Adding Powers   进制转换

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

在线测评地址https://codeforces.ml/contest/1312/problem/C

Problem	Lang	Verdict	Time	Memory
C - Adding Powers	GNU C++11	Accepted	46 ms	0 KB

at i-th step (0-indexed) you can该句的写法还是有些问题的，虽然最后理解是i是从0开始，但一开始缺读不到这个意思，是配合了样例，才有了这个层面的理解。

题意清楚后，很快就反应过来，该题是一个进制转换问题，并且同一位上的数据和不能超过1.

若不明白，上述说法，请看手工算法

3 9
0 59049 810

0=            0*9^0+0*9^1+0*9^2+0*9^3+0*9^4+0*9^5
59049=        0*9^0+0*9^1+1*9^2+1*9^3+0*9^4+1*9^5
810=          0*9^0+0*9^1+0*9^2+0*9^3+0*9^4+0*9^5
同一位上数据和  0     0     1     1     0     1


同一位上数据和  没有超过1   故打印YES

3 2
0 1 3

0=            0*2^0+0*2^1
1=            1*2^0+0*2^1
3=            1*2^0+1*2^1
同一位上数据和  2     0     

同一位上数据和  有超过1   故打印NO

int b[35][64]对64做个说明，2^63=9.223372037×10¹⁸>10^16

b[i][j]表示第i个数在j位上的数值

感觉代码写得有一点点罗嗦，但是是比赛时的AC代码，要原汁原味的，也就不做修改了。

#include <stdio.h>
#include <string.h>
#define LL long long
LL a[35];
int b[35][64],c[35],vis[35],sum[64];
void f(int p,int k){
	LL d=a[p];
	int top=0;
	while(d){
		b[p][top++]=d%k;
		d/=k;
	}
	c[p]=top;
}
int main(){
	int t,n,i,k,j,flag;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&k);
		memset(vis,0,sizeof(vis));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		memset(sum,0,sizeof(sum));
		for(i=1;i<=n;i++){
			scanf("%lld",&a[i]);
			if(a[i]==0)vis[i]=1;
		}
		for(i=1;i<=n;i++)
			if(vis[i]==0)f(i,k);
		for(j=0;j<=63;j++)
			for(i=1;i<=n;i++)
				sum[j]+=b[i][j];
		flag=0;
		for(i=0;i<=63;i++)
			if(sum[i]>=2){
				flag=1;
				printf("NO\n");
				break;
			}
		if(flag==0)printf("YES\n");
	}
	return 0;
}