目录
- 题目
- 方法一(暴力法:28分)
- 思路分析
- 代码
- 方法二(96分)
题目
方法一(暴力法:28分)
思路分析
- 肯定要先发现数字的规律:
我们以第8行为例,数字由三段构成
- 第一段绿色:是i-3的数字串
- 第二段蓝色:是i-1的去除前几位剩余的数字串,去除的位数等于i-4数字串的位数
- 第三段黄色:是i-2的数字串
得到数字串的规律:str[i] = str[i - 3] + str[i - 1].substr(str[i - 4].size()) + str[i - 2];
- 在字符串中匹配n时用到string.find()函数
这样出现的限制主要在空间方面,内存不够储存数字串
代码
#include<iostream>
#include<string>
using namespace std;
int main()
{
int n;
string s_num;
cin >> n >> s_num;
string str[1010];
str[1]="2";
str[2]="4";
str[3]="16";
str[4]="264";
int ans=0, position=0;
//生成数字串
for(int i=5;i<=n;i++)
str[i]=str[i-3]+str[i-1].substr(str[i-4].size())+str[i-2];
string str_n = str[n];
while ((position = str_n.find(s_num, position)) != string::npos)
{
position++;
ans++;
if(ans>998244353)
ans%=998244353;
}
cout<<ans;
return 0;
}
方法二(96分)
稍后附加