如果贪心是一只兔子不断往目标跳去，那模拟退火就是一只喝醉的兔子不停乱跳

SA 算法的基本思想是用马尔可夫链的形式进行随机搜索，它不仅接受改善目标函数的变化，而且还能保留一些不理想的变化。
对于改善目标函数的变化直接转移
对于不理想的变化，发生转移的概率为$P=e^{\frac{\Delta E}{kT_{0}}}$
其中$T_{0}$为当前温度，$k$为玻尔兹曼常数，为了方便计算可设$k=1$
需要设定的参数为初温$S$，末温$T$，和降温系数$dT$

适当的温度至关重要

• 若$T_{0}$过大$\left ( T\rightarrow \infty \right )$，几乎所有转移都会被接受

• 若$T_{0}$过小$\left ( T\rightarrow0 \right )$，几乎所有不理想的转移均无法被接受，算法将会变为贪心，容易陷入局部最优解

此外，优秀的状态产生函数和状态评估函数将会提高SA的效率
最好是能面向数据编程

放一张Wiki的动图

有了SA这题就好写了
状态生产函数采用随机交换两个元素
状态评估函数采用动态规划
设$dp\left [ i\right ]\left [ j \right ]$为前i 个分成j 组的最小$j\sigma ^{2}$

调参调了很久

听说正解是高斯消元，但我还是选择搜索

考虑从右往左搜
退出条件是搜完所有位置
剪枝好像只能可行性剪枝
复杂度还是很高

枚举的时候还能再优化一下

• 三个数均未确定
  • 枚举其中两个计算第三个
• 两个数未确定
  • 枚举一个计算一个
• 一个数未确定
  • 直接计算
• 均确定
  • 可行性剪枝

比较容易忽略的是回溯过程
不合法也要先回溯再退出

最慢点1000+ms，吸口氧就能过了

正难则反
合法答案 = 所有三角形 - 水平（竖直）共线 - 斜共线

所有三角形$C_{\left (n+1 \right )\left (m+1 \right )}^{3}$
水平（竖直）共线$C_{n+1}^{3}\left ( m+1 \right )+C_{m+1}^{3}(n+1)$

斜共线不好直接求，考虑枚举向量$\left ( i,j \right )\ i\leq n+1,j\leq m+1$
为了保证不重不漏，第一和第二个点分别为$\left ( i,j \right )$起点与终点，第三个点在$\left ( i,j \right )$中间
对于一组$\left ( i,j \right )$，共有$\left ( n-i+1 \right )\left ( m-j+1 \right )$种可能，其中第三个点还有$gcd\left ( i,j \right )-1$种可能
考虑到左右对称，答案还需要$*2$

x，y，z 分别记录行，列和九宫格内已填数的集合
每次选可填数最少的格子进行扩展

没有限制就是一个完全背包
考虑仅有一个c 的硬币限制为d 枚
正难则反，易得$dp\left [ val \right ]$为全部方案数
而不合法的方案使用c 的个数肯定为d+1，d+2..
假设c 强制选d+1 个，则现在所有的方案均为不合法的，也就是$dp\left [ val-\left ( d+1 \right )*c \right ]$
对于多个硬币，只需容斥即可

用可持久化线段树实现

消元形成倒三角

证明省略

Hungary 算法

无法有效（不会）直接计算，考虑二分答案

对于一个二分的k
显然尽可能地向上移动军队最优
然而问题并没有这么简单
因为根节点不能覆盖
所以当一棵子树有多支军队，而其他子树没有时
简单地贪心就会出错

需要考虑军队在子树之间的转移
记录所有能在子树间转移的军队的剩余路程和所有需要封锁的子树
在寻找未被封锁的子树时，需要转移的军队并不能参与封锁
从大到小贪心地考虑所有要封锁的子树

• 优先选择已在该子树且剩余距离最小的军队
• 否则选择当前能够使用的军队

细节很多（调了很久）