可能有很多乱搞方法，介绍其中一种，见谅。
先构造一个大致正确的矩阵，令 $a_{i,j}=(j-1)\times 101+i$，空出 $a_{2\sim100,100}$。这样已经填上去的位置都是合法的。
将 $a_{i,100}$ 填上 $(i-1)\times 101$，令估价函数为相邻不合法位置的数量，则枚举 $i=2\to 100$，每次将 $a_{i,100}$ 与某个位置交换，取最优的那个位置。等待十分钟就能得到答案。
QOJ.ac
QOJ
Discussion #3021 for Problem #22895. Coprime Matrix
Type: Editorial
Status: Open
Posted by: Euphoria_
Posted at:
Last updated:
New Editorial for Problem #22895
Comments
No comments yet.