骰子的学问

构造的本质在于找到合理的决策中最有秩序的一种，将实在无法解决的概念拆成更简单的信息，会降低问题的难度。

我们发现按照骰子 $x$ 大于骰子 $y$ 的关系建立有向图，就形成了一个基环内向树森林。

将图分成两部分，分别是环内（很明显环长要大于$2$筛子数也是）和环外，对于任意的处于环外的点，它应当保证所有的父亲均大于它。那么可以形成一种在环外的构造方法：

对于环外的每一个点，保证保证它的父亲的每一面的点数都比它的最大点数大。显然环外的骰子直接分配极大值就行了。

环内的点构成非传递性悖论，两个骰子可以等概率的投出 $m^2$ 种组合。因此对于一个合法的填法，任意一个点与它的后继形成的组合中应至少有 $\left \lceil \frac{m^2 + 1}{2} \right \rceil$ 种满足前者较大。

连续向父亲的连续往大的填数，可以保证本点外的后继传递，不难发现只要一个点不被选中多次，就可以构造一个合法方案。

对于任意的 $i > j$ ，在这种构造下都满足了任何一个骰子的第 $i$ 面一定比另一个骰子的第 $j$ 面大，所以相邻的骰子一定存在 $\frac{m \cdot (m- 1)}{2}$ 种情况是保证了前驱大于后继的。

对于填在第 $i$ 个骰子上的 $q$ 个数除了最大的一个数所在的骰子的前驱，所有的数都大于自己的后继。那么实际上就相当于给每个骰子都增加的 $m$ 种可行情况。而同时会进行 $m$ 次选择，选择哪一个骰子为起点。每次选择会将这个骰子大于后继的数量减一。

而对于任意的一个骰子，被选出的次数最多应该为 $\frac{m \cdot (m+1)}{2} - \left \lceil \frac{m^2 + 1}{2} \right \rceil$ 而总选择次数应该乘以一个 $q$

构造为选择一个，向父亲方向依次放下 $(1,n)$ 的值，再选择另一个，向父亲方向依次放下 $(n+1,2n)$ 。如此重复直到填满。

为了方便实现可将原有环内操作修改为如下：

选择一个点，向父亲方向依次放下 $(1,n)$ 的值，再选择它的父亲，向父亲方向依次放下 $(n+1,2n)$ 。如此重复直到填满。

这样显然与原有结论并不矛盾，同时又方便实践。

但对于被选出次数还要进一步讨论，不难发现要对 $m$ 为奇数和偶数的情况分类讨论，从而得到这个构造方式对于 $q=3,m=4$ 的情况不合法，手动模拟后单独构造即可。

最后用拓扑排序解决。

波浪

我们人为定义一个顺序，将贡献改为插值计算。

考虑 拆开绝对值计算贡献，对于 $1$ 到 $N$ 的排列，从小到大地将插入它们插入排列中，假设即将插入数 $i$ ，则前 $i−1$ 个数已经被插入到排列中。考虑如何计算 $i$ 的贡献。

不难发现：在最终的排列中，$i$ 的贡献与它和前 $i−1$ 个数和边界的相邻情况有关。如果 $i$ 某一边与边界相邻，会产生 $0$ 的贡献；某一边与小于 $i$ 的数相邻，会产生 $i$ 的贡献；某一边与大于 $i$ 的数相邻，会产生 $−i$ 的贡献。

但是在这里大于 $i$ 的数还没有被插入，所以这里必须要强制数 $i$ 与前 $i−1$ 个数和边界的相邻情况才能够在当前阶段计算出 $i$ 对序列价值的贡献。

设 $f_{i,j,k,l}$ 表示放完前 $i$ 个数、数列中存在 $j$ 个连通块（定义连通块为一段极长区间，满足这一段区间任意的相邻的两个数都被强制定为相邻，也就是说在之后的转移中，这一段区间内不能插入数）、数列总价值为 $k−5000$、有 $l$ 个边界已经与某个数强制相邻的方案数。

转移考虑数 $i$ 的相邻情况：

1. 一边与边界相邻，一边不与当前存在的连通块相邻。这会产生额外的一个连通块，并产生 $−i$ 的价值，方案数为 $2−l$；

