USACO Training3.2 01串 By cellur925

一句话题意：求长度为n的有m个1的大小为第k个的01串。

暑假我做的时候是真·大暴力，用二进制枚举，55分，成功T掉无数点。

正解：开始可以用计数类dp来“预处理”，状态和转移都比较好想。

　　状态：设f[i][j]表示i位二进制数，1的个数不超过j的种类数。

　　转移：f[i][j]=f[i-1][j]+f[i-1][j-1] （当前位取0或1）

　　初值：f[i][0]=0,f[0][i]=0;

然后？我们尝试倒序枚举答案。我们知道在二进制中最高位为1时一定比最高位为0的情况大，所以我们在尝试的过程中，如果当前的k仍大于f[i-1][j]，则第i位一定为1，因为还没达到第k个的要求。所以我们不断将k减去f[i-1][j]，这样不断向下枚举就能得到答案。

Code

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 int n,m;

 ll pos,f[][];

 int main()

 {

     scanf("%d%d%lld",&n,&m,&pos);

     for(int i=;i<=n;i++) f[i][]=,f[][i]=;

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             if(j<=i) f[i][j]=f[i-][j]+f[i-][j-];

             else f[i][j]=f[i][i];

     int a=n,b=m;

     while(a!=)

     {

         if(pos>f[a-][b])

         {

             pos-=f[a-][b];

             printf("");

             a--;b--;

         }

         else

         {

             printf("");

             a--;

         }

     }

     printf("\n");

     return ;

 }

* 注意：开long long 。防止越界。（2^31）

巴特西

USACO Training3.2 01串 By cellur925

最新文章

热门文章