Codeforces Round #308 (Div. 2) C. Vanya and Scales dfs

题目链接:

http://codeforces.com/contest/552/problem/C

题意:

给你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 <bits/stdc++.h>
 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 <bits/stdc++.h>
52 using namespace std;
53 typedef long long ll;
54 #define MS(a) memset(a,0,sizeof(a))
55 #define MP make_pair
56 #define PB push_back
57 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 }