网格

答案只可以是无解或者 $0,1,2$（围棋常识）。

显然若图不连通为$0$，有割点为$1$，不够两个点无解，其余为$2$。

数据提示我们复杂度和$c$有关，不难发现 $0,1$ 最好和已有点配合，优化建图。

显然只需要保留：

1. 与网格四个角的至少一个角的 $x,y$ 坐标之差 $\leq2$（处理边界）

2. 与某个黑点八连通

3. 在网格的上边或下边上，且所在列有至少一个黑点

4. 在网格的左边或右边上，且所在行有至少一个黑点

然后对于 所有剩下的白点，若两个白点点在同一行或者同一列，且中间没有其它点（包括没有保留的点），就连一条边。

对于两个白格子，一个白格子的图特判即可。

国王饮水记

先找贪心策略，不难从小情况出发得出并证明如下策略：

1. 只考虑比第一个数大的数。

2. 在一般情况下，一个一个操作(可能会超过 $k$ 次，所以是在一般情况下)。

3. 在一个一个操作时，从小到大操作。

此时难点是找出该在那一段区间操作，由如上策略，排序设计$DP$，前缀和优化，

此时，我们发现$DP$可以斜率优化，且前缀和具有单调性，复杂度 $O(nkp)$，转移已经优化到了尽头，回归题目挖掘性质。

首先，一个明显的单调性是 每一次操作的区间长度一定不比上一次操作的区间长度长。 其实就是越大的饼越少与人分享（之所以分享是因为他们的饼更大可以白嫖）。

还有一个不明显的结论，在所有水量高度互不相同的情况下（题目给出的性质），长度大于 $1$ 的区间仅有 $O(\log{ \frac{nh}{H}})$个，其中 $H=\min(h_i-h_{i-1})$。

官方证明非常不严谨，我们暴力打表，大概发现最多14层，之后就不会再有大于1的区间出现。

那么我们DP14层之后就可以直接计算答案了。

成长快乐

提交答案题，采用非完美程序法，第一组数据直接手算，第二组数据暴搜顺序。

好了，进入正题，本题有两种特殊数据，第一类，数字金字塔，第二类，接礼物。

第一类中，虾米不会移动，且排的位置恰好构成金字塔形，由于时间上的限制，$Nemo$ 恰好可以从上到下走一次，可以用 $DP$ 求解，得 $10$ 分。

第二类，虾米都以超高速从上向下垂直移动（我们可以预处理它们掉到某一点的时间，并按此排序），而 $Nemo$ 处于最底层，由于$Nemo$不可能追上虾米，所以$Nemo$必然与虾米迎面碰撞，所以按照$Nemo$向上走不同距离的情况枚举答案，只考虑左右移动，显然可以用三参$DP$处理，滚掉时间就是双参。

第三类可以类似第二类，所有小虾静止不动且在一条直线上，一个简单的双参区间$DP$即可处理，就是第二类的简化。

第四类所有小虾静止不动，但没有其它性质，设置价值后用随机化贪心调参求出，第五类小虾运动同理、

讲一下随机化贪心的构造，首先根据余弦定理用求根公式求较小正根。

每次在当前所有能吃的食物中按某种关系选出最优的那一个并吃掉。重复该流程直至找不到可以吃的食物为止。

设对于一个食物 $i$，其权值为 $w_i$，nemo 吃掉它所需时间为 $t_i$，nemo 吃掉它时 nemo 的位置距当前位置为 $d_i$。

肯定会有一些感性的认识：$w_i$ 越大越好，$t_i$ 越小越好，$d_i$ 越小越好。

因为我太懒了，直接用Aly的参数，$k_i = \frac{w_i}{t_i^2} + \frac{1}{K_1d_i}$

每次选 $k_i$ 最大的吃。$K_1,K_2$ 为两个 $[1,10]$ 的随机数。

多次贪心取最优解，这里在十次以内就可以出。

智能车比赛

贪心

显然两点之间走直线要比折线短.先求出所有矩形相交的那部分线段(就叫通道好了),取其中点,从左到右相连,这样就得到了一个折线的路径,然后不断对其进行修正:

假设我们到了第i个相交部分上的点

1. 若i-1和i+1直接相连能从这个通道通过,则相连之

2. 若不能的话,折线向上凸就将i点移到通道的下边界,向下凸则是上边界

多次修正至不再变化就好了。

DP

显然，我们只用考虑每次离开一个矩形时的y坐标。如果我们离开一个矩形时，走的是相邻两矩形相交的那条线段，我们称其为一次“关键通过”，通过点称为“关键点”。那么一次通过，要么走一个前面的关键点和后面一个关键点，离开点连线交点，要么“关键通过”该矩形。

如果起点的x坐标比较大，就交换一下起点终点。

动态规划，记f[i][0]表示从可通过线段的最低点离开矩形i，记f[i][1]表示从最高点通过矩形i。每次枚举上一个“关键通过”的矩形（或者从前往后转移，枚举下一个“关键通过”的矩形）进行转移，最后考虑第一个和最后一个被“关键通过”的矩形，然后从起点走到第一个关键点，从最后一个关键点走到终点。

那么如何判断能否直接从一个关键点走到另一个呢？在起点固定的情况下，我们的直线行走路径的斜率会被限制在一个区间里，那么直接在枚举下一个点的过程中（或固定终点，枚举上一个点），不断更新合法斜率区间，来判断当前这个转移是否合法。

有以下坑点：

