1 条题解

  • 0
    @ 2022-11-9 17:31:28

    疫情传播

    一般给一个数字输出一个数字的都可以优先考虑一下找规律/递推。

    仔仔细细推理了一早上,得到了前几天的人数大概是这么一个情况:

    2, 3 ,4 ,6 ,9 ,13 ,19……

    计算一下两两数字之间的差,发现还是一个和上面一样的数列。这不就是肥不拉几斐波那契数列的一个变种嘛!

    因此,通过“苦思冥想”之后得到结论:每一天的总的被感染人数=前一天已经被感染的+今天新被感染的

    那么如果用数组a来存储,那么a[i]前一天被感染的人数就是a[i-1],当天新增的感染人数就是当天的显性感染者的数量。同时,因为当天显性感染者的数目实际上就等于3天前的总感染人数(三天前的感染人数无论显性隐性,在当前这一天都会变成显性),所以可以得到递推式:

    a[i]=a[i-1]+a[i-3]

    注意取模即可。上代码

    #include<bits/stdc++.h>
    using namespace std;
    int a[1010],n;
    int main()
    {
    	a[1]=2;
    	a[2]=3;
    	a[3]=4;//注意初始化前三天,从第四天开始循环
    	cin>>n;
    	for(int i=4;i<=n;i++)
    		a[i]=(a[i-1]%1000000007+a[i-3]%1000000007)%1000000007;
    	cout<<a[n];
    	return 0;
    }
    

    信息

    ID
    1130
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    50
    已通过
    23
    上传者