常州Day3

逆天，逆天，逆天

T1：

水，过；

T2：

要求所有节点深度和最小，直接bfs树然后求解即可。

T3：

线性dp，条件：

k一定向左走，不然就挂了，dp[i]，表示考虑前i个史莱姆，且第i个向左走，有几种方案。转移方程看代码，可以使用前缀和和解方程优化，甚至可以有等比数列，可是我写了这些都挂了，然后看了一下std发现无一例外这些部分全用暴力，见代码。

#include<bits/stdc++.h>
using namespace std;
int n,k,tmp,dp[1000001],sum[1000001],p2[1000001],mod=1000000007;
int main()
{
    cin>>n>>k;
    p2[0]=1;
    for(int i=1;i<=1000000;i++)
    {
        p2[i]=p2[i-1]*2%mod;
    }
    while(2*(tmp+1)*(tmp+2)<k*(k+1))
    {
        tmp++;
    }
    dp[k]=2;
    for(int i=2;i<=tmp;i++)
    {
        dp[k]=(dp[k]+p2[i-1])%mod;
    } 
    sum[k]=dp[k];
    for(int i=k+1;i<=n;i++)
    {
        while(2*(tmp+1)*(tmp+2)<i*(i+1)) 
        {
            tmp++;
        }
        dp[i]=(sum[i-1]-sum[tmp-1])%mod;
        sum[i]=(sum[i-1]+dp[i])%mod;
    }
    cout<<2*dp[n]%mod;
    return 0;
 } 

死活不A，终于好了=）