2018 牛客多校第二场

2018 牛客多校第二场 个人总结+部分题解

1 dp 入门题

dp[j][i] 表示 到i这个点是跑过来还是走过来的，走过来就是1，跑过来就是0
转移方程
上一次是跑过来或者走过来，这一次都可以走

void init(void){
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;
    for(int i = 0;i < maxn; ++i){
        dp[0][i+1] += (dp[0][i]+dp[1][i]);
        dp[0][i+1] %= mod;
        dp[1][i+k] += dp[0][i];
        dp[1][i+k] %= mod;
    }
    for(int i = 1;i < maxn; ++i)
         ans[i] =(ans[i-1]+dp[0][i]+dp[1][i])%mod;
}

B discount

dp+基环内向树
具体做法看题解（先挖坑）

C message

凸包+dp

D money

就是一个求连续不下降区间的过程，模拟一下就行了

E tree

逆向dp

F trade

先排除***扰的，就跟几何没关系了。。

G transform

看这里详细题解

H travel

裸的树形dp

I car

本来以为是个高科技，没想到推出来试了一发是个模拟

J farm

这一题有很多操作需要学啊
学弟博客

K carpet