2. 一边与边界相邻，一边与当前存在的连通块相邻。这不会导致连通块数变化，产生 $i$ 的价值，方案数为 $2−l$ ，要求 $j \neq 0$；

3. 两边均与当前存在的连通块相邻。这会导致两个连通块合并从而连通块数减少 $1$，产生 $2i$ 的价值，方案数为 $j−1$ ，要求 $j \geq 2$；

4. 两边均不与当前存在的连通块相邻。这会产生额外的一个连通块，产生 $-2i$ 的价值，方案数为 $j+1-l$；

5. 一边与当前存在的连通块相邻，另一边不与当前存在的连通块相邻。这不会产生额外的连通块，产生 $0$ 的价值，方案数为 $2j−l$ ，要求 $j \neq 0$。

注意到 $45$ 两种转移的方案数都减去了 $l$，因为对于两端都不与边界相邻的连通块，可以选择左右之一与当前的数相邻，但是有一段与边界相邻的连通块只有另一端可以。

答案是 $\frac{\sum\limits_{i=5000+M}^{10000} f_{N,1,i,2}}{n!}$

千年虫

设$f[0/1][i][j]$表示需要加的最小块数，
$0$凹,$1$凸，$i$为行，可以滚一维，$j$为该行长度
$f[0][i][j]=min(f[0][i−1][j],f[1][i−1][k])+j−a[i];k> j$
$f[1][i][j]=min(f[1][i−1][j],f[0][i−1][k])+j−a[i];k< j$

然后我们在每一维维护一下最小值就可以 $O(n^2)$ 转移。

转移已经优化到头了，再去找一下结论，通过打表，我们发现最优转移点距离与当层$j$在一个较小的区间内。

考虑证明，我们首先考虑一下如果每段长度都是 $1$（即相邻两数都不相等），那么有显然的结论：若 $i$ 在谷，那么 $b_i=a_i$，若 $i$ 在峰，那么 $b_i=\max(a_i,a_{i-1}+1,a_{i+1}+1)$。因为一个谷的位置我们一定不会给它加，而峰的位置只要加到比相邻两数大即可。

然而现在麻烦的地方在于段长度不为 $1$ 的时候。

我们的思路是先随便考虑一个合法的解，然后来改造它使得代价不增并使它满足一些特殊的性质。

也就是用调整法构造。

数组游戏

我们现在要做的就是求每个数的SG值，首先得找出数$x$的后继状态。

我们假设只有$x$是白色。于是，我们可以选择翻$x,2x,\dots,kx$。翻完之后$x$会变黑，其他的会变白。

根据翻棋子游戏的解法，此时这个后继状态的SG值为现在的白色棋子的SG值异或和。由于只翻$x$时没有任何棋子是白色，故此后继状态SG值为$0$。其他后继状态的SG值分别为$SG(2x)，SG(2x) xor SG(3x)，\dots…$，故我们得到当前的$S_x=[0,SG(2x),SG(2x) xor SG(3x),\dots ]$。由于$2x,3x,\dots$ 均大于$x$，所以需要从大至小推SG值。

对于$\left\lfloor \dfrac{n}{x} \right\rfloor$相同的$x$有$SG(x)$相同，直接数论分块处理，

则我们只需将此状态的SG值与当前维护的前缀异或和取异或得到的结果标记入$S_x$，然后再判断区间长度奇偶性，奇数则将前缀异或和异或上此状态的SG值，否则前缀异或和不变。

预处理出SG就可以求解了。

取石头游戏

根据对抗搜索，为了简化信息，我们维护先手收益减去后手收益的值 $val$。

继续分析题目性质，发现取石子的过程可以转化为两端分别有一个栈，可以从栈顶取石子，中间有若干个双端队列，可以从其两端取石子。

如果取一个位置后，接下来的位置比刚才取的那个位置权值小，也就是从选择方向开始权值是递减的，每次决策肯定都是取当前局面权值最大的位置。如果不保证递减，就有可能取完一个位置后，使得一个权值更大的位置可以取，这时按最大值决策就有可能不是最优。

对于 $a_{i-1},a_i,a_{i+1}$，若其满足 $a_i \geqslant a_{i-1},a_i \geqslant a_{i+1}$，当一次决策选 $a_{i-1}$最优时，

