P5664 [CSP-S2019] Emiya 家今天的饭
容斥一下，对每一列做一次dp,记一下差值来压掉一维
*CF521D Shop
把赋值先转化成加法，再把加法全转化成乘法
P5689 [CSP-S2019 江西] 多叉堆
直接做
P5503 [JSOI2016]灯塔
决策单调性优化dp板子题，转化一下式子然后对决策点分治
P3628 [APIO2010] 特别行动队
直接斜率优化
*CF1320D Reachable Strings
容易想到奇偶分组，然后发现因为0不能越过0，所以相对奇偶性不变，对这个东西哈希一下。
CF311B Cats Transport
注意到铲屎官一定至少恰好接走一只猫，记一下接走每只猫的出发时间，就变成了一个划分的问题，可以斜率优化dp。
CF1715E Long Way Home
考虑只飞一次的情况，先跑出最短路，然后建出凸壳，dp一下更新最短路，把被更新的点重新扔进Dij的队列里，分层跑k次即可。
*[AGC005D] K Perm Counting
与错排的不同点在于有些位置有两种非法状态，所以容斥的时候会碰撞。发现在模k意义下同余的点之间构成一条链，对每条链dp，然后合并起来即可。
CF1753C Wish I Knew How to Sort
考虑把0换出去，期望转方案数，就是里面没换的\(\times\)外面可以换的
CF1613D MEX Sequences
记一下当前的mex和有没有比它大的，直接dp就行了
CF1174D Ehab and the Expected XOR Problem
转化成构造前缀，选一个ban一个
CF1523E Crypto Lights
奥妙题，加深期望转方案的理解
CF981D Bookshelves
从高到低枚举每一位是否可以行，用\(n^3\)的dp$\ $check一下
*CF1634F Fibonacci Additions
转化成判断差分数组\((d_i=f_i-f_{i-1}-f_{i-2})\)是否相同，因为每次修改操作至多改三位，暴力做就可以。
CF1630D Flipping Range
考虑只有一个长度\(len\)怎么做，就是建立关于\(len\)的剩余系，发现正负数的奇偶性不变，然后贪一下。有多个长度就取一下gcd，因为gcd可以表示出所有长度。
*CF1333E Road to 1600
人类智慧题，爆搜出\(3\times3\)的，然后用比较小的数引导车和后强制走到左上角\(3\times3\)里。
CF1737E Ela Goes Hiking
选一下每个人干死前面人的概率，然后每个人win的概率就是自己干死前面人的概率减去后面人全寄了的概率。
CF1630C Paint the Middle
只要考虑端点的情况，考虑区间的每一个连通块，保留端点的下界是线段数+1，倒着删就行。
CF1753D The Beach
转化成空格的移动，黑白染色跑最短路
标签：11,Training,概率,转化成,一下,短路,然后,dp From： https://www.cnblogs.com/xxxXmz/p/16856235.html