Codeforces Round #639 (Div. 1)
用桶判定即可。
发现在同一行或同一列中最多出现一段连续的黑格，不然 \(N\) 极磁铁就会被吸到黑格之间的白格。若某一行不存在黑格，则所有列不能都有黑格，可以在该行中没有黑格的一列放一个 \(S\) 极磁铁，因为当前行列都没有黑格，所以其不会产生影响，列的情况同理。
判完无解后，答案为黑色连通块个数。
不等关系具有传递性，将其用有向边表示，即若 \(x_i<x_j\) 则连边 \(i \to j\)，有环则无解。
发现当 \(i<j\) 时，若 \(x_i\) 和 \(x_j\) 存在不等关系 \(x_i<x_j\) 或 \(x_j>x_i\) 时，\(j\) 必须为 \(E\)，其在图上对应的就是能否到达。那么可以建出正图反图后拓扑排序，求出每个点能到达的最小的编号和能到达该点的最小的编号，通过这个就能判断每个点是 \(A\) 还是 \(E\) 了。
设 \(f_i(x)=x(a_i-x^2),x\in[0,a_i]\)，得：
因此 \(\Delta f_i(x)\) 是单调不降的。
考虑一开始所有的 \(b_i\) 都为 \(0\)，每次可以将某个 \(b_i\) 加 \(1\)，要加 \(k\) 次。最优情况下每次操作后的变化量是单调不降的，因此可以二分最后一次操作的变化量，设二分的变化量为 \(v\)，得：
可以通过二分或者求根公式得出每个 \(b_i\) 要至少加多少，根据二分的结果调整即可构造方案。
本题为求多元函数在限制下的极值，因此也可以用拉格朗日乘数法做。其为在满足 \(\sum\limits_{i=1}^n b_i=k\) 的限制下，最大化 \(\sum\limits_{i=1}^n b_i(a_i-b_i^2)\)。
设 \(f(b_i)=\sum\limits_{i=1}^n b_i(a_i-b_i^2),\varphi(b_i)=\sum\limits_{i=1}^n b_i-k\)，拉格朗日函数为 \(L(b_i)=f(b_i)+\lambda\varphi(b_i)\)。
得拉格朗日函数 \(L(b_i)\) 梯度为 \(0\) 时，\(f(b_i)\) 最优，得：
可以二分 \(\lambda\)，因为还有 \(b_i \leqslant a_i\) 的限制，得到的 \(b_i\) 可能不合法，因此在外面还要再套一层二分。
在?了
在?了
原文：https://www.cnblogs.com/lhm-/p/13828788.html