先手选 $a_{i-1}$，其后手一定会接着选 $a_i$，然后先手会接着选 $a_{i+1}$。选 $a_{i-1}$时，当前局面一定没有比 $a_{i-1}$更好的选择，而 $a_i$比 $a_{i-1}$更优，所以后手一定选 $a_i$，因为之前 $a_{i-1}$ 是最优的选择，所以先手会接着选 $a_{i+1}$。

因此把 $a_{i-1},a_i,a_{i+1}$ 对 $val$ 的贡献看作整体，将其合并为一个权值为 $a_{i-1}+a_{i+1}-a_i$ 的石子。

合并完后所有的权值情况只存在递增，递减和下凹的情况了，这三个情况对于双端队列都是可以单调的从大到小选，对于从栈顶方向开始递减的栈的部分位置，也是可以单调的从大到小选，这些位置就可以直接排序后先后手一个一个选了。

而对于从栈顶方向开始递增的栈的部分位置，一定是最后才开始选的，因为这些决策一定是劣于其他决策，提前处理出其选择的结果，最后根据先后手的情况分配即可。

合并删除操作可以用链表来实现。

围棋

明显是轮廓线$DP$，由于匹配时只需要去掉最后一步就是不合法的，所以用容斥的思想计算不合法方案，

设$f_{x,y,k,i,j}$表示当前考虑到第$x$行第$y$列，上面的轮廓线状态为$i$，矩阵第一行匹配的位置为$j$，第二行匹配位置为的方案总数$k$。$x$和$y$这两维可以不存，滚动。

对于所有$x$和$y$，初始状态为$f_{x,y,0,0,0}=1$。计算到新的一行时，所有上一行的$f_{x-1,y,i,j,k}$都要转移到$f_{x,y,0,0,0}$。

由匹配不难想到可以预处理两行的失配函数，记为$nxt_{0,x}$和$nxt_{1,x}$，

同时预处理出模式串位置$x$对应的文本串位置上的值是$v$的话的失配函数，记为$t_{0,x,v}$和$t_{1,x,v}$。

转移的过程中，当$i$和$j$达到$c$时，很显然存在这样的匹配，应该删掉这种情况，此时值应设为$0$；其他时候，将$i$或$j$沿着失配边向前跳一下。

淘金

数位$DP$，首先需要想到转置（题目提示），从质因数出发，减少状态数量，

$dp[i,j,0/1]$表示从低到高位到了第$i$位，各位数的积为$j$（需要离散化），第三维表示小于等于/大于$N$的从低到高前$i$位。

等于求表格前$K$大值，用大根堆维护。

话旧

有前置知识的题，这个函数一旦下降就只能下降到$0$点，

上升下降相交在何处可以用两点坐标判断，本质是一个状态机。

但落地情况很$interesting$啊，用插板法统计并化简得 2^{y-1} * 2 = 2^y。

第二问记得如果它不能上升，我们就让它下降到 $0$ ，以这个点作为我们之前分析的 $B$（最低点） 点，

电阻网络

二端串并联图板子题，首先要判定二端串并联图，

我们考虑选择的源点和汇点，如果两个点在同一点双以内，则我们可以在 SPQ 上直接判定两点是否在同一串联节点以内可以得到。

否则从割点分离每个点双，判断两个点双路径上的每个点双的两个端点是否为二端串并联图。

考虑对每个点双建出 SPQ 树，同时计算出该点双内部的对答案的贡献，即每个 串联节点 的儿子中任意选两个 非源汇 的方案数。

同时这个点双的根仍然可能是其他点双的根或者一部分。

令一个数组 dp 记录每个节点 作为源点并且作为点双根的时候能够向上贡献二端串并联图的个数。

这样在上面他作为点双一部分时就可以直接调用贡献算出跨越点双的答案。

在串联节点和并联节点分别加减该有的贡献就可以直接算出答案。

线段树

显然枚举所有情况不可行，考虑未来概率$DP$，那怎么转移呢？

维护较小值，等价于连续较少值区间从左右端点开始缩小，如果是$01$序列的话，可以 $O(n^2q)$ 解决。

