DP优化&博弈

· · 个人记录

\text\ By\text\ Myself

CF150E/P4292

长链剖分优化DP

二分答案，然后就有一个关于深度的DP，直接转移是 O(n^2) 的。

考虑每次先继承长儿子的DP值，然后再暴力合并轻儿子，因为每个点只会在第一条轻边的地方合并。

淀粉质+BFS+单调队列

代码写起来较复杂。

淀粉质后，BFS连通块根节点的每个子树，因为深度随BFS序只增不减，可以用单调队列来维护区间最大值。但是单调队列有个 O(R) 的预进队过程，可能会使复杂度退化成 O(n^2) 。

于是将儿子按 maxdep 排序，每次只预处理到前一个儿子的 maxdep 即可。

P6773

https://www.luogu.com.cn/paste/4aie2q5n

key observation: 如果 (u,v_1) 被满足且 v_2 深度比 v_1 小且也为 u 的祖先，那么限制 (u,v_2) 也能被满足。

考虑DP设 f_{u,i} 表示确定 u 子树里的边，u 子树外的深度最深的限制深度为 i ，没有限制为 f_{u,0} ，转移的话在合并 u 的儿子 v 时，考虑边 (u,v) 为 1 还是为 0 即可，有：

f_{u,i}=f_{u,i}\sum_{j=0}^{dep_v-1}f_{v,j}+f_{u,i}\sum_{j=0}^i f_{v,j}+f_{v,i}\sum_{j=0}^{i-1}f_{u,j}

记 g_{u,i}=\sum_{j=0}^if_{u,i} ,则：

f_{u,i}=f_{u,i}(g_{v,dep_u}+g_{v,i})+g_{u,i-1}f_{v,i}

直接做是 O(n^2) 的，线段树合并优化即可。

具体的，以DP的第二维为下标，即深度。合并时维护对于 u,v 分别维护两个前缀和标记，遇到一边空的节点就不再往下递归，只打个乘法标记。


//sx的初值为0,sy的初值为g[v][dep[u]] 

inline int merge(int x,int y,int l,int r,ll &sx,ll &sy){
    if(!x&&!y) return 0;
    if(!x){
        sy=(sy+f[y])%mod;
        f[y]=f[y]*sx%mod;
        tag[y]=tag[y]*sx%mod;
        return y;
    }
    if(!y){
        sx=(sx+f[x])%mod;
        f[x]=f[x]*sy%mod;
        tag[x]=tag[x]*sy%mod;
        return x;
    }
    if(l==r){
        ll u=f[x],v=f[y];
        sy=(sy+v)%mod;
        f[x]=(f[x]*sy+f[y]*sx)%mod;
        sx=(sx+u)%mod;
        return x;   
    }
    RI mid=l+r>>1;
    down(x);down(y); 
    lc[x]=merge(lc[x],lc[y],l,mid,sx,sy);
    rc[x]=merge(rc[x],rc[y],mid+1,r,sx,sy);
    up(x);
    return x;
}

AT_agc023_d

https://www.luogu.com.cn/paste/gb65z5c1

看起来很神仙的博弈题，不敢相信自己做出来了。

其实也不难，只要想到点上就可以秒掉。

从最外围的两个点开始考虑，假如只剩它们两个点 x,y 的话，是肯定能分出大小的。那么考虑小的那一边， 假设为 x ，那么它的到达时间 T(x) 其实可以写作 T(y)+|x-y| ，为什么呢？因为 x 在到家之前，肯定会存在一段孤身在车的一侧的情况，而如果当前 y 没有到家，那么单凭 y 就可以调转车头，所以 x 必须等 y 到了之后才能到家。

于是， x 肯定会帮助 y 先到家，将 y 的人数加上 x 的人数，并把 x 在数轴上删除。

重复以上操作，直到 s 的一边没有点。

AT_arc137_c

经典博弈结论：

证明：

若 x 为必败状态，则有 S->x ，所以 S 为必胜状态；

若 x 为必胜状态，则\exists x->y 满足 y 为必败状态，又 S->y ，所以 S 为必胜状态；

显然对于 a_n>a_{n-1}+1 的情况，有 a_n->x,(x>a_{n-1}) ，而接下来的所有 x 的转移状态，a_n 都可以达到，所以这种情况直接判 Alice 赢。

剩下的判断奇偶性即可。

\text\ By\text\ Emissary

AT_agc002_e

将 a_i 从大到小排序，那么每次操作看作向右或向上走一步，不能走的判负。

记 f(x,y) 表示 (x,y) 的胜负状态。

结论: f(x,y)=f(x+1,y+1) 。

