作者:睿哲小宝贝 | 来源:互联网 | 2023-10-11 20:32
//在群里看到了老师发布的下面这条消息,许久没打代码,打算找找感觉,第一道就拿捏我了,题目不是很难,但是高数据范围的超时问题一直是我未找到解决办法的一个问题,虽然现在比赛未结束,不过我的错误代码也不具有太多参考性,只是分享出来做个记录,也希望大佬能替我解决。
//不过本篇博客的意义在于这道题的思维,至于那些限制就先抛开,若是样例变简单一点马,那么代码就是可行的
今晚7点,牛客挑战赛65马上开始,时长3h。
300元购物卡、算法竞赛课程、牛可乐大鼠标垫等礼品等你来拿。
比赛地址:https://ac.nowcoder.com/acm/contest/48458#description
链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
题目描述
读入一个正整数nnn,代表将字符串"abc"重复nnn次,形成一个长度为3n3n3n的字符串。
例如n=3n=3n=3时,形成的字符串为"abcabcabc"。
请你计算该字符串中有多少个"acb"子序列。答案对109+710^9+7109+7取模。
输入描述:
一个正整数nnn
1≤n≤1091\le n \le 10^91≤n≤109
输出描述:
"acb"子序列的数量。答案对109+710^9+7109+7取模。
示例1
输入
复制3
3
输出
复制4
4
说明
abcabcabc
abcabcabc
abcabcabc
abcabcabc
如上,四个子序列的位置已加粗。
//我拢共用到了两个办法
第一个方法简单粗暴,就是循环
#include
using namespace std;
int main(){int n,a=0;
string x="abc",y;cin>>n;while(n--){y+=x;}for(int i=0;i}
下面是系统报错
第二个方法是后面想出来的,本人也更倾向于第二个方法,第一种方法就是模拟,我们初学代码时,用到很多模拟,去模拟输出样例的代码解释是如何产生,但还有算法,数学思维等,下面的方法有点类似斐波那契数列的思想,主要是发现其中的规律。
#include
using namespace std;
int main(){int n,i,x=0;cin>>n;int a[n],m;a[1]=0;for(i=2;i<=n;i++){m=i-1;x=m*(m+1)/2;a[i]=(a[i-1]+x)%1000000007;}cout<}