常州集训DAY3

总算没很寄了
T1 水题不说，直接输出log₁₀（n）个9或者n即可
T2 赛时我是用多源最短路AC的，但赛后讲解时时算树的深度。由于每个父节点的值要大于所有子节点的值之和，对于一个根节点，其他任意=一节点对答案的贡献就是该节点到根节点的最短路。但每次都跑单源最短路加上枚举根节点一定会TLE，每次枚举根节点后跑多源最短路也会，所以就先跑多源最短路预处理后再枚举每一个节点作为根节点时的答案，然后去最小值就行。代码就不贴了~其实是被ntscz吞了
T3 DP,对每个史莱姆进行线性DP即可，但由于我只改到了60分就不细说了（怕有错），~标程都快成我代码的形状了（虽然标程被我往我的代码的方向改后也只有60分了）~直接贴代码吧。
这是我的代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,a[10000005],t,dp[10000005][2];
signed main()
{
//  freopen("game.in","r",stdin);
//  freopen("game.out","w",stdout);
    cin>>n>>k;
    if(k==1)
    {
        cout<<"0"<<endl;
        return 0;
    }
    a[0]=1;
    for(int i=1;i<=n;i++)
    {
        a[i]=2*a[i-1];
        a[i]%=1000000007;
    }
    while(2*(t+2)*(t+1)<k*(k+1))
    {
        t++;
    }
//  t+=1;
    dp[k][0]=2;
    dp[k][1]=2;
    for(int i=2;i<=t;i++)
    {
        dp[k][0]+=a[i-1];
        dp[k][0]%=1000000007;
        dp[k][1]=dp[k][0];
    }
//  cout<<dp[k][1]<<endl;
    for(int i=k+1;i<=n;i++)
    {
        while(2*t*(t+1)<i*(i+1))
        {
            t++;            
        }
        dp[i][0]=dp[i-1][1];
        dp[i][0]-=dp[t-1][1];
        dp[i][0]%=1000000007;
        dp[i][1]=(dp[i-1][1]+dp[i][0])%1000000007;
    }
    cout<<(2*dp[n][0])%1000000007<<endl;
}

这是被我改爆的标程

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define mod 1000000007
#define int long long
using namespace std;
int pw[1000010],dp[1000010],pre[1000010],tmp,n,k;
signed main()
{
//  freopen("game.in","r",stdin);
//  freopen("game.out","w",stdout);
    pw[0]=1;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        pw[i]=(2*pw[i-1])%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]+pw[i-1])%mod;
    pre[k]=dp[k];
//  cout<<pre[k]<<endl;
    rep(i,k+1,n)
    {
        while(2*tmp*(tmp+1)<i*(i+1))tmp++;
        dp[i]=pre[i-1];dp[i]=(dp[i]-pre[tmp-1])%mod;
        pre[i]=(pre[i-1]+dp[i])%mod;
    }
    cout<<(2*dp[n])%mod;
    return 0;
}