证明：如果 f(x,y)=1 ，则 f(x+1,y)=0 或者 f(x,y+1)=0 ，于是 f(x+1,y+1)=1 ；如果 f(x,y)=0 ，则 f(x+1,y)=f(x,y+1)=1 ，然后 f(x+2,y+1)=f(x+1,y+2)=1 ，最后发现 f(x+1,y+1) 无论如何都会走到 1 ，于是 f(x+1,y+1) 。

所以找到右上靠边界的点，判断其往右和往上的奇偶性。

P6189

拆分数经典求法。

考虑根号分治，对于 x_i\le B 的数，直接做一个 O(nB) 的背包；对于 x_i>B 的数，其出现次数不会超过 \frac{n}{B} 次，直接做一个拆分数，考虑每次加一个 B+1 ，或者将所有数 +1 。

最后将二者合并即可。

\text\ By\text\ Oscar

P8290

喵喵题。

首先考虑暴力，枚举钦定的最小值 x ，则取值范围为 [x,x+k] ，那么 x 做最小值的贡献为 [x,x+k]-[x+1,x+k] ，换根DP算出 f(x) 。

接着考虑优化掉 O(k) ，然后发现每个点关于 x 的区间是个分段函数，总体的区间段数为 O(n) ，每一段的区间取值类似，于是可以考虑对每一段分别快速计算答案。

对于一段的答案，它是一个 n+1 次函数，将其前缀和就变成了 n+2 次多项式，然后考虑拉插，换根DP算出前 n+3 项的值，然后 计算这一整段的答案即可。

CF1866I

随便手玩一下，发现每行除关键点最多有一个为 0 ，双指针扫一下即可。

\text\ By\text\ tytyty

P4055

二分图博弈板子。

结论：先手必胜当且仅当起点为二分图最大匹配的必经点。

证明就不写了。

求必经点：

跑个最大匹配，首先不在可行解中的点肯定不是，然后发现可以被这些点代替的点也不是。

于是，在残余网络中从源点沿流量 1 的边跑到的左部点不合法，从汇点沿着 0 的边跑到的右部点不合法，其余的合法。

\text\ By\text\ Mr.Avalan

CF708E

喵喵题。

首先左右的格子消失互不影响，设 p= \frac{a}{b}\pmod {10^9+7} 一边 k 天消失 i 个格子有 P_i={k\choose i}p^i{(1-p)}^{k-i} 。

设 f_{i,l,r} 表示考虑完前 i 行，上一行为 [l,r] 的概率，再加上一堆前缀和优化就可以做到 O(n^3) ，但是还是过不去。

但是，这题有一个关键性质：对称性。

设 f_{i,r} 表示考虑完前 i 行，上一行为右端点为 r 的概率，转移的话考虑用所有的减去不合法的，假设这一行为 l,r ，上一行为 l',r' ，不合法的情况有：

r'<l, \sum_{j=1}^{l-1} f_{i-1,j} l'>r, \sum_{j=1}^{m-r} f_{i-1,j}

其中第二个转移运用了对称性，于是:

f_{i,r}=\sum_{l=1}^r P_lP_{r-m}(\sum_{j=1}^m f_{i-1,j}-\sum_{j=1}^{l-1} f_{i-1,j}-\sum_{j=1}^{m-r} f_{i-1,j})

然后随便前缀和优化一下即可。

理解

运用对称性来解题的想法太妙了！

\text\ By\text\ 0ccdreamer

P6144

首先，这题有个 k 次方，我们考虑怎么维护在 k 次方的意义下将 x^k 变为 (x+1)^k 。

因为 k 很小，所以可以维护每个 x^i,(i\le k) ，根据二项式定理暴力展开，将 x^i 乘以对应的系数加在一起即可。

不同寻常地，按左端点升序排序，设 f_i 表示以位置 i 结尾的方案数。

转移的话有三种情况:

发现可以用线段树简单维护。

AT_agc010_d

容易想到这题和奇偶性有关。

如果 \sum (a_i-1) 为奇数，那么先手每次操作都可以将一个偶数变为奇数，使所有数不会除以一个偶数，那么奇偶性不变，先手必胜。

否则先手不能让后手碰到以上情况，所以只能让所有数不会除以一个偶数，然后转换先后手。

这样的话每一次的最优操作是唯一的，照着上面的策略模拟即可，每次所有数至少除以 2，所以总操作次数为 O(log n) 。

\text\ By\text\ RY

P7519

有一个显然的DP状态是设 f_{S,i,j,k} 表示当前已选为 S ，代价 i ，上一个数为 j ，加了 b_j=k 的方案数，显然过不去。

考虑优化状态，因为要满足 b_i 不降，那不如直接每次加上一个差分值，同时将这个差分值往后的代价都算上，于是就省去了 k 那一位状态。

理解

看到单增、单减，可以往差分那方面想。

\text\ By\text\ Diwanul

AT_agc010_f

最优策略下，棋子必然往 a_i 更小的位置移动，暴力判断即可。