1. 起点和第一个关键点，终点和最后一个关键点，起点和终点的横坐标相同，要特判。并且还要注意这个相同还分起点/终点夹在通过线段中间的情况和起点终点在通过线段一侧的情况。

2. 没有关键点，起点直接走到终点的情况。

最短路（复杂度错误算法但是能过）

类似 房间最短路问题 ，在每一个点之间利用一次函数判断后建边。

显然顶点都是有用点（不过我们只用考虑一个面，也就是最多$4000$个点），写一个精度判定函数即可。

迷失游乐园

先从树开始考虑，显然树形换根，或者容斥处理，

利用拓扑图通用期望逆推公式（下转移） $f[u] = \sum \frac{1}{out[u]} × (f[v] + w(u,v))$

和通用（除下转移），$g[v] = w(u,v) + (g[u] + f[u] × out[u] - f[v] - w(u, v)) / (out[u] - [u==root])$

再来考虑基环树的情况，我们将基环树看做若干普通树根节点相连成环的结果。

那么不难发现其实$f[u]$是不受影响的，可以对每棵小树跑dfs处理出来。关键在于$g[u]$：对于不在环上的结点，$g[u]$其实也不受影响，但是环上的结点的$g[u]$需要特别处理，因为有两条路。

考虑到环上的结点不超过$20$个，可以对每个节点都这样做一遍：从它（记为$st$，起始点）开始沿着环顺时针走一圈，再逆时针走一圈。走的过程中既可以往环上走，也可以往树上走，但是不能走已经走过的结点。

处理完环上结点的$g$之后跑树上的$g$，这时要注意环上的结点向上有两条路，而非环上的结点向上只有一条路，所以转移方程也要微调，其实更一开始一样，打个标记提出来处理即可。

然后统计答案就行了。

邮递员

插头$DP$有最小表示法和括号表示法两种表示回路集合的方法。

路径模型由多条回路，一条回路，一条路径，染色模型和图论模型组成。

多条回路是最简单的插头模板，我们不需要括号表示，相遇的话可以直接闭合，而单条回路不一样，需要用最小（括号）表示法，为了更快实现，可以用四进制，一般有效状态很少，不是明显的超出就不要在意。

染色模型要采用最小表示法，至于图论模型则是插头$DP$的扩展运用。

其实插头$DP$就是轮廓线$DP$在连通性上的扩展，插头的设计要具有无后效性，与其他类型的状态一样插头也可以被看作一个状态机。

本题是括号表示法求一条哈密顿回路个数的板题，只是要开高精度，然后输出的时候 ans 要乘二而已。

旅行路线

给你一个 $n∗m$ 的 01 表格。你要找到一条哈密顿路径（经过所有点恰好一次），满足：

1) 起点在表格边缘；

2）路径上的值连接起来恰好等于一个给定的 01 序列。求方案数。

插头$DP$，将不连缀定义为空插头（记作 0），连缀且递增定义为递增插头（记作 1），连缀且递减定义为递减插头（记作 2）。

继续观察，显然地：1 恰有一个 1插头，n*m 恰有一个 2插头，其他数字恰有一个 1插头 和一个 2插头。

现在插头的转移已经可以确定了。

要保证不填重复的数字，我们还得知道一条轮廓线上方已经填过哪些数字，所以对于每个轮廓线开一个bitset，理解一下为什么不会出现轮廓线相同但数字集合不同的情况。

线上有连通块 3-4 和 11。轮廓线上方的数字要么与 3-4 以 1插头 联通，要么 与 11 以 2插头 联通。因此可以唯一确定上方的数字集合为 $[1,2]\cup[12,15]$。

设 $ct_0$ 为左插头，$ct_1$ 为上插头，$nm_0$ 为左边格子填的数字，$nm_1$ 为上边格子填的数字，分类讨论即可。

上面这些算特殊规则，本题还有通用规则：

已经填过的数字不能再填。
下边没有格子时不能插下插头，右边没有格子时不能插右插头。
必须满足一开始给出的 01 序列的限制。
如果要填 1，还需检查是否在边缘。

轮廓线上最多 $n+1=4$ 个插头，每个插头需要 $2$ 位存插头类型 + $8$ 位存填的数字，共计 $40$ 位（实际上一条轮廓线上最多 $3$ 个数字， $32$ 位就够了

使用 ungsigned long long 记录状态。不用 long long 的理由是可能左移时炸出负数。

喵星人的入侵

因为每个点的权值是由它周围的八个点的状态决定的，所以我们还要记录轮廓线的路径，也就是轮廓线上是放障碍还是炮台还是路径

我们记轮廓线上如果是障碍则为状态 0，如果是路径则为状态 1，如果是炮台则为 3

当然，我们发现插头状态仅记录左括号（记为1），右括号（记为2），和无插头（记为0）是不够的，因为本题中可能有没有括号和它匹配的插头，我们称其为独立插头（记为3）

我们又发现炮台的数量还有个限制，于是还要加一个状态记录炮台的数量

接下来，我们来讲讲点权的事情

如果经过这个点，由于我们只知道轮廓线上的周围四个点的情况，所以只能加上这四个点中炮台的个数

如果这个点放障碍，不加，直接传下去就行

如果这个点放炮台，我们就要加上轮廓线上路径的个数，那为啥这样直接加是对的呢？

我们如果不经过一个点，我们可以直接把它设置成障碍，这样，一个炮台的贡献就是轮廓线上的周围四个点中路径的个数。