杭州网站建设杭州,丰城做网站,青岛市建设厅网站,网站建设的目标和需求分析资源限制
内存限制#xff1a;256.0MB C/C时间限制#xff1a;10.0s Java时间限制#xff1a;30.0s Python时间限制#xff1a;50.0s
问题描述 斐波那契串由下列规则生成#xff1a; F[0] 0; F[1] 1; F[n] F[n-1] F[n-2]…资源限制
内存限制256.0MB C/C时间限制10.0s Java时间限制30.0s Python时间限制50.0s
问题描述 斐波那契串由下列规则生成 F[0] 0; F[1] 1; F[n] F[n-1] F[n-2] n≥2表示连接 给出一个由0和1构成的串S和一个数n求出F[n]中S出现的次数。
输入格式 第一行一个数n。 第二行一个01串S。
输出格式 答案。
样例输入
96 10110101101101
样例输出
7540113804746346428
数据规模和约定 n≤263-1子串长≤10000答案≤263-1。
暴力特别暴力的方法显然是不行的但是为了方便理解n30还是可以的但这里n很大
#includeiostream
#includestring
using namespace std;
int main(){long long int n;string s10,s21,s3,s;scanf(%d,n);cins;for(int i2;in;i){s3s1s2;s1s2;s2s3;}//求个数long long int cnt0;for(int j0;js3.length();j){if(s3.substr(j,s.length())s){cnt;}} printf(%lld\n,cnt);return 0;
}
以下是100分的代码
#includeiostream
#includestring
using namespace std;
int flag;
long long int L1,L2,L;//成斐波那契数列的答案,L1为第一个不为0的个数L2为第2个不为0的个数
long long int x;//第一个不为0的位置
int main(){long long int n;string s10,s21,s3,s;scanf(%lld,n);cins;for(int i2;in;i){s3s1s2;s1s2;s2s3;for(int j0;js3.length();j){if(s3.substr(j,s.length())s){flag1;break;}} if(flag1){xi; break; }}for(int j0;js3.length();j){if(s3.substr(j,s.length())s){L1;}} s3s1s2;s1s2;s2s3;for(int j0;js3.length();j){if(s3.substr(j,s.length())s){L2;}}for(int ix2;in;i){LL1L21;//规律L1L2;L2L; }printf(%lld\n,L);return 0;
} 思路s串的个数成类似于斐波那契数列的规律。
虽然前面提到的暴力方法不能求解n很大的情况但是前25个绝对没问题根据暴力方法输出前25个来找规律
假设串s10110101101101
#includeiostream
#includestring
using namespace std;
int main(){string s10,s21,s3,s;int n;scanf(%d,n);cins;for(int i2;in;i){s3s1s2;//求个数int cnt0;for(int j0;js3.length();j){if(s3.substr(j,s.length())s){cnt;}} printf(n%d:%d个\n,i,cnt);s1s2;s2s3;}return 0;
} 可以发现从含有串s个数不为0的F[n]之后如F[7]F[8]之后有以下规律 因此只需找到第一个含s串的位置x求出个数L1然后求出位置x1的个数L2之后根据规律即可求出所有。
//但是这个规律好像也不大对当s“01”时 第三个数是前两个数的和不需要1了。。这个方法还是不太严谨虽然它通过了吧。希望可以给你带来一些思路如果有更好的方法欢迎在评论区留言或私信我。
