Vanya and Scales （天平砝码称重）

题目链接

题意：给你一个天平和101个砝码，砝码的质量各不相同，分别为 w0, w1, w2, …, w100 ,物品质量为m,问能不能称出物品的质量。

做法一：
将m展开为w进制数列
1后面只能跟0和1
w-2后面不能跟1
最后一位不能是w-2

#include using namespace std;
int num[100],len=0,w,m;
bool check(){int i,flag=0;for(i = len;i > 1;i --){if(num[i]==w-1)continue;if(num[i]==0)continue;if(num[i]==1){if(num[i-1]==1||num[i-1]==0) continue;return 0;}if(num[i]==w-2){if(num[i-1]==0||num[i-1]==w-1||num[i-1]==w-2) continue;return 0;}return 0;}if(num[1]==1||num[1]==0||num[1]==w-1) return 1;return 0;
}
int main()
{freopen("a.txt","r",stdin);cin>>w>>m;if(w==3||w==2) {cout<<"YES";return 0;}while(m){len ++;num[len] = m%w;m/=w;}if(check())cout<<"YES";else cout<<"NO";return 0;
}

做法二（原创）
将m进行w进制拆分，每一位的值可能是1,0,-1。
但是在进行%w取最后一位时，不会得到-1
解决方法：
先对w进制的每一位都加上1，然后每一位的取值只能是0,1,2

#include using namespace std;
int num[100],len=0,w,m,k[100];
bool check(int w,int m){while(m){int t = m%w;m/=w;if(t==0)continue;if(t==1)continue;if(t==2)continue;return 0;}return 1;
}
int main()
{freopen("a.txt","r",stdin);cin>>w>>m;int cpy = m;while(m){len ++;num[len] = m%w;m/=w;}m = cpy;int i;k[1] = 1;for(i = 2;i <= len;i ++)k[i] = k[i-1]*w;for(i = 2;i <= len;i ++)k[i] += k[i-1];   //其实可以直接等比数列前n项和m += k[len];  //每一位都加1if(check(w,m))cout<<"YES";else cout<<"NO";return 0;
}

做法三：
同做法二
%w时发现余w-1时就是-1
然后加上1继续拆数

#include using namespace std;
int main()
{int w,m;cin>>w>>m;while(m){if(m%w==1){m--;m/=w;continue;}if(m%w==w-1){m ++;m/=w;continue;}if(m%w==0){m/=w;continue;}cout<<"NO";return 0;}cout<<"YES";return 0;
}

做法四：神仙

#include using namespace std;
int main()
{int w,m;cin>>w>>m;while(m){if((m-1)%w==0){m--;m/=w;continue;}if(m%w==0) {m/=w;continue;}if((m+1)%w==0) {m++;m/=w;continue;}cout<<"NO";return 0;}cout<<"YES";return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！