网站建设投标ppt,网站建设必会的软件,创建网站的六个步骤,网站建设与管理是什么题意
link.
给定一个 nmn\times mnm 的棋盘#xff0c;每次操作可以选择两个相邻的格子#xff0c;让这两个各自上的数都 1。问最少多少次操作使得所有格子的数相等。如果永远不行则输出-1。
题解
因为相邻两个格子进行操作#xff0c;而且是方格#xff0c;所以很容易…题意
link.
给定一个 n×mn\times mn×m 的棋盘每次操作可以选择两个相邻的格子让这两个各自上的数都 1。问最少多少次操作使得所有格子的数相等。如果永远不行则输出-1。
题解
因为相邻两个格子进行操作而且是方格所以很容易想到黑白染色好久没做题了这个都想不到了/kk。
黑白染色后发现如果黑色格子数量等于白色格子数量那我们可以转换成二分图网络流模型这部分应该是个很常见的 trick二分一下操作次数判断是否满流然后无解的判断在于一开始黑白两种格子的权值和是否相等。
但是但是如果黑色格子数量与白色不相等呢这时候其实可以直接确定最后的每个格子的值。
假设白色格子有 www 个权值和为 WWW黑色格子有 bbb 个权值和为 BBB。再假设最后每个格子的权值为 xxx那么有
w×x−Wb×x−Bw\times x-Wb\times x-Bw×x−Wb×x−B
因为次数是相等的。转换一下得到
xB−Wb−wx\frac{B-W}{b-w}xb−wB−W
然后因为 b≠wb\neq wbw所以这个 xxx 可以直接解出来。
那么我们直接用二分图那个来判断一下是否有解就行了。
