题目链接:

题意:

给你100个砝码，第i个砝码质量是w^i，然后问你能不能在有m的情况下，左边和右边都放砝码，使得这个天平平衡

题解:

dfs直接暴力

对于这个砝码来说，只有3种选择，放左边，不放，放右边

由于2和3直接输出yes，所以答案也就没多少了

正解：m的w进制， 从低位到高位 模拟。。 每一位只能是0，1，w-1，因为每种位置的砝码只有一个 所以 在i位上是1 就是要在另一端天平上 放一个w^i的砝码与其抵消 对于w-1 就是相当于进到高一位上去

dfs~390ms maxn开到4e9 。。 1e9会WA 1e10会TLE 唉….

代码:

1 #include 
      
        2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){10     ll x=0,f=1;char ch=getchar();11     while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}13     return x*f;14 }15 //16 ll maxn = 4e9;17 ll w,m;18 bool f;19 20 void dfs(ll b,ll c){21     if(c == m){22         f = 1;23         return ;24     }25     if(f) return ;26 27     if(abs(b) <= maxn){28         dfs(b*w,c+b);29         dfs(b*w,c-b);30         dfs(b*w,c);31     }32 }33 34 int main(){35     f = 0;36     cin >> w >> m;37     // cout << (ll) (w*m) << endl;38     if(w<=3){39         puts("YES");40         return 0;41     }42     dfs(1,0);43 44     if(f) puts("YES");45     else puts("NO");46 47     return 0;48 }49 正解代码：50 51 #include 
       
        52 using namespace std;53 typedef long long ll;54 #define MS(a) memset(a,0,sizeof(a))55 #define MP make_pair56 #define PB push_back57 const int INF = 0x3f3f3f3f;58 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;59 inline ll read(){60     ll x=0,f=1;char ch=getchar();61     while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}62     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}63     return x*f;64 }65 //66 const int maxn = 1e5+10;67 68 int main(){69     int w = read(), m = read();70     if(m <= 3) {71         puts("YES");72         return 0;73     }74 75     while(m){76         int yu = m % w;77         if(yu <= 1)78             m /= w;79         else if(yu == w-1)80             m = m/w+1;81         else{82             puts("NO");83             return 0;84         }85     }86     puts("YES");87 88     return 0;89 }