编程介的小学生 2019-05-01 15:54 采纳率: 20.5%
浏览 590

用C语言来计算:字符串的第L位(从1开始)到第R位,含有的B的个数是多少

Problem Description
众所周知,度度熊喜欢的字符只有两个:B和D。

今天,它发明了一种用B和D组成字符串的规则:

S(1)=B

S(2)=BBD

S(3)=BBDBBDD

S(n)=S(n−1)+B+reverse(flip(S(n−1))

其中,reverse(s)指将字符串翻转,比如reverse(BBD)=DBB,flip(s)指将字符串中的B替换为D,D替换为B,比如flip(BBD)=DDB。

虽然度度熊平常只用它的电脑玩连连看,这丝毫不妨碍这台机器无与伦比的运算速度,目前它已经算出了S(21000)的内容,但度度熊毕竟只是只熊,一次读不完这么长的字符串。它现在想知道,这个字符串的第L位(从1开始)到第R位,含有的B的个数是多少?

Input
第一行一个整数T,表示T(1≤T≤1000) 组数据。

每组数据包含两个数L和R(1≤L≤R≤1018) 。

Output
对于每组数据,输出S(21000)表示的字符串的第L位到第R位中B的个数。

Sample Input
3
1 3
1 7
4 8

Sample Output
2
4
3

  • 写回答

1条回答 默认 最新

  • 都市奇人 2019-05-01 20:42
    关注

    思路:

    L[i],R[i]分别表示node==i时这个串的左右端点,dp[i][0]表示node==i时B的个数,dp[i][1]表示D的个数;
    给一个区间[l,r]进行分治,mid=(L[i]+R[i])/2,如果rmid时这时就可以把求node==i-1时的[l,r]的B的
    个数转化成求node==i-1时的[l',r']的D的个数,在转化成求r'-l'-[l',r']里面的B的个数,递归就可以了,
    当l AC代码:
    #include
    /*
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    */
    using namespace std;
    #define Riep(n) for(int i=1;i<=n;i++)
    #define Riop(n) for(int i=0;i #define Rjep(n) for(int j=1;j #define Rjop(n) for(int j=0;j #define mst(ss,b) memset(ss,b,sizeof(ss));
    typedef long long LL;
    const LL mod=1e9+7;
    const double PI=acos(-1.0);
    const int inf=0x3f3f3f3f;
    const int N=1e5+25;
    int n;
    LL L[70],R[70],dp[70][2];
    int fun()
    {
    L[1]=1;
    R[1]=1;
    dp[1][0]=1;
    dp[1][1]=0;
    for(int i=2;i {
    L[i]=1;
    R[i]=2*R[i-1]+1;
    dp[i][0]=dp[i-1][0]+1+dp[i-1][1];
    dp[i][1]=dp[i-1][0]+dp[i-1][1];
    }
    }
    LL dfs(LL l, LL r,int node)
    {
    if(l>r||node if(l==L[node]&&r==R[node])return dp[node][0];
    LL mid=(L[node]+R[node])>>1;
    if(r<=mid)
    {
    if(r==mid)return 1+dfs(l,r-1,node-1);
    else return dfs(l,r,node-1);
    }
    else
    {
    if(l>=mid)
    {
    if(l==mid)return r-l+1-dfs(R[node]-r+1,R[node]-l,node-1);
    else return r-l+1-dfs(R[node]-r+1,R[node]-l+1,node-1);
    }
    else return dfs(l,mid-1,node-1)+1+r-mid-dfs(R[node]-r+1,R[node]-mid,node-1);
    }
    }
    int main()
    {
    int t;
    scanf("%d",&t);
    fun();
    while(t--)
    {
    LL l,r;
    scanf("%I64d%I64d",&l,&r);
    LL ans=dfs(l,r,62);
    printf("%I64d\n",ans);
    }
    return 0;
    }

    评论

报告相同问题?

悬赏问题

  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)