组合数学

之前看了一段组合数学，但是没怎么做题。最近暂时补了2题：

POJ3252

题目定义了一个"round number" 意思是：一个数的二进制表达中0的个数不少于1的个数，这个数就是一个round number。给你2个数Start,Finish(1 ≤ Start < Finish ≤ 2,000,000,000)，求这两个数中间有多少个round number。

由于这道题是在POJ题目分类里找的，又刚好写在“递推关系.”下面……所以一开始我还打了张表在研究有神马规律……简直囧翻天……

不过后来也就发现这不是一个找规律，或者说递推关系式的题目……

这两个数字太大，几乎不可能递推，除非初始化把全部的东西都先打出来，但是数字太大连1维数组都开不下。

所以肯定是一个数学式子就差不多出来的，不会是递推式子。

一开始想的是一个101010（随便一个x）二进制序列，要是我能把其中一位（不妨设为第k位（从左到右计数为0,1,2……））的1变成0，那么这个新的数（不妨设做y）肯定比之前的小，那么y的k位以后的数不管怎么变都会比x小；然后再在这些数中取满足条件的，把个数加起来就好了。

而且这样做不会出现重复，因为改变第k位的时候，我保证第0~k-1位的数不动，所以当从1变成0的位置不同的时候，前缀是不一样的，一定不会重复。

而最高位（最左边的，即k=0）一定是1，当最高位从1变成0的时候，就是求所有二进制总位数比x还小的round number的个数和了。

用bin(x)表示 <=x 的数中有多少个round number。然后从第a个到第b个(包含a,b)就是bin(b) - bin(a-1)。

至于求总位数（即二进制串的长度）比x小的round number的个数和的方法：不管是什么数，只要定下来了，最高位一定是1，所以把长度i定下来（0<i<len((x)₂)），最高位是1，其余位数的0的个数满足不少于1的个数。即：

（在i个位置中选(i+1)/2个位置放置0）

 

由于写的代码实在太少，边界条件经常处理不到位。

出现减法的时候要注意会不会出现负数。

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
using namespace std;
const int maxn = 33;
int c[maxn][maxn];
int num[maxn];
int len[maxn];
void anslen(int i)
{
  if(i == 1){
    len[i] = 0;
    return ;
  }
  int sum = 0;
  //int x = i/2;
  int j = (i+1)/2;
  while(j<=i-1)
  {
    sum += c[i-1][j++];
  }
  anslen(i-1);
  len[i] = len[i-1]+sum;
}
void init()
{
  c[0][0] = 1,c[1][0] = 1;c[1][1] = 1;
  memset(len,0,sizeof len);
  for(int i = 2;i<maxn;i++)
  {
    c[i][0] = c[i][i] = 1;
    for(int j = 1;j<i;j++)
    {
      c[i][j] = c[i-1][j-1]+c[i-1][j];
      //if(c[i][j] < 0)printf("ii:%d\n",i);
      //printf("%d\n",c[i][j]);
    }
  }
  //printf("%d\n",c[3][2]);
  anslen(maxn-1);
  //for(int i = 0;i<maxn;i++)printf("len[%d]:%d\n",i,len[i]);
}
int bin(int a)
{
  memset(num,0,sizeof num);
  memset(count0,0,sizeof count0);
  int t = a,llen = 0,cnt0 = 0;
  while(t>0)
  {
    num[llen] = t%2;
    llen++;
    t=t/2;
  }
  int ans = len[llen-1];
  int tp = (llen+1)/2;
 // cout<<"cnt0:"<<cnt0<<endl;
  for(int i = llen-2;i>=0;i--){
    if(num[i])
    {
      int  base = tp-cnt0-1;
      if(base < 0)base = 0;//就是这里啊！wa到死……
      while(base<=i)
      {
        ans += c[i][base++];
       // printf("i:%d -- c[%d][%d]:%d\n",i,i,base-1,c[i][base-1]);
      }
    }
    else cnt0++;
  }
  if(tp <= cnt0)
  {
    ans ++;
  }
  return ans;

}
int main()
{
  #ifdef LOCALL
  freopen("in","r",stdin);
  //freopen("out1","w",stdout);
  #endif
  init();
  int a,b;
//  for(int i = 1264567;i<1264867;i++)
//    cout<<bin(i-1)<<endl;
  while(scanf("%d%d",&a,&b)!=EOF)
  {
    int x,y;
    if(a == 2||a == 1) x = 0;
    else x = bin(a-1);
    if(b == 1) y = 0;
    else y = bin(b);
    printf("%d\n",y-x);
  }

  return 0;
}

 

POJ1850

http://poj.org/problem?id=1850

组合数学很多时候为了不重复计算，都要固定一个前缀(或后缀，总之)让这个东西成为唯一性的标志。

首先本题由于字符是有序的（相同长度的按照字典序编号，不同长度的按照长度从小到大编号），所以一旦字母确定下来，其升序一定是确定，所以一个序列就是一个组合数。

这道题和上题其实很像，首先当给出一个字符串s时，长度len是已知的。

首先长度比它小的字串，一定在s的前面。因为规定字母不能重复，那么就是26个字母中取0<i<len-1个。

然后长度一样的时候，从左到右第k个字符，每次固定前k-1个，当第k个字符变成从s[k-1]+1到s[k]-1，那么第k+1个到len个的部分可以在s[k-1]+1~'z' 里面随便选(len-k-1)个。这样，到最后一个字母的时候事实上已经把所有长度为len的所有编号小于s[]的可能统计了一遍。

这题有个坑的地方……"or 0 if the word can not be codified."……一开始没看到……wa了一次……

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
using namespace std;
const int maxn = 33;
int c[maxn][maxn];
void init()
{
  c[0][0] = 1,c[1][0] = 1;c[1][1] = 1;
  for(int i = 2;i<maxn;i++)
  {
    c[i][0] = c[i][i] = 1;
    for(int j = 1;j<i;j++)
    {
      c[i][j] = c[i-1][j-1]+c[i-1][j];
    }
  }
}
int main()
{
  #ifdef LOCALL
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  #endif
  init();
  char s[22];

  while(scanf("%s",s)!=EOF)
  {
    int ans = 0;
    int len = strlen(s),flag = 0;
    for(int i = 1;i<len;i++)ans += c[26][i];
    for(int i = 0;i<len;i++){
      int n ,st; n = s[i]-'a';
      if(i){st = s[i-1]-'a'+1;
        if(s[i]<=s[i-1]){flag =1;break;}
      }
      else st = 0;
      //printf("\nn:%d\n",n);
      for(int j = st;j<n;j++){
        ans += c['z'-'a' - j][len-i-1];
        //printf("j:%d\tc[%d][%d]:%d\n",j,'z'-'a'-j,len-i-1, c['z'-'a' - j][len-i-1]);
      }
    }
    if(!flag)printf("%d\n",ans+1);
    else printf("0\n");
  }

  return 0;
}

 

加上前几次CF和近段写题目等的总结下来，代码能力太不够了，把思路实现出来要太长的时间，还不能保证对…… 

总之干巴爹吧！