题意：
平衡树定义为“一个整数的某个数位若是奇数，则该奇数必定出现偶数次；偶数位则必须出现奇数次”，比如 222，数位为偶数2，共出现3次，是奇数次，所以合法。给一个区间[L,R]，问有多少个平衡数？
思路：
这题比较好解决，只有前导零问题需要解决。如果枚举到011，那么其前导零（偶数）出现了1次而已，而此数11却是平衡数，所以不允许前导零的出现！
由于dfs时必定会枚举到前导零，否则位数较少的那些统计不到。状态需要3维or2维也行，3维的比较容易处理，用一维表示数位出现次数，另一维表示数位是否已经出现过了，而剩下一维自然就是位数了。乱搞一下就行了。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x7f3f3f3f
#define LL long long
#define ULL unsigned long long
using namespace std;
const double PI = acos(-1.0);
const int N=; LL f[N][<<][<<], bit[N];
//[位数][状态][是否出现过] int isok(int s,int w)
{
if(!w) return ;
for(int i=; i<; i++)
{
if( i%== && (w&(<<i)) && (s&(<<i))== ) return ; //偶数
if( i%!= && (w&(<<i)) && (s&(<<i))!= ) return ;
}
return ;
} LL dfs(int i,int s,int w,int sum,bool e)
{
if(i==) return isok(s,w);
if(!e&&~f[i][s][w]) return f[i][s][w]; LL ans=;
int u= e? bit[i]: ;
for(int d=; d<=u; d++)
{
int ww=w, ss=s;
if( sum+d!= ) ww|=<<d,ss^=<<d;
ans+=dfs(i-, ss, ww, sum+d, e&&d==u);
}
return e? ans: f[i][s][w]=ans;
} LL cal(LL n)
{
if(n==) return ;
int len=, s=;
while(n) //拆数
{
bit[++len]=n%;
n/=;
}
return dfs(len,,,,true);
} int main()
{
//freopen("input.txt","r",stdin);
memset(f, -, sizeof(f));
LL L, R;int t;
cin>>t;
while( t-- )
{
cin>>L>>R;
cout<<cal(R)-cal(L-)<<endl;
}
return ;
} AC代码
AC代码
为了省空间，以为只是标记一下偶数位就行了，奇数位若是出现偶数次，相当于没有出现（抵消）。注意要考虑0的情况，举例，如果出现数字11，抵消后状态为0，那么和出现数字0没有什么两样。然而过了样例却WA。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x7f3f3f3f
#define LL long long
#define ULL unsigned long long
using namespace std;
const double PI = acos(-1.0);
const int N=; LL f[N][<<][<<], bit[N];
//[位数][状态][是否出现过] int isok(int s,int w)
{
for(int i=; i<; i+=) //奇数
if( (s&(<<i)) )
return ;
for(int i=; i<&&w; i++) //偶数
if( (w&(<<i)) && (s&(<<*i))== )
return ;
//cout<<"123"<<endl;
return ;
} LL dfs(int i,int s,int w,int sum,bool e)
{
if(i==) return isok(s,w);
if(!e&&~f[i][s][w]) return f[i][s][w]; LL ans=;
int u= e? bit[i]: ;
for(int d=; d<=u; d++)
{
if(!sum&&!d) ans+=dfs(i-, s, w, , e&&d==u);
else
{
int ww=w;
if( d%== ) ww|=<<d/;
ans+=dfs(i-, s^(<<d), ww, sum+d, e&&d==u);
}
}
return e? ans: f[i][s][w]=ans;
} LL cal(LL n)
{
if(n==) return ;
int len=;
while(n) //拆数
{
bit[++len]=n%;
n/=;
}
return dfs(len,,,,true)-;
} int main()
{
//freopen("input.txt","r",stdin);
memset(f, -, sizeof(f));
LL L, R;int t;
cin>>t;
while( t-- )
{
cin>>L>>R;
cout<<cal(R)-cal(L-)<<endl;
}
return ;
}
WA代码
进行一番YY之后AC了，因为像只出现偶数个奇数位的情况，而被抵消了，相当于没有出现过，而由于记录的时候并没有记录到底是否是前导零还是被抵消的那种，两种的结果是不一样的，只需要加多一维来区分开这两种就可以了。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x7f3f3f3f
#define LL long long
#define ULL unsigned long long
using namespace std;
const double PI = acos(-1.0);
const int N=; LL f[N][<<][<<][], bit[N];
//[位数][状态][是否出现过] int isok(int s,int w)
{
for(int i=; i<; i+=) //奇数
if( (s&(<<i)) )
return ;
for(int i=; i<&&w; i++) //偶数
if( (w&(<<i)) && (s&(<<*i))== )
return ;
return ;
} LL dfs(int i,int s,int w,bool sum,bool e)
{
if(i==) return isok(s,w);
if(!e&&~f[i][s][w][sum]) return f[i][s][w][sum]; LL ans=;
int u= e? bit[i]: ;
for(int d=; d<=u; d++)
{
if(==sum+d) ans+=dfs(i-, , , , e&&d==u);
else
{
int ww=w;
if( d%== ) ww|=<<d/;
ans+=dfs(i-, s^(<<d), ww, sum+d, e&&d==u);
}
}
return e? ans: f[i][s][w][sum]=ans;
} LL cal(LL n)
{
if(n==) return ;
int len=;
while(n) //拆数
{
bit[++len]=n%;
n/=;
}
return dfs(len,,,,true)-;
} int main()
{
//freopen("input.txt","r",stdin);
memset(f, -, sizeof(f));
LL L, R;int t;
cin>>t;
while( t-- )
{
cin>>L>>R;
cout<<cal(R)-cal(L-)<<endl;
}
return ;
}
AC代码