不难发现对于一般序列，我们也可以拆成$01$的形式，复杂度 $O(n^3q)$，统计每一个位置最终为 $0$ 的方案数。

可以发现，所有的 $dp$ 值的转移式子都完全一致，所以我们可以把所有初始值放到同一个 $dp$ 数组里面，然后进行一次整体的 $dp$，就可以求出答案。

具体地说$f(v,i,l,r)$实际对答案的贡献为$f(v,i,l,r)(val[v]-val[v+1])$

那么我们可以直接带着总贡献DP，也就是我们设$dp(i,l,r)=\sum_v f(v,i,l,r)(val[v]-val[v+1])$

实际的转移方程是不变的。

UCI-The Great Escape

在走螺旋线，而螺旋状的本质就是一个个不断缩小的矩阵。

只要知道在哪个矩形上走，向着哪个方向走就可以了，由于还有建筑物，复杂度 $O(n^5)$，但其实可以优化至 $O(1)$ 判断，复杂度 $O(n^4)$。

/*
最初的方程: 
f[u][r][d][l][上]=∑f[k][r][d][l+1][右]*(路径上无障碍?1:0) 
f[u][r][d][l][右]=∑f[u+1][k][d][l][下]*(路径上无障碍?1:0)
f[u][r][d][l][下]=∑f[u][r-1][k][l][左]*(路径上无障碍?1:0)
f[u][r][d][l][左]=∑f[u][r][d-1][k][上]*(路径上无障碍?1:0)
这个显然是n^5的，时间会炸
但是我们仔细一看就会发现 
f[u][r][d][l][上]=∑f[k][r][d][l+1][右]*check(k)+f[u][r][d][l+1][右]*check(u)
f[u][r][d][l][右]=∑f[u+1][k][d][l][下]*check(k)+f[u+1][r][d][l][下]*check(u)
f[u][r][d][l][下]=∑f[u][r-1][k][l][左]*check(k)+f[u][r-1][d][l][左]*check(u)
f[u][r][d][l][左]=∑f[u][r][d-1][k][上]*check(k)+f[u][r][d-1][l][上]*check(u)
其中k的范围会缩小一步。
也就是说，转移方程可以写成这样 
f[u][r][d][l][上]=f[u][r][d][l+1][右]*(路径上无障碍?1:0)+f[u+1][r][d][l][上]
f[u][r][d][l][右]=f[u+1][r][d][l][下]*(路径上无障碍?1:0) +f[u][r-1][d][l][右]
f[u][r][d][l][下]=f[u][r-1][d][l][左]*(路径上无障碍?1:0)+f[u][r][d-1][l][下]
f[u][r][d][l][左]=f[u][r][d-1][l][上]*(路径上无障碍?1:0)+f[u][r][d][l+1][左]
但是发现空间不够用 
不过，我们可以发现的是，每次转移，行数+列数恰好减少1,然后刚好转移也是一步步来的，可以滚动数组优化掉
*/              

WYR-Leveling Ground

不显然的序列，还和$>1$个数相关？直接上差分就好了。

以上当然是开玩笑，但这题一眼差分，然后自然想到了 $gcd(a,b)$，注意这个差分序列要在末尾添加一个$-a_n$，这样就能够处理以结尾为右端点的区间的情况。

首先考虑对每个差分值单独求解，等于解二元不定方程，显然只有右边整除$d$时有解，我们只需要检查 $x_i$ 和 $y_i$ 分别取到最小非负整数和最大负整数的情况。

然后考虑组合的情况，这里值得说一下，很多题都有从单个/特殊值/杂项的从特殊到一般的转化过程，这之所以是难，大半是在后效性，这让题目似乎不符合之前的逻辑，实则不然，我们虽然无法用之前的逻辑硬套，然而我们有先想办法或者分类转化为特殊情况再对此找性质和找性质并用数据结构优化以及简单直观的方法。

在这里我们无法根据分类和确定管辖的方式消除后效性，最智慧的技巧是用数据结构 反悔贪心，由于$x,y$是方程的解，所以维护一个即可，

每次取出代价最小的 $i$ 并弹出，在需求次数与不改变符号的限制下尽可能多地调整。若经过调整后需求次数为 $0$，则算法结束，否则将新的调整代价压入堆。