admin 管理员组

文章数量: 1086019

橘猫

**问题 B: 橘猫** **时间限制: 1 Sec 内存限制: 512 MB**
**题目描述** NiroBC 有了一间小屋，真是太好了，终于可以养猫了。 NiroBC 想养N 只猫，编号为1……N。 NiroBC 希望，第i 只猫为橘猫，当且仅当在i 的十进制表示下（不含前导零），每个阿拉伯数字出现的次数都是偶数。 NiroBC 想知道她会养多少只橘猫。 **输入** 一行一个正整数N，表示猫的数量。 **输出** 一行一个整数，表示橘猫的数量。 **样例输入** 65

2360596325
样例输出
5

7080461
提示
样例解释1
总共有5 只橘猫，编号分别为11; 22; 33; 44; 55。
样例解释2
解释略，另外，这个输入的值是出题人的QQ 号。
数据范围
对于30% 的数据，1<= N <= 10^6。
对于另外20% 的数据，N 是10 的整次幂。
对于所有数据，1 <= N <= 10^18。
题解：
这是一道数位dp裸题，具体在代码中讲解。
C o d e ： Code： Code：

#include<iostream> 
#include<cmath> 
#include<cstring> 
#include<cstdio> 
#include<algorithm> 
#include<cstdlib> 
#define ll long long 
using namespace std; 
ll dp[20][60000],bit[20]; 
bool check(int s)//求出答案
{ int num[10]; for(int i=0;i<10;i++) { num[i]=s%3; s/=3; } for(int i=0;i<10;i++) if(num[i]!=0) if(num[i]==1)return false; return true; 
} 
int work(int x,int s)//加入x，更新状态
{ int num[10]; for(int i=0;i<10;i++) { num[i]=s%3; s/=3; } if(num[x]==0)num[x]=1;elsenum[x]=3-num[x]; int sum=0; for(int i=9;i>=0;i--) { sum*=3; sum+=num[i]; } return sum; 
} 
ll dfs(int pos,int s,int flag,int zero)//pos表示第几位，s表示状态，flag表示是否贴上界，zero表示前导零
{ if(pos==-1)return check(s); if(!flag&&dp[pos][s]!=-1) return dp[pos][s]; ll ans=0;int t; if(flag)t=bit[pos];else t=9; for(int i=0;i<=t;i++) ans+=dfs(pos-1,(zero&&i==0)?0:work(i,s),flag&&i==t,zero&&i==0); if(!flag)dp[pos][s]=ans; return ans; 
} 
int main() 
{ ll n; memset(dp,-1,sizeof(dp)); scanf("%lld",&n); int len=0; while(n) { bit[len++]=n%10; n/=10; } printf("%lld\n",dfs(len-1,0,1,1)-1); //减掉等于0的情况return 0; 
}

本文标签： 橘猫

版权声明：本文标题：橘猫 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/b/1687894426a154403.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。