首页 > 代码库 > [haoi2010]计数
[haoi2010]计数
你有一组非零数字（不一定唯一），你可以在其中插入任意个0，这样就可以产生无限个数。比如说给定{1,2},那么可以生成数字12,21,102,120,201,210,1002,10200,等等。
现在给定一个数，问在这个数之前有多少个数。（注意这个数不会有前导0）。
基础数位dp之一；
普通dp思路：
首先想到设状态，怎么设呢？设的状态肯定要把前面用了多少数表示出来，按照这个思路就只能设f[i][j]表示在第i位，j是所有非0数字的二进制表示；
然后可以记忆化搜索进行转移；
这个方法可以过（HA的数据太水），但数据稍稍加强一下，时空全炸；
AC思路：
其实每个数都是原数的一个组合，那么我们自然可以用排列组合的方法计算；
思路还是逐位确定，从高位向低位确定数字，然后对下面的不确定的数进行排列组合，结果累积；
无论是空间还是时间都到了最优的程度；
第一种思路：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cmath> 5 #include<cstring> 6 #include<ctime> 7 #include<iomanip> 8 #include<queue> 9 #include<map> 10 #include<set> 11 #include<algorithm> 12 using namespace std; 13 #define FILE "dealing" 14 #define LL long long 15 #define up(i,j,n) for(int i=(j);i<=(n);i++) 16 void chkmin(int &a,int b){a>b?a=b:0;} 17 void chkmax(int &a,int b){a<b?a=b:0;} 18 namespace IO{ 19 char buf[1<<15],*fs,*ft; 20 int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1<<15,1,stdin),fs==ft))?-1:*fs++;} 21 int read(){ 22 int x=0,f=0,ch=gc(); 23 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=1;ch=gc();} 24 while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=gc();} 25 return f?-x:x; 26 } 27 }using namespace IO; 28 const int maxn=150; 29 int q[maxn],tail=0,pre[maxn]; 30 char s[maxn],ch[maxn]; 31 LL f[51][100000]; 32 LL dfs(int pos,int num,int limit){ 33 if(pos<1) 34 return num==0; 35 if(!limit&&f[pos][num]!=-1)return f[pos][num]; 36 int len=limit?s[pos]:9; 37 LL ret=0; 38 ret+=dfs(pos-1,num,limit&&0==len); 39 up(i,1,len){ 40 if(pre[i]==-1)continue; 41 up(j,pre[i],tail){ 42 if(q[j]==i&&(num&(1<<j-1))){ 43 ret+=dfs(pos-1,num^(1<<j-1),limit&&i==len); 44 break; 45 } 46 } 47 } 48 if(!limit)f[pos][num]=ret; 49 return ret; 50 } 51 int main(){ 52 freopen(FILE".in","r",stdin); 53 freopen(FILE".out","w",stdout); 54 scanf("%s",ch+1); 55 int len=strlen(ch+1); 56 up(i,1,len)s[i]=ch[len-i+1]-‘0‘; 57 up(i,1,len)if(s[i]) 58 q[++tail]=s[i]; 59 sort(q+1,q+tail+1); 60 memset(pre,-1,sizeof(pre)); 61 up(i,1,tail) 62 if(pre[q[i]]==-1)pre[q[i]]=i; 63 memset(f,-1,sizeof(f)); 64 printf("%I64d\n",dfs(len,(1<<tail)-1,1)-1); 65 return 0; 66 }
第二种思路：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cmath> 5 #include<cstring> 6 #include<ctime> 7 #include<iomanip> 8 #include<queue> 9 #include<map> 10 #include<set> 11 #include<algorithm> 12 using namespace std; 13 #define FILE "dealing" 14 #define LL long long 15 #define up(i,j,n) for(int i=(j);i<=(n);i++) 16 void chkmin(int &a,int b){a>b?a=b:0;} 17 void chkmax(int &a,int b){a<b?a=b:0;} 18 namespace IO{ 19 char buf[1<<15],*fs,*ft; 20 int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1<<15,1,stdin),fs==ft))?-1:*fs++;} 21 int read(){ 22 int x=0,f=0,ch=gc(); 23 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=1;ch=gc();} 24 while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=gc();} 25 return f?-x:x; 26 } 27 }using namespace IO; 28 const int maxn=52; 29 char s[maxn]; 30 int a[10],len; 31 LL fac[30],c[maxn][maxn]; 32 int main(){ 33 freopen(FILE".in","r",stdin); 34 freopen(FILE".out","w",stdout); 35 c[0][0]=1; 36 for(int i=1;i<=50;i++){ 37 c[i][0]=1; 38 for(int j=1;j<=50;j++)c[i][j]=c[i-1][j-1]+c[i-1][j]; 39 } 40 scanf("%s",s+1); 41 len=strlen(s+1); 42 up(i,1,len)a[s[i]-‘0‘]++; 43 LL ans=0; 44 for(int i=1;i<=len;i++){ 45 for(int j=0;j<s[i]-‘0‘;j++){ 46 if(!a[j])continue; 47 a[j]--; 48 int now=len-i; 49 LL sum=1; 50 for(int k=0;k<=9;k++) 51 sum*=c[now][a[k]],now-=a[k]; 52 ans+=sum; 53 a[j]++; 54 } 55 a[s[i]-‘0‘]--; 56 } 57 cout<<ans<<endl; 58 return 0; 59 }
[haoi2010]计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。