问题标题: 酷町堂：1148 奇妙变换（magic）

Question

0

已解决

陈曦

资深天翼

#include<iostream>
#include<string>
using namespace std;
int q,m,n,cnt;
string s="A";
string f(string s){
    for(int i=0;i<s.size();i++){
        if(s[i]=='B') s[i]='A';
        if(s[i]=='A') s.insert(i+1,"B");
    }
    return s;
}
int main(){ 
    cin>>q;
    for(int y=1;y<=q;y++){
        cin>>m>>n;
        s=f(s);
        for(int k=m-1;k<=n-1;k++){
            if(s[k]=='A')
                cnt++;
        }   
        cout<<cnt<<endl;
    }
    return 0;
}

我要疯了

Answer 1

已采纳

张帆

中级天翼

需要找规律嗒，

 len[1]=1,len[2]=2;
    a[1]=1,a[2]=1;
    for(int i=3;i<=91;i++){
        len[i]=len[i-1]+len[i-2];
        a[i]=a[i-1]+a[i-2];
    }

long long cal(long long x){
    if(x==0) return 0;
    int i=1;
    while(len[i]<=x){
        i++;
    } 
    return a[i-1]+cal(x-len[i-1]);
}

每次输入x,y只用输出cal(y)-cal(x-1)就可以嗒。

Answer 2

陈正朔

初级光能

你这样模拟会TLE的，看看数据范围

1≤Q≤5000
1≤m≤n≤2^63

要用递推来优化

问题标题: 酷町堂：1148 奇妙变换（magic）

2 个回答: