SPOJ 10606 Balanced Numbers

题意:一个数被称为是平衡的数当且仅当对于所有出现过的数位,偶数出现奇数次,奇数出现偶数次。给定A,B,请统计出[A,B]内所有平衡的数的个数。

思路:对于每个数字,定义状态0为没出现过,1为出现了奇数次,2为出现了偶数次,那么可以用一个103进制数来表示所有数字的状态。定义dp[i][S][0]表示从从高位到低位已经填了i位,所有数字状态为S,且当前数字已经小于n的数字个数,dp[i][S][1]表示从从高位到低位已经填了i位,所有数字状态为S,且当前数字等于n的数字个数,直接转移不太会写,所以扔掉最后一维记忆化搜索dp,这时候这里的dp[i][S]是相当于dp[i][S]0],转移枚举下一个数字转移即可,同时要考虑前导零的影响。

#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=genchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
int T,digit[21];
ll l,r,dp[21][600000];
bool check(int S){
    for (int i=0;i<=9;++i,S/=3){
        int t=S%3;
        if (!t) continue;
        if ((i&1)&&(t&1)) return 0;
        if (!(i&1)&&!(t&1)) return 0;
    }
    return 1;
}
int get(int S,int x){
    int newS=S,val=1;
    for (int i=0;i<x;++i){
        val*=3;
        S/=3;
    }
    return (S%3)<=1?newS+val:newS-val;
}
ll dfs(int pos,int S,bool preZero,bool jud){
    if (pos==0) return check(S);
    if (!jud && !preZero && ~dp[pos][S]) return dp[pos][S];
    int limit=jud?digit[pos]:9;
    ll ret=0;
    for (int i=0;i<=limit;++i){
        ret+=dfs(pos-1,(preZero && i==0)?0:get(S,i),preZero && i==0,jud && i==limit);
    }
    if (!jud && !preZero) dp[pos][S]=ret;
    return ret;
}
ll cal(ll x){
    if (x==0) return 1;
    int len=0;
    while (x){
        digit[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,1,1);
}
int main(){
    memset(dp,-1,sizeof(dp));
    for (read(T);T--;){
        read(l),read(r);
        printf("%lld\n",cal(r)-cal(l-1));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注