2025 年福建预赛

思路

双计数可先固定唯一的红色拐角。分离乘积用 $uv\le (u^2+v^2)/2$；三次式 $(N-t)t^2$ 可看成 $(N-t)(t/2)(t/2)$，以三元均值不等式求上界。

想法从哪来：有序直角组的三个位置作用不同，先固定作为拐角的红格，另外两个白格选择便相互独立，只由该行和该列白格数决定。这样三格计数变成对红格的行列数量乘积求和，既不会把同一个组重复归给不同拐角，也自然保留有序性。 每一项的行列数量耦合难以直接优化，用两数乘积不超过平方和的一半将它们分离。按行求和时，行白格数的平方重复次数就是该行红格数，得到一个单变量三次式；列同理。这个式子的最优值给出理想行列白格比例，最后再设计周期染色，让所有行列都同时达到该比例，并使每个红格处行列白格数相等。

固定作为拐角的红格 $C_2$，可选的 $C_1,C_3$ 数量分别只由该行、该列的白格数决定， 从而把总数写成对红格的加权和。用 $uv\le (u^2+v^2)/2$ 将行列变量分离， 再逐行、逐列优化三次式；最后构造每行每列白格数都达到等号条件的染色。