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 唉….

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//
ll maxn = 4e9;
ll w,m;
bool f;

void dfs(ll b,ll c){
    if(c == m){
        f = 1;
        return ;
    }
    if(f) return ;

    if(abs(b) <= maxn){
        dfs(b*w,c+b);
        dfs(b*w,c-b);
        dfs(b*w,c);
    }
}

int main(){
    f = 0;
    cin >> w >> m;
    // cout << (ll) (w*m) << endl;
    if(w<=3){
        puts("YES");
        return 0;
    }
    dfs(1,0);

    if(f) puts("YES");
    else puts("NO");

    return 0;
}
正解代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//
const int maxn = 1e5+10;

int main(){
    int w = read(), m = read();
    if(m <= 3) {
        puts("YES");
        return 0;
    }

    while(m){
        int yu = m % w;
        if(yu <= 1)
            m /= w;
        else if(yu == w-1)
            m = m/w+1;
        else{
            puts("NO");
            return 0;
        }
    }
    puts("YES");

    return 0;
}