频道栏目
首页 > 资讯 > 其他 > 正文

SPOJ - BALNUM Balanced Numbers (数位dp*)

18-07-28        来源:[db:作者]  
收藏   我要投稿

题目:奇数出现偶数次,偶数出现奇数次

光写这个dp数组写的就快睡着了。。。状态0表示这个数字没出现过,1表示出现了奇数次,2表示出现了偶数次。x和y数组统计每个不同的数字出现的次数,简单易懂。可以用三进制来表示状态,我写的与其对比起来就low了好多,效果其实是一样的。最后前导零不要忘记判断。

#include 
using namespace std;
typedef long long ll;
int t,wei[20];
ll A,B,dp[20][3][3][3][3][3][3][3][3][3][3];
ll dfs(int pos,int x[],int limit,int lead)
{
 int a[11]={0};
 for(int i=0;i<=9;i++)
 if(x[i])
 {
  if(x[i]&1) a[i]=1;
  else a[i]=2;
 }
 if(pos<1)
 {
  int flag=1;
  for(int i=0;i<10;i++)
  if(a[i])
  {
if((i%2==1&&a[i]==1)||(i%2==0&&a[i]==2))
{
 flag=0;
 break;
}
  }
  return flag;
 }
 if(!limit&&dp[pos][a[0]][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]!=-1)
  return dp[pos][a[0]][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]];
 int up=limit?wei[pos]:9;
 ll ans=0;
 int y[11];
 memcpy(y,x,sizeof y);
 for(int i=0;i<=up;i++)
 {
  y[i]++;
  if(lead&&i==0)
y[i]--;
  ans+=dfs(pos-1,y,limit&&i==up,lead&&i==0);
  y[i]--;
  if(lead&&i==0)
y[i]++;
 }
 if(!limit) dp[pos][a[0]][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]=ans;
 return ans;
}
ll solve(ll x)
{
 int len=0,a[11]={0};
 while(x)
 {
  wei[++len]=x%10;
  x/=10;
 }
 ll ans=dfs(len,a,1,1);
 return ans;
}
int main()
{
 memset(dp,-1,sizeof dp);
 scanf("%d",&t);
 while(t--)
 {
  scanf("%lld%lld",&A,&B);
  ll ans=solve(B)-solve(A-1);
  printf("%lld\n",ans);
 }
 return 0;
}
相关TAG标签
上一篇:storm的学习理解
下一篇:C#入门教程之Helloworld!详解
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站