注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

noip2006之第四题  

2008-05-24 11:40:43|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

/*4.2k进制数(digital.pas/c/cpp)
【问题描述】
设r是个2k 进制数,并满足以下条件:
(1)r至少是个2位的2k 进制数。
(2)作为2k 进制数,除最后一位外,r的每一位严格小于它右边相邻的那一位。
(3)将r转换为2进制数q后,则q的总位数不超过w。
在这里,正整数k(1≤k≤9)和w(k≤30000)是事先给定的。问:满足上述条件的不同的r共有多少个?

我们再从另一角度作些解释:设S是长度为w 的01字符串(即字符串S由w个“0”或“1”组成),S对应于

上述条件(3)中的q。将S从右起划分为若干个长度为k 的段,每段对应一位2k进制的数,如果S至少可分

成2段,则S所对应的二进制数又可以转换为上述的2k 进制数r。例:设k=3,w=7。则r是个八进制数

(23=8)。由于w=7,长度为7的01字符串按3位一段分,可分为3段(即1,3,3,左边第一段只有一个二

进制位),则满足条件的八进制数有:2位数:高位为1:6个(即12,13,14,15,16,17),高位为2:

5个,…,高位为6:1个(即67)。共6+5+…+1=21个。3位数:高位只能是1,第2位为2:5个(即123,

124,125,126,127),第2位为3:4个,…,第2位为6:1个(即167)。共5+4+…+1=15个。所以,满足

要求的r共有36个。
【输入文件】
输入文件digital.in只有1行,为两个正整数,用一个空格隔开:
k    W
【输出文件】输出文件digital.out为1行,是一个正整数,为所求的计算结果,即满足条件的不同的r的

个数(用十进制数表示),要求最高位不得为0,各数字之间不得插入数字以外的其他字符(例如空格、

换行符、逗号等)。(提示:作为结果的正整数可能很大,但不会超过200位)*/

//myprogram:

#include <fstream>
#include <iostream>
using namespace std;
struct big_num{
       int num[201];
};
int K;
int W;
int k2[10];
ifstream fin("digital.in");
ofstream fout("digital.out");
int inibn(big_num &who)
{
    for(int i=0;i<201;i++)who.num[i]=0;
    return 0;
}
big_num chengfa(big_num who,int how)
{
        int i,j=0,k;
        for (i=0;i<201;i++)
        {
            k=who.num[i]*how+j;
            j=k/10;
            who.num[i]=k%10;
        }
        return who;
}
big_num chufa(big_num who,int how)
{
        big_num r;
        inibn(r);
        int i,j,k;
        int yushu=0;
        for (i=200;i>=0;i--)
        {
            yushu=yushu*10+who.num[i];
            r.num[i]=yushu/how;
            yushu%=how;
        }
        return r;
}
big_num jisuan(int a,int b)
{
        big_num j;
        inibn(j);
        j.num[0]=1;
        int i;
        for (i=b;i+a>b;i--)
        {
            j=chengfa(j,i);
            j=chufa(j,b-i+1);
        }
        return j;
}
int outputit(big_num he)
{
    int i,j;
    for (i=200;i>0 && (he.num[i]==0);i--)0;
    for (i;i>=0;i--)fout<<he.num[i];
    fout <<endl;
}
int main()
{
    k2[0]=1;
    k2[1]=2;
    k2[2]=4;
    k2[3]=8;
    k2[4]=16;
    k2[5]=32;
    k2[6]=64;
    k2[7]=128;
    k2[8]=256;
    k2[9]=512;
    fin >>K>>W;
    big_num res;
    inibn(res);
    if (W%K==0)
    {
       res=jisuan(W/K,k2[K]-1);
    }
    else
    {
        res=jisuan(W/K,k2[K]-2);
        res=chengfa(res,k2[W%K]-1);
    }
    outputit(res);
    fin.close();
    fout.close();
    return 0;
}

  评论这张
 
阅读